Difference between revisions of "Recurrence"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | French Mathematician | + | French Mathematician Edouard Lucas invented the Hanoi problem in 1883, which can be resolved recursively. |
− | '''Hanoi''': Let | + | '''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.