Questions tagged [towers-of-hanoi]
The towers-of-hanoi tag has no usage guidance.
13
questions
1
vote
1answer
45 views
Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$
I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my ...
2
votes
1answer
496 views
Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi
Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
3
votes
1answer
133 views
Analysis of the Banana Game
My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.
Game Description
The banana game is played with a ...
1
vote
4answers
647 views
Towers of Hanoi First Move
I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.
However one thing still bugs me - I can't yet work out how this simple seeming ...
1
vote
0answers
125 views
Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs
Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
1
vote
0answers
597 views
2
votes
0answers
319 views
Complexity class of Towers of Hanoi problem
Given a problem
List all steps to move n disks from rode 1 to rode 2.
I guess you are familiar with Towers of Hanoi rules.
I couldn't find a proper answer for the complexity class of this problem....
1
vote
2answers
59 views
How do I approach inductive design problems with no information or context given?
As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given ...
2
votes
1answer
271 views
Computing a Sequence of People Entering and Leaving a Room
I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows.
You start with an empty room and a group of n people waiting outside. At each step, ...
1
vote
2answers
302 views
Tower Of Hanoi Time Calculation
I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution.
The setup is the standard Towers of Hanoi, except that moving the ...
11
votes
1answer
2k views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
6
votes
1answer
937 views
An Alternative Hanoi Tower problem
We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...).
Now we want to move all $2n$ disks to tower $T_3$.
If $T(p,q)$ is a recurrence relation of minimum ...
20
votes
1answer
8k views
Complexity of Towers of Hanoi
I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments.
Is it in NP?
Attempted answer: Suppose Peggy (prover) solves the problem & submits it ...
