[C++] Recursieve implementatie van Hanoi vectorrepresentatie

[Neophyte808]

Hoi, ik probeer een recursieve implementatie van het Towers of Hanoi probleem te maken in c++. Alle algoritmen die ik gevonden heb op internet printen iets in zo'n trant van "move disk 1 from peg A to peg B".

Zo'n oplossing heb ik zelf ook al geprogrammeerd en dat is ook niet zo lastig, want je kunt gewoon de linkse, middelste en rechtse peg swappen door de volgorde van de parameters te veranderen. Nu wil ik iets anders proberen: ik wil na (of vóór) elke stap de state printen van een peg, d.w.z: de disks op volgorde van groot naar klein, bijvoorbeeld:

L: 5 4 3 2 1
M:
R:

...zou dan de begin state zijn.

Ik wil dit probleem oplossen door gebruik te maken van 3 vectoren die de pegs representeren. Het nadeel van de recursieve hanoi functie is alleen dat het swappen van de volgorde van de vectoren niet dezelfde werking heeft als het swappen van de pegs: de werking van het torens van Hanoi probleem zit al impliciet in de recursie en ik vind het daarom lastig om een vector representatie van het probleem te maken.
Ik zou namelijk het laatste positieve getal uit de vector (in dit geval 1) moeten vervangen door een 0, en de eerste 0 moeten vervangen door de 1, terwijl het consistent blijft met het hanoi algoritme. Ik wil me graag beperken tot recursie in dit topic.

[code=c++]
int solve_hanoi (int n, vector <int>& left_peg, vector <int>& right_peg, vector <int>& mid_peg)
{
if (n == 0)
return 0;
else
{
solve_hanoi (n - 1, left_peg, mid_peg, right_peg);

int a = left_peg.back();
left_peg.pop_back();
right_peg.push_back(a);

cout << endl << endl << "Left:";
for (int i = 0; i < left_peg.size(); i++)
cout << left_peg[i] << " ";

cout << endl << "Mid:";
for (int i = 0; i < mid_peg.size(); i++)
cout << mid_peg[i] << " ";

cout << endl << "Right:";
for (int i = 0; i < right_peg.size(); i++)
cout << right_peg[i] << " ";

solve_hanoi(n - 1, mid_peg, right_peg, left_peg);
}
}


void tower_of_hanoi (int n)
{
vector <int> left_peg;
vector <int> mid_peg;
vector <int> right_peg;

for (int i = n; i > 0; i--)
{
left_peg.push_back(i);
}
solve_hanoi(n, left_peg, right_peg, mid_peg);
}
[/code=c++]

Mijn huidige code resulteert in het printen van het woord "left" met elke keer een random integer erachter, dit zo'n 10000 keer, totdat de limiet van een integer is gebruikt en dan crasht het programma.

Voor de duidelijkheid: ik begrijp hoe het Hanoi probleem kan worden opgelost met recursie, dat is het probleem ook niet, het probleem ligt hem bij het feit dat je op vectoren operaties uit kan voeren zoals .push_back, maar ik niet weet hoe ik die dan als parameters kan meegeven in de recursieve aanroep.

[ Voor 9% gewijzigd door Neophyte808 op 17-01-2012 02:42 ]

[RobIII]

offtopic:
zonder je code bekeken te hebben; een typische limiet voor een integer is 2^15-1, 2^31-1 e.d (uitgaand van signed integers). Het klapt nu waarschijnlijk door een stack overflow; dat is een heel ander beestje

[Verwijderd]

Neem eerst nog eens een goed boek over C++ door. Je geeft je vectoren nu door als pass-by-value. Hoewel dit kan zijn wat je wilt, laat je dat niet zien.

Bekijk daarna elke regel van je code en schrijf eerst eens op wat je daar precies wilt bereiken. Vergelijk dat met de code die je geschreven hebt. Je zou zo direct al een aantal bugs moeten vinden (R14: wil je back() daar gebruiken?, R42: van 1 tot n of van n tot 1?)

[Soultaker]

Er is van alles mis met je huidige code. Ik zou je aanraden om eerst eens te beginnen met een simpeler programma dat een speltoestand kan weergeven en zetten die de gebruiker invoert kan uitvoeren. Dan weet je in ieder geval dat de implementatie van je datastructuren klopt.

Het implementeren van een algoritme om het probleem automatisch op te lossen is dan een logische tweede stap, waarbij je de bestaande functies om zetten uit te voeren en tussentoestanden weer te geven kunt hergebruiken. Dan is het ook duidelijker om te zien waar het mis gaat.

Met je huidige code is zoveel mis dat het weinig zin heeft om precies aan te geven hoe je de problemen kunt oplossen. Yexo geeft al één probleem aan: de functie die je hebt geschreven doet niets aangezien hij geen data van buiten de functie muteert (en hij returnt waarschijnlijk niet eens een zinnige waarde bij gebrek aan een return statement in de code achter de else).

Verder denk ik dat je regel 14, 19 en 24 size bedoelde in plaats van back.

Wat je algoritme betreft: je lijkt ongeveer een idee te hebben in welke richting je moet denken maar ik snap niet waarom je op regels 7-9 en 27-29 al schijven verplaatst. Sowieso lijkt het me geen goed idee om de linker twee stapels steeds te verplaatsen. Ik zou je wel pseudo-code kunnen geven voor een werkend algoritme maar ik denk dat je er verstandiger aan doet om eerst een simpeler programma zoals ik hierboven noemde probeert te maken, zodat je zelf ook snapt wat je aan het doen bent.

[Neophyte808]

@ rob, hij crasht als de waarde ongeveer 2 miljard is.

Verwijderd schreef op maandag 16 januari 2012 @ 15:38:
Neem eerst nog eens een goed boek over C++ door. Je geeft je vectoren nu door als pass-by-value. Hoewel dit kan zijn wat je wilt, laat je dat niet zien.

Ik heb in mijn eerste Hanoi algoritme ook call-by-value gebruikt, en ik weet niet waarom ik hier call-by-reference zou moeten gebruiken. Immers print ik in de procedure zelf al de verandering van de states... en ik zie nu dat ik een int-functie heb gemaakt die niks returned (hij moet het aantal zetten returnen).

back -> size is aangepast.

[RobIII]

Neophyte808 schreef op maandag 16 januari 2012 @ 16:58:
@ rob, hij crasht als de waarde ongeveer 2 miljard is.

Dat is heel iets anders dan je net zei:

Neophyte808 schreef op maandag 16 januari 2012 @ 15:11:
Mijn huidige code resulteert in het printen van het woord "left" met elke keer een random integer erachter, dit zo'n 10000 keer, totdat de limiet van een integer is gebruikt en dan crasht het programma.

Scheelt een factor, euh, mwah, 214.000

[ Voor 3% gewijzigd door RobIII op 16-01-2012 17:05 ]

[Neophyte808]

Maargoed, even over dat spel, hier mijn semi-implementatie:

C++:

void print_states(vector <int> left_peg, vector<int> mid_peg, vector <int> right_peg)
{
        cout << endl << "Left:";
        for (int i = 0; i < left_peg.size(); i++)
            cout << left_peg[i] << " ";

        cout << endl << "Mid:";
        for (int i = 0; i < mid_peg.size(); i++)
            cout << mid_peg[i] << " ";

        cout << endl << "Right:";
        for (int i = 0; i < right_peg.size(); i++)
            cout << right_peg[i] << " ";

        cout << endl;
}

void swap_disk(int from, int to,vector <int>& left_peg, vector<int>& mid_peg, vector <int>& right_peg)
{
    if (from == 1 && to == 2)
    {
        int a = left_peg.back();
        left_peg.pop_back();
        mid_peg.push_back(a);
    }
    // ... etc.
}

void hanoi_game(int n)
{
    int from, to;
    vector <int> left_peg;
    vector <int> mid_peg;
    vector <int> right_peg;

    for (int i = n; i >= 1; i--)
    {
        left_peg.push_back(i);
    }

    print_states(left_peg,mid_peg,right_peg);

    while (true) // bij gebrek aan beter
    {
    cout << "Give source and destination peg: ";
    cin >> from >> to;
    swap_disk(from, to, left_peg, mid_peg, right_peg);
    print_states(left_peg,mid_peg,right_peg);
    }
}

Er is nog maar 1 zet mogelijk, het programma controleert niet op valse states en er zit een afgrijselijke while loop in, maar het werkt.
Maar hier komt geen recursie aan te pas, dus het probleem dat ik in de TS wel heb, heb ik hier niet.

[ Voor 4% gewijzigd door Neophyte808 op 16-01-2012 17:31 ]

[Tanuki]

Daarnaast lijkt mij 3 parameters ook niet de oplossing. Je moet 1 parameter (een array van int arrays) doorgeven.

Wat nou als je ooit een toren van hanoi wilt maken die 5 pegs heeft i.p.v. 3? Tevens wordt dan de rest van je code ook een stuk makkelijker.

[Soultaker]

Neophyte808 schreef op maandag 16 januari 2012 @ 16:58:
hij moet het aantal zetten returnen

Doe dan gelijk (1 << n) - 1.

[Neophyte808]

Tanuki schreef op maandag 16 januari 2012 @ 17:36:
Daarnaast lijkt mij 3 parameters ook niet de oplossing. Je moet 1 parameter (een array van int arrays) doorgeven.

Wat nou als je ooit een toren van hanoi wilt maken die 5 pegs heeft i.p.v. 3? Tevens wordt dan de rest van je code ook een stuk makkelijker.

Het klassieke torens van hanoi-probleem heeft 3 palen, het aantal disks is niet vastgesteld, maar om ook een vector te maken van vectoren is in dit geval een beetje overdreven. Ook al vind jij dat lelijk.

Soultaker schreef op maandag 16 januari 2012 @ 17:39:
[...]
Doe dan gelijk (1 << n) - 1.

Ja dat kan natuurlijk ook, maar ik heb het in mijn vorige programma opgelost met een counter tussen de twee recursieve aanroepen en dat werkte ook. Bovendien weet je dan ook meteen dat je programma geen onnodige stappen doet.

RobIII schreef op maandag 16 januari 2012 @ 17:05:

Scheelt een factor, euh, mwah, 214.000

Die 10000 was symbolisch bedoeld, dat was het aantal integers dat geprint werd, maar ze namen toe met random stappen die véél groter waren dan 1. Maargoed ik moet natuurlijk geen exact getal noemen als ik iets symbolisch bedoel in een programmeercontext

Soultaker schreef op maandag 16 januari 2012 @ 16:19:
Wat je algoritme betreft: je lijkt ongeveer een idee te hebben in welke richting je moet denken maar ik snap niet waarom je op regels 7-9 en 27-29 al schijven verplaatst. Sowieso lijkt het me geen goed idee om de linker twee stapels steeds te verplaatsen. Ik zou je wel pseudo-code kunnen geven voor een werkend algoritme maar ik denk dat je er verstandiger aan doet om eerst een simpeler programma zoals ik hierboven noemde probeert te maken, zodat je zelf ook snapt wat je aan het doen bent.

Hier loop ik dus op vast.

[ Voor 55% gewijzigd door Neophyte808 op 16-01-2012 21:04 ]

[pedorus]

Tanuki schreef op maandag 16 januari 2012 @ 17:36:
Wat nou als je ooit een toren van hanoi wilt maken die 5 pegs heeft i.p.v. 3?

Dat is onmogelijk omdat een toren van hanoi per definitie 3 pegs heeft. Iets met KISS.

Neophyte808 schreef op maandag 16 januari 2012 @ 16:58:
Ik heb in mijn eerste Hanoi algoritme ook call-by-value gebruikt, en ik weet niet waarom ik hier call-by-reference zou moeten gebruiken. Immers print ik in de procedure zelf al de verandering van de states... en ik zie nu dat ik een int-functie heb gemaakt die niks returned (hij moet het aantal zetten returnen).

Misschien omdat je als je call-by-value gebruikt na het returnen van je functie er niets veranderd is; dit terwijl je na je functie wil dat de functie wat stenen heeft verplaatst (bij n>0)... Kortom, er ontbreken 3 &-tekens.

Wat is eigenlijk de bedoeling? C++ leren of recursie leren? Het lijkt me handig om eerst eens op papier of in pseudo-code het algoritme uit te werken. Hier klopt nu niet zoveel van namelijk. Neem vooral eerst eens rustig handmatig de stappen door. Pas dan wordt het tijd om te gaan programmeren. En begin ook bij n=1, n=2, enz. en kijk of er gebeurd wat je verwacht.

[Neophyte808]

pedorus schreef op maandag 16 januari 2012 @ 21:30:

Wat is eigenlijk de bedoeling? C++ leren of recursie leren? Het lijkt me handig om eerst eens op papier of in pseudo-code het algoritme uit te werken. Hier klopt nu niet zoveel van namelijk. Neem vooral eerst eens rustig handmatig de stappen door. Pas dan wordt het tijd om te gaan programmeren. En begin ook bij n=1, n=2, enz. en kijk of er gebeurd wat je verwacht.

