Dear mr. enginer
Please help me to rezolv this prolem.
We have some arrays:
A1 1 2 3 4 5 6 14 17 23 24 27 33
A2 7 11 13 17 19 20 25
A3 23 25 26 27
A4 34 45 46 47 48 49
A5 1 5 15 17 18 23 26 29 33 34 35 36 39 46 47
............... ............
............... ........
............... ........
A n
Another array B 2 3 4 5 23 25 33 34 44 45 46 (with maxim 15 nr. )
Combine NR. from B in n {it is necesary to be able to modificate n-ul } with condition to apear maxim z nr. {it is necesary to be able to modificate z-ul } from A1 ,maxim z nr. from A2 , A3 ETC .
I have a book with problems for high school but is not enough informations
to learn how to resolv this problem.The book is in Pascal anyway.
Generat the combinations :
if we have 2 nr n and k genarat all combinations de n luate cite k.
program R I4_6; {combimari de n cite 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=’)l readln (n);
write ( ‘k=’)l 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, returnind true sau false}
var i: integer; ok:boolean;
begin
{valoarea de pe nivelul p nu trebuie sa se mai gaseasca pe nici unul din 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; {virful stivei}
begin
p:=1; st[p]:=0; {initializam primul nivel}
while p>0 do {cit timp stiva nu devine din nou vida}
begin
if st[p]<n then {daca mai exista vreo valoare neincercata pe 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 este 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.
............... ............... ............... ............... ............... ............... ............... ............... ..
............... ............... ............... ............... ............... ............... ............... ............... ...........
Procedura recursiva {bktr(p:integer );} implementeaza algoritmul recursiv de backtracking tratind un nivel oarecare p al stivei.
-prin variabila pval vor trece pe rind , intr-un ciclu, toate valorile care teoretic ar putea fi puse pe nivelul p.
Ele sunt nr. naturale de la 1 la n .
Pentru fiecare dintre aceste valori :
--daca respectiva valoare a generat o solutie valida ( daca functia valid(p) a returnat TRUE ) , atunci:
--daca respectiva e si finala (p=k ) atunci o tiparim ( apelind procedura tipar(p) ) . In caz contrar , trecem la nivelul urmator ( pt. a completa solutia cu un nou nivel) , prin auto-apelul bktr(p+1) .
In programul principal ,apelam mai intai procedura initializari , apoi facem apelul bktr(1) care va declansa lantul de auto-apeluri.
Program RI4_2 ;
{COMBINARI DE N ELEMENTE LUATE CATE K }
type vector=array[1..25] of integer;
var st: vector; n,k:integer; {st=vectorul stiva}
procedure initializari;
var i: integer;
begin
for i:=1 to 25 do st[i]:=0; {initializeaza stiva}
{citeste k si n, cu validarea conditiei n>=k}
repeat
write (‘n=’); readln(n);
write (‘k=’); readln(k);
until n>=k;
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):boo lean;
{testeaza daca valoarea pusa pe nivelul p generat o solutie valida, returnind true sau false}
var I :integer;
begin
{valorile de pe stiva trebuie sa fie in ordine crescatoare, deci st[p] trebuie sa fie mai mare decit elementul st[p-1] de pe nivelul anterior}
if (p>1) and (st[ p ]<=st[p-1]) then valid:=false
else valid:=true;
end;
procedure bktr (p:integer) ; {implementeaza algoritmul de backtracking}
var pval:integer;
begin
{in variabila pval trec pe rind toate valorile care ar putea fi incercate pe nivelul p}
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=k then {daca este si finala(o solutie finala are k nivele)}
tipar (p) {tipareste solutia}
else
bktr (p+1); {trece la nivelul urmator in stiva , pt. a completa solutia}
end;
end;
begin
initilizari;
bktr (1) ; {plecam de la nivelul 1 pe stiva}
readln;
end.
……………………………………… ……………………………………… …………………………….
Thank you . The next code is corect ?? :
Dim st(100), n, k As Integer
Private Sub CommandButton1_ Click()
initializari
back
End Sub
Private Sub UserForm_Click( )
End Sub
Sub initializari() '/{initializeaza stiva si citeste n si k}
Do
n = Int(InputBox("n =?"))
k = Int(InputBox("k =?"))
Loop Until k <= n
For i = 1 To 25
st(i) = 0
Next i
End Sub
Sub tipar(p)
rez = ""
For i = 1 To p
rez = rez + Str(st(i))
Next i
ListBox1.AddIte m rez
End Sub
Function valid(p)
ok = True
For i = 1 To p - 1
If st(p) <= st(i) Then ok = False
Next i
valid = ok
End Function
Sub back() ' {implementeaza algoritmul ne recursiv de backtracking}
p = 1
st(p) = 0
While (p > 0)
If st(p) < n Then
st(p) = st(p) + 1
If valid(p) Then
If p = k Then
tipar (p)
Else
p = p + 1
st(p) = 0
End If
End If
Else
p = p - 1
End If
Wend
End Sub
Please help me to rezolv this prolem.
We have some arrays:
A1 1 2 3 4 5 6 14 17 23 24 27 33
A2 7 11 13 17 19 20 25
A3 23 25 26 27
A4 34 45 46 47 48 49
A5 1 5 15 17 18 23 26 29 33 34 35 36 39 46 47
............... ............
............... ........
............... ........
A n
Another array B 2 3 4 5 23 25 33 34 44 45 46 (with maxim 15 nr. )
Combine NR. from B in n {it is necesary to be able to modificate n-ul } with condition to apear maxim z nr. {it is necesary to be able to modificate z-ul } from A1 ,maxim z nr. from A2 , A3 ETC .
I have a book with problems for high school but is not enough informations
to learn how to resolv this problem.The book is in Pascal anyway.
Generat the combinations :
if we have 2 nr n and k genarat all combinations de n luate cite k.
program R I4_6; {combimari de n cite 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=’)l readln (n);
write ( ‘k=’)l 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, returnind true sau false}
var i: integer; ok:boolean;
begin
{valoarea de pe nivelul p nu trebuie sa se mai gaseasca pe nici unul din 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; {virful stivei}
begin
p:=1; st[p]:=0; {initializam primul nivel}
while p>0 do {cit timp stiva nu devine din nou vida}
begin
if st[p]<n then {daca mai exista vreo valoare neincercata pe 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 este 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.
............... ............... ............... ............... ............... ............... ............... ............... ..
............... ............... ............... ............... ............... ............... ............... ............... ...........
Procedura recursiva {bktr(p:integer );} implementeaza algoritmul recursiv de backtracking tratind un nivel oarecare p al stivei.
-prin variabila pval vor trece pe rind , intr-un ciclu, toate valorile care teoretic ar putea fi puse pe nivelul p.
Ele sunt nr. naturale de la 1 la n .
Pentru fiecare dintre aceste valori :
--daca respectiva valoare a generat o solutie valida ( daca functia valid(p) a returnat TRUE ) , atunci:
--daca respectiva e si finala (p=k ) atunci o tiparim ( apelind procedura tipar(p) ) . In caz contrar , trecem la nivelul urmator ( pt. a completa solutia cu un nou nivel) , prin auto-apelul bktr(p+1) .
In programul principal ,apelam mai intai procedura initializari , apoi facem apelul bktr(1) care va declansa lantul de auto-apeluri.
Program RI4_2 ;
{COMBINARI DE N ELEMENTE LUATE CATE K }
type vector=array[1..25] of integer;
var st: vector; n,k:integer; {st=vectorul stiva}
procedure initializari;
var i: integer;
begin
for i:=1 to 25 do st[i]:=0; {initializeaza stiva}
{citeste k si n, cu validarea conditiei n>=k}
repeat
write (‘n=’); readln(n);
write (‘k=’); readln(k);
until n>=k;
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):boo lean;
{testeaza daca valoarea pusa pe nivelul p generat o solutie valida, returnind true sau false}
var I :integer;
begin
{valorile de pe stiva trebuie sa fie in ordine crescatoare, deci st[p] trebuie sa fie mai mare decit elementul st[p-1] de pe nivelul anterior}
if (p>1) and (st[ p ]<=st[p-1]) then valid:=false
else valid:=true;
end;
procedure bktr (p:integer) ; {implementeaza algoritmul de backtracking}
var pval:integer;
begin
{in variabila pval trec pe rind toate valorile care ar putea fi incercate pe nivelul p}
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=k then {daca este si finala(o solutie finala are k nivele)}
tipar (p) {tipareste solutia}
else
bktr (p+1); {trece la nivelul urmator in stiva , pt. a completa solutia}
end;
end;
begin
initilizari;
bktr (1) ; {plecam de la nivelul 1 pe stiva}
readln;
end.
……………………………………… ……………………………………… …………………………….
Thank you . The next code is corect ?? :
Dim st(100), n, k As Integer
Private Sub CommandButton1_ Click()
initializari
back
End Sub
Private Sub UserForm_Click( )
End Sub
Sub initializari() '/{initializeaza stiva si citeste n si k}
Do
n = Int(InputBox("n =?"))
k = Int(InputBox("k =?"))
Loop Until k <= n
For i = 1 To 25
st(i) = 0
Next i
End Sub
Sub tipar(p)
rez = ""
For i = 1 To p
rez = rez + Str(st(i))
Next i
ListBox1.AddIte m rez
End Sub
Function valid(p)
ok = True
For i = 1 To p - 1
If st(p) <= st(i) Then ok = False
Next i
valid = ok
End Function
Sub back() ' {implementeaza algoritmul ne recursiv de backtracking}
p = 1
st(p) = 0
While (p > 0)
If st(p) < n Then
st(p) = st(p) + 1
If valid(p) Then
If p = k Then
tipar (p)
Else
p = p + 1
st(p) = 0
End If
End If
Else
p = p - 1
End If
Wend
End Sub