473,324 Members | 2,196 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

highschool problem backtracking LIFO STACK

Dear mr. enginer
Please help me to rezolv this prolem.

We have some arrays:
Expand|Select|Wrap|Line Numbers
  1.   A1             1 2 3 4 5 6  14 17 23 24 27 33
  2.   A2               7 11 13 17 19 20 25
  3.   A3             23 25 26 27 
  4.    A4            34 45 46 47 48 49
  5.    A5              1 5 15 17 18 23 26 29 33 34 35 36 39 46 47
  6.  
...........................
.......................
.......................
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 .

Am intr-o culegere de probleme de informatica de la biblioteca codul in PASCAL dar nu chiar asa cum e problema asta.Nu stiu sa scriu conditia.

Generarea combinarilor
Fiind date 2 nr n si k sa se genereze toate combinarile de n luate cite k.

Expand|Select|Wrap|Line Numbers
  1.  program R I4_6;   {combimari de n cite k ne-recursiv}
  2.  type  vector=array[1..25] of integer;
  3.  var  st:vector; n,k:integer;  {st=vectorul stiva}
  4.  
  5.  procedure initializari; {initializeaza stiva si citeste n si k}
  6.  var I: integer;
  7.  begin
  8.  repeat
  9.           write  ( ‘n=’)l readln (n);
  10.             write  ( ‘k=’)l readln (k);
  11.       until n>=k;
  12.          for  i:=1 to 25 do st[i]:=0;
  13.  end;
  14.  
  15.  procedure tipar  (p: integer)  ; {tipareste o solutie memorata in vectorul st}
  16. var i: integer;
  17.        begin
  18.           for  i:=1 to p do
  19.              write  (st [ i ] :4, ’  ’ )  ;
  20.         writeln;
  21.  end;
  22.  
  23. function valid (p: integer) : boolean;
  24. {testeaza daca valoarea st[p] a generat o solutie valida, returnind  true sau false}
  25.  
  26. var i: integer; ok:boolean;
  27. begin
  28.  {valoarea de pe nivelul p nu trebuie sa se mai gaseasca pe nici unul din nivelele anterioare 1, 2,….,p-1}
  29.  
  30. ok:=true;
  31.     for  i:=1 to p-1 do
  32.       if st[p]<=st[i]  then
  33.               ok:=false;
  34.     valid:=ok;
  35. end;
  36.  
  37. procedure back;   {implementeaza algoritmul ne recursiv de backtracking}
  38.  
  39. var p: integer;  {virful stivei}
  40.  begin
  41.  p:=1; st[p]:=0;   {initializam primul nivel}
  42. while p>0 do {cit timp stiva nu devine din nou vida}
  43.     begin
  44.      if st[p]<n then {daca mai exista vreo valoare neincercata pe nivelul p}
  45.       begin
  46.            {punem pe nivelul p urmatoarea valoare din multimea solutiilor posibile}
  47.  
  48.      st[p]:= st[p]+1;
  49.     if valid(p) then {daca solutia (st[1],st[2],…st[p]) este valida}
  50.       if p=k then   {daca solutia este si finala}
  51.       tipar (p)        {tiparim solutia}
  52.       else
  53.         begin
  54.                p:=p+1; st[p]:=0; {trecem la nivelul urmator, pe care il re initializam}
  55.            end;
  56.        end
  57. else  {adica pe nivelul p nu se mai poate incerca nici o valoare}
  58.      p;=p-1;  {pasul inapoi la nivelul anterior}
  59.   end;
  60. end;
  61.  
  62. begin
  63. initializari;
  64. back;
  65. end.
[Non-English content removed because we can't verify the content. --pbmods]

Expand|Select|Wrap|Line Numbers
  1. Program RI4_2 ;
  2. {COMBINARI DE N ELEMENTE LUATE CATE K }
  3.  
  4. type vector=array[1..25] of integer;
  5. var st: vector; n,k:integer; {st=vectorul stiva}
  6.  
  7. procedure initializari;
  8. var i: integer;
  9. begin
  10. for i:=1 to 25 do st[i]:=0; {initializeaza stiva}
  11. {citeste k si n, cu validarea conditiei n>=k}
  12.  
  13. repeat
  14. write (‘n=’); readln(n);
  15. write (‘k=’); readln(k);
  16. until n>=k;
  17. end;
  18.  
  19.  
  20. procedure tipar ( p:integer) ;
  21. {tipareste o solutie memorata in vectorul st}
  22. var j:integer;
  23. begin
  24. for j:=1 to p do
  25. write (st[ j ]:4,’ ‘);
  26. writeln ;
  27. end;
  28.  
  29. function valid (p:integer):boolean;
  30. {testeaza daca valoarea pusa pe nivelul p generat o solutie valida, returnind true sau false}
  31. var I :integer;
  32. begin
  33. {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}
  34. if (p>1) and (st[ p ]<=st[p-1]) then valid:=false
  35. else valid:=true;
  36. end;
  37.  
  38. procedure bktr (p:integer) ; {implementeaza algoritmul de backtracking}
  39. var pval:integer;
  40. begin
  41. {in variabila pval trec pe rind toate valorile care ar putea fi incercate pe nivelul p}
  42. for pval:=1 to n do
  43. begin
  44. st[p]:=pval; {pune o noua valoare pe nivelul p}
  45. if valid(p) then {daca solutia obtinuta e valida}
  46. if p=k then {daca este si finala(o solutie finala are k nivele)}
  47. tipar (p) {tipareste solutia}
  48. else
  49. bktr (p+1); {trece la nivelul urmator in stiva , pt. a completa solutia}
  50. end;
  51. end;
  52.  
  53. begin
  54. initilizari;
  55. bktr (1) ; {plecam de la nivelul 1 pe stiva}
  56. readln;
  57. end.
…………………………………………………………………………………………………………….
Thank you . The next code is corect ?? :

Expand|Select|Wrap|Line Numbers
  1.  Dim st(100), n, k As Integer
  2.  
  3.  
  4.  
  5. Private Sub CommandButton1_Click()
  6.     initializari
  7.     back
  8.  
  9. End Sub
  10.  
  11. Private Sub UserForm_Click()
  12.  
  13. End Sub
  14.  
  15.  
  16.  
  17.  Sub initializari() '/{initializeaza stiva si citeste n si k}
  18.  
  19.     Do
  20.         n = Int(InputBox("n=?"))
  21.         k = Int(InputBox("k=?"))
  22.     Loop Until k <= n
  23.     For i = 1 To 25
  24.         st(i) = 0
  25.     Next i
  26.  
  27.  
  28.  
  29.  End Sub
  30.  
  31.  Sub tipar(p)
  32.         rez = ""
  33.           For i = 1 To p
  34.              rez = rez + Str(st(i))
  35.           Next i
  36.                        ListBox1.AddItem rez
  37.  
  38.  
  39.  End Sub
  40.  
  41. Function valid(p)
  42.     ok = True
  43.     For i = 1 To p - 1
  44.         If st(p) <= st(i) Then ok = False
  45.     Next i
  46.     valid = ok
  47.  
  48. End Function
  49.  
  50. Sub back() ' {implementeaza algoritmul ne recursiv de backtracking}
  51.  
  52.     p = 1
  53.     st(p) = 0
  54.     While (p > 0)
  55.         If st(p) < n Then
  56.             st(p) = st(p) + 1
  57.             If valid(p) Then
  58.                 If p = k Then
  59.                     tipar (p)
  60.                 Else
  61.                     p = p + 1
  62.                     st(p) = 0
  63.                 End If
  64.             End If
  65.         Else
  66.             p = p - 1
  67.         End If
  68.  
  69.  
  70.     Wend
  71.  
  72.  
  73. End Sub
[Please use CODE tags when posting source code. Thanks! --pbmods]
Jul 19 '07 #1
1 1745
pbmods
5,821 Expert 4TB
Removed email links.

Non-English portions of your post were removed because I could not verify the content. Please review the Posting Guidelines.
Jul 19 '07 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

15
by: Andrew | last post by:
Last night I was reading about implementing my own stack. The example given pushes items on and off the stack at the start and end of each procedure (ie. in a std module). What's not so clear is...
1
by: Steven Spear | last post by:
Hi. I am trying to perform backtracking with this search function. Something is going wrong when I enter 2 at the command line. Entering 1 at the command line seems to work fine. I notice that...
4
by: Chris Mabee | last post by:
Hello all, and Merry Christmas, I'm having a problem understanding an example of an array based implementation of a stack in a textbook of mine. The code in question is written below. The syntax...
3
by: shoo | last post by:
I am writing a program on Backtracking recursion in search of the gold. but I don't know how to start my search at location (1,1), which should be Island in a empty space character.. Here is...
6
by: Talin | last post by:
I've been using generators to implement backtracking search for a while now. Unfortunately, my code is large and complex enough (doing unification on math expressions) that its hard to post a...
2
by: ChuckB | last post by:
Ok, I'm working on this program to do recursive backtracking, however it's not working for all cases. Any help would be apprietiated. (all 4 should be true, but 168 is coming up false) Heres the...
12
by: NOO Recursion | last post by:
Hi everyone! I am trying to write a program that will search a 12x12 for a thing called a "blob". A blob in the grid is made up of asterisks. A blob contains at least one asterisk. If an...
5
AmberJain
by: AmberJain | last post by:
HELLO, The book (which I'm presently referring) of C programming says- "A stack is an example of a LIFO (Last In First Out) structure, as opposed to, for example, a queue, which is a FIFO (First In...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.