Chapter 2: Induction and Recursion ----------------------------------------- The lecture slides are here: hyde.eng.tau.ac.il/Even-Medina/Slides/induction-recursion.pdf A warm-up exercise before the weekend: The Tower of Hanoi is a puzzle consisting of three rods and k disks of different sizes. Initially, all the disks are stacked in descending order on the first rod (the largest disk is at the bottom, the smallest on the top). The goal is to transfer the k disks to the third rod using a sequence of moves subject to two rules: (1) In each move, we may move a disk at a top of a stack to the top of another stack. (2) A disk may not be added to a stack if it is larger than the disk currently at the top of the stack. Solving this puzzle with one or two disks is trivial. With three disks we need seven moves. To promote the puzzle, a legend was invented about priests solving a puzzle with k=64 disks, with the danger that once solved, the world will end. Should we really worry about the truthfulness of the legend? Let f(k) denote the minimum number of moves required to solve the puzzle with k disks. (1) Formulate a recursive definition of f(k). (2) Formulate a closed formula for f(k) and prove it by induction.
Posted on: Wed, 05 Jun 2013 14:33:08 +0000
Trending Topics
Recently Viewed Topics
© 2015