Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Hanojeve kule brojac poteza...

[es] :: C/C++ programiranje :: Hanojeve kule brojac poteza...

[ Pregleda: 1949 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Mooky
student
Sarajevo

Član broj: 297663
Poruke: 8
*.dynamic.telemach.ba.



Profil

icon Hanojeve kule brojac poteza...19.01.2012. u 23:43 - pre 148 meseci
Pozdrav.
Interesuje me kako da ispred svakog poteza ispise redni broj primjer "3.prebaci disk sa ......",
za vec dobro poznati kod za rjesavanje problema towers of hanoi.

void Hanoi(int n,int x=1,int y=2,int z=3) {
if(n!=0) {
Hanoi(n-1,x,z,y);
cout<<"Prebaci disk sa "<<x<<" na "<<y<<endl;
Hanoi(n-1,z,y,x);
}
}
Znam kako rijesiti pomocu globalne varijable,ili staticke,no problem se sastoji u tome što se u
zadatku trazi da se funkcija modificira tako da postane funkcija koja vraca vrijednost, tj. da
se moze rijesiti pomocu naredbe "return".
Uspio sam ubaciti brojac ali on vraca samo ukupan broj poteza.
int Hanoi(int n,int x=1,int y=2,int z=3,int brojac=1) {
if(n!=0) {
brojac+=Hanoi(n-1,x,z,y);
cout<<"Prebaci disk sa "<<x<<" na "<<y<<endl;
brojac+=Hanoi(n-1,z,y,x);
}
return brojac;
}
No međutim to je najdalje sto sam stigao.....
Molio bih ako bilo ko zna da mi pomogne.
Unaprijed zahvaljujem.
Pozdrav.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Hanojeve kule brojac poteza...20.01.2012. u 17:06 - pre 148 meseci
Code:
void Hanoi(int rings, int from, int to, int remained, int &move)
{
    if (rings == 0) {
        return;
    }

    Hanoi(rings-1, from, remained, to, move);
    cout << move++ << ". Move ring " << rings << " from position " << from << " to position " << to << endl;
    Hanoi(rings-1, remained, to, from, move);
}

void Hanoi(int rings)
{
    int move = 1;

    Hanoi(rings, 1, 2, 3, move);
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Mooky
student
Sarajevo

Član broj: 297663
Poruke: 8
*.dynamic.telemach.ba.



Profil

icon Re: Hanojeve kule brojac poteza...20.01.2012. u 20:24 - pre 148 meseci
Nedeljko hvala na odgovoru,interesantno rijesenje uz pomoc referenci,no ipak to nije ono sto se trazi u zadatku.
Problem je u tome sto se morala uvesti nova promjenljiva(move) izvan funkcije,pa time reference ispadaju iz igre.
Funkcija Hanoi treba biti potpuno neovisna,dakle dozvoljena je upotreba samo lokalnih parametara (bez statickih varijabli),
a u tekstu zadatka je data uputa da se funkcija moze modifikovati tako da vraca vrijednost (pri tome je poznato da se povratna
vrijednost funkcije smije ignorirati ukoliko nije potrebna).

 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Hanojeve kule brojac poteza...21.01.2012. u 09:36 - pre 148 meseci
Pišem napamet, ali možda ovako nekako:

Code:
int Hanoi(int rings, int from, int to, int remained, int move)
{
    if (rings == 0)
        return 0;

    move += Hanoi(rings-1, from, remained, to, move);
    cout << ++move << ". Move ring " << rings << " from position " << from << " to position " << to << endl;
    move += Hanoi(rings-1, remained, to, from, move);

    return move;
}

void Hanoi(int rings)
{
    Hanoi(rings, 1, 2, 3, 0);
}
 
Odgovor na temu

Mooky
student
Sarajevo

Član broj: 297663
Poruke: 8
*.dynamic.telemach.ba.



Profil

icon Re: Hanojeve kule brojac poteza...21.01.2012. u 15:26 - pre 148 meseci
Mihajlo,hvala na odgovoru,vjerovatno bi tako nekako trebalo ici,imam slicnu ideju,no medjutim analizom ovog koda,
vec nakon zadavanja funkciji da ispise poteze za 3 diska pojavljuje se problem.
Nakon kompajliranja program ispisuje:
1.
2.
3.
6.
7.
14.
15.
Analizirajuci tok izvrsavanja funkcije,vec nakon cetvrtog rekurzivnog poziva (tj.nakon sto je zavrseno izvrsavanje prvog
rekurzivnog poziva,dok prvi puta varijabla "rings" ne postane 0,pocinje ispisivati redom 1,2,3),
funkcija daje Hanoi(1,2,3,1,2)=3,pri cemu vraca na move=2+Hanoi(1,2,3,1,2) sto je jednako 5,
nakon naredbe "++move" povecava move na 6,te ispisuje 6.

I meni se otprilike slicne oscilacije desavaju,gdje sam izbacio problem hanojevih kula,da mi ne ometaju
u razmisljanju te sveo samo funkciju na problem ispisivanja redoslijed poteza,funkcija "kloz":

Code:
int kloz(int n,int a=1) {
    
    if(n>1) {
             a+=kloz(n-1,a);
             
             a+=kloz(1,a);
             
             a+=kloz(n-1,a);
             }
    if(n==1){
             cout<<a<<endl;
             return 1;
             }
    else return --a;

}


Medjutim kompajliranjem za primjer 4 "diska" ispisuje sljedeci redoslijed:

1,2,3,4,5,6,7,12,13,14,15,28,29,30,31.
Dok recimo za 3 ispisuje ispravno.

Pozdrav.

 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Hanojeve kule brojac poteza...22.01.2012. u 09:46 - pre 148 meseci
A da, moja greška. Umesto move += treba samo move =. Brojač treba samo da broji, a ne i da se sabira sam sa sobom.
 
Odgovor na temu

Mooky
student
Sarajevo

Član broj: 297663
Poruke: 8
*.dynamic.telemach.ba.



Profil

icon Re: Hanojeve kule brojac poteza...22.01.2012. u 12:40 - pre 148 meseci
Da,ali ako samo stavim samo "move=" svaka instanca funkcija (function frame) ce uvijek ispisivati "1",
jer ce uvijek biti proslijeđena 0 gdje ce naredba ++move uvecati u svakom okviru sa 0 na 1.
Ovaj zadatak je prava glavobolja za mene :D ostvariti komunikaciju izmedju razlicitih instanci rekurzivne funkcije
nije nimalo jednostavno (barem ne meni :D).
Pozdrav.
 
Odgovor na temu

Mooky
student
Sarajevo

Član broj: 297663
Poruke: 8
*.dynamic.telemach.ba.



Profil

icon Re: Hanojeve kule brojac poteza...22.01.2012. u 21:56 - pre 148 meseci
Shvatio sam u cemu je problem,"ko konta taj skonta" :D
Zahvaljujem se Nedeljku i Mihajlu u svakom slucaju.
Pozdrav.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Hanojeve kule brojac poteza...22.01.2012. u 22:13 - pre 148 meseci
Evo nerekurzivnog rešenja, koje je doduše sporije od rekurzivnog:

Code:
void Hanoi(int ringsNumber)
{
    int rings[ringsNumber];
    int moves = 0;

    for (int i = 0; i < ringsNumber; ++i) {
        rings[i] = 1;
    }

    while (true) {
        int i;

        for (i = ringsNumber - 1; i >= 0; --i) {
            if (rings[i] != 2) {
                break;
            }
        }

        if (i < 0) {
            break;
        }

        int from = rings[i], to = 2, remained = 4 - from, ring = i;

        for (--i; i >= 0; --i) {
            if (rings[i] != remained) {
                from = rings[i];
                to = remained;
                remained = 6 - from - to;
                ring = i;
            }
        }

        cout << ++moves << ".\tMove ring " << ring + 1 << " from position " << from << " to position " << to << endl;
        rings[ring] = to;
    }
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Hanojeve kule brojac poteza...24.01.2012. u 01:45 - pre 148 meseci
Evo još jednog nerekurzivnog rešenja:

Code:
void Hanoi(int ringsNumber)
{
    int moves = (1 << ringsNumber) - 1;

    for (int i = 1; i <= moves; ++i)
    {
        int from = 1, to = 2, moveNumber = i;

        for (int j = ringsNumber - 1; j >= 0; --j)
        {
            if (moveNumber & (1 << j)) {
                moveNumber ^= (1 << j);

                if (moveNumber) {
                    from = 6 - from - to;
                } else {
                    cout << i << ".\tMove ring " << j + 1 << " from position " << from << " to position " << to << endl;

                    break;
                }
            } else {
                to = 6 - from - to;
            }
        }
    }
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: C/C++ programiranje :: Hanojeve kule brojac poteza...

[ Pregleda: 1949 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.