-
Towers of Hanoi
I have to use recursion (evil evil... for me anyhow) to make a Towers of Hanoi program. Towers of Hanoi is where you have those 3 pins. The user enters the number of disks, and the program prints in order "Move disk # from pin # to pin #". Right now, I can get about half the stack moved correctly, then after that, it begins giving me bogus input... any ideas how to go about making this program because i'm totally lost!
-
Check the thread, "When to use recursion?"
-
search these boards and you will find some code to learn from. We have done this before.
here is an iterative solution..... lol
Code:
#include <stdio.h>
int main() {
long z,y,n;
scanf("%d",&n);
for(y=1;(1<<n)-y; y<<=z-1,
printf("disk %i from %i to %i.\n",z,(y&y-1)%3,((y|y-1)+1)%3),
y++)
for(z=1; !(y&1); z++,
y>>=1);
return 0;
}
-
Hi,
My book also tells me to solve the problem of Towers of Hanoi and i skipped that bit coz it's already too hard to do it for real, like by hand as if there's a real toy in front of me lol.
But it'll good if someone post the recursion solution for me to study.
thnx
-
Hey wait i found the solution!
Code:
void hanoi (int src, int aux, int dest, int num)
{
if (num != 0)
{
// Move the pegs above to the auxillary peg...
hanoi (src, dest, aux, num - 1);
// Move the current peg to the destination peg...
printf ("Peg moved from %d to %d.\n", src, dest);
// Move the pegs from the auxillary peg to dest
hanoi (aux, src, dest, num - 1);
}
return;
}
-
Wait sorry thats not my code, got it off somewhere. But i havce one question. If all disks are to be moved to peg 3 and uses peg 2 as a temporary holding area ( that means there are 3 pegs together ), then why don't you just move all the disk one by one to disk 2 and one by one again to peg 3?
anyway, i can't figure out the function either!
-
like I said. search these boards you lazy sod.....
this is what i was telling you about earlier.
-
Solution
/* t_of_hanoi.c */
#include<stdio.h>
int shift(int, int, int);
int main()
{
int disk;
printf("Number of disk:");
scanf("%d",&disk);
shift_disk(1,3,disk);
}
int shift_disk(int from, int to, int disk)
{
/* 1,2,3 are the towers*/
int new_to;
new_to= from+to;
new_to = 6-new_to;
if(disk==0) return 0;
/* first move all except the last */
/*to the mid tower*/
shift_disk(from, new_to, disk-1);
printf("Move a disk from tower %d to %d\n",from,to);
/*Then move all disks from mid tower*/
/* to destination tower*/
shift_disk(new_to, to, disk-1);
return 0;
}
-
This might help you somewhat. Probably
best to do this with pencil and paper.
Code:
#include <stdio.h>
#define N 3
#define NR_STACKS 3
static int disk_stack[NR_STACKS] = { N, 0, 0 };
int max(int a[], int n)
{
int i;
int greatest = a[0];
for (i = 1; i < n; ++i)
if (a[i] > greatest)
greatest = a[i];
return greatest;
}
void print_disk_stack()
{
int i, j;
j = max(disk_stack, NR_STACKS);
for (; j > 0; --j) {
for (i = 0; i < NR_STACKS; ++i) {
if (disk_stack[i] >= j)
putchar('*');
else
putchar(' ');
}
putchar('\n');
}
putchar('\n');
}
void hanoi(int src, int aux, int dst, int num)
{
if (num == 1) {
print_disk_stack();
printf("(%d, %d)\n", src, dst);
disk_stack[src]--;
disk_stack[dst]++;
} else {
hanoi(src, dst, aux, num-1);
hanoi(src, aux, dst, 1);
hanoi(aux, src, dst, num-1);
}
}
int main(void)
{
hanoi(0, 1, 2, N);
print_disk_stack();
return 0;
}
-
thnx
To Zahid:
Why call the function twice in that function ?
I am very confused. Are you guys all good at maths and stuff?
-
I have divided the solution into two parts:
If I want to move the bottom disk of first tower to my destination tower (Third Tower).
=> First I have to move all except the bottom disk to the second tower.
=>Now time to move the target disk. (1 step)
=> Then I have to move all of second to third tower.
Isn't it very simple to think in this way?
This is actually the reflaction of my thinking to solve the problem.
-
Your signature says 'Never code before desk work', and i'm very new to c and had many problems, so can you post your pseudocode here for me to study if it's possible?
thnx
-
Welcome to CBOARD....
You can say my previous posting was a pseudocode for Tower of Hanoi Problem...