Radacinile intregi ale unui polinom de gradul n. Se cere sa se determine pe baza relatiilor lui Viete

Se citeste n si x₁, x₂, . , x_n radacinile intregi ale unui polinom de gradul n. Se cere sa se determine pe baza relatiilor lui Viete coeficientii a_n, a_n-1, . , a₁, a₀.

Analiza problemei – elaborarea algoritmului;

Cea mai des intilnita rezolvare este cea de tip back-tracking, aparent mai usoara, dar in fapt extrem de ineficienta pentru n nu mare ci doar maricel ! Urmatoarea solutie de tip iterativ este o mica 'bijuterie' de program iterativ si de aceea va lasam placerea de a-l intelege singuri.

#include <stdio.h>

void main(void)

a[0]=1;a[n]=0;

for(k=1;k<=n;k++)

for(i=n;i>=0;i--) printf('a[%d]=%d ',i,a[i]);

Se citeste n. Sa se afiseze toate numerele de n cifre, formate numai cu cifrele 1 si 2, divizibile cu 2ⁿ.

Analiza problemei – elaborarea algoritmului:

Problema a fost data la olimpiada scolara de informatica. Abordarea 'in forta' a acestei probleme nu duce la nici un rezultat:

daca s-ar alege varianta de rezolvare 'la prima mina' ar trebui verificate toate cele 2ⁿ posibilitati, adica toate cele 2ⁿ numere de n cifre ce se pot forma numai cu cifrele 1 si 2 (cite 2 posibilitati pentru fiecare pozitie). In acest caz, programul avind o complexitate exponentiala, ar dura un timp exponential, pt. n=50 ar dura cit virsta sistemului nostru solar

pt.n=1 avem unica solutie numarul 2;

pt. n=2 avem deasemenea unica solutie 12; observam ca 2-ul este 'folosit'

pt. n=3 avem deasemenea unica solutie 112; observam ca 12 este din nou 'folosit'

In general, se deduce ca numerele de n cifre, ce trebuie sa se divida cu 2ⁿ , se divid cu 2^n-1; ele se pot scrie sub forma c*10^(n-1)+M=c*2^n-1*5^n-1+M= Multiplu(2^n-1)+M; inseamna ca M (cele n-1 cifre ramase) trebuie sa se divida cu 2^n-1; inseamna ca M este unul din numerele gasite ca solutie la pasul n-1.

Daca exista o singura solutie M pt.cazul n-1 (M se divide cu 2^n-1) acest nr.se poate scrie M=2^(n-1)*par sau 2^(n-1)*impar, rezulta ca M mod 2ⁿ=0 sau M mod 2ⁿ=2^(n-1). Deci,in cazul a n cifre din cele doua posibilitati (1M sau 2M) se va alege astfel unica solutie:

daca M mod 2ⁿ=0 atunci solutia este 2M=2*10^(n-1)+M=Multiplu(2ⁿ)

daca M mod 2ⁿ=2^(n-1) atunci solutia este 1M=10^(n-1)+M=2(^n-1)*5⁽ⁿ¹⁾+M=Multiplu(2ⁿ)!

Solutia propusa este una iterativa si face maximum n pasi !

Program 1_2_si_2_la_n;

Var

nr,zece_la_n:longint;

n,i:byte;

BEGIN

Writeln('Se citeste n. Sa se afiseze toate numerele de n cifre,');

Writeln('formate numai cu cifrele 1 si 2, si divizibile cu 2^n.');

Write('Introduceti n (max.10):');Readln(n);

nr:=2;zece_la_n:=1;

For i:=2 to n do begin

zece_la_n:=10*zece_la_n;

If nr mod (1 shl i)=0 then nr:=2*zece_la_n+nr

else nr:=zece_la_n+nr;

end;

Writeln('Solutia este:',nr);

readln;

END.