Probleme.GrileCostea Anneliese

1. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patrulitere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primeleopt 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

babe bace bade bbbe bbce bbde bcbe bcce bcde bdbe bdce bdde bebe bece bede

b.15

2. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patrulitere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primeleopt 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

d.eded

3. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patrulitere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primeleopt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este penultimul cuvânt generat? a. edec b. eded c. edde d. edcb

a.edec

4. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele dinmulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o dată într-un cuvânt şi literele nşi o să nu se afle pe poziţii vecine. Ştiind că primul cuvânt generat este info, iar al treilea, alpatrulea şi al cincilea sunt nifo, niof, nfio care este cel de-al doilea cuvânt obţinut?

a. iofn b. inof c. ionf d. niof

Info ..iofn.. nifo niof nfio1234..1432.. 2134 2143 2314a.iofn

5. Generarea matricelor pătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pefiecare linie şi pe fiecare coloană există un singur element egal cu 1, se poate realizautilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:a. combinărilor b. permutărilor c. aranjamentelor d. produsuluicartezian

C.aranjamentelor

6. Se generează, prin metoda backtracking, toate modalităţile de aşezare a numerelornaturale de la 1 la 5, astfel încât oricare 2 numere consecutive să nu se afle pe poziţiialăturate. Dacă primele 2 soluţii sunt: (1,3,5,2,4) şi (1,4,2,5,3), care este primasoluţie generată în care primul număr este 4? a. (4, 1, 3, 2, 5) b. (4, 2, 5, 1, 3) c. (4, 3, 5, 3, 1) d. (4, 1, 3, 5, 2)

d.(4,1,3,5,3)

7.Utilizând metoda backtracking pentru afişarea tuturor modalităţilor de descompunere a unuinumăr natural ca o sumă de numere naturale nenule, pentru n=3 se obţin în ordine soluţiile:1+1+1; 1+2; 2+1; 3. Ordinea de scriere a termenilor dintr-o descompunere estesemnificativă. Folosind aceeaşi metodă pentru n=10, care este soluţia generată imediat după1+1+3+5? a. 1+1+4+1+1+1+1 b. 1+1+7+1 c. 1+2+7 d. 1+1+4+4

a. 1+1+4+1+1+1+1

8.Construim anagramele unui cuvânt c1c2c3c4 prin generarea în ordine lexicografică apermutărilor indicilor literelor cuvântului şi obţinem c1c2c3c4 c1c2c4c3 c1c3c2c4 … c4c3c1c2c4c3c2c1. Pentru anagramele cuvântului pateu, după şirul paetu, paeut, paute cuvinteleimediat următoare sunt: a. pauet şi ptaeu b. ptaeu şi ptauec. pauet şi ptaue d. ptaeu şi patue

pateu …paetu paeut paute pauet ptaeu12345…12435,12453,12534,12543,13245a. pauet şi ptaeu

9.Se generează, prin metoda backtracking, toate modalităţile de aşezare a numerelornaturale de la 1 la 5, astfel încât oricare 2 numere consecutive să nu se afle pe poziţiialăturate. Dacă primele 2 soluţii sunt: (1,3,5,2,4) şi (1,4,2,5,3), care este primasoluţie generată în care primul număr este 4? a. (4, 1, 3, 2, 5) b. (4, 2, 5, 1, 3) c. (4, 3, 5, 3, 1) d. (4, 1, 3, 5, 2)

d.(4,1,3,5,2)

10.Se generează în ordine crescătoare, toate numerele naturale de 5 cifre distincte, care sepot forma cu cifrele 2,3,4,5 şi 6. Să se precizeze numărul generat imediat înaintea şinumărul generat imediat după secvenţa următoare : 34256, 34265, 34526, 34562 a. 32645 şi 34625 b. 32654 şi 34655c. 32654 şi 34625 d. 32645 şi 34655

32654,34256, 34265, 34526, 34562,34625

c. 32654 şi 34625

11.Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate utiliza metodabacktracking ? a. determinarea reuniunii a 3 mulţimib. determinarea tuturor divizorilor unui număr din 3 cifrec. determinarea tuturor elementelor mai mici decât 30000 din şirul lui Fibonaccid. determinarea tuturor variantelor în care se pot genera steagurile cu 3 culori (din mulţimea:”roşu”, ”galben”, ”albastru” şi ”alb”), având la mijloc culoarea ”galben”

d. determinarea tuturor variantelor în care se pot genera steagurile cu 3 culori (din mulţimea:”roşu”, ”galben”, ”albastru” şi ”alb”), având la mijloc culoarea ”galben”

12.Se generează în ordine crescătoare toate numerele de exact 4 cifre care se pot forma cuelementele mulţimii {0,1,2,3,4}. Primele 8 soluţii generate sunt, în ordine: 1000, 1001,1002, 1003, 1004, 1010, 1011, 1012. Care sunt primele trei numere ce se vor generaimediat după numărul 3443? a. 4000,4001,4002 b. 3444,4443,4444c. 3444,4444,4000 d. 3444,4000,4001

3443 3444 4000 4001d. 3444,4000,4001

13. Prin metoda backtracking se generează toate anagramele (cuvintele obţinute prinpermutarea literelor) unui cuvânt dat. Ştiind că se aplică această metodă pentru cuvântulsolar, precizaţi câte cuvinte se vor genera astfel încât prima şi ultima literă din fiecarecuvânt generat să fie vocală (sunt considerate vocale caracterele a, e, i , o, u)? a. 24 b. 6 c. 10 d. 12

aslro asrlo alsro alrso arslo arlso oslra osrla olsra olrsa orsla orlsa

d.12

14. Dacă se utilizează metoda backtracking pentru a genera toate permutările de 4 obiecte şiprimele 5 permutări generate sunt, în această ordine, 4 3 2 1, 4 3 1 2, 4 2 3 1, 42 1 3, 4 1 3 2, atunci a 6-a permutare este: a. 3 2 1 4 b. 3 4 2 1 c. 1 4 3 2 d. 4 1 2 3

d.4123

15. Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte dinmulţ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 numerelenaturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8}, câte dintre numerelegenerate au prima cifră 2 şi ultima cifră 7? a. 8 b. 3 c. 4 d. 6

2347 2357 2367 2457 2467 2567d.6

16. 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 a8-a soluţie generată de acest algoritm? a. 01110 b. 01100 c. 01011 d. 01101

b.01100

17. Trei băieţi, Alin, Bogdan şi Ciprian, şi trei fete, Delia, Elena şi Felicia, trebuie să formeze o echipă de 3 copii, care să participe la un concurs. Echipa trebuie să fie mixtă(adică să conţină cel puţin o fată şi cel puţin un băiat). Ordinea copiilor în echipă este importantă deoarece aceasta va fi ordinea de intrare a copiilor în concurs (de exemplu echipa Alin, Bogdan, Delia este diferită de echipa Bogdan, Alin, Delia). Câte echipe se pot forma, astfel încât din ele să facă parte simultan Alin şi Bogdan?

ABD,ABE,ABF,ADB,AEB,AFB,BAD,BAE,BAF,BDA,BEA,BFA,DAB,DBA,EAB,EBA,FAB,FBA

18 echipe

18. 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.

77773,77775,77777

19.Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare având cifrele ordonate strict crescător, este echivalent cu algoritmul de generare a: a. submulţimilor unei mulţimi cu 5 elemente b. produsului cartezian a unor mulţimi decifrec. aranjamentelor de 9 elemente luate câte 5 d. combinărilor de 9 elemente luate câte 5

d. combinărilor de 9 elemente luate câte 5

20. Utilizând metoda backtracking sunt generate numerele de 3 cifre care au cifrele în ordinecrescă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 estecel de al 8-lea număr generat? a. 169 b. 149 c. 167 d. 147

123, 125, 127, 129, 145,147,149,167,169

c.167

21. 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: a. produsului cartezian b. combinărilorc. aranjamentelor d. permutărilor

a. produsului cartezian

I.Generarea permutărilorSe citeşte un număr natural n. Să se genereze permutările de n elemente ale mulţimii {1,2,…,n}.

type vector=array [1..100] of integer; var x:vector;n:integer;procedure solutie;var i:integer;beginwrite (‘(‘);for i:=1 to n-1 do

write (x[i],’,‘);writeln ( x[n],’)‘);nr:= nr+1;

end;function continuare(k:integer):boolean;var i:integer;ok:boolean;nr:integer;beginok:= true;if k=1 then continuare:=true else

for i:=1 to k-1 doif k[x]:=k[i] thenok:=false;

continuare:=ok;end;

procedure back (k:integer);beginif (k=n+1) then solutie elsefor i:= 1 to n do beginx[k]:=i ;if continuare (k) thenback (k+1);end;end;beginwrite (‘n=‘);readln (n);back(1);write (‘nr=‘,nr);readln;end.

Simulaţi executarea algoritmului pentru n=3.

3!=6

II.Generarea produsului cartezian

Se citesc numerele naturale n şi p. Să se genereze toate elementele produsului cartezian P=AxAx...xA=Ap, unde A={1,2,…,n}.

type vector=array [1..100] of integer;var x:vector;procedure solutie;var x:integer;beginwrite (‘(‘);for i:=1 to n-1 do

write (x[i],’,‘);writeln ( x[n],’)‘);

end;

procedure back (k:integer);var i:integer;beginif (k=n+1) then solutie else beginfor i:= 1 to n do begin

x[k]:=i ;back (k+1);

end;end;beginwrite (‘n=’);readln (n);back(1);readln;end.

III.Problema reginelorSă se determine toate posibilităţile de aranjare a n regine pe o tablă de şah de dimensiune nxn astfel încât reginele să nu se atace reciproc. Regina atacă piesele saflate pe aceeaşi linie, coloană sau diagonală

type vector=array [1..30] of integer; var x:vector;n:integer;procedure solutie;var i,j:integer;beginwrite (‘(‘);for i:=1 to n do begin

for j:=1 to n doif x[i]=j then write (‘*’) elsewrite (‘_’);writeln;

end;function continuare(k:integer):boolean;var i:integer;ok:boolean;beginok:= true;for i:=1 to k-1 do

if ( x[k]=x[i]) or (abs (x[k]-x[i])=(k-i))then ok:=false;

continuare:=ok;end;procedure back (k:integer);var i:integer;beginif (k=n+1) then solutie else begin

for i:= 1 to n do beginx[k]:=i ;

if continuare (k) thenback (k+1);

end;end;end;beginwrite (‘n=’);readln (n);back(1);readln;end.

IV.Generarea partiţiilor unui număr naturalSe citeşte numărul natural n. Să se genereze toate modurile de descompunere a lui n ca sumă de numere naturale.

type vector=array [1..20] of integer; var x:vector;n,s:integer;procedure solutie (k:integer);var i:integer;beginfor i:=1 to n do

write (x[i],’ ‘);end;function continuare(k:integer):boolean;begin

continuare:= (x[k]+s)<n;end;

procedure back (k:integer);beginif (s=n) then solutie (k-1) else

beginx[k]:=0;

while continuare (k) do beginx[k]:=x[k]+1;s:=s+x[k]:back(k+1);s:=s-x[k];end;

end;end;beginwrite (‘n=’);readln (n);back(1);readln;end.

V.Problema turelorSă se determine toate posibilităţile de aranjare a n ture pe o tablă de şah de dimensiune nxn astfel încât turele să nu se atace reciproc. Tura atacă piesele aflate pe aceeaşi linie sau coloană.

type vector = array [1..100] of integer; var x: vector; n: integer; nr:integer;procedure solutie; var i,j :integer; begin nr:= nr+1; for i:= 1 to n do begin for j:= 1 to n do if x[i]=j then write ('*') else write (' '), writeln;end; readln; end;function continuare (k:integer):boolean; var i:integer; ok:boolean;

beginok:= true; if k=1 then continuare := true; for i:=1 to k-1 do if x[k]=x[i] then ok:= false; continuare:= ok;end;procedure back (k:integer); var i:integer;begin if (k=n+1) then solutie else for i:= 1 to n dobegin x[k]:=i; if continuare (k) then back (k+1);end;end;beginwrite ('n=',n);back(1);write('nr',nr); readln; end.

VI.Săritura caluluiSe consideră o tablă de şah nxn şi un cal plasat în colţul din stânga, sus. Se cere să se afişeze un drum al calului pe table de şah, astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

type vector= array[1..400] of integer ; matrice=array (1..20,1..20] of integer;const dx:array [1..8] of integer =(-2,-1,1,2,2,1,-1,-2); dy:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);var A:matrice x,y:vector; n:integer;procedure solutie; vari,j:integer; begin writeln; for 1:=1 to n do begin forj:= 1 to n do write('A[',i,',',j,']='); readln (A[i,j]); writeln; end;end;function continuare (k:integer):boolean; var ok:boolean;begin ok:=true;if (x[k]<1)or (x[k]>n) or (y[k]<1) or (y[k]>n) or (A[ x[k],y[k]]>o) then ok:= false; continuare:= ok;end;

procedure back (k:integer); var i:integer;begin if (k=n*n+1) then solutie else begin for i:= 1 to 8 do begin x[k]:= x[k-1]+dx[i]; y[k]:=y[k-1]+dy[i]; A[x[k],y[k]]:=k;if continuare (k) then back (k+1); A[x[k],y[k]]:=0; end;end; end;begin write('n=');readln(n); x[1]:=1; y[1]:=1;A[1,1]:=1; back(2);readln; end.

VII.Generarea aranjamentelorSe citesc două numere naturale n şi p. Să se genereze toate aranjamentele de n elemente luate câte p ale mulţimii {1,2,…,n}.

type=array [1..20] of integer; var x:vector; n,p:integer; var i:integer;begin for i:= 1 to p do write(x[i],' ');function continuare (k:integer):boolean;var i:integer;begin continuare i:=1 to k-1 do if x[i]=x[k] then continuare:=falseend;

procedure back (k:integer);var i:integer;begin if (x=p+1) then solutie else for i:= 1 to n do begin x[k]:=i; if continuare(k) then back (k+1);end; end;begin write ('n=');readln (n);write('p=');readln(p);back(1);readln;end.

Simulaţi executarea algoritmului pentru n=4 şi p=2.4!/(4-2)!=12

VIII.Generarea combinărilorSe citesc două numere naturale n şi p. Să se genereze toate combinările de n elemente luate câte p ale mulţimii {1,2,…,n}.

type vector=array [0..20] of integer; var x:vector; n,p:integer;procedure solutie; var i:integer;begin for i: 1 to p do write (x[i],' '); writeln; end;procedure back(k:integer); var i:integer;begin if (k=p+1) then solutie else for i:= x[k-1]+1 to n do begin x[k]:=1; back (k+1); end; end;beginwrite('n=');readln (n);write ('p=');readln (p);back(1);readln;end.

Simulaţi executarea algoritmului pentru n=4 şi p=2.4!/((4-2)!*2!)=6