“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 22 — #32
i
i
i
i
i
i
i
i
22
1
• Introduction aux concepts de programmation
temps
C={NewCell 0}
I=@C
J=@C
C:=I+1
(C contient 1)
(C contient 1)
(I égal 0)
(J égal 0)
(C contient 0)
C:=J+1
Figure 1.5 Une exécution possible du deuxième exemple non-déterministe.
1.15 EXERCICES
➤ Exercice 1 — Une calculatrice
La section 1.1 montre comment utiliser le Labo interactif et le système Mozart
comme une calculatrice. Explorons les possibilités :
a) Calculez la valeur exacte de 2
100 sans utiliser de fonctions. Essayez d’utiliser
des raccourcis pour éviter de taper cent fois le chiffre 2 dans la formule
2 * 2 * 2 * ... * 2.
Indice : Utilisez des variables pour garder les résultats intermédiaires.
b) Calculez la valeur exacte de 100! sans utiliser de fonctions. Des raccourcis
sont-ils possibles ?
➤ Exercice 2 — Le calcul des combinaisons
La section 1.3 définit la fonction Comb qui calcule les combinaisons. Cette
fonction n’est pas très efficace parce qu’elle demande parfois le calcul de grandes
factorielles.
7 Le but de cet exercice est d’écrire une version plus efficace de
Comb.
a) Dans un premier temps, utilisez la définition suivante pour faire une fonction
plus efficace :
n
k
=
n × (n − 1) × · · · × (n − k + 1)
k × (k − 1) × · · · × 1
Calculez le numérateur et le dénominateur séparément et faites ensuite la
division. Vérifiez que le résultat est 1 quand k = 0.
b) Dans un deuxième temps, utilisez l’identité suivante :
n
k
=
n
n − k
7. Par contre, elle a le grand avantage de toujours donner la bonne réponse ! C’est parce que dans notre
modèle les entiers sont de vrais entiers à cause de l’arithmétique qui se fait avec une précision arbitraire.
On ne peut pas en dire autant pour la même fonction en Java, parce que le type int en Java n’est pas un
vrai entier (c’est un entier modulo 2
32 , ce qui est bien plus compliqué). Il y a une leçon à retenir de cet
exemple : les abstractions (comme les entiers) doivent être simples.
i
i
i
i
i
i
i
i
22
1
• Introduction aux concepts de programmation
temps
C={NewCell 0}
I=@C
J=@C
C:=I+1
(C contient 1)
(C contient 1)
(I égal 0)
(J égal 0)
(C contient 0)
C:=J+1
Figure 1.5 Une exécution possible du deuxième exemple non-déterministe.
1.15 EXERCICES
➤ Exercice 1 — Une calculatrice
La section 1.1 montre comment utiliser le Labo interactif et le système Mozart
comme une calculatrice. Explorons les possibilités :
a) Calculez la valeur exacte de 2
100 sans utiliser de fonctions. Essayez d’utiliser
des raccourcis pour éviter de taper cent fois le chiffre 2 dans la formule
2 * 2 * 2 * ... * 2.
Indice : Utilisez des variables pour garder les résultats intermédiaires.
b) Calculez la valeur exacte de 100! sans utiliser de fonctions. Des raccourcis
sont-ils possibles ?
➤ Exercice 2 — Le calcul des combinaisons
La section 1.3 définit la fonction Comb qui calcule les combinaisons. Cette
fonction n’est pas très efficace parce qu’elle demande parfois le calcul de grandes
factorielles.
7 Le but de cet exercice est d’écrire une version plus efficace de
Comb.
a) Dans un premier temps, utilisez la définition suivante pour faire une fonction
plus efficace :
n
k
=
n × (n − 1) × · · · × (n − k + 1)
k × (k − 1) × · · · × 1
Calculez le numérateur et le dénominateur séparément et faites ensuite la
division. Vérifiez que le résultat est 1 quand k = 0.
b) Dans un deuxième temps, utilisez l’identité suivante :
n
k
=
n
n − k
7. Par contre, elle a le grand avantage de toujours donner la bonne réponse ! C’est parce que dans notre
modèle les entiers sont de vrais entiers à cause de l’arithmétique qui se fait avec une précision arbitraire.
On ne peut pas en dire autant pour la même fonction en Java, parce que le type int en Java n’est pas un
vrai entier (c’est un entier modulo 2
32 , ce qui est bien plus compliqué). Il y a une leçon à retenir de cet
exemple : les abstractions (comme les entiers) doivent être simples.