clrscr; write (n=); readln (n); end; procedure init (k: integer); begin x[k]: =0; end; function exista (k: integer): Boolean; begin exista: = (x[k]0 do if exista (k) then begin x[k]: =x[k]+1; if cont (k) then if solutie (k) then tipar (k); else begin k: =k+1; init (k); end; end; else k: =k-1; end; begin citire; bkt; readln end. Algoritmul utilizat pentru generarea acestor combinari are in vedere faptul ca orice permutare este alcatuita din toate elementele multimii, care sunt distincte.
Pentru a scrie programul, stabilim urmatoarele repere: Vectorul solutie are n componente: x[k]=v are semnificatia ca valoarea v este asezata pe pozitia k in combinatie; Pentru orice k din {1, k-1} multimea valorilor posibile pentru x[k] este Ak={1, 2, k-1}; initializare se va face cu x[k]=0; Conditia de continuare pentru ca o valoare x[k] sa fie acceptata trebuie ca pentru orice I apartine {1, 2, k-1}, x[k] diferit x[i] (elementele nmultimii nu trebuie sa se repete); Am gasit o solutie finala daca an completat toate componentele vectorului (deci k=n). Pentru exemplul considerat, initial k=1, x[k]=0; (se incepe cu prima componenta si nu s-a testat nici o valoare). Vectorul solutie se va completa astfel; Stabilim prima valoare posibila pentru componenta k=1; aceasta convine si trecem la urmatoarea comoonenta; k=2. Stabilim prima valoare posubila pemtru componenta; k=2, x[2]=1; Conditiile de continuare nu sunt indeplinite, deoarece valoare 1 mai apare in aceasta combinatie.
De aceea ramanem la k=2. Testam urmatoarea valoarea posibila pentru x[2], care este 2 convine si se trece la urmatoarea componenta, k=3. Incepem cu prima valoare posibila pentru aceasta componenta, x[3]=1; nu Convine, deci ramanem la k=3. Urmatoarea valoare posibila pentru x[k] este 2 si din nounu convine.
Valoarea x[3]=3 corespunde; cum am completat toate cele n=3 componente, tiparim solutia (1, 2, 3); valoarea 3 este ultima valoare posibila si ca urmare revenim la componenta anterioara, k=2. Ultima valoare testate pentru x[2] era 2, de aceea trecem la urmatoarea valoare, x[2]=3, care convine si deci trecem la k=3. Testam urmatoarea valoare posibila pentru x[3], care este 2 convine cum am completat vectorul x, tiparim solutia (1, 3, 2) si urmatoarea la k=3. Testam ultima valoare posibila pentru aceasta componenta, x[3]=3; nu convine, deci revenim la k=2; Pentru x[2] am testat toate valorile posibile si ca urmare revenim la k=1. Ultima valoare testate pentru x[1] este 1; deci verificam ...
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
