Programatorii reprezintă adesea cicluri tind să atingă un obiectiv specific: pentru a găsi elementul cu proprietățile dorite, sortare, etc Dar cum să se asigure că obiectivul va fi atins fără a efectua ciclul de sine ..? Buclă invarianta ne va ajuta în acest sens.
Ciclul invariant este o afirmație referitoare la variabilele programului, care rămâne adevărată la începutul și la sfârșitul fiecărei iterații a buclei.
Luați în considerare utilizarea buclă invariant cu exemplul de a găsi indicele celui mai mic element într-o matrice integeră.
Să fie o matrice a. constând din n elemente. Introduceți variabila TemporarySmallest (indexul elementului care este în prezent cel mai mic) și setați-l la 0 înainte de a începe testul. Apoi, vom compara o [TemporalSmallest] secvențial cu un [1], a [2]. a [n-1]. Dacă se dovedește că un [TemporarySmallest] este mai mare decât oricare dintre [k]. atunci vom actualiza valoarea TemporarySmallest. Să desemnați variabila nextToCheck ca indice al elementului care trebuie verificat.
Ciclul invariant va arăta astfel:
- TemporarySmallest este în interiorul [0, nextToCheck),
- și pentru toate k din [0, nextToCheck), A [k]> = A [TemporarySmallest] este efectuată.
[a, b] înseamnă: toate numerele întregi în intervalul de la a la b. inclusiv a. dar fără a include b.
Cu alte cuvinte: elementul cel mai mic al matricei cu indexul TemporarySmallest cunoscut este în interiorul spațiului explorat [0, nextToCheck). Această afirmație trebuie să rămână adevărată la începutul și la sfârșitul fiecărei iterații.
Inițializați variabilele care sunt în invarianți, astfel încât să fie adevărate înainte ca buclele să înceapă:
-- indicele celui mai mic element este egal cu 0. Acesta este singurul element din intervalul [0,1]. În timp ce invarianții se păstrează.
La fiecare etapă a ciclului, valoarea nextToCheck este incrementată cu 1. și, dacă este necesar, modifică TemporarySmallest:
-- astfel încît buclă invariantă să rămână adevărată la sfârșitul fiecărei iterații. Prin urmare, la sfârșitul ciclului, invariabilul este păstrat - cel mai mic element al matricei cu indicele TemporarySmallest cunoscut va fi localizat în interiorul spațiului explorat [0, nextToCheck).
Condiția pentru sfârșitul bucla este absența în matrice a elementelor care urmează să fie verificate: nextToCheck == n. Astfel, păstrarea invariantului buclă garantează că după sfârșitul ciclului (epuizarea elementelor care urmează să fie verificate), va fi găsit indicele celui mai mic element TemporarySmallest - obiectivul ciclului este atins. Acest lucru poate fi scris ca
Ciclu invariabil End_Cycle Condition => Scopul bucla
În loc de condiția finală, puteți folosi condiția pentru a executa buclă. În cazul nostru, acesta este: nextToCheck Ciclu invariabil ! (Condiție_execuție_cycle) => Scopul ciclului Astfel, prin selectarea ciclului invariant și asigurarea conservării acestuia, putem garanta realizarea scopului fără a efectua singur ciclul. Rețineți că utilizarea invariante buclă poate fi considerată separat iterație, deoarece fiecare dintre ele începe cu aceeași stare - buclă de adevăr invariante, și, în acest sens, nu conține o „urme“ de iterații anterioare. Ca urmare, argumentul dacă ciclul se execută în mod corect, a redus pentru a verifica dacă bucla adevărul invariantă este restabilită la sfârșitul unei iterații. Întrebări pentru auto-examinare în pregătirea ciclurilor: La elaborarea ciclurilor poate fi convenabil la conceptul de zone de incertitudine. utilizat în metode computationale de matematică. Intervalul de variație a parametrilor problemei (în acest exemplu: [0, n)) poate fi împărțită în două părți: examinate regiune (pentru care a găsit TemporarySmallest [0, nextToCheck)) și regiunea de incertitudine ([nextToCheck, n)) .. Trebuie sa fie un ciclu, astfel încât la fiecare iterație a intervalului de incertitudine a fost redusă. Să revenim la exemplul nostru. La începutul primei iterații, regiunea studiată a fost singurul punct de 0. Regiunea de incertitudine a fost [1, n). La a doua etapă, regiunea de incertitudine a fost redusă la [2, n). pe a treia, la [3, n), etc., până când în final se transformă într-un set gol care nu conține puncte. Să luăm în considerare încă un exemplu - sortare după selecție în ordine descrescătoare. Să ordonăm matricea a din n întregi. Găsiți cel mai mic element și puneți-l la capătul matricei, în poziția n-1. Apoi, printre elementele rămase din nou pentru a alege cele mai mici și puneți-l în poziția n-2 și așa mai departe. D. La am iterație sortate elemente vor ocupa pozițiile de la i la n-1. iar restul neselectat - de la 0 la i-1. Pentru a găsi cel mai mic element, utilizați funcția FindMin (int a [], int n). Revenind indexul celui mai mic element și scris pe baza exemplului considerat mai sus. Introduceți variabila numSorted. care indică numărul elementelor sortate în matrice. Ciclul invariant va fi după cum urmează: Imediat înainte de buclă, inițializați valoarea numSorted: ceea ce face buclă invarianta adevărată. La fiecare iterație, numSortul este incrementat cu unul. Pentru a realiza acest lucru, cel mai mic printre primii selectat [0, n-numSorted) elemente nesortate și este interschimbat (folosind funcția swap ()) c n-numSorted elementul Astfel, "coada" sortată a matricei este extinsă de fiecare dată de un element, iar "capul" nesortat este redus. Bucla se termină când numSorted == n este atinsă. Cunoștințe, prelegere, construirea unui ciclu cu ajutorul unui invariant Ciclul sexual, estru într-un câine - 22 aprilie 2018 - un câine sănătos
Ce să citească
Articole similare
Trimiteți-le prietenilor: