Hanojski stolpi: Razlika med redakcijama

dodanih 208 zlogov ,  pred 13 leti
m
dp/zmanjšal zamike v kodah C in Java zaradi zgoščenosti
m (dp/zmanjšal zamike v kodah C in Java zaradi zgoščenosti)
== Izvor igre ==
 
Igro je izumil francoski matematik [[Édouard Lucas]] leta [[1883]] in o njej v reviji ''Science et Nature'' napisal članek, ki je izšel naslednje leto [[1884]].<ref name="Klavzar">Klavžar, str. 148.</ref> Obstaja legenda o [[Indija|indijskem]] templju, ki ima veliko sobo s tremi obrabljenimi drogovi, ki jih obkroža 64 [[zlato|zlatih]] ploščic. Brahmani premikajo te ploščice glede na pravila igre. Po legendi bo po zadnjem premiku ploščice [[konec sveta]]. Uganka je zaradi tega znana tudi kot '''brahmanski stolpi'''. Ni znano ali si je Lucas sam izmislil legendo ali ga je le navdahnila. To nalogo (igro) lahko rešujemo na več načinov. Najbolj znana rešitev je [[rekurzija|rekurzivna]] in je zato znana tudi kot šolski primer pri [[računalnik|računalniškem]] [[programiranje|programiranju]].
 
Če bi bila legenda resnična in če bi lahko duhovniki premikali ploščice s hitrostjo 1 na [[sekunda|sekundo]], bi bil za najmanjše možno število potez ploščic potreben [[čas]] 2<sup>64</sup>−1 sekund, oziroma približno 584.542 [[milijarda|milijard]] [[leto|let]]. [[Vesolje]] je trenutno staro okrog [[starost Vesolja|13,7 milijard let]].
// Hanoi.java
public class Hanoi {
public static void main(String[] args) {
int n = 3;
hanoi(n,'A','B','C'); // prestavljamo z A na C; B je pomozna palica
}
 
private static void hanoi(int n, char a, char b, char c) {
if (n==1) {
System.out.println("Premakni obroc s palice "+a+" na palico "+c);
} else {
hanoi(n-1,a,c,b);
hanoi(1,a,b,c);
hanoi(n-1,b,a,c);
}
}
}
}
</source>
 
void move(int d, int t) {
/* premik ploščice d na stolp t */
conf[d] = t;
}
 
void hanoi(int h, int t) {
if (h > 0) {
int f = conf[h-1];
if (f != t) {
int r = 3 - f - t ;
hanoi(h-1, r);
move(h-1, t);
}
hanoi(h-1, t);
}
}
</source>
 
class Zahtevek {
public int n;
public char a,b,c;
 
public Zahtevek(int n, char a, char b, char c) {
this.n=n;
this.a=a;
this.b=b;
this.c=c;
}
}
 
public class Hanoi {
public static void main(String[] args) {
hanoi(3,'A','B','C'); // prestavljamo z A na C; B je pomozna palica
}
 
private static void izpisiSklad(Stack s) {
Iterator i = s.iterator();
System.out.println("SKLAD:");
while (i.hasNext()) {
Zahtevek z = (Zahtevek) i.next();
System.out.printf("%d %s %s %s\n", z.n, z.a, z.b, z.c);
}
System.out.println();
}
 
private static void izpisiSkladhanoi(Stackint n, char a, char b, char sc) {
Stack s=new Stack();
Iterator i = s.iterator();
System.out.println("SKLAD:");
while (i.hasNext()) {
Zahtevek z = (Zahtevek) i.next();
System.out.printf("%d %s %s %s\n", z.n, z.a, z.b, z.c);
}
System.out.println();
}
 
s.push(new Zahtevek(n,a,b,c));
private static void hanoi(int n, char a, char b, char c) {
while (!s.empty()) {
Stack s=new Stack();
izpisiSklad(s);
Zahtevek z=(Zahtevek)s.pop(); // Eksplicitna pretvorba v zahtevek
s.push(new Zahtevek(n,a,b,c));
n=z.n;
while (!s.empty()) {
a=z.a;
izpisiSklad(s);
b=z.b;
Zahtevek z=(Zahtevek)s.pop(); // Eksplicitna pretvorba v zahtevek
n c=z.nc;
if (n==1) {
a=z.a;
System.out.println("Premakni obroc s palice "+a+" na palico "+c);
b=z.b;
} else { // Zahtevki v obratnem vrstnem redu obdelovanja
c=z.c;
s.push(new Zahtevek(n-1,b,a,c));
if (n==1) {
s.push(new Zahtevek(1,a,b,c));
System.out.println("Premakni obroc s palice "+a+" na palico "+c);
s.push(new Zahtevek(n-1,a,c,b));
} else { // Zahtevki v obratnem vrstnem redu obdelovanja
}
s.push(new Zahtevek(n-1,b,a,c));
}
s.push(new Zahtevek(1,a,b,c));
}
s.push(new Zahtevek(n-1,a,c,b));
}
}
}
}
</source>