Ideile principale ale primei misiuni sunt: PERIOADA, RECURRENȚA, PASUL CU DEȘEURI. Aceste concepte ar trebui să fie bine stăpânite de fiecare programator. În plus, sarcinile de enumerare reprezintă o parte semnificativă a tuturor olimpiadelor școlare din domeniul informaticii.
1. Generarea și pieptănarea obiectelor combinatoriale
În multe probleme aplicate, este necesar să găsim soluția optimă între un număr foarte mare (dar finit!) Numărul de variante. Uneori este posibil să construim această soluție imediat, dar în cele mai multe cazuri singura modalitate de a găsi aceasta este să căutați toate opțiunile posibile și să le comparați unul cu celălalt. Prin urmare, este foarte important pentru noi să învățăm cum să construim algoritmi pentru PERIODAREA diferitelor obiecte combinatoriale - secvențe, permutări, subseturi etc.
Schema de enumerare va fi întotdeauna aceeași:
-
- În primul rând, trebuie să stabilim ordinea privind elementele care urmează să fie transferate (în special, pentru a determina care dintre acestea vor fi primele și care este ultima);
- în al doilea rând, să învețe cum să treacă de la un element arbitrar la cel următor (adică pentru un element dat x1, construiește un element x2 astfel încât x1 H el modul cel mai natural de ordonare a obiectelor compozite este o ordine lexicografica a trecut în nici un dicționar (mai întâi comparat primele litere ale cuvintelor, apoi a doua și așa mai departe) - și asta este ceea ce vom folosi cel mai des. Dar procedura de obtinere a urmatorului element va trebui sa reinventeze de fiecare data. Până acum, vom scrie schema de enumerare în această formă: unde primul este primul element; Ultimul este ultimul element; Următoarea este procedura de obținere a următorului element. Imprimați toate secvențele de lungime N de la numerele 1,2. M. Prima = (1,1,1) Ultima = (M, M.M) În total, astfel de secvențe vor fi M ^ N (dovada!). Pentru a înțelege. Cum ar trebui să funcționeze procedura următoare, să începem cu exemplele. Fie N = 4, M = 3. apoi: Următorul (1,1,1,1) -> (1,1,1,2) Următor (1,1,1,3) -> (1,1,2,1) Următor (3,1,3, 3) -> (3,2,1,1) Acum puteți scrie procedura generală Următorul: Dacă un astfel de nu pot fi găsit, atunci următoarea secvență nu există - am ajuns la ultima (M, M.M). Rețineți, de asemenea, că în cazul în care termenii secvenței au fost numere nu de la 1 la M, ci de la 0 la M-1, atunci mergerea la următoarea ar însemna adăugarea 1 în sistemul de numere M-ary. Programul complet pe Pascal arată astfel: Imprimați toate permutările numerelor 1.N (adică secvențe de lungime N în care fiecare dintre numerele 1.N intră exact o singură dată). Prima = (1,2, N) Ultima = (N, N-1, 1) În total, astfel de permutări sunt N1 = N * (N-1) *. * 2 * 1 (dovedi!). Pentru a compila algoritmul În continuare, să ne întrebăm: în ce caz poate fi crescut i-lea membru de permutare fără a schimba cel precedent? Răspuns: dacă este mai mic decât oricare dintre următorii membri (membri cu numere mai mari decât i). Trebuie să găsim cel mai mare i, pentru care este așa, adică. cum ar fi X [i] Acum puteți scrie programul: Se afișează toate partițiile unui număr întreg N pozitiv în numere întregi pozitive (partițiile care diferă numai în ordinea termenilor sunt considerate ca fiind una). Exemplu: N = 4, partiționare: 1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2, 3 + 1, 4. Mai întâi = (1,1,1) - N unități Ultima = (N) Pentru a ne asigura că partițiile nu sunt repetate, suntem de acord să enumerăm termenii într-o ordine nesemnificativă. A spune cât de multe dintre ele vor fi toate nu este atât de ușor (a se vedea punctul următor). Pentru a compune algoritmul În continuare, să ne punem aceeași întrebare: în ce caz poate fi mărit i-al termen al partiției fără a schimba cele anterioare? Mai întâi, trebuie să existe X [i-1]> X [i] sau i = 1. În al doilea rând, nu trebuie să fiu ultimul element (creșterea trebuie să fie compensată prin scăderea următoarelor). Dacă nu există astfel de i, atunci această partiție este ultima. Prin mărirea lui i, toate elementele următoare ar trebui luate cât mai puțin posibil, adică egal cu unul: Indicăm cu L numărul de termeni din partiția curentă (este clar că 1<=L<=N). Программа будет выглядеть так: Uneori puteți găsi numărul de obiecte cu această sau acea proprietate, fără a le lista. Un exemplu clasic: C (n, k) - numărul tuturor subseturilor k-element ale unui set n-element - poate fi găsit prin completarea tabelului valorilor funcției C prin formule: C (n, k) = C (n-1, k) + C (n-1, k) 1, 0 sau cu formula n! / (k! * (n-k)!) (prima cale este mai eficientă dacă este necesar să se calculeze mai multe valori ale lui C (n, k)). Să încercăm să calculam în acest fel numărul de partiții de la punctul 1.3. Notăm R (N, k) (când N> = 0, k> = 0), numărul Nij razbie- N termeni pentru întregi pozitivi care nu depășesc k (în care R (0, k) este egală cu 1 pentru toți k> = 0). Evident, numărul R (N, N) este numărul dorit. Toate partiție N în condiții care nu depășesc k, vor fi împărțite în grupe în funcție de termenul maxim (notat cu i). Numărul R (N, k) este egal cu suma (peste toate i de la 1 la k) a numărului de partiții cu summands nu mai mare de k și termenul maxim egal cu i. O partiție de N în termeni de cel mult k cu primul summ și egală cu i este în esență partițiile lui n-i în termeni care nu depășesc i (pentru i<=k). Так что Restul pe care-l vei face în temele tale. Jocul "Turnul Hanoi" este după cum urmează. Există trei nuclee. Primul dintre ele poartă o piramidă de inele N (inele mari de jos, mai mici de sus). Este necesar să mișcați inelele pe o altă tijă. Este permisă mutarea inelelor de la tija la tija, dar nu puteți pune un inel mai mare peste cel mai mic. Creați un program care să indice acțiunile necesare. H Se scrie o procedură recursivă pentru mutarea inelelor superioare M de la tija A la cea de-a patra, presupunând că inelele rămase sunt mai mari în dimensiune și se află pe tije fără mișcare: Mai întâi transferat din piramida M-1 inele pe a treia tijă C. După aceea, inelul M-lea este eliberat, iar acesta poate fi transferat la B. Este necesar să se mute piramida de la N-1 până la C inelul B. Sarcina inițială este mai ușor? Faptul că numărul de inele a devenit unul mai puțin. Acum, programul principal poate fi scris în mai multe rânduri: Dacă știți elementele de bază ale graficii pe calculator, puteți încerca să "desenați" fiecare mișcare de pe ecran. Astfel, ideea de bază a oricărei soluții recursive este de a reduce problema exact la fel, dar cu o valoare mai mică a parametrului. În acest caz, orice valoare minimă a parametrului (de exemplu, 1 sau 0) ar trebui să ofere o soluție fără un apel recursiv - în caz contrar, programul va "merge în cicluri" (secvența apelurilor recursive va fi infinită). Acest lucru amintește de metoda inducției matematice în matematică. În unele probleme este convenabil să inverseze, să crească valoarea unui parametru într-un apel recursiv. Apoi, firește, trebuie furnizată o soluție "recursivă" pentru o valoare maximă a parametrului. Să încercăm să folosim această idee pentru a căuta obiecte combinatoriale. Sarcina este aceeași ca la punctul 1.1. Descriim procedura recursivă Generați (k), care prezintă toate secvențele de lungime N de la numerele 1. M, pentru care începutul X [1], X [2] este fix. X [k]. Este clar că pentru k = N avem o soluție trivială: există doar o astfel de secvență - ea însăși. Pentru k Programul principal pare acum foarte simplu: Sarcina este aceeași ca la punctul 1.2. Descriim procedura recursivă Generați (k), care prezintă toate permutările numerelor 1. N, pentru care este stabilit începutul X [1], X [2]. X [k]. După ieșirea din procedură, matricea X va avea aceeași valoare ca înainte de a intra (aceasta este esențială!). Este clar că pentru k = N avem din nou doar soluția trivială - permutarea însăși. Pentru k După cum ați înțeles deja, combinarea obiectelor combinatoriale este o sarcină foarte laborioasă, chiar și pentru un computer. De exemplu, permutarea a opt numere va fi de 8! = 40320 - numărul este destul de mare. Prin urmare, în orice sarcină enumerată, obiectivul principal este de a reduce numărul de PERES, În excluderea acelor obiecte care evident nu pot fi o soluție la problemă. Să presupunem că trebuie să luăm în considerare numai acele permutări pentru care suma | X [i] -i | este egal cu 8. Este clar că acestea vor fi mult mai mici: de exemplu, toate permutările începând de la 8.7. nu trebuie să ia în considerare! Cum putem modifica algoritmul de căutare în acest caz? Dacă la un moment dat suma deja mai mare de 8, luați în considerare toate permutările începând cu X [1]. X [k] nu mai este necesar - ar trebui să ne întoarcem la X [k] și să îi schimbăm valoarea ("merge înapoi" - de aici numele metodei). Pentru o astfel de situație, vom lua în considerare o metodă comună, care aproape întotdeauna face posibilă reducerea semnificativă a bustului. Lăsați soluția dorită să fie printre secvențele formei unde fiecare X [i] este selectat dintr-un set de variante A [i]. Să presupunem că deja am construit începutul acestei secvențe X [1]. X [k] (k Să presupunem de asemenea că avem o metodă simplă P (X [1], X [k]), care ne permite să răspundem la întrebarea: putem continua X [1]. X [k] înainte de decizie (adevărat) sau nu (fals). Rețineți că valoarea adevărului încă nu garantează existența unei astfel de continuări, dar valoarea falsă garantează necontinuitatea ("nu mai merge și nu încercați"). Avem o procedură recursivă simplă pentru RISCUL PASAGERII CU DEȘEURI: Un exemplu de aplicare a acestei metode este în Problema celor 8 regine.
1.1. Secvențele
1.2. permutări
1.4. Numărătoare de cantități
2.3. Secvențe (algoritm recursiv)
2.4. Permutări (algoritm recursiv)Program principal:
3. Bustul cu retragerea
Trimiteți-le prietenilor: