Submit
Improve company productivity with a Business Account.Sign Up
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.
Please enter a first name
Please enter a last name
We will never share this with anyone. Privacy Policy
Must be at least 4 characters long.
Join and Comment
By clicking you are agreeing to Experts Exchange's Terms of Use.
From novice to tech pro — start learning today.
Premium members can enroll in this course at no extra cost.
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?