Hanojske kule

Teme vezane za console/GUI programiranje u C/C++ jeziku
3 post(ov)a • Stranica: 1/1.

Hanojske kule

PostPostao/la gagiD » 22 srp 2013, 17:16

Ev da prvo kazem sta su Hanojse kule.( ako ne znate :D )

Hanojske kule su zadatak, koji je još davne 1883. god. sastavio francuski matematičar Edvard Lukas.

Postavka zadatka i pravila

Postoje tri stubića. Na prvi stubić su naslagani prstenovi. Vaš zadatak je da sve prstenove prebacite sa prvog na poslednji stubić.

Pravilo 1: Dozvoljeno je prebacivanje samo jednog prstena u jednom trenutku vremena.
Pravilo 2: Nije dozvoljeno da se prsten većeg prečnika stavlja preko prstena manjeg prečnika.
Pravilo 3: Dozvoljeno je korišćenje jednog pomoćnog stubića (u sredini).

Postoji i legenda o Hanojskim kulama:

Legenda kaže da su postojala tri stuba na postolju hrama Brahma u Hanoiju. Na levom stubu stajaše 64 zlatna diska, svaki različite veličine, poređani koncentrično, od najvećeg na dnu do najmanjeg na vrhu stuba. Sveštenici su imali zadatak da prebace sve diskove sa prvog stuba na drugi koristeći treći stub kada im je neophodan ALI jedan po jedan disk i pravilo je bilo jasno, ne sme se nikad veći disk naći na manjem. Kada oni izvrše ovaj zadatak nastupiće kraj sveta.


Ovaj problem se moze rijesiti na sledeci nacin:

cpp code
#include<iostream>
using namespace std;
void hanoj(int n,char x,char y,char z){
if(n>1) hanoj(n-1,x,z,y);
cout<<"prebaci sa "<<x<<" na "<<y<<endl;
if(n>1) hanoj(n-1,z,y,x);
}
int main () {
int n;
cout<<"Unesite broj diskova: "<<endl;
cin>>n;
hanoj(n,'1','2','3');
return 0;
}


Ovaj programcic prebacuje na drugi stubic koristeci treci kao pomocni ali u biti nije ni bitno koji se koristi kao pomocni a i to se lako moze promeniti.( ako zelite da prebaci na treci stupac stavite ovako hanoj(n,'1','3','2'); )

Postoji i mnogo igrica na ovu temu , evo jedne : http://www.mathsisfun.com/games/towerofhanoi.html

Nadam se da vam je zanimljiv ovaj programcic: Meni jeste :D

Re: Hanojske kule

PostPostao/la HepeK » 22 srp 2013, 17:52

Zanimljivo. Ovo je rekurzivna verzija ali se može ovo riješiti i iterativnom metodom i odličan je primjer za pokazati razliku u brzini izvođenja.

Inače treba spomenuti da je potrebno odraditi (2^n)-1 operacija. :)
"Ko nema u glavi ima na internetu"
Što čujem - poštujem, dok ne vidim - ne vjerujem.

Re: Hanojske kule

PostPostao/la gagiD » 22 srp 2013, 18:13

HepeK je napisao/la:Inače treba spomenuti da je potrebno odraditi (2^n)-1 operacija. :)


Da to sam zaboravio spomenut , pa ako zelite pokrenut ovaj gore "programcic" nemoj da stavljate velik broj diskova jer moze da potraje ako je veci broj :D


3 post(ov)a • Stranica: 1/1.

Na mreži

Trenutno korisnika/ca: / i 1 gost.