Difference between revisions of "Recurrence"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
| 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. |
Revision as of 21:49, 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.
