Înlocuirea algoritmilor recursivi cu iterativi
Având în vedere că noul context este creat de fiecare dată când o altă instanță a unei rutine recursive (el încă rămâne neterminat) se numește din nou aceeași, apoi se consumă memoria calculatorului foarte repede. Prin urmare, recursivitate pentru toată claritatea ei nu poate fi atribuită la costul de metode de programare. Există chiar și o știință specială - programare dinamică. studiind metode de a înlocui algoritmii recursive algoritm iterativ corespunzătoare. Nu vom îngropa în declarația de principii ale programării dinamice, și ne limităm la exemple de transformare a programelor recursive în non-recursive.
Dacă execuția subrutinei are ca rezultat numai un apel al aceleiași subrutine, atunci această recursiune se numește liniară. Recurgerea liniară este destul de ușor de înlocuit cu un algoritm iterativ. De exemplu, puteți implementa funcția factorial. definită la începutul paragrafului "Recursiune", în două moduri.
Dacă fiecare instanță a subrutinei se poate numi de mai multe ori, atunci recursiunea este numită neliniară sau "ramificată". Pentru a transforma această recursivitate într-un algoritm iterativ, este necesar să se lucreze din greu și poate chiar să facă unele schimbări în structura datelor prelucrate. Un exemplu de recursiune "ramificată" este procedura de descompunere a unui număr în factori, așa cum sa discutat mai sus.
Exemplu de comparare a unui algoritm recursiv și nerecursiv
Sarcina. Doi prieteni au decis să meargă la camping, au adunat și au cântărit toate lucrurile necesare. Cum împart un set de obiecte în două părți în modul cel mai onest?
(Există un set de numere naturale, eventual cu repetiție. Este necesar să-l împartă în două subseturi, astfel încât diferența de sume de greutăți este minimă.)
Algoritmul recursiv
Este necesar să treceți prin toate subseturile posibile ale unui anumit set de greutăți. Pentru a rezolva această problemă, există mai mulți algoritmi clasici, vom folosi cel mai simplu, care se numește "bust total". În conformitate cu numele său, acest algoritm trece prin toate variantele posibile ale seturilor.
Implementarea unui algoritm recursiv
Căutați complet cu tăierea
Programul de mai sus face o mulțime de muncă inutilă. De exemplu, nu este necesar să continue să genereze următorul set după diferența de curent a depășit minimul găsit anterior. De asemenea, în cazul în care la un moment dat se dovedește un minim de 1 sau 0 (în funcție de paritatea datelor de intrare), eforturi suplimentare au devenit, de asemenea inutile, pentru că încă nimic mai puțin nu poate fi.
Cu aceste comentarii, textul programului poate fi îmbunătățit. Lăsăm această muncă necomplicată celor dispuși.
Un algoritm nerecursiv
Aici avem nevoie de un raționament suplimentar și de reuniuni lineare.
Partea principală a programului prezentată mai jos este o implementare iterativă a algoritmului pentru o căutare completă a tuturor variantelor posibile care satisfac constrângerile de intrare. Diferența sa principală față de recursivitate este utilizarea unei cantități mici de memorie pentru a stoca datele curente. Toate informațiile sunt stocate în mese. ia și dif. Pentru calcule, numai această informație este utilizată la fiecare pas. Această abordare evită recalculări continue, care sunt cauza "greutății" algoritmului recursiv.
Deci, prima parte a programului ar trebui să fie angajată în numărarea și aranjarea elementelor de intrare în ordinea descrescătoare a greutății lor. Pentru a economisi spațiu, nu vom oferi o implementare detaliată a acestui bloc: orice metodă de sortare este potrivită aici (vezi prelegerea 4). Este important doar ca, ca urmare a acestei sortare, toate datele de intrare să fie scrise în două linii lineare cu lungimea k (numărul de greutăți diferite).
Considerăm acum că mulțimea ves stochează diferite greutăți ale obiectelor, ordonate în ordine descrescătoare, iar array kola reprezintă numărul de obiecte pentru fiecare greutate.
În plus, în timpul introducerii datelor, se însumează greutatea tuturor obiectelor, această greutate totală este înscrisă în suma variabilă. Cu toate acestea, atunci, aceeași variabilă nu va păstra toate din greutatea totală, însă doar jumătate din ea (ținând cont de paritatea inițial suma) - pentru a facilita comparațiile ulterioare.
Nu furnizăm în textul programului și în implementarea funcției min () - ca neavând un interes deosebit.
Articole similare
Trimiteți-le prietenilor: