Difference between revisions of "Recurrence"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
| Line 2: | Line 2: | ||
'''Hanoi''': Let T(n) be the number of steps for move n-disk tower from one post to another. We first move the top n-1 disks, i.e.,T(n-1) steps; then move the remaining disk to another post, 1 step; finally move the n-1 disks onto that disk: T(n-1) steps. In total, T(n)=2*T(n-1)+1. | '''Hanoi''': Let T(n) be the number of steps for move n-disk tower from one post to another. We first move the top n-1 disks, i.e.,T(n-1) steps; then move the remaining disk to another post, 1 step; finally move the n-1 disks onto that disk: T(n-1) steps. In total, T(n)=2*T(n-1)+1. | ||
| + | |||
| + | Now the Hanoi problem is a recurrence: | ||
| + | * T(1)=1; | ||
| + | * T(n)=2*T(n-1)+1; | ||
| + | To solve the recurrence, we have the following methods. | ||
Latest revision as of 21:52, 17 January 2009
French Mathematician Edouard Lucas invented the Hanoi problem in 1883, which can be resolved recursively.
Hanoi: Let T(n) be the number of steps for move n-disk tower from one post to another. We first move the top n-1 disks, i.e.,T(n-1) steps; then move the remaining disk to another post, 1 step; finally move the n-1 disks onto that disk: T(n-1) steps. In total, T(n)=2*T(n-1)+1.
Now the Hanoi problem is a recurrence:
- T(1)=1;
- T(n)=2*T(n-1)+1;
To solve the recurrence, we have the following methods.
