program recursion;

uses crt;

const MAX = 100;
	  
function fibo_rec(n:integer):longint; {Les résultats obtenus sont grands!}
begin
   if n=0 then fibo_rec:=1
   else if n=1 then fibo_rec:=1
   else
      fibo_rec:=fibo_rec(n-1)+fibo_rec(n-2)
end;

function fibo_iter(n:integer):longint;
var tab	: array[0..MAX] of longint;
   i	: integer;
begin	
   tab[0]:=1;
   tab[1]:=1;
   for i:=2 to n do
   begin
      tab[i]:=tab[i-1]+tab[i-2]
   end;
   fibo_iter:=tab[n];
end;

function mini(a,b,c:longint):longint;
var min_tmp : longint;
begin	    
   if a<b then min_tmp:=a else min_tmp:=b;
   if c<min_tmp then mini:=c else mini:=min_tmp;
end;

function suivant(x:longint):longint;
begin
   if x<6 then suivant:=x+1
   else suivant := mini(2*suivant(x DIV 2),3*suivant(x DIV 3),
			5*suivant(x DIV 5)) {la relation de recurrence donnee}
end;

procedure Hamming_rec(n:integer);
var i : integer;
var x : longint;
begin 
   x:=0;
   for i:=1 to n do
   begin
      x:=suivant(x);
      write(x,' ');
   end
end;

const MAXI = 1000;
	   
procedure Hamming_iter(n:integer);
var a,b,c,i	      : integer;
var en_cours,va,vb,vc : longint;
   stock	      : array[0..MAXI] of longint;
begin
   stock[0]:=1;
   a:=0;b:=0;c:=0; {les exposants de 2, 3 et 5}
   write('1 ');
   for i:=2 to n do
   begin
      va:=2*stock[a];vb:=3*stock[b];vc:=5*stock[c]; {les 3 valeurs à comparer}
      en_cours:=mini(va,vb,vc);
      stock[i-1]:=en_cours;
      write(en_cours,' ');
      if en_cours=va then a:=a+1;		    {incrémentation d'un des exposants}
      if en_cours=vb then b:=b+1;
      if en_cours=vc then c:=c+1;
   end
end;


var nb : integer;
       
begin
   clrscr;
   write('n?');
   readln(nb);
   write('fibo(',nb,') = ',fibo_iter(nb));
   readln;
   write('n?');
   readln(nb);
   write('Hamming ->',nb,' : ');Hamming_rec(nb);
   readln;
   writeln;
   write('Hamming ->',nb,' : ');Hamming_iter(nb);
   readln;
end.