iMÁTICA - www.matematica.br

iVProg2 iLM --- activity 1

iVProg is a free software from LInE to be used to teach and lear algorithms and programming principles.
The current Web page of iVProg2 is this one.
It has an heuristic to automatic evaluation. This mechanism is illustrated bellow.
 
Activity: The Hanoi puzzle has as mininum number of movements given by the following description function
       f(1) = 1, and f(n) = 2*f(n-1)+1, if n>1.
Using iVProg2, try to implement the algorithm that ask for the user/learner to enter a natural value N (N>0) and your algorithm prints the values of f(1), f(2), and so on, until f(N).
When your algorithm is ready, before sending it to the server, verify the solution with the iVProg top-left button .


About the Hanoi puzzle:
The Towers of Hanoi problem was initially proposed by the French mathematician François Èdouard Anatole Lucas, in 1883. Lucas proposed an curious legend to his "invention": the Tower of Brahma (or Towers of Hanoi) was created at beginning of the world, with 3 rods (sticks), the first one with 64 concentric discs.
The "world creator" also created a community of monkeys with a single task, to move all the discs from the first rod ("A") to the destination one ("C"). The creator established that the world will reaches its end when the monkeys finished their job. However, the monkeys must respect 3 laws:
  1. never put a bigger disc over any smaller one;
  2. it is possible to move a single disc per time;
  3. any disc is under movement or rest in one of the 3 rods.
Here is the challenge: try to find an scheme (algorithm) to perform the job using the minimum number of disc movement. By doing so, you could estimate the time the world has until its ending (in accordance to the legend!!).
To solve the second problem of the puzzle (estimate the remaining time), you can admit the a constant time move any single disc (e.g. 1 second). Try to find a formula that represent the number of movements by using "n" discs (function).

You can try here the interactive "applet" of Hanoi, also from LInE.


You can see: iVProg2 Web page, iAssign Web page, and iAssign in Moodle.org.


Instituto de Matemática e Estatística
Universidade de São Paulo
iMath
LInE