Programarea Calculatoarelor, seria CC
Se citesc de la tastatură un întreg N și un vector de N cifre și un întreg M și un vector de M cifre, reprezentând 2 numere mari: A, respectiv B (1 <= N, M <= 100). Să se afișeze numerele A + B, |A - B| și A * B, fiecare pe câte 2 rânduri: pe primul rând numărul de cifre, iar pe al doilea, vectorul de cifre.
Intrare | Ieşire |
5 1 2 3 4 5 3 6 7 8 |
5 1 3 0 2 3 5 1 1 6 6 7 7 8 3 6 9 9 1 0 |
Se citește un întreg N (0 <= N <= 10 000). Să se afișeze al N-lea termen al șirului Fibonacci (sub forma număr de cifre, vector de cifre). (va trebui să folosiți operații cu numere mari - F10 000 are 2090 cifre)
Șirul Fibonacci este:
Intrare | Ieşire |
38 |
8 3 9 0 8 8 1 6 9 |
100 |
21 3 5 4 2 2 4 8 4 8 1 7 9 2 6 1 9 1 5 0 7 5 |
Avem de calculat XP (P întreg). Cel mai simplu se poate calcula prin înmulțiri secvențiale.
Putem face acest lucru mult mai eficient dacă observăm urmatorul lucru:
De ex., vrem să calculăm:
27 = 21 * 22 * 24
210 = 22 * 28
Prin urmare, cunoscând descompunerea binară a lui P putem să determinăm cu care din termeni x1, x2, x4, ... vom înmulți rezultatul final.
Acești termeni pot fi calculați ușor folosind faptul ca X2 * P = XP * XP (Nu va fi nevoie să ridicăm de fiecare dată la putere, ci doar să ne folosim de rezultatul de la pasul anterior, pe care îl ridicăm la pătrat).
Se citesc de la tastatură un întreg N (1 <= N <= 100), un vector de N cifre reprezentând numărul X și un întreg P (0 <= P <= 100). Să se calculeze XP. (Rezultatul nu va avea mai mult de 3000 de cifre)
Intrare | Ieşire |
10 1 2 3 4 5 6 7 8 9 0 0 |
1 1 |
9 1 1 1 1 1 1 1 1 1 11 |
89 3 1 8 6 6 3 5 5 1 0 2 7 1 9 4 3 9 6 9 2 7 0 9 5 7 5 6 1 1 8 3 2 2 4 5 1 2 5 7 6 7 1 7 8 7 4 3 3 2 3 7 5 4 8 5 8 4 9 0 6 8 8 9 5 9 1 9 5 7 5 5 2 7 5 4 9 2 2 9 5 5 9 8 6 0 2 7 1 1 |
Considerăm în continuare șirul Fibonacci:
Putem scrie relația de recurență sub forma:
Evident, putem folosi ideea de ridicare la putere descrisă mai sus și pentru matrice.
Se citește un întreg N ( N <= 1 000). Să se afișeze al N-lea termen al șirului Fibonacci, folosind ridicarea la putere în timp logaritmic a unei matrice de numere mari.
Intrare | Ieşire |
38 |
8 3 9 0 8 8 1 6 9 |