Aplicaţii ale ridicării la putere în informatică

Fără ridicarea la putere o parte din informatică ar fi complet inaccesibilă. Ea are o varietate de aplicaţii şi este esenţiala în rezolvarea unor probleme în timp optim.

Cu ajutorul acestei prezentări vom arăta la ce este utilă ridicarea la putere în informatică.

Pentru a nu mări lungimea prezentării am decis că unele surse de la probleme se vor găsi la o adresa web specificată.

Probleme de numărareProblemele de numărare sau de

combinatorică sunt caracterizate de natura lor atipică, ce impune din partea rezolvitorului ingeniozitate, flexibilitate şi perseverenţă în căutarea soluţiei.

In continuare vom prezenta 2 probleme de combinatorică în a căror rezolvare, ridicarea la putere este predominantă.

1. Pătrate(preluata de pe site-ul infoarena) Fie A o matrice cu N linii şi N coloane. Se cere să se

găsească numărul posibilităţilor de a completa matricea A cu elemente din mulţimea {-1, 1, -5, 5} astfel încât produsul numerelor de pe fiecare linie sau coloană este -5 sau 5. 

Rezolvare: Din cerinţă ne dăm seama că pe fiecare linie sau coloană trebuie să avem un 5 sau -5. Astfel pe prima linie avem N posibilităţi de a plasa 5 sau -5. Pe linia 2 avem N-1 posibilităţi, pe linia 3 avem N-2, etc. In total avem 1*2*3*….*N=N!(se citeste N factorial) configuraţii. Pentru cele N celule din fiecare configuraţie avem posibilităţi de a plasa 5 sau -5. Acum ne mai rămâne să plasăm pe cele N*N-N celule 1 sau -1. Pentru fiecare configuraţie avem posibilităţi deci în total avem posibilităţi de a completa matricea A cu elemente din mulţimea {-1,1,-5,5} astfel încât produsul de pe fiecare linie sau coloană să fie 5 sau -5.

2N

*2N N N

* *!*2 *2 !*2N N N N N NN N

2.Funcţii(din lista lui Francu)Pentru N şi S date, câte funcţii surjective definite pe

mulţimea { 1,2,3,4..N } cu valori în mulţimea numerelor { 0,-1,1 } există astfel încât |f(1)| + |f(2)| + .. |f(N)| =S (toate sunt în modul) .

Rezolvare:Din faptul că funcţiile sunt surjective rezultă că trebuie să

avem cel puţin un 1,un 0 şi un -1.Deoarece valoarea lui |f(i)|,1 i N, poate fi doar 0 sau 1 ne dăm 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 posibilităţi( 1 sau -1) deci în total sunt . Observăm că am numărat şi variantele 1,1,1,…1 şi -1,-1,-1…-1 care nu sunt corecte deoarece funcţiile sunt surjective. Deci numărul corect este posibilităţi de a alege S valori de 1 sau -1 astfel încât funcţiile să fie corecte. Mai rămân N-S valori de 0, care pot fi alese în C(N,N-S) ( combinări de N luate câte N-S). In final numărul funcţiilor surjective cu proprietatea din enunţ este .

2S

2 2S

(2 2)* ( , )S C N N S

Ridicare la putere în timp logaritmicProprietăţile puterilor pot fi folosite pentru a

ridica un număr la o putere în timp logaritmic. In limbajul C++ există o instrucţiune: 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 următor:

Dacă b este par calculăm .Dacă b este impar calculăm .Deoarece puterea se tot înjumătăţeste

complexitatea este logaritmică.In continuare prezentăm o funcţie recursivă ce

calculează în timp logaritmic.

*n m m na a a ba

/2 /2*b b ba a a1 *b ba a a

ba

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;}else

return pow(a,b-1) * a;}Aceasta metodă de ridicare la putere poate fi

folosita ca optimizare în multe probleme ce implică puteri, reducând timpul de execuţie.

Ridicare la putere de matriciO serie de probleme din informatică presupun

calcularea unor recurenţe. De exemplu: care este al n-lea termen Fibonacci. Metoda naivă este calcularea pas cu pas al fiecarui termen până ajungem la al n-lea termen , această soluţie având 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 concurenţii. Ele nu sunt foarte grele dar trebuie un pic de experienţă, ingeniozitate şi cunoştinte matematice.

In continuare prezentăm o problemă importantă, însă care necesită cunoştine matematice mai avansate.

1. Al n-lea termen Fibonacci( preluat de pe site-ul infoarena) Fie şirul lui Fibonacci dat prin recurenţa: 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 cunoaştem Fn-1 şi Fn-2 şi dorim să aflăm Fn.Considerăm matricea (Fn-2 Fn-1). Acum trebuie sa căutam o matrice

Z astfel încât 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)

Notăm (Fi-1 Fi) cu Mi. Astfel observăm că Mi= Mi-1 Z , dar Mi-1=Mi-2 Z. Deci Mi = Mi-2 . Inductiv deducem că Mi=M1

Calculăm mai întâi folosind ridicarea la putere în timp logaritmic (descrisă mai sus) apoi înmulţim matricea rezultată cu M1.

Complexitatea finală este O( logK ). Astfel, folosind ridicarea la putere am calculat Fk în timp logaritmic, soluţie ce obţine punctajul maxim.

0 1

1 1

0 1

1 1

2Z 1iZ

1iZ

Aplicaţii diverseRidicarea la putere are o mulţime de utilizări pe

lânga cele specificate mai sus. In continuare prezentăm câteva chestiuni ce pot fi desluşite prin ridicare la putere:

1. Câte numere în baza 2 de n cifre există?Rezolvare: Observăm că pentru fiecare cifră

avem 2 opţiuni 1 sau 0. Deci numărul total va fi .

2. Un călător vrea sa viziteze n insule. Acestea sunt legate între ele prin câte 5 poduri şi sunt dipuse liniar. Ultima insulă este legată de precedenta numai prin 3 poduri. Câte drumuri de la insula 1 la insula n există?

2n

Rezolvare:Problema este oarecum asemănătoare cu cea de mai

sus.Observăm ca pe insula 2 putem ajunge în 5

moduri(traversând 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 greşită pentru i=n deoarece insula n-1 este legată de insula n doar prin 3 poduri. Deci numărul de drumuri de la insula 1 la insula n este .

3. Care este complexitatea căutarii binare în cel mai defavorabil caz ?

Rezolvare:Să considerăm că metoda este recursivă. Cel mai

defavorabil caz înseamna că elementul căutat x nu se află

15i

25 *3n

în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.

La fiecare apel recursiv spaţiul de căutare se injumătaţeste. După primul apel din cele n elemente iniţiale, rămân n/2 elemente. După al doilea apel, rămân n/ , etc. Inductiv putem afirma că după k apeluri recursive spaţiul de căutare va conţine n/ elemente. In final, numărul de elemente din spaţiul de căutare trebuie să fie cel mult 1 deci:

n/ 1 deci n . In final se obţine k=log n.

2

22

2k

2k 2k

Probleme propuse1.Tritzi(preluată de pe site-ul infoarena, text modificat)Un trit este o unitate logică care poate lua 3 valori: 0, 1 şi 2.

Sirurile de tritzi au o proprietate specială : doi tritzi având valorile 0 şi respectiv 1 nu pot fi puşi unul după altul. Astfel, există şiruri de tritzi valide şi invalide (care conţin cel puţin o pereche de tritzi alăturaţi egali cu 0 şi 1). De exemplu, şirul 02212212000211 este un şir valid, dar şirurile 0122212 sau 2221022 nu sunt valide.

Determinaţi numărul de şiruri de tritzi valide, de lungime N. Indiciu: ridicare la putere de matrici

2.Suma şi numarul divizorilorPentru un număr n dat să se determine numărul divizorilor

acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.