Esercizio 9
Scrivi un programma che applicando la regola di Ruffini, sia in grado di individuare le radici intere di un polinomio di grado n ordinato per potenze decrescenti della variabile x.
La regola di Ruffini viene usata nella pratica, per dividere
un polinomio di grado n ordinato per potenze decrescenti della variabile
x.
La sua applicazione è spesso laboriosa per vari motivi ( perché non ci si
ricorda lo schema, perché bisogna procedere per tentativi) .
Il metodo è collegato al problema della divisione di un polinomio di grado
n per un binomio di primo grado.
Supponiamo di voler eseguire la divisione fra un polinomio A(x) di grado
3 ed un binomio di primo grado B(x) :
Si disegna lo schema seguente:
poi si eseguono i seguenti movimenti
Il risultato finale sarà
viene ottenuto un polinomio quoziente di grado n-1
con un resto R=+16.
Particolarmente interessante è la soluzione con resto zero; questo significa che A(x) è divisibile per B(x) e si potrà scrivere:
Poi se Q(x) è un trinomio di secondo grado, si può
tentare di decomporlo con la formula del trinomio, altrimenti si cerca di
decomporlo ancora con la regola di Ruffini.
Ad esempio la divisione
si
svolge nel seguente modo
Il risultato finale sarà
si può quindi scrivere :
in questo modo si può decomporre un polinomio di ordine
n nel prodotto di tanti binomi.
Il problema è sempre quello di individuare il termine noto del binomio.
Se il polinomio è divisibile il termine noto del binomio è sempre un divisore
del termine noto del polinomio. Nel caso precedente i divisori (interi)
di -6 sono: +1,-1,+2,-2,+3,-3,+6,-6; quindi per sapere se un polinomio ha
un binomio divisore bisogna eseguire la regola di Ruffini con tutti questi
tentativi.
L'algoritmo implica la soluzione di un problema molto 'gettonato' in informatica,
cioè, l'individuazione di tutti i divisori (interi) di un numero intero,
qui risolti dal passaggio
(ma
si può fare di meglio) :
for(i=2;i <=Math.abs(n/2);i++)
if(n%i==0)divisori++;
Il nostro obiettivo è automatizzare queste operazioni, d'altra parte se
è possibile eseguirle manualmente sarà certamente possibile farle eseguire
all'elaboratore. Non vogliamo discostarci da questo schema, pertanto chiederemo
in input il grado g del polinomio, allocheremo in
memoria un vettore P di dimensione g+1 P[g+1] verranno
contati ed ottenuti i divisore del termine noto di P(x).
Questi k divisori saranno memorizzati in un vettore T di dimensione opportuna,
dopodichè il programma eseguirà tutti i tentativi possibili (con i divisori
interi) ottenendo i coefficienti del polinomio quoziente Q(x) che verranno
memorizzati nel vettore Q di dimensione g Q[g].
Alla prima occorrenza in cui viene trovata una radice il programma si ferma
restituisce in output il valore della radice e viene stampato il vettore
dei coefficienti del polinomio ridotto Q(x).
Questo breve scritto è stato pensato per elaborare polinomi con coefficienti
interi, ricercando radici intere, ma può essere ulteriormente ampliato
per considerare polinomi a coefficienti razionali e/o per cercare radici
razionali; ma in quest'ultimo caso, i possibili divisori del termine noto
sarebbero infiniti e qundi occorrerebbe scrivere una procedura di ricerca
esaustiva (bruteforce).
import java.util.Scanner;
class ruffini{ public static void main (String args []) {
Scanner in=new Scanner(System.in);
int g,i,n,m,j;
int radice=0,divisori=0;
do{
System.out.print("inserire il grado del polinomio:
");
g=in.nextInt();
}while(g < 3 || g > 9);
int P[]=new int[g+1];
int Q[]=new int[g]; //acquis. dei coefficienti del
polinomio P(x)
for(i=0;i <=g;i++){
System.out.print("ins.coeff.grado "+(g-i)+":");
P[i]=in.nextInt();
}
for(i=0;i < P.length;i++)System.out.print(P[i]+" ");
System.out.println("\n");
n=P[P.length-1]; //conta i divisori del termine
noto
for(i=2;i <=Math.abs(n/2);i++)
if(n%i==0)divisori++;
int T[]=new int[2*(divisori+2)];//istanzia
il vettore T dei divisori
T[0]=1;//il 1°elem. è 1
T[1]=-1;//il 2°elem. è -1
T[T.length-2]=n;//il penultimo elem. è n coefficiente
di grado 0
T[T.length-1]=-n;//l'ultimo elem. è -n
j=2;//memorizza i restanti divisori nel vettore
T
//calcola il vettore dei
coefficienti del quoziente Q(x)
for(i=2;i <=Math.abs(n/2);i++)
if(n%i==0){T[j]=i;T[j+1]=-i;j+=2;};
for(j=0;j < T.length;j++){
n=T[j];
m=Q[0]=P[0];
for(i=1;i < P.length;i++){
m=n*m+P[i];
if(i < P.length-1)Q[i]=m;
}
if(m==0){radice=T[j];break;}
}//fine for j
if(radice!=0){
System.out.println("ha una radice:"+radice+"\n");
System.out.println("i coefficienti del polinomio di grado "+
(g-1)+" sono:");
for(i=0;i < Q.length;i++)System.out.print(Q[i]+" ");
}else System.out.println("nessuna radice trovata");
}//fine main
}//fine classe
Lo stesso codice potrà poi essere facilmente tradotto in altri linguaggi.