Referat Sortare Prin Interclasare
Mai jos puteti citi fragmente din
Referat Sortare Prin Interclasare si de asemenea puteti face
Download Referat Sortare prin interclasareCiteste fragmente din Referat Sortare Prin Interclasare
Sortare prin interclasare
Se considera vectorul a cu n componente numere întregi. Să se sorteze
crescător, utilizând sortarea prin interclasare.
program sort;
type vector=array[1..10] of integer;
var a:vector;
n,i:integer;
procedure sort(p,q:integer;var a:vector);
var m:integer;
begin
if a[p]>a[q] then
begin
m:=a[p];
a[p]:=a[q];
a[q]:=m
end;
end;
procedure interc(p,q,m:integer;var a:vector);
var b:vector;
i,j,k:integer;
begin
i:=p;
j:=m+1;
k:=1;
while (i<=m) and (j<=q) do
if a[i]<=a[j] then
begin
b[k]:=a[i];
i:=i+1;
k:=k+1
end
else begin
b[k]:=a[j];j:=j+1;k:=k+1
end;
if i<=m then
for j:=i to m do begin
b[k]:=a[j];
k:=k+1;
end
else
for i:=j to q do begin
b[k]:=a[j];
k:=k+1;
end;
k:=1;
for i:=p to q do begin
a[i]:=b[k];
k:=k+1;
end
end;
procedure divimp(p,q:integer; var a:vector);
var m:integer;
begin
if (q-p)<=1 then sort(p,q,a)
else begin
m:=(p+q) div 2;
divimp(p,m,a);
divimp(m+1,q,a);
interc(p.q.m.a);
end
end;
write(‘n= ‘);read(n);
for i:=1 to n do
begin
write(‘a[‘,i,’]=’);readln(a[i]);
end;
divimp(1,n,a);
for i:=1 to n do
writeln(a[i]);
end.
Turnurile din Hanoi
Se dau 3 tije simbolizate prin a,b,c. Pe tija a se găsesc discurile de
diametre diferite aşezate in ordine descrescătoare a diametrelor
privite de jos in sus. Se cere sa se mute discurile respectând
regulile:
la fiecare pas se muta cate un disc
nu este permis sa se aÅŸeze un disc cu diametru mai mare peste un disc
cu diametru mai mic.
program p2;
var a,b,c:char;
n:integer;
procedure hanoi(n:integer;a,b,c:char);
begin
if n=1 then writeln(a,b)
else begin
hanoi(n-1,a,c,b);
writeln(a,b);
hanoi(n-1,c,b,a);
end;
end;
begin
write( n= );readln(n);
a:= a ;b:= b ;c:= c ;
hanoi(n,a,b,c);
readln;
end.
Metoda backtracking
Created by Stănculescu AUTHOR Mihai
Metoda BACKTRACKING
Este o tehnica de programare aplicabila algoritmilor care oferă mai
multe soluţii şi are ca rezultat obţinerea tuturor soluţiilor
problemei. Fiecare soluţie se memorează într-o structura de date de
tip stivă implementată cu ajutorul unui vector. Deci fiecare soluţie
poate fi pusă sub forma unui vector.
Într-un algoritm backtracking ne interesează toate soluţiile
posibile. Pentru a obţine fiecare soluţie finală se completează
stiva nivel cu nivel trecând astfel prin nişte soluţii parţiale.
Astfel soluţiile finale cât şi cele parţiale pentru a fi luate în
considerare trebuie să îndeplinească anumite condiţii numite
condiţii de validare. O soluţie care îndeplineşte o astfel de
condiţie se numeşte soluţie validă.
Toate configuraţiile stivei ce reprezintă soluţii finale sunt
alcătuite din elementele aceleiaşi mulţimi bine definite pe care o
numim mulţimea soluţiilor. Fiecare nouă soluţie parţială se
obţine prin completarea soluţiei parţiale precedente cu încă o
nivel pe stivă. La fiecare nivel se pun valori din mulţimea
soluţiilor care nu au fost încercate până când se obţine o
soluţie validă. În acest moment se trece la nivelul următor în
stivă pentru a completa mai departe soluţia reluând încercările pe
noul nivel.
La un moment dat pe un anumit nivel nu mai există nici o valoare
neîncercată din mulţimea valorilor problemei. În acest caz se face
un pas înapoi în stivă la nivelul anterior şi se reia căutarea cu
valorile rămase neîncercate pe acest nivel anterior.
Respectivul nivel a mai fost vizitat dar l-am abandonat după ce am
pus o valoare care a generat o soluţie validă. Deci este posibil să
fi rămas aici valori neîncercate. Dacă nici pe acest nivel nu mai
avem valori neîncercate mai facem un pas înapoi în stivă. Mecanismul
revenirilor a determinat denumirea de metoda backtracking.
Plecând de la nivelul 1 şi repetând algoritmul până când pe
toate nivelele au fost încercate toate valorile din mulţimea valorilor
se obţin soluţii finale care se tipăresc.
Vom implementa metoda backtracking iterativ folosind o rutină unică
aplicabilă oricărei probleme. Rutina va apela proceduri şi funcţii
care au întotdeauna acelaşi nume şi parametri şi care din punct de
vedere al metodei realizează acelaşi lucru.
Sarcina rezolvatorului este să scrie explicit - pentru fiecare
problemă – procedurile şi funcţiile aplicate pe rutină. Astfel
găsirea următorului element netestat de pe un nivel k al stivei St se
face cu procedura succesor (as,St,k)
Odată ales un element testarea condiţiilor de validare se face cu
procedura valid (ev,St,k).
Testul dacă s-a ajuns sau nu la o soluţie finală se face cu
funcţia soluţie (k)
Soluţia se tipăreşte cu procedura tipar.
De asemenea fiecare nivel al stivei trebuie iniţializat cu o valoare
aflată înaintea tuturor valorilor posibile din mulţimea soluţiilor.
Această afişare se face cu procedura init (k,St).
Rutina Backtracking
K:=1; init (1,St);
while k>0 do
begin
repeat
succesor (as,St,k);
if as then valid (ev,St,k);
until (not as) or (as and ev);
if as then
if solutie (k) then tipar
else begin
k:=k+1;
init(k,St);
end;
else k:=k-1;
end;
end;
Probleme rezolvate
Backtracking iterativ
Generarea permutărilor.
program permutări; {iterativ}
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
n,k:integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin if st[k]
0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Generarea aranjamentelor.
program aranjamente; {iterativ}
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
n,k,p:integer;
procedure init(k:integer;var st:stiva);
begin st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin if st[k]0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Generarea combinărilor
program combinari;
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
n,k,p:integer;
procedure init(k:integer;var st:stiva);
begin
if k>1 then st[k]:=st[k-1]
else if k=1 then st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]2) and (st[k-1]>st[k]) then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=p);
end;
procedure tipar;
var i:integer;
begin
for i:=1 to p do write (st[i]);
writeln;
end;
begin;
write ( n:= );readln (n);
write ( p:= );readln (p);
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Dintr-un nr. de 6 cursuri opţionale un elev trebuie să aleagă 3. Să
se afişeze toate posibilităţile de alegere precum şi nr. lor.
program cursuri;{iterativ}
const n=6;
p=3;
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
k:integer;
procedure init(k:integer;var st:stiva);
begin
if k>1 then st[k]:=st[k-1]
else if k=1 then st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Numerele care îi plac lui Gigel
Lui Gigel îi plac nr. formate numai din cifre pare cifre aflate
în ordine descrescătoare. Să se determine şi să se afişeze pe
ecran toate nr. de n cifre (0 0 then ev:=false;
for i:=1 to k-1 do
if st[i]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
readln;
end.
iv s-au înscris n concurenţi având numerele de concurs 1,2,...,n.
Pentru fiecare sportiv se cunoaÅŸte tara de origine (ÅŸir de caractere).
In prima zi vor intra in concurs m concurenţi. Afişaţi toate
posibilităţile de a stabili ordinea intrării in concurs a celor m
concurenţi respectând următoarele condiţii:
2 sportivi din aceeaşi tara nu pot evolua unul după altul
trebuie respectata ordinea crescătoare a numerelor de concurs ale
sportivilor.
program comcurs_sportiv;{iterativ}
type stiva=array[1..100] of integer;
var st:stiva;
tara:array[1..50] of string;
m,i,n,k:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]1) and (tara[st[k-1]]=tara[st[k]]) then ev:=false;
if (k>1) and (st[k]0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Sa se afişeze toate modurile posibile de a descompune un număr natural
n in suma de k numere naturale diferite(n si k sunt cunoscute).
program desc;
type stiva=array[1..100] of integer;
var st:stiva;
s,n,k,p:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]=2) and (st[k]n then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=p);
end;
procedure tipar;
var i:integer;
begin
if s=n then
for i:=1 to p do write(st[i], );
writeln;
end;
begin
write ( n:= );readln (n);
write ( p:= );readln (p);
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
La un festival de muzica s-au înscris n melodii codificate 1,2,3,...,n
(n>=4). Sa se afişeze toate posibilităţile de a stabili ordinea
intrării in concurs a melodiilor ştiind ca melodiile cu codurile C1 si
C2 trebuie obligatoriu sa evolueze a doua respectiv penultima. Valorile
lui C1 si C2 se citesc de la tastatura C1,C2 aparţin {1,2,...,n}.
program festival;
type stiva=array[1..100] of integer;
var st:stiva;
k,n,C1,C2:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]C1) then ev:=false;
if (k=n-1) and (st[k]<>C2) then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=n);
end;
procedure tipar;
var i:integer;
begin
for i:=1 to n do write(st[i]);
writeln;
end;
begin
write( n= );readln(n);
write( melodia a II-a este: );readln(C1);
write( penultima melodie este: );readln(C2);
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Se da un număr natural par. Sa se afişeze toate şirurile de n
paranteze care se închid corect.
program paranteze;
type stiva=array[1..100] of integer;
var st:stiva;
npd,npi,n,k:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]<2 then
begin
st[k]:=st[k]+1;
as:=true;
end
else as:=false;
end;
procedure valid(var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
npd:=0;
npi:=0;
for i:=1 to k do
if st[i]=1 then npd:=npd+1
else npi:=npi+1;
if (npd>=npi) and (npd<=n div 2) then ev:=true
else ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=n);
end;
procedure tipar;
var i:integer;
begin
if npd=npi then
for I:=1 to k do
if st[i]=1 then write(‘(‘)
else write(‘)’);
writeln;
begin
write(‘n= ‘);read(n);
st[1]=1;
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Problema celor n dame.
Fiind dată o tablă de şah n x n se cer toate soluţiile de aranjare a
n dame astfel încât să nu se afle 2 dame pe aceeaşi linie, coloană
sau diagonală.
program dame;{iterativ}
type stiva=array[1..100] of integer;
var st:stiva;
n,k:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st); end
else k:=k-1;
end;
readln;
end.
mulţimi A1,A2,...,An. Sa se calculeze produsul cartezian al mulţimilor
date.
program pcartez;
type stiva=array[1..100] of integer;
var st:stiva;
i,n,k:integer;
as,ev:boolean;
a:array [1..100] of integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
end.
Se citeşte un număr natural n. Se cere sa se tipărească toate
modurile de descompunere a lui n ca suma de numere naturale.
program desc2;
type stiva=array[1..100] of integer;
var st:stiva;
s,n,k:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
end.
Problema Comis-voiajor
Un comis-voiajor trebuie sa viziteze un numar n de orase. Iniţial,
acesta se afla intr-unul dintre ele, notat 1. Comis-voiajorul doreÅŸte
sa nu treacă de doua ori prin acelaşi oraş, iar la întoarcere sa
revină in oraşul 1. Cunoscând legaturile existente intre orase, se
cere sa se tipărească toate drumurile posibile pe care le poate
efectua comis-voiajorul.
program comisv;
type stiva=array[1..100] of integer;
var st:stiva;
i,j,n,k:integer;
as,ev:boolean;
a:array[1..20,1..20] of integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=1;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
â€ â€ ã©«æ¬½ã„«à ´»â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€Â
††††††椠楮⡴Ⱬ瑳㬩â€Â††††††††††â€Â
â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ â€ æ¹¥à µ¤â€ â€ â€ â€ â€ â€ â€ æ±¥æ•³
欠㴺⵫㬱â€Â††æâ€Â æ‘®à ´»æ¹¥â¹¤à ´Â
Scrieţi un program care, folosind metoda backtracking, afişează
toate modurile de a aranja elementele unui şir dat de numere întregi
astfel încât in şirul rezultat sa nu existe doua elemente negative
alăturate.
program sir;
type stiva=array[1..100] of integer;
vector=array[1..100] of integer;
var st:stiva;
n,k,i:integer;
as,ev:boolean;
a:vector;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
end.
Turnuri de cuburi
Se dau n cuburi numerotate 1,2,...,n, de laturi Li si culori Ci,
i=1,2,...,n (fiecare culoare este codificata printr-un caracter). Sa se
afişeze toate turnurile care se pot forma luând k cuburi din cele n
disponibile, astfel încât:
-laturile cuburilor din turn sa fie in ordine crescătoare;
-culorile a oricare doua cuburi alăturate din turn sa fie
diferite.
program cuburi;
type stiva=array [1..100] of integer;
var st:stiva;
i,n,p,k:integer;
as,ev:boolean;
L:array [1..10] of integer;
C:array [1..10] of char;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then if solutie(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
end.
Generarea partiţiilor unui nr.
Se citeşte un nr. natural n .Se cere să sa tipărească toate
modurile de descompunere a lui n ca sumă de nr. naturale.
program partiţii_ale_unui_nr;
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
n,k:integer;
procedure init(k:integer;var st:stiva);
begin st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin if st[k]0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Drapele
Se dau 7 culori, codificate prin nr. 1, 2, …, 7. Afişaţi toate
posibilităţile de alcătuire a unor drapele tricolore care să
conţină numai culori dintre cele date, astfel încât: culoarea din
mijloc să aparţină unui set dat de patru culori din rândul celor 7
disponibile; a treia culoare nu poate să fie c unde c este un nr.
întreg cuprins între 1 şi 3; cele trei culori de pe drapel să fie
distincte.
program drapele;
const n=7;
type stiva=array [1..10] of integer;
var st:stiva;
ev,as:boolean;
n,k:integer;
procedure init(k:integer;var st:stiva);
begin st[k]:=0;
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if st[k]<7 then begin st[k]:=st[k]+1;
as:=true;
end
else as:=false;
end;
procedure valid(var ev:boolean;var st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do if st[i]=st[k] then ev:=false;
if (st[3]=1) or (st[3]=3) or (st[3]=2) then ev:=false;
if st[3]=(1,2,3) then ev:=false;
for i:=1 to 4 do if st[2]<>st[i] then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=n);
end;
procedure tipar;
var i:integer;
begin
for i:=1 to n do write (st[i]);
writeln;
end;
begin;
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k) then tipar
else begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.
Backtracking recursiv(după schemă)
Generarea permutărilor.
program permutări;
type stiva=array [1..10] of integer;
var st:stiva;
ev:boolean;
n,k:integer;
procedure init(k:integer;var st:stiva);
begin st[k]:=0;
end;
function succesor(var st:stiva;k:integer);
begin
if st[k]2) and (st[k-1]>st[k]) then ev:=false;
end;
procedure tipar;
var i:integer;
begin
for i:=1 to p do write (st[i]);
writeln; end;
procedure back(k:integer)
begin
if k=p then tipar
else begin
init(k,st);
while succesor(st,k) do
begin
valid(ev,st,k);
if ev then
back(k+1);
end;
end;
end;
begin
write(‘n= ‘);read(n);
write(‘p= ‘);read(p);
back(1);readln;
end.
Backtracking recursiv(fără schemă)
Generarea permutărilor.
program permutări;
type stiva=array [1..10] of integer;
var st:stiva;
n,k:integer;
procedure init(k:integer;var st:stiva);
begin st[k]:=0;
end;
function valid(k:integer):boolean;
var i:integer;
ok:boolean;
begin
ok=true;
for i:=1 to k-1 do
if st[i]=st[k] then ok=false;
{if (st[k]<0) and (st[k-1]<0) then ok=false;}
valid:=ok
end;
procedure tipar;
var i:integer;
begin
for i:=1 to n do write (st[i]);
writeln;
end;
procedure back(k:integer)
var val:integer;
begin
for val :=1 to n do
begin
st[k]:=val;
if valid(k) then
if k=n then tipar
else back(k+1);
end;
begin
write(‘n= ‘);read(n);
init(k);
back(1);
end.
Generarea aranjamentelor.
program aranjamente;
type stiva=array [1..10] of integer;
var st:stiva;
n,k:integer;
procedure init(k:integer;);
begin st[k]:=0;
end;
function valid(k:integer):boolean;
var i:integer;
ok:boolean;
begin
ok=true;
for i:=1 to k-1 do
if st[i]=st[k] then ok:=false;
if (st[k]<0) and (st[k-1]<0) then ok:=false;
valid:=ok;
end;
procedure tipar;
var i:integer;
begin
for i:=1 to p do write (st[i]);
writeln;
end;
procedure back(k:integer)
var val:integer;
begin
for val :=1 to n do
begin
st[k]:=val;
if valid(k) then
if k=p then tipar
else back(k+1);
end;
begin
write(‘n= ‘);read(n);
write(‘p= ‘);read(p);
init(k);
back(1);
end.
ărilor.
program combinărilor;
type stiva=array [1..10] of integer;
var st:stiva;
n,k:integer;
procedure init(k:integer);
begin st[k]:=0;
end;
function valid(k:integer):boolean;
var i:integer;
ok:boolean;
begin
ok:=true;
for i:=1 to k-1 do
if st[i]=st[k] then ok:=false;
if (k=>2) and (st[k-1]>st[k]) then ok:=false;
valid:=ok;
end;
procedure tipar;
var i:integer;
begin
for i:=1 to p do write (st[i]);
writeln;
end;
procedure back(k:integer)
var val:integer;
begin
for val :=1 to n-p+k do
begin
st[k]:=val;
if valid(k) then
if k=p then tipar
else back(k+1);
end;
begin
write(‘n= ‘);read(n);
write(‘p= ‘);read(p);
init(k);
back(1);
end.
PAGE 33
PAGE 32
ì¥Â