Geen van beide: de bedoeling is om vectoren te gebruiken in een recursief hanoi algoritme. De syntax van mijn hierboven geschreven functie is correct, dus C++ leren is niet het doel, de semantiek is het probleem. Zoals ik in de TS ook al aan heb gegeven, heb ik al een werkend recursief algoritme geschreven van de vorm "move disk 1 from peg A to peg B", recursie leren is dus ook niet de juiste omschrijving: "het probleem ligt hem bij het feit dat je op vectoren operaties uit kan voeren zoals .push_back, maar ik niet weet hoe ik die dan als parameters kan meegeven in de recursieve aanroep."

Om een disk te verplaatsen van vector A naar vector B, moeten 3 operaties worden uitgevoerd: kopieer A.back(), A.pop_back, B.push_back(var). Hoe prop ik dit in de recursieve aanroep van de functie?

[Soultaker]

Ik snap ook niet precies waar je nu op vastloopt.

[Ik heb] al een werkend recursief algoritme geschreven van de vorm "move disk 1 from peg A to peg B"

Ok, laat eens zien dan?

Om een disk te verplaatsen van vector A naar vector B, moeten 3 operaties worden uitgevoerd: kopieer A.back(), A.pop_back, B.push_back(var).

Je kunt de tijdelijke variabele natuurlijk ook achterwege laten:

C++:

a.push_back(b.back());
b.pop_back();

Maar goed, als je dit weet, wat is dan concreet het probleem?

[Neophyte808]

Soultaker schreef op dinsdag 17 januari 2012 @ 10:18:
Ik snap ook niet precies waar je nu op vastloopt.


[...]


Ok, laat eens zien dan?


[...]
Je kunt de tijdelijke variabele natuurlijk ook achterwege laten:

C++:

a.push_back(b.back());
b.pop_back();

Maar goed, als je dit weet, wat is dan concreet het probleem?

De volgorde van de recursieve aanroepen en de vector functies.

[Soultaker]

Ok, laat je (werkende) recursieve algoritme dan eens zien, misschien dat het me dan duidelijker wordt wat het probleem is.

Het lijkt me namelijk dat als je al een algoritme hebt dat "move disk from stack 1 to stack 2" print, het niet zo moeilijk is om op die plaats ook "stack[2].push_back(stack[1].back()); stack[1].pop_back();" te doen.

[Neophyte808]

Soultaker schreef op dinsdag 17 januari 2012 @ 11:55:
Ok, laat je (werkende) recursieve algoritme dan eens zien, misschien dat het me dan duidelijker wordt wat het probleem is.

Het lijkt me namelijk dat als je al een algoritme hebt dat "move disk from stack 1 to stack 2" print, het niet zo moeilijk is om op die plaats ook "stack\[2].push_back(stack\[1].back()); stack\[1].pop_back();" te doen.

C++:

int hanoi_towers (int n, int& cnt, char from[], char help[], char to[])
{
    if (n == 1)
    {
        cout << from << " -> " << to << endl;
        cnt++;
    }
    else
    {
        hanoi_towers ((n - 1), cnt, from, to, help);
        cout << from << " -> " << to << endl;
        cnt++;
        hanoi_towers ((n - 1), cnt, help, from, to);
    }
    return cnt;
}

Om het Hanoi probleem op deze manier op te lossen, hoef je tussen de recursieve aanroepen geen operatie uit te voeren op de pegs (in dit geval cstrings). In het geval van vectoren moest dit dus wel, en daar raakte ik mee in de war.

Overigens heb ik in de tussentijd de code in de TS al een stuk of 10 keer aangepast en heb ik het probleem nu bijna opgelost. De states worden alleen verkeerd geprint omdat de pegs steeds swappen en hij print telkens òf de beginstate niet, òf de eindstate niet. Maar ik denk dat ik het wel voor elkaar kan krijgen om dat recht te zetten door modulo 3 te gebruiken. Iig bedankt voor jullie hulp allemaal.

[Soultaker]

Ok, die functie ziet er zinnig uit (al is het me niet helemaal duidelijk waarom from, help en to strings zijn -- voor de oplossing met vectoren is het handiger als het gewoon integers zijn). Als je de regels waarop je zetten print (regel 5 en 11) vervangt door code om de zetten uit te voeren op de vectors, dan ben je klaar, toch?

(De code in de TS wijkt momenteel wel af van deze structuur: je hebt daar n == 0 als basisgeval van de recursie en hier n == 1.)