Fr ridicarea la putere o parte din informatic ar fi complet inaccesibil. Ea are o varietate de aplicaii i este eseniala n rezolvarea unor probleme n timp optim.Cu ajutorul acestei prezentri vom arta la ce este util ridicarea la putere n informatic.Pentru a nu mri lungimea prezentrii am decis c unele surse de la probleme se vor gsi la o adresa web specificat.

Probleme de numrareProblemele de numrare sau de combinatoric sunt caracterizate de natura lor atipic, ce impune din partea rezolvitorului ingeniozitate, flexibilitate i perseveren n cutarea soluiei.In continuare vom prezenta 2 probleme de combinatoric n a cror rezolvare, ridicarea la putere este predominant.

1. Ptrate(preluata de pe site-ul infoarena)FieAo matrice cuNlinii iNcoloane. Se cere s se gseasc numrul posibilitilor de a completa matriceaAcu elemente din mulimea{-1, 1, -5, 5}astfel nct produsul numerelor de pe fiecare linie sau coloan este-5sau5.Rezolvare: Din cerin ne dm seama c pe fiecare linie sau coloan trebuie s avem un 5 sau -5. Astfel pe prima linie avem N posibiliti de a plasa 5 sau -5. Pe linia 2 avem N-1 posibiliti, pe linia 3 avem N-2, etc. In total avem 1*2*3*.*N=N!(se citeste N factorial) configuraii. Pentru cele N celule din fiecare configuraie avem posibiliti de a plasa 5 sau -5. Acum ne mai rmne s plasm pe cele N*N-N celule 1 sau -1. Pentru fiecare configuraie avem posibiliti deci n total avem posibiliti de a completa matricea A cu elemente din mulimea {-1,1,-5,5} astfel nct produsul de pe fiecare linie sau coloan s fie 5 sau -5.

2.Funcii(din lista lui Francu)Pentru N i S date, cte funcii surjective definite pe mulimea {1,2,3,4..N} cu valori n mulimea numerelor {0,-1,1} exist astfel nct |f(1)| + |f(2)| + .. |f(N)| =S(toate sunt n modul) .Rezolvare:Din faptul c funciile sunt surjective rezult c trebuie s avem cel puin un 1,un 0 i un -1.Deoarece valoarea lui |f(i)|,1 i N, poate fi doar 0 sau 1 ne dm seama c trebuie s avem S de f(i),1 I N, pentru care |f(i)|=1.Pentru fiecare din cei S de f(i) avem 2 posibiliti( 1 sau -1) deci n total sunt . Observm c am numrat i variantele 1,1,1,1 i -1,-1,-1-1 care nu sunt corecte deoarece funciile sunt surjective. Deci numrul corect este posibiliti de a alege S valori de 1 sau -1 astfel nct funciile s fie corecte. Mai rmn N-S valori de 0, care pot fi alese n C(N,N-S) ( combinri de N luate cte N-S). In final numrul funciilor surjective cu proprietatea din enun este .

Ridicare la putere n timp logaritmicProprietile puterilor pot fi folosite pentru a ridica un numr la o putere n timp logaritmic. In limbajul C++ exist o instruciune: pow(int a,int b) care ridic a la puterea b, ns ea este liniar( o(b) ) deoarece efectueaz produsul a*a**a(b termeni). Folosind proprietatea putem calcula n modul urmtor:Dac b este par calculm .Dac b este impar calculm .Deoarece puterea se tot njumteste complexitatea este logaritmic.In continuare prezentm o funcie recursiv ce calculeaz n timp logaritmic.

int pow(int a,int b){int nr;if(b==0) return 1;if(b%2==0){nr=pow(a,b/2);return nr*nr;}elsereturn pow(a,b-1) * a;}Aceasta metod de ridicare la putere poate fi folosita ca optimizare n multe probleme ce implic puteri, reducnd timpul de execuie.

Ridicare la putere de matriciO serie de probleme din informatic presupun calcularea unor recurene. De exemplu: care este al n-lea termen Fibonacci. Metoda naiv este calcularea pas cu pas al fiecarui termen pn ajungem la al n-lea termen , aceast soluie avnd complexitatea liniar. Pentru valori mari ale lui n, rezolvarea nici nu se ncadreaz n timp.Astfel de probleme sunt date la concursuri pentru a partaja concurenii. Ele nu sunt foarte grele dar trebuie un pic de experien, ingeniozitate i cunotinte matematice.In continuare prezentm o problem important, ns care necesit cunotine matematice mai avansate.

1. Al n-lea termen Fibonacci( preluat de pe site-ul infoarena) Fie irul lui Fibonacci dat prin recurena: F0=0 , F1=1, , Fn=Fn-1+Fn-2Sa se calculeze al n-lea termen al irului, 0 n 1000000.Rezolvare: Observam ca la pasul n cunoatem Fn-1 i Fn-2 i dorim s aflm Fn.Considerm matricea (Fn-2 Fn-1). Acum trebuie sa cutam o matrice Z astfel nct Z (Fn-2 Fn-1) s fie egal cu (Fn-1 Fn).O astfel de matrice este deoarece:

(Fn-2 Fn-1) = ( Fn-2*0 + Fn-1*1 Fn-2*1 + Fn-1*1 )=( Fn-1 Fn)

Notm (Fi-1 Fi) cu Mi. Astfel observm c Mi= Mi-1 Z , dar Mi-1=Mi-2 Z. Deci Mi = Mi-2 . Inductiv deducem c Mi=M1 Calculm mai nti folosind ridicarea la putere n timp logaritmic (descris mai sus) apoi nmulim matricea rezultat cu M1.Complexitatea final este O( logK ). Astfel, folosind ridicarea la putere am calculat Fk n timp logaritmic, soluie ce obine punctajul maxim.

Aplicaii diverseRidicarea la putere are o mulime de utilizri pe lnga cele specificate mai sus. In continuare prezentm cteva chestiuni ce pot fi desluite prin ridicare la putere:1. Cte numere n baza 2 de n cifre exist?Rezolvare: Observm c pentru fiecare cifr avem 2 opiuni 1 sau 0. Deci numrul total va fi .2. Un cltor vrea sa viziteze n insule. Acestea sunt legate ntre ele prin cte 5 poduri i sunt dipuse liniar. Ultima insul este legat de precedenta numai prin 3 poduri. Cte drumuri de la insula 1 la insula n exist?

Rezolvare:Problema este oarecum asemntoare cu cea de mai sus.Observm ca pe insula 2 putem ajunge n 5 moduri(traversnd cele 5 poduri), pe insula 3 n 5*5 moduri, pe insula 4 n 5*5*5 moduri , pe insula i in , i 0. Formula de mai sus este greit pentru i=n deoarece insula n-1 este legat de insula n doar prin 3 poduri. Deci numrul de drumuri de la insula 1 la insula n este .

3. Care este complexitatea cutarii binare n cel mai defavorabil caz ?Rezolvare:S considerm c metoda este recursiv. Cel mai defavorabil caz nseamna c elementul cutat x nu se afl

n vector sau x se afl n vector dar este depistat doar la ultimul apel al funciei.La fiecare apel recursiv spaiul de cutare se injumtaeste. Dup primul apel din cele n elemente iniiale, rmn n/2 elemente. Dup al doilea apel, rmn n/ , etc. Inductiv putem afirma c dup k apeluri recursive spaiul de cutare va conine n/ elemente. In final, numrul de elemente din spaiul de cutare trebuie s fie cel mult 1 deci: n/ 1 deci n . In final se obine k=log n.

Probleme propuse1.Tritzi(preluat de pe site-ul infoarena, text modificat)Un trit este o unitate logic care poate lua3valori:0,1i2. Sirurile de tritzi au o proprietate special : doi tritzi avnd valorile0i respectiv1nu pot fi pui unul dup altul. Astfel, exist iruri de tritzi valide i invalide (care conin cel puin o pereche de tritzi alturai egali cu0i1). De exemplu, irul02212212000211este un ir valid, dar irurile0122212sau2221022nu sunt valide.Determinai numrul de iruri de tritzi valide, de lungimeN. Indiciu: ridicare la putere de matrici

2.Suma i numarul divizorilorPentru un numr n dat s se determine numrul divizorilor acestuia i suma lor folosint ridicarea la putere n timp logaritmic.