Probleme cu solutie surprinzatoare

Probleme cu solutie surprinzatoare

In rezolvarea fiecareia din problemele urmatoare este foarte usor de cazut in capcana solutionarii de genul 'la prima mina' sau brute-force-approach in limba engleza (abordare in forta bruta). Este cea mai des intilnita capcana pentru programatorii lipsiti de subtilitate, experienta sau cultura de specialitate. Este si aceasta o rezolvare, desigur, dar lipsa ei de eficienta si de eleganta este evidenta. Tocmai de aceea, consideram foarte utila prezentarea citorva exemple elocvente, impreuna cu solutiile lor. Unele dintre probleme au fost selectionate dintre problemele date la concursurile si olimpiadele scolare de programare .

Prin acest capitol nu urmarim doar insusirea unor cunostinte practice de programare ci, mai ales, aprofundarea capacitatii de analiza si proiectare a solutiilor. Aceasta presupune un salt calitativ in invatarea programarii si de aceea acest capitol devine cu adevarat util numai pentru acei programatori inteligenti si dornici de auto-perfectionare. Sau pentru cei care se pregatesc pentru participarea la concursurile si olimpiadele de informatica.

Solutiile oferite de noi sint, pentru fiecare problema, eficiente si 'elegante'. Acest fapt se datoreaza accentului pus pe aprofundarea si imbunatatirea primei analize a problemei.

Putem atunci spune, ca motto-ul acestui capitol este: 'Nu te multumi niciodata cu solutia la prima mina !'.

Sa se afiseze numarul cuburilor perfecte mai mici decit n.

Analiza problemei - elaborarea algoritmului:

Capcana problemei consta in tentativa de a parcurge printr-un ciclu for toate numerele de la 1 la n si de a contoriza cele care sint cuburi perfecte.

La o a noua privire, mai atenta, observam ca partea intreaga a radicalului de ordinul 3 din n ne ofera acel numar care ridicat la a 3-a este cel mai apropiat cub de n. Deci, partea intreagp a radicalului de ordinul 3 din n este egala chiar cu numarul cuburilor mai mici decit n.

(Este suficient sa calculam radical de ordinul 3 din n pentru a afla cite cuburi mai mici decit n exista.)

program cuburi_perfecte;

var n,i,nr_cub:word;

BEGIN

write('n=');readln(n);

nr_cub:=trunc(exp(1/3*ln(n)));

writeln('numarul cuburilor perfecte < ',n,' este = ', nr_cub);

readln;

END.

Se citesc m, n numaratorul si numitorul unei fractii. Sa se simplifice aceasta fractie.

Analiza problemei - elaborarea algoritmului:

Capcana consta in a efectua simplificarea pas cu pas, cautind pe rind fiecare divizor comun al numaratorului si numitorului. In plus, ar trebui sa avem grija ca, pentru unii divizori comuni, este nevoie de o simplificare repetata. Deci, doua cicluri imbricate !

-pentru a obtine o fractie ireductibila este suficient sa o simplificam o singura data cu cmmdc al numitorului si al numaratorului,eliminindu-se astfel simplificarile succesive

-vom folosi subalgoritmul (Euclid) care calculeaza cmmdc al numaratorului si al numitorului.

program simplificare;

var m,n:word;

function cmmdc(m,n:word):word;

begin

while m<>n do

if m>n then m:=m-n

else n:=n-m;

cmmdc:=m;

end;

BEGIN

write('numaratorul fractiei m= ');readln(m);

write('numitorul fractiei n= ');readln(n);

if n=0 then writeln('Fractie inexistenta.')

else

if m=0 then writeln(m,'/',n,'=',0)

else

writeln(m,'/',n,' = ',m div cmmdc(m,n),'/',n div cmmdc(m,n));

readln;

END.

Se citesc a, b, c intregi. Sa se determine toate perechile intregi (x,y) solutii ale ecuatiei ax+by=c.

Analiza problemei – elaborarea algoritmului;

Problema a fost data la olimpiada scolara de informatica. Ea pare la prima vedere imposibila. Exista ecuatii, de exemplu: 3x+2y=1 care are o infinitate de solutii …, (1,-1), (3,-4), (5,-7), (7,-10),… Cum ar putea fi afisata atunci pe ecran o multime infinita de perechi ? Solutia este de a afisa aceasta multime printr-o descriere sintetica a ei (afisind formula care poate genera toate perechile ce o compun).

1. daca c=1 atunci exista (x₀,y₀) a.i. ax₀+by₀=1 doar daca [a,b]=1 ; restul solutiilor (x,y) au forma x=x₀+kb , y=y₀-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x₀,y₀) doar daca [a,b]|c; restul solutiilor se construiesc la fel;

prin [a,b] se intelege cmmdc(a,b)

Programul trebuie doar sa determine x₀ si y₀.

Program ax_plus_by_egal_c;

Var a,b,c,x0,y0,y:integer;

BEGIN

Write('a,b,c=');Readln(a,b,c);

x0:=0;

For y:=0 to a do

If abs(c-b*y) mod a=0 then begin

y0:=y;x0:=(c-b*y) div a;break;

end;

If x0<>0 then Writeln('Sol. (x,y) ale ec. ',a,'x+',b,'y=',c,' sint (',x0,'+k*',b,',',y0,'-k*',a,')')

else Writeln('Nu exista solutii pentru ecuatia ',a,'x+',b,'y=',c);

END.

/*Varianta C de solutionare:

1. daca c=1 atunci exista (x0,y0) a.i. ax0+by0=1 doar daca cmmdc[a,b]=1 ;

restul solutiilor (x,y) au forma x=x0+kb y=y0-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x0,y0) doar daca cmmdc[a,b] | c;

restul solutiilor se construiesc la fel.

3. exista posibilitatea ca, pornind de la perechi (x0,y0) distincte, sa se

obtina solutii noi diferite (multimi infinite de perechi distincte).

4. toate solutiile (multimi infinite de perechi) pleaca de la o pereche

(x0,y0) aflata in dreptunghiul (-b,-a)x(b,a).

Un bun exemplu este ecuatia 18x+42y=6.*/

#include <stdio.h>

#include <math.h>

int a,b,c,x0=0,y0=0,y,k;

void main(void)

if(!x0 && !y0 && c)printf('Nu exista solutii pentru ecuatia %ix+%iy=%i',a,b,c);

Se citeste n o valoare intreaga pozitiva. Sa se determine toate descompunerile in diferenta de patrate ale lui n.

Analiza problemei – elaborarea algoritmului:

Aratam in continuare cum se poate evita solutia 'banala'-capcana ce-ar consta in doua cicluri for imbricate. Solutia urmatoare efectueaza doar radical din n pasi, fata de n² pasi ai solutiei 'la prima mina'.

-pentru a determina toate descompunerile in diferenta de patrate ale lui n pornim de la formula a²-b²=(a+b)(a-b)=n

-observam ca produsul termenilor a+b si a-b este produsul a doi dintre divizorii lui n,unul din termeni este divizor (d) a lui n celalalt este tot divizor a lui n si il aflam impartindu-l pe n la d (n div x)

-notam cu x primul divizor a lui n (x=d) si cu y=n div x si obtinem relatiile

a+b=x deci un sistem de doua ecuatii cu doua necunoscute ,pe care il rezolvam

a-b=yprin metoda reducerii ,si avem 2a=x+y => a=(x+y )/2 , b=(y-x)/2,

-pentru ca (x+y)/2 sa fie o solutie a ecuatiei a²-b²=(a+b)(a-b)=n trebuie ca x+y sa fie un numar par si y-x sa fie un numar par

-daca aceasta conditie este indeplinita afisam solutia care indeplineste conditia ceruta.

Program descompunere_patrate;

var n,d,a,b,x,y:integer;

BEGIN

write('n=');readln(n);

for d:=1 to trunc(sqrt(n)) do

if n mod d =0 then

begin

x:=d;

y:=n div x;

if (x+y) mod 2 =0 then

begin

a:=(x+y) div 2;

b:=(y-x) div 2;

writeln(n,'=',a*a,'-',b*b);

end;

end;

readln;

END.

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.

Se citeste n. Sa se determine o alegere a semnelor + si - astfel incit sa avem relatia 1 2 n=0.

Analiza problemei – elaborarea algoritmului:

Problema a fost data la olimpiada scolara de informatica. Daca se incearca o abordare 'in forta' si 'la prima mina' vor trebui verificate 2ⁿ posibilitati de asezare a semnelor + si -. Adica se obtine un algoritm exponential, total ineficient. Solutia 'eleganta' ce rezulta printr-o analiza mai aprofundata:

-mai intai se va imparti suma in doua parti: cea cu plus si cea cu minus.

Privindu-se atent se observa ca se pot deosebi trei cazuri:

1. cind avem intre cele n numere un numar impar de numere impare (de ex.n=3,5,6) caz in care numerele impare nu pot fi repartizate in cele doua parti (plus si minus) decit astfel: un nr.par de numere impare intr-o parte si un nr.impar de nr impare in cealalta; implica ca cele doua parti au paritati diferite, deci suma lor nu poate fi 0 !

Acest caz apare cind n=4k+1, 4k+2.

2. cind n=4k atunci numerele de la 1 la n pot fi grupate cite patru astfel:

1-2-3+4, , (4i+1)-(4i+2)-(4i+3)+(4i+4), si vor avea suma 0 pe fiecare grupa de patru !

3. altfel, n=4k+3, putem grupa numerele asemanator ca la cazul dinainte cu exceptia primei grupe: -1-2+3, 4-5-6+7, , (4i)-(4i+1)-(4i+2)+(4i+3),reazultind din nou suma 0 pe fiecare grupa !

Program Plus_Minus;

Var

n,i,c:byte;

BEGIN

Writeln('Se citeste n. Sa se determine o alegere a semnelor + si - ');

Writeln('astfel incit sa avem relatia 1 2 n=0.');

Write('n:');Readln(n);

c:=n mod 4;

case c of

1,2: Writeln('Nu exista solutie.');

0: For i:=1 to n div 4 do

write('+',4*(i-1)+1,'-',4*(i-1)+2,'-',4*(i-1)+3,'+',4*(i-1)+4);

3:begin

Write('-1-2+3');

For i:=1 to n div 4 do

write('+',4*i,'-',4*i+1,'-',4*i+2,'+',4*i+3);

end;

end;

Readln;

END.