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