Suma de termeni ai unui șir

Descrierea algoritmului în limbaj natural

Subprogramul termen. Dacă n este 1, subprogramul returnează 1, primul termen al șirului. Altfel, se generează termenii șirului în ordine crescătoare și se păstrează ultimii doi termeni calculați, a și b, cu valorile inițiale 1 și 2. Termenul următor se calculează cu formula de recurență, c = 1 + 3·b − 2·a. Cât timp c nu depășește n, cei doi termeni păstrați avansează cu o poziție: a primește valoarea lui b, iar b valoarea lui c, după care se calculează din nou c. La ieșirea din structura repetitivă, b este cel mai mare termen al șirului mai mic sau egal cu n, iar subprogramul îl returnează.

Determinarea termenilor sumei. Se citește n. Cât timp n este diferit de 0, se apelează subprogramul termen pentru valoarea curentă a lui n, termenul returnat se scrie în fișierul def.out, iar n se micșorează cu valoarea acestui termen. La fiecare pas se alege, deci, cel mai mare termen care încape în valoarea rămasă. Structura repetitivă se încheie când n devine 0, adică atunci când termenii scriși în fișier au suma egală cu valoarea citită.

Termenii se scriu în fișier în ordinea în care au fost determinați. Primul termen se scrie separat, iar fiecare termen următor este precedat de un spațiu, astfel încât valorile să fie separate prin câte un spațiu. La sfârșit fișierul se închide.

De ce soluția respectă condițiile din enunț

Termenii șirului au forma f_i = 2ⁱ − i. Formula este adevărată pentru f₁ = 2 − 1 = 1 și pentru f₂ = 4 − 2 = 2, iar dacă este adevărată pentru f_i-2 și f_i-1, din relația de recurență rezultă:

f_i = 1 + 3·(2^i-1 − i + 1) − 2·(2^i-2 − i + 2) = 2ⁱ − i.

Fie f_k termenul ales la un pas, deci f_k ≤ n < f_k+1.

• Termenii se scriu în ordine descrescătoare. Valoarea rămasă, n − f_k, este mai mică decât f_k+1, deci termenul ales la pasul următor este cel mult f_k.
• Un termen nu apare de trei ori. Dacă f_k se alege de două ori, valoarea rămasă este n − 2·f_k < f_k+1 − 2·f_k = k − 1. Pentru orice k ≥ 1, f_k = 2^k − k ≥ k − 1, deci valoarea rămasă este mai mică decât f_k, iar f_k nu mai poate fi ales a treia oară.
• Structura repetitivă se termină. Primul termen al șirului este 1, deci pentru orice valoare rămasă nenulă există un termen care încape în ea, iar n scade la fiecare pas.