• C

solution to towers of hanoi

i think i already know the answer but want to double check on my answer. the solution of the towers of hanoi with 7 disks requires how many disk moves? 128 disks
 
beachbummAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
Advertise Here
 
imladrisConnect With a Mentor Commented:
Now there's a recursive problem for ya!

Anyway, I'm coming to 127. I figure it as follows:

For a 1 disk problem: 1 disk move.

For a 2 disk problem:
    Move the smallest disk to an empty
    Move the bottom to another empty
    Move the smallest onto the other

    3 moves

For a 3 disk problem:

    Move the top two to an empty:3 moves
    Move the bottom to an empty
    Move the two onto the bottom:3 moves

    7 moves

So the number of moves for n disks looks like the number of moves for a stack one less times 2, plus one:

moves for stack of n=2*(moves for stack of n-1)+1

So we have:

1  -  1
2  -  3
3  -  7
4  -  15
5  -  31
6  -  63
7  - 127

That's almost the same you have. Are we defining the problem the same? Are we counting exactly the same thing? What do you think?
0
 
beachbummAuthor Commented:
i was close..i forgot the equation of solution (2n -1)! thanks
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.