Secvențele de calcul recurente

secvență periodică. Studiul conceptului de calcul al secvenței recursiv. Acest concept este introdus după cum urmează: dacă știm k numere a1. ak. Aceste numere sunt primele numere ale secvenței numerice. Următoarele elemente ale secvenței sunt calculate după cum urmează:

Există f- funcție de k argumente. tip de formula

Se numește o formulă de recurență. Valoarea lui k se numește adâncime recursivitate.

Cu alte cuvinte, putem spune că secvența de recurente - o serie nesfârșită de numere, fiecare dintre acestea, cu excepția k inițială, exprimată în termeni de cele anterioare.

Exemple sunt secvențe recurente aritmetice (1) și geometric (2) progresie:

Formula recurență pentru progresie aritmetică a spus:

Formula de recurență pentru această progresie geometrică:

Recursie adâncime în ambele cazuri, este egal cu una (această dependență este, de asemenea, numit un pas recursivitate). In general, secvența recursiv descrisă de un set de valori inițiale și o formulă de recurență. Toate acestea pot fi combinate într-o singură formulă ramificare. Pentru progresie aritmetică:

Pentru exponențial:

Următoarea secvență numerică este cunoscută în matematică, numit numerele Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Din moment ce fiecare element al treilea număr este suma celor două anterioare, adică. E. secvență recurentă cu adâncime egală cu 2 (două etape recursivitate). Noi l descriem sub formă de ramificare:

Introducerea noțiunilor de secvențe de recurență permite o privire proaspata, la unele dintre ele deja cunoscute la noi problema. De exemplu, factorialul unui număr întreg n! Acesta poate fi considerat ca valoarea elementului n-lea din următoarele serii de numere:

Descrierea recursivă a unei astfel de secvență este următoarea:

Programarea de calcul secvențe recurente. Cu probleme de secvențe recurente asociate de acest tip:

1) pentru a calcula un element de secvență (n-lea) predeterminat;

2) tratează porțiunea secvență definită matematic (de exemplu, pentru a calcula suma sau produsul primilor n termeni);

3) se calculează numărul de elemente la secvențe interval predeterminate satisfac anumite proprietăți;

4) determinarea numărului primului element care satisface o anumită condiție;

5) se calculează și se păstrează un număr prestabilit de elemente de secvență.

Această listă de activități nu este exhaustivă, dar cele mai frecvente tipuri acoperă. În primele patru sarcini simultan nu este necesară pentru a stoca în memorie o multitudine de serii de numere. În acest caz, elementele sale pot fi produse în mod succesiv într-o singură variabilă, unul după altul.

Exemplul 1. Se calculează elementul n-lea al progresiei aritmetice (1).

Pentru I: = 2 până la N Do

Formula recurență ai = ai - 1 + 2 mutat la operatorul A: = A + 2.

Exemplul 2. Suma primelor n elemente ale unei progresie geometrică (2) (nu folosind formula pentru suma primilor membri n progresie).

Pentru K: = l Pentru 20 Do WriteLn (Fibon (K))

Trebuie remarcat faptul că utilizarea funcțiilor recursive încetinește contul. În plus, s-ar putea întâlni problema lipsei de lungime stivă, care este amintit „rută“ apeluri recursive.

Secvențele recurente sunt adesea folosite pentru a rezolva tot felul de probleme de evoluție, și anume probleme în care trasat un proces care se dezvoltă în timp. Luați în considerare următoarea problemă.

Exemplul 6. In timpul de repaus alimentar greutatea corporală a pacientului timp de 30 zile a scăzut de la 96 la 70 kg. Sa constatat că pierderile zilnice de greutate sunt proporționale cu greutatea corporală. Calculați ceea ce este egal cu greutatea pacientului cu zile k după începutul postului pentru k = 1, 2, 29.

Notăm greutatea pacientului în ziua i-lea după pi (i = 0, 1, 2, 30). Din condițiile problemei este cunoscut faptul că P0 = 96 kg, p30 = 70 kg.

Fie K un factor de proporționalitate de scădere în greutate într-o singură zi. atunci

Obținem o secvență descrisă de următoarea formulă recursivă:

Cu toate acestea, noi nu știm K. Coeficientul său poate fi găsit folosind starea P30 = 70.

Pentru a face acest lucru vom face căutare inversă:

Programarea în continuare devine banal.

Var I: Byte; P, Q: Real;