DM 1S, algorithmes troisième partie. A rendre par binôme.

1 Boucles bornées et non bornées

Voici un résumé de ce qu’il faut savoir à ce sujet.

1. Concernant les boucles for :

1

2. Concernant les boucles while :

2 Exercices

Exercice 1. Nous voulons calculer une valeur approchée de la somme 1 + 1

3+

(

1

3

)2+ . . . +

(

1

3

)20.

Compléter la fonction pour qu’elle renvoie cette somme

2

Exercice 2. Nous voulons calculer, pour tout entier n ≥ 1, la somme Sn définie par

Sn = 1 −1

2+

1

3−

1

4+ . . . + (−1)n+1 ×

1

n.

Compléter la fonction somme donnée ci dessous.

Exercice 3. La conjecture de Syracuse est encore non résolue à ce jour. Détaillons le procédé algo-rithmique définissant cette suite. Soit n ∈ N. Si n est pair, on le divise par 2 ; sinon on le multipliepar 3 et on ajoute 1. Ce processus est répété avec le résultat obtenu. La conjecture de Syracuseaffirme qu’au bout d’un nombre fini (éventuellement grand) d’itérations, le résultat obtenu seratoujours 1.

1. Compléter la fonction Syracuse qui répond à la conjecture et la tester pour plusieurs valeursd’entiers n.

2. Modifier la fonction Syracuse en une fonction Syracuse2 afin de compter le nombre d’itérationsnécessaires pour obtenir 1. Ce nombre d’itérations s’appelle le temps de vol associé au nombren.

3. Soit N ∈ N un entier fixé. Ecrire une fonction Maximum qui renvoie l’entier n ∈ {1, . . . , N}ayant le plus grand temps de vol ainsi que le temps de vol correspondant.

Exemple 2.1. Si N = 4, nous avons les temps de vol suivant

(a) le temps de vol de k = 1 vaut 0,

(b) le temps de vol de k = 2 vaut 1,

3

(c) le temps de vols de k = 3 vaut 7,

(d) le temps de vol de k = 4 vaut 2.

Le programme Maximum(4) doit alors renvoyer le couple (3, 7).

Exercice 4. Considérons la suite géométrique de premier terme u0 = 1

3et de raison q = 2.

1. Quelle est la forme explicite de cette suite ?

2. Compléter la fonction seuil ci-dessous qui détermine le plus petit entier n pour lequelun ≥ 1000.

4