solution to towers of hanoi

Posted on 2000-04-26
Last Modified: 2010-05-18
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
Question by:beachbumm
LVL 16

Accepted Solution

imladris earned 10 total points
ID: 2753070
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?

Author Comment

ID: 2753453
i was close..i forgot the equation of solution (2n -1)! thanks

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now