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.