qui calcule la racine carrée d'un nombre réel positif a par l'algorithme de Newton. Préciser bien le test d'arrêt de l'algorithme.
Principe : la suite

converge vers

3. Nombre de 1

Écrire la fonction
    nombreDeUn données n : entier positif ou nul
        résultat : entier
qui calcule le nombre de 1 dans l'écriture binaire de n.
Par exemple,
    nombreDeUn (23) }->
car 23 s'écrit 10111 en base 2

4. Qu'affichera ce programme ?

x\leftarrow1
Y\leftarrow1
tant que x \leq y faire
    afficher (x)
    x}\leftarrowx*
    y\leftarrowy + 10
fin tant que

5. Le triangle de Pascal

Le triangle de Pascal est un tableau qui se construit de la manière suivante :

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1

En convenant que les lignes et colonnes sont numérotées à partir de 1 , la ligne

contient

éléments (numérotés de 1 à

). L'élément 1 et l'élément

valent 1. L'élément

(avec

) est égal à la somme des éléments

de la ligne précédente.

Écrire la fonction suivante:

lignePascal données n :entier
    résultat t : liste d'entiers

qui range dans la liste

la ligne

du triangle de Pascal, et ce sans utiliser de matrice ou de tableau à deux dimensions.

6. Tri d'une liste à petit ensemble de valeurs

Le but de cet exercice est de trier une liste

dont les éléments ne peuvent prendre qu'un "petit" nombre fini de valeurs (ici, trois valeurs : 0,1 ou 2).

Par exemple, de la liste initiale:

2	0	1	0	2	1	1	0	1	2	2	1	0
1	2	3	4	5	6	7	8	9	10	11	12	13

il faut obtenir la liste finale :

0	0	0	0	1	1	1	1	1	2	2	2	2
1	2	3	4	5	6	7	8	9	10	11	12	13

Le programme sera itératif. Pour trouver comment écrire le corps de la boucle, on suppose que la liste

(de taille

) a été traitée jusqu'au rang

, et que sont connus

vérifiant

tous les éléments du tableau d'indice inférieur ou égal à sont égaux à 0
tous les éléments d'indice supérieur à et inférieur ou égal à sont égaux à 1
tous les éléments d'indice supérieur à et inférieur ou égal à sont égaux à 2.

Le prochain élément à traiter est

noté

En supposant (c'est à dire qu'il y a au moins un 0 , un 1 et un 2 placés), quelles sont les modifications à faire sur et si ? si ? si ?

Il se peut qu'il n'y ait pas encore de 0,1 ou 2 dans la partie de liste déjà triée. Il faut en tenir compte dans les modifications de

selon les valeurs de

Écrire le traitement complet de tri.

7. Génération de nombres pseudo-aléatoires

Dans son livre Seminumerical algorithms, The Art of Computer Programming, vol 2, (1969), Donald E . Knuth présente un algorithme de génération de nombres pseudo-aléatoires, basé sur la suite

où

est un nombre entier positif inférieur à 10000000000 et

une fonction entière à valeur entière de [0..9 999999 999] dans [0..9 999999 999]. Le calcul de

emploie 12 étapes différentes, répétées un nombre variable de fois, selon la valeur de

.
Ces 12 étapes sont les suivantes:
K1 : prendre le chiffre des milliards de

K2 : prendre le chiffre des centaines de millions de

.
K2 (3 456789 123)

K2 (2004)

K3 : si

000, ajouter 5000000000 à

K4 : élever

au carré, supprimer les cinq derniers chiffres, prendre les 10 derniers chiffres du résultat.

K4 (3 456789123 )

911, K4 (2004)

K5 : multiplier x par 1001001001 et prendre les 10 derniers chiffres du résultat
K5 (3 456789123 )

123, K5 (2004)

K6 : si

000, ajouter 9814055677 à

, sinon ôter

de 10000000000

K7 : permuter les 5 premiers chiffres de

avec les 5 derniers

    K7 (3 456789123 ) $\rightarrow 8912334$ 567, K7 (2004) $\rightarrow 200400000$
K8 : multiplier x par 1001001001 et prendre les 10 derniers chiffres du résultat ( $=$ K5)
    $\mathrm{K} 8(3456789123) \rightarrow 2368912$ 123, $\mathrm{K} 8(2004) \rightarrow 6006006004$
K9 : alors enlever 1 à tous les chiffres non nuls de $x$
    $\mathrm{K} 9(3456789123) \rightarrow 2345678$ 012, $\mathrm{K} 8(2004) \rightarrow 1003$
K10 : si $x<100000$ alors élever $x$ au carré et lui ajouter 99999 sinon ôter 99999 de $x$
    $\mathrm{K} 10(3456789123) \rightarrow 3456689124, \mathrm{~K} 10(2004) \rightarrow 4116015$
K11 : compléter $x$ par des 0 à droite pour qu'il ait 10 chiffres
    $\mathrm{K} 11(3456789123) \rightarrow 3456789123, \mathrm{~K} 11(2004) \rightarrow 2004000000$
K12 : multiplier $x$ par $x-1$, supprimer les cinq derniers chiffres, prendre les 10 derniers
chiffres du résultat
    $\mathrm{K} 12(3456789123) \rightarrow 3910374343, \mathrm{~K} 12(2004) \rightarrow 40$

L'algorithme

est le suivant :

Donnée x : entier
Résultat r : entier
début K
    a\leftarrowK1 (x)
    répéter a+1 fois
        b\leftarrowK2 (x)
        si b=0 alors r\leftarrowK12(K11(K10(K9(K8(K7(K6(K5(K4(K3(x)))))))))) fin si
        si b=1 alors r\leftarrowK12(K11(K10(K9(K8(K7(K6(K5(K4(x))))))))) fin si
        si b=2 alors r\leftarrowK12(K11(K10(K9(K8(K7(K6(K5(x)))))))) fin si
        si b=3 alors r\leftarrowK12(K11(K10(K9(K8(K7(K6(x))))))) fin si
        si b=4 alors r\leftarrowK12(K11(K10(K9(K8(K7(x)))))) fin si
        si b=5 alors r\leftarrowK12(K11(K10(K9(K8(x))))) fin si
        si b=6 alors r\leftarrowK12(K11(K10(K9(x)))) fin si
        si b=7 alors r\leftarrowK12(K11(K10(x))) fin si
        si b=8 alors r\leftarrowK12(K11(x)) fin si
        si b=9 alors r\leftarrowK12(x) fin si
    fin répéter
    retour r
fin K

Écrire les fonctions K1, K2, K3, K4, K5, K6, K7, K8, K9, K10, K11, K12
Écrire la fonction K

Note: on supposera que les entiers sont représentables sans limite de valeur.

8. Programmation d'expressions logiques

Les calculs des valeurs de vérité d'expressions comme

peuvent être programmés si

est un sous-ensemble fini de

une expression logique calculable pour toute valeur de

Programmer le calcul de la valeur de vérité des expressions suivantes:

modulo 4
modulo