Programarea Calculatoarelor, seria CC

Tema 2

Data publicării: Vineri, 6 noiembrie 2009, ora 20:00

Deadline: Duminică, 22 noiembrie 2009, ora 22:00

Precizări:



Problema 1. [50 puncte] Operații cu numere mari

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.

Observație! Se va implementa câte o funcție pentru fiecare dintre cele trei operații.

Exemplu:

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

Problema 2. [20 puncte] Șirul Fibonacci

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: F0 = 0         F1 = 1         Fn + 2 = Fn + 1 + Fn, pentru n >= 0

Observație! Se va implementa o funcție care calculează FN.

Exemplu:

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

Problema 3. [30 puncte] Ridicare la putere în timp logaritmic

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)

Observație! Se va implementa o funcție care calculează XP.

Exemplu:

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

Problema 4. [BONUS 20 puncte] Calculul unor recurențe folosind exponențiere de matrici

Considerăm în continuare șirul Fibonacci: F0 = 0         F1 = 1         Fn + 2 = Fn + 1 + Fn, pentru n >= 0.

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.

Observație! Se va implementa o funcție care calculează FN.

Exemplu:

Intrare Ieşire
38
8
3 9 0 8 8 1 6 9