Algorithmique, TD n°5
Exercice 1 :
Fonction PGCD( a : Entier, b : Entier) : Entier
	Si (a<b)
		Alors
			Retourner PGCD(b-a,a)
	Sinon Si (a=b)
		Alors
			Retourner a
		Sinon
			Retourner(a-b,b)
	FinSi
FinFonction

Exercice 2

a)	Méthode Récursive
Procedure AfficheBinaire(n : Entier) : Entier
Si ( n != 0)
	Alors
	Si  (n  mod  2  = 0)
		Alors
			AfficheBinaire(n div 2)
			Ecrire(‘0’) ;
		Sinon
			AfficheBinaire( (n-1) div 2)
			Ecrire(‘1’) ;
	FinSi
	Sinon
		Ecrire(‘0’) ;
FinSi
FinFonction
b)	Méthode Itérative
Utiliser le while dans un tableau car on connait le nombre de cases a alouer.
 
Exercice 3

Fonction Fib(n : Entier) :Entier
Si (n=0) ou (n=1)
	Retoutner n
Sinon
	Retourner FibAux(n,0,1)
FinSi
FinFonction

Fonction FibAux( n : Entier , a : Entier , b : Entier) : Entier
	Si n = 1 Alors
		Retourner (b)
	Sinon
		Retourner FibAux(n-1,b,a+b)
	FinSi
FinFonction

Exercice 4
Procedure Hanoi( n : Entier , depart : Entier , arrivee : Entier , 			intermediaire : Entier ) : Entier

	Si (n>0) Alors
		Hanoi(n-1,depart,intermediaire,arrivee)
		Bouger(depart,arrivee)
		Hanoi(n-1,intermediaire,arrivee,depart)
	FinSi
FinFonction

Compléxité => EXPONENTIELLE (multiplié par 2 a chaque appel).
Rq : le plus petite élément se déplace une fois sur 2, il se déplace tjrs ds le même sens (vers gauche si nb disques impair, vers la droite sinon). Et pour l’élément suivant à bouger on n’a pas le choix : il n’y en a qu’un qui peut bouger .
Cà donne qqchose du style :
Pour i ← 1 à 2^{n-1}
	Déplacer le plus petit de
			+1(vers la droite) si n pair
			-1(vers la gauche) si n impair
	Déplacer l’autre disque
FinPour

Montrer qu’il y a 3^n configurations. Donner un algo passe par toutes.