Aplicaţii ale ridicării la putere în informatică
Yüklə 445 b.
|
 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.
 Probleme de numărare
 1. Pătrate(preluata de pe site-ul infoarena)
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.
 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 . 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. Yüklə 445 b. Dostları ilə paylaş:
|
{ 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 matrici
O 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)
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-2
Sa 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.
Aplicaţii diverse
Ridicarea 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ă?
Rezolvare:
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ă
în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.
î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.
Probleme propuse
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.
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 matrici
O 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)
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-2
Sa 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.
Aplicaţii diverse
Ridicarea 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ă?
Rezolvare:
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ă
în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.
î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.
Probleme propuse
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.
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 matrici
O 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)
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-2
Sa 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.
Aplicaţii diverse
Ridicarea 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ă?
Rezolvare:
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ă
în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.
î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.
Probleme propuse
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.
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 matrici
O 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)
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-2
Sa 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.
Aplicaţii diverse
Ridicarea 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ă?
Rezolvare:
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ă
în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.
î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.
Probleme propuse
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.
} 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 matrici
O 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)
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-2
Sa 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.
Aplicaţii diverse
Ridicarea 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ă?
Rezolvare:
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ă
în vector sau x se află în vector dar este depistat doar la ultimul apel al funcţiei.
î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.
Probleme propuse
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.
Aceasta metodă de ridicare la putere poate fi folosita ca optimizare în multe probleme ce implică puteri, reducând timpul de execuţie.
O 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-2
Sa 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.
Ridicarea 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ă?
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ă
î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.
1.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 divizorilor
Pentru un număr n dat să se determine numărul divizorilor acestuia şi suma lor folosint ridicarea la putere în timp logaritmic.