Grile
description
Transcript of Grile
Grile
1)Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere
din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele opt cuvinte
generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.
Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e?
a. 9 b. 15 c. 12 d. 20
Rezolvare: babe, bace, bade, bbce, bbde, bbbe, bcce, bcbe, bcde, bdbe, bdce, bdde, bebe,
bece, bede
2) Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.
Care este ultimul cuvânt generat?
a. edcb b. eeee c. edde d. eded
Rezolvare: c) eded
3) Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din mulţimea {1,2,3,7}, numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine: 123, 127, 137, 237. Dacă se utilizează exact aceeaşi metodă pentru a genera numerele naturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8}, câte dintre numerele generate au prima cifră 2 şi ultima cifră 7?
a. 8 b. 3 c. 4 d. 6 Rezolvare: 2347, 2357, 2367, 2457, 2467, 2567
=> d.6
4) Utilizând metoda backtracking sunt generate numerele de 3 cifre care au cifrele în ordine crescătoare, iar cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele cinci soluţii generate sunt, în această ordine: 123, 125, 127, 129, 145, care este cel de al 8-lea număr generat? a. 169 b. 149 c. 167 d. 147
Rezolvare: 123, 125, 127, 129, 145, 147, 149 => c. 167
5) Utilizând metoda backtracking sunt generate în ordine crescătoare toate numerele de 3 cifre, astfel încât cifrele sunt în ordine crescătoare, iar cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele trei soluţii generate sunt, în această ordine, 123, 125, 127, scrieţi toate numerele generate care au suma cifrelor egală cu 12.
Rezolvare: 129, 147, 345
6) Un algoritm de tip backtracking generează, în ordine lexicografică, toate şirurile de 5 cifre 0 şi 1 cu proprietatea că nu există mai mult de două cifre 0 pe poziţii consecutive. Primele 7 soluţii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a 8-a soluţie generată de acest algoritm?
a. 01110 b. 01100 c. 01011 d. 01101
Rezolvare: 00100, 00101, 00110, 00111, 01001, 01010, 01011 => b. 01100
7) Pentru a scrie valoarea 10 ca sumă de numere prime se foloseşte metoda backtracking şi se generează, în această ordine, sumele distincte: 2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7, 5+5. Folosind exact aceeaşi metodă, se scrie valoarea 9 ca sumă de numere prime. Care sunt primele trei soluţii, în ordinea generării lor?
Rezolvare: 2+2+2+3, 2+2+5, 2+7, 3+3+3
8) Utilizând metoda backtracking se generează permutările cuvântului info. Dacă primele trei soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie?
a. foin b. fnoi c. foni d. ifon
Rezolvare: info-1234, fino-3124, fion-3142, fnio-3214, fnoi-3241
9) Un algoritm generează în ordine crescătoare toate numerele de n cifre, folosind doar cifrele 3, 5 şi 7. Dacă pentru n=5, primele 5 soluţii generate sunt 33333, 33335, 33337, 33353, 33355, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
Rezolvare: 77773, 77775, 77777
10) Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Ştiind că primele 5 soluţii generate sunt 56789,46789, 45789, 45689, 45679, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
Rezolvare: 56789, 46789, 45789, 45689, 45679, …, 12347, 12346, 12345
11) Un algoritm generează, în ordine lexicografică, toate şirurile alcătuite din câte n cifre binare (0 şi 1). Ştiind că pentru n=5, primele 4 soluţii generate sunt 00000, 00001, 00010, 00011, precizaţi care sunt ultimele 3 soluţii generate, în ordinea obţinerii lor.
Rezolvare: 11101, 11110, 11111
12) Un algoritm generează în ordine crescătoare, toate numerele de n cifre (n<9), cu cifre distincte, care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate sunt 10325, 10327, 10329, 10345, 10347, precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.
Rezolvare: 10349, 10365, 10367, 10369
13) Un algoritm generează în ordine descrescătoare, toate numerele de n cifre (n<9), cu cifrele în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate sunt 56789, 45789, 45679, 45678, 36789, precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.
Rezolvare: 35679, 34678, 34789
14) Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E}, ordonatelexicografic, obţinem succesiv: A, AB, ABC, ABD,…. Ce şir va fi generat imediat după BAE?
a. BCA b. CAB c. BC d. BEA• Rezolvare: A B C D E • 1 2 3 4 5 • 1 • 12 • 123• 124 • 214• 23=> BC
15) Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:
• - încep şi se termină cu 0;• - modulul diferenţei între oricare două cifre alăturate
dintr-o combinaţie este 1.• Astfel, pentru n=5, combinaţiile afişate sunt, în ordine,
următoarele: 01010, 01210. Dacă se rulează acest program şi se citeşte pentru n valoarea 7, imediat după combinaţia 0101210 va fi afişată combinaţia:
• 0121210 b. 0123210 c. 0111210 d. 0121010• Rezolvare: 0101210 => d
16) Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,2,9} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele
• 20,22,29,90,92,99.• Dacă n=4 şi se utilizează acelaşi algoritm, care
este numărul generat imediat după numărul 2009?
• a. 2002 b. 2020 c. 2090 d. 2010• Rezolvare: 2000-2002-2009-2020
17) Pentru generarea în ordine crescătoare a numerelor cu n cifre formate cu elementele mulţimii {0,2,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 20,22,28,80,82,88.
• Dacă n=4 şi se utilizează acelaşi algoritm, precizaţi câte numere generate sunt divizibile cu 100?
• 8 b. 90 c. 6 d. 10• Rezolvare: 2000-2200-2800-8000-8200-8800
18) Generarea tuturor cuvintelor de trei litere mici, nu neapărat distincte, ale alfabetului englez, se poate realiza cu ajutorul unui algoritm echivalent cu cel de generare a: (4p.)
• a. produsului cartezian b. combinărilor• c. aranjamentelor d. permutărilor• Rezolvare: a.produs cartezian
19) În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocalele apar pepoziţii consecutive?
• a. 24 b. 6 c. 12 d. 4• Rezolvare: IONF-IOFN-NIOF-NOIF-OINF-OIFN-
FION-FOIN-NFIO-FNIO-NFOI-FNOI
20) Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,4,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele
• 40,44,48,80,84,88. Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat după numărul 4008 ?
• a. 4040 b. 4004 c. 4080 d. 8004• Rezolvare: a) 4040
Probleme
• Problema reginelor• Type vector= array[1..30] of integer;• Var x:vector;• n:integer;• Procedure solutie;• Var I,j : integer;• Begin writeln;• for i:= 1 to n do• Begin• for j:= 1 to n do• if x[i]= j then write (‘*’)• else write (‘_’);• writeln• End;• Function continuare ( k:integer) : boolean• Var i: integer; ok: boolean;• Begin ok:=true;• for i:= 1 to k-1 do• if (x[k]-x[i]=(k-i))• then ok:=false;• Continuare:= ok;• End.
• Saritura calului
• Type vector=array[1..400] of integer;
• matrice=array[1..20, 1..20] of integer;
• Const dx:array [1..8] of integer;
• dy:array[1..8] of integer;
• A: matrice {tabla de sah}
• x,y: vector;
• n:integer;
• Procedure solutie;
• Var I,j:integer;
• Begin writeln;
• for i:=1 to n do
• Begin
• for j:=1 to n do
• Write (A[I,j] , ‘ ‘);
• Writeln;
• End;
• End;
• Function continuare (k:integer):boolean;
• Begin
• If( x[k]<1) or (x[k]>n)
• Or (y[k]<1) or (y[k]>n)
• Or ( A[x[k], y[k]]>0)
• Then ok:= false;
• Continuare:=ok;
• End;
Procedure back (k:integer);
Var i:integer;
Begin
If ( k=n*n+1) then solutie
Else
Begin
Fot i:=1 to 8 do
Begin
X[k]=x[k-1]+ dx[i];
Y[k]=y[k-1]+ dy[i];
If continuare (k) then
back (k+1);
End;
End;
End;
Begin
Write (‘n=‘); readln (n)’
X[1]:=1; y[1]:=1; A[1,1]:=1;
Back(2);
Readln;
End.
Partitiile unui numar natural
• Type vector= array [1..20] of integer;• Var x:vector• n,s:integer;• Procedure solutie (k:integer);• var i:integer;• Begin• for i:= 1 to k do• write (x[i], ‘ ‘);• writeln;• end;• Function contiunare (k:integer) boolean;• Begin• Continuare:= (x[k]+ s)<n;• End;• Procedure back (k:integer);• Begin• If (s=n) then• solutie (k-1)• else• Begin• X[k]:=s;• While continuare (k) do• Begin• X[k]=x[k]+1• S:=s+ x[k];• Back (k+1);• S:=s-x[k];
• End;
• End;
• End;
• Begin
• write (‘n=‘); readln(n);
• back(1);
• Readln ;
• End.
• Generarea combinarilor• Fiind date doua numere naturale n si k , sa se genereze
toate combinarile de n elemente luate cate k.• program RIV_6; {combinari de n cate k
ne-recursiv}• type vector=array [1..25] of integer;• var st:vector; n,k:integer; {st=vectorul stiva}• procedure initializari ; {initializeaza stiva si
citeste n si k }• var i:integer;• begin• repeat• write('n='); readln (n);• write('k='); readln (k);• until n>=k;• for i:=1 to 25 do st[i]:=0;• end;
• procedure tipar (p:integer); {tipareste o solutie memorata in vectorul st}
• var i:integer;• begin• for i:=1 to p do• write(st[i]:4,' ');• writeln;• end;• function valid (p:integer): boolean ;• {testeaza daca valoarea st[p] a generat o
solutie valida, returnand true sau false}• var i:integer; ok:boolean;• begin• {valoarea de pe nivelul p nu trebuie sa se
mai gaseasca pe niciunul dintre nivelele anterioare 1,2,...,p-1}
• ok:=true;• for i:=1 to p-1 do• if st[p]<=st[i] then• ok:=false;• valid:=ok;• end;
• procedure back; {implementeaza algoritmul ne-recursiv de backtracking}
• var p:integer; {varful stivei}• begin• p:=1; st[p]:=0; {initializam primul nivel}• while p>0 do {cat timp stiva nu devine din
nou vida}• begin• if st[p]<n then {daca mai exista vreo
valoare neicercata oe nivelul p}• begin• {punem pe nivelul p urmatoarea valoare din
multimea solutiilor posibile}• st[p]:=st[p]+1;• if valid(p) then {daca solutia (st[1],
st[2],...,st[p]) este valida}• if p=k then {daca solutia esti si
finala}• tipar(p) {tiparim solutia}• else • begin• p:=p+1; st[p]:=0; {trecem la
nivelul urmator, pe care il re-initializam}• end;• end• else {adica pe nivelul p nu se
mai poate incerca nici o valoare}• p:=p-1; {pasul inapoi la nivelul
anterior}• end;• end;• begin• initializari;• back;• end.
Generarea aranjamentelor• Se citesc n si p. Sa se genereze toate
aranjamentele de n luate cate p.• program aranjamente;• type stiva-array [1..100] of integer;• var st:stiva ;• 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]<n• 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• ev:=true;• for i:=1 to k-1 do if st[k]=st[i] 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• end.•
• Plata unei sume cu bacnote de valori de date.
• Se dau suma s si n tipuri de monede avand valori de a1,a2, ... , an lei. Se cer toate modalitatile de plata a sumei s utilizand aceste monede.
• program bacnote;• uses crt;• type vector=array[1..9] of integer;• var sol,a,b:vector;• n,i,s:integer;• procedure tipar(k:integer);• begin• writeln('Solutie');• for i:=1 to k do• if sol[i]<>0 then writeln(sol[i],' becnote
de ',a[i]);• readln;• end;• procedure plata (k,s0:integer);• begin• while (sol[k]<b[k]) and (s0+a[k] <=s) do• begin• sol[k]:=sol[k]+1;• if sol[k]>0 then s0:=s0 + a[k];• if s0=s then tipar(k)• else• if k<n then plata(k+1,s0)• end;• sol[k]:=-1;• end;
• begin• clrscr;• write('cate tipuri de bacnote avem? ');
readln(n);• write('suma='); readln(s);• for i:=1 to n do• begin• write('valoarea monedei de tipul', i,' ');• readln (a[i]);• b[i]:=s div a[i];• sol[i]:=-1;• end;• plata(1,0);• end.
• Programul principal :program backtracking;
• type vector=array[1..25] of integer;• var st:vector; n:integer; {sv=vectorul
stiva}• procedure initializari; {initializeaza stiva si
citeste n}• var i:integer;• begin• write ('n='); readln (n);• for i:=1 to 25 do st[i]:=0;• end;• procedure tipar (p:integer); {tipareste o
solutie memorata in vectorul st}• var j:integer;• begin• for j:=1 to p do write (st[j]:4,' ');• writeln;• end;• function valid (p:integer): boolean;• {testeaza daca valoarea st[p] a generat o
solutie valida , returnand true sau false}• var i:integer; ok:boolean;• begin• {valoarea st[p], de pe nivelul p, nu trebuie
sa se mai gaseasca pe nici unul din nivelele anterioare 1,2,...,p-1}
• ok:=true;• for :=1 to p-1 do• if st[p]=st[i] then ok:=false;• valid:=ok;• end;
• procedure bktr (p:integer); {implementeaza algoritmul de backtracking}
• var pval:integer;• begin• {in variabila pval trec pe rand toate valorile
care pot fi incercate pe nivelul p al stivei}• for pval:=1 to n do• begin• st[p]:= pval; {pune o noua valoare
pe nivelul p}• if valid(p) then {daca solutia
obtinuta e valida}• if p=n then {daca este si finala}• tipar (p) {tipareste solutia}• else• bktr (p+1) ; {trece la nivelul urmator in
stiva, pentru a completa solutia}• end;• end;• begin• initializari;• bktr (1); {plecam de la nivelul 1 pe stiva}• end.