Lista Probleme Rezolvate Informatica Goja Razvan
-
Upload
denisa-corbu -
Category
Documents
-
view
327 -
download
2
Transcript of Lista Probleme Rezolvate Informatica Goja Razvan
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
1/16
Lista probleme rezolvate informatica
1.Generarea combinarilorvar sol:array[1..9] of integer;
n,p:integer;
procedure back(k:integer);
var i:integer;
begin
if k=p+1 then
begin
for i:=1 to p do
write (sol[i])l
writeln;
end;
else
begin
if k>1 then sol [k]:=sol[k-1];
else sol[k]:=0;
while sol[k]
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
2/16
2.Algoritmul de sortare cu metoda bulelor
Type vector:=array[1..100] of integer;
var x:vector;
n,I,f,t:integer;
gata:Boolean;
begin
write (n=); readln(n);
for i:=1 to n do
begin
write (x[,I,); readln (x[i]);end;
f:=n;
repeat gata:=true;
for i:=1 to f-1 do
if x[i] > x[i+1] then
begin
gata:=false;
t:=x[i], x[i]:=x[i+1];
x[i+1]:=t;
end;
f:=f-1 until gata;
for i:=1 to n do writeln (x[i]); readln;
end.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
3/16
3.Algoritmul de sortare rapida (Quick Sort)
Type vector:=array[1..100] of integer;
Var i,n,k:integer;
a:vector;
procedure poz (p,q:integer;
var k:integer;var a:vector);
var i,j,c:integer;
begin
i1:=0;
j1:= -1;
i:=p;
j;=q;
for while ia[j} then
begin
c:=a[j];
a[j]j:=a[i];
a[i]:=c;
c:=i1:
i1:= -j1:j1:= -c;
end;
i:=i+i1;
end;
k:=I;
end:
end.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
4/16
4.Metoda injumatatirii unui interval
Var a:real;
Function logn(a,p,q:real):real; var m:real;
Begin
m:=(p+q)/2;
if a:=1 then begin:=0;
else if abs(p-q)
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
5/16
5.Generarea permutarilor
Type vector=array[1..100] of integer;
Var x:vector;
n:integer;
procedure citire (var x:vector; var n:integer);
var i:integer;
begin
write(n=);
readln (n);
for i:=1 to n do
begin write (x[,i,]=);
readln(x[i]);
end;
end;
procedure solutie;
var i:integer;
begin
write (();
for i:=1 to n-1 do
write (x[i],,);writeln (x[n], ));
end;
function continuare (k:integer):Boolean;
var i:integer; ok:=Boolean; ok:=true;
begin
if k=1 then continuare:=true;
else
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 begin
for i:=1 to n do
begin
if continuare (k) then back(k+1);
end;
end;
end.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
6/16
6.Problema colorarii hartiilor
Const c:array[1..4] of char=(G,R,A,V);
Type vector=array[1..50] of integer;
Matrice=array[1..50,1..50] of integer;
Var A:matrice;
x:vector;
n:integer;
procedure citire (var n:integer; var A:matrice);
var i,j:integer;
begin
write (n=); readln(n);
for i:=1 to n do
for j:=1 to n do
begin write (A[ ,i,,,]=);
procedure solutie;
var i:integer;
begin
for i=1 to n do
writeln (tara,i,:,C[x[i]];
end;function continuare (k:integer):boolean;
var i:integer;
begin
continuare:=time;
for i:=1 to k-1 do
if (A[i,k]=1) and (x[i]=x[k]) then
continuare :=false;
end;
procedure back(k:integer);
var i:integer;
begin
if (k=n+1) then solutie
else
for i:=1 to 4 do
begin x[k]:=i;
if continuare (k) then
back(k+1);
end;
end;
begin
citire (n,A);back (1);
end.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
7/16
7.Generarea aranjamentelor de n elemente luate cate p
Type vector=array[1..20] of integer;
Var x:vector;
n,p:integer;
procedure solutie;var i:integer;
begin
for i:=1 to p do
write (x[i], );
end;
procedure back (k:integer);
var i:integer;begin
if (k=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);
wrte (p=); readln(p);
back(1);
end.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
8/16
8.Partile unui numar naturalType vector=array[1..20] of integer
Var x:vector
n,s:integer;
procedure solutie (k:integer);
var i:integer;
begin
for i:=1 tok dowrite (x[i], );
writeln;
end;
function continuare (k:integer):Boolean;
begin
continuare:=(x[k] + s)
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
9/16
Lista grile rezolvate
1.Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de cte patrulitere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale alturate. Primele optcuvinte generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.
Cte dintre cuvintele generate ncep cu litera b i se termin cu litera e?
a. 9 b. 15 c. 12 d. 20
Babe bebe
Bace bece
Bade bede
Bbbe
Bbce R:15 b.
Bbde
Bcbe
Bcce
Bcde
Bdbe
Bdce
Bdde
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
10/16
2.Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de cte patru
litere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale alturate. Primele opt cuvinte
generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.
Care este ultimul cuvnt generat?
a. edcb b. eeee c. edde d. eded5555 Eeee F
5554 Eeed F R: eded d
5454 Eded A
5445 Edde F
3.Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de
cte patru litere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale
alturate. Primele opt cuvinte generate sunt, n ordine: abab, abac, abad, abba,
abbb, abbc, abbd, abbe.
Care este penultimul cuvnt generat?
a. edec b. eded c. edde d. edcb
5454 eded ultimul cuvant generat
5453 edec penultimul cuvant generat R: a.edec
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
11/16
4.Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de cte patru
litere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale alturate. Primele opt cuvinte
generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe. Care este
antepenultimul cuvnt generat?a. edde b. eddb c. edeb d. edcb
5452 edebc.antepenultimul R:c.
5.Folosind modelul combinrilor se genereaz numerele naturale cu cte trei cifre distincte din
mulimea {1,2,3,7}, numere cu cifrele n ordine strict cresctoare, obinndu-se, n ordine: 123, 127,
137, 237. Dac se utilizeaz exact aceeai tehnic pentru a genera numerele naturale cu patru
cifre distincte din mulimea {1,2,3,4,5,6,7,8}, cte dintre numerele generate au prima cifr 2 i ultima
cifr 7? (4p.)
a. 8 b. 3 c. 4 d. 6
2345 2458
2346 25672347 R: b.
2348
2456
2457
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
12/16
6. Utiliznd metoda backtracking sunt generate numerele de 3 cifre, avnd toate cifrele
distincte i cu proprietatea c cifrele aflate pe poziii consecutive sunt de paritate diferit. tiind c
primele ase soluii generate sunt, n aceast ordine, 103, 105, 107, 109, 123, 125, care este a
zecea soluie generat?
a. 145 b. 147 c. 230 d. 149
103 105 107 109 123 125 127 129 123 125 127 129 143 145 147 149 R: a.
7.Utiliznd metoda backtracking sunt generate numerele de 3 cifre care au cifrele n ordine
cresctoare, iar cifrele aflate pe poziii consecutive sunt de paritate diferit. tiind c primele cinci
soluii generate sunt, n aceast ordine, 123, 125, 127, 129, 145, care este cel de al 8-lea numr
generat?
a. 169 b. 149 c. 167 d. 147
123 125 127 129 145 147 149 167 169 189 R: c.
8.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 poziii consecutive. Primele 7 soluii
generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a 8-a soluie generat
de acest algoritm? (4p.)
a. 01110 b. 01100 c. 01011 d. 01101
00100 00101 00110 00111 01001 01010 01011 01110 100 101 111 1001 1010 R: a.
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
13/16
9.Folosind tehnica bactracking un elev a scris un program care genereaz toate numerele de
cte n cifre (0
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
14/16
12.Trei biei, 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
conin cel puin o fat i cel puin un biat). 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). Cte echipe se pot forma, astfel nct din ele s fac parte
simultan Alin i Bogdan?
1. Alin,Bogdan,Delia / Alin,Delia,Bogdan
2. Bogdan,Alin, Delia / Bogdan.Delia,Alin
3. Delia, Alin,Bogdan / Delia,Bogdan,Alin
4. Alin,Bogdan,Elena / Alin,Elena,Bogdan
5. Bogdan,Alin,Elena / Bogdan,Elena,Alin
6. Elena,Alin,Bogdan / Elena,Bogdan,Alin7. Alin,Bogdan,Felicia / Alin,Felicia,Bogdan
8. Bogdan,Alin,Felicia / Bogdan,Felicia, Alin => 18
13.Cate numere cu exact doua cifre poti fi construite folosind doar cifre pare distincte?
a.12 b.14 c.20 d.25
24,26,28,42,46,48,62,64,68,82,84,86 R:a.12
14.Un elev a scris un program care folosind metoda backtracking genereaza toate nr de
cate 5 cifre, cifrele fiind in ordine strist crescatoare.Scrieti toate nr.generate de program care au
prima cifra 5.
56 -> 59
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
15/16
15.Generand sirurile de meximum 3 caractere distincte din multimea {A,B,C,D,E}, ordonate
lexicografic obtinem succesiv: A, AB,ABC, ABD .Ce sir va fi generat imediat dupa BAE?
a.BCA b.CAB c.BC D.BEA R:c.BC
16.Utilizand med. Backtracking se genereaza permutarile cuv. Info.Daca primele 3 solutii
generate sunt:fino, fion, fnio care este cea de-a cincia solutie?a.foin b.fnoi c.foni d.ifon
info fino fion fnio fnoi R:b.fnoi
17.Un algoritm genereaza in ordine crescatoare toate numerele de n cifre (n
-
7/28/2019 Lista Probleme Rezolvate Informatica Goja Razvan
16/16
19.Urmatoarele probleme se refera la multimea de numere reale M={x1,x2xn}.Care dintre aceste ,
comparativ cu celelalte, admite un algoritm care se incheie dupa un nr. Minim de pasi?
a.sortarea elementelor multimii M b.generarea elem.produsului cartezian MxM
c.Determinarea elementului minim al multimii M
d.Generarea tuturor permutarilor multimii M R: c.
20.Utilizand metoda backtracking sunt generate in ordine crescatoare toate numerele de 3 cifre ,a.i,
cifrese sunt in ordine crescatoare, iar cifrele aflate pe pozitii consecutive sunt de paritate
diferita.Stiind ca primele 3 solutii generate sunt, inaceasta ordine, 123,125,127, scrieti toate
nr.generate care au suma cifrelor egala cu 12.
123,125,127,129145,147,149
167,169
199
R:129,147,345
Realizator: Goja Razvan