“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 4 — #14
i
i
i
i
i
i
i
i
4
1
• Introduction aux concepts de programmation
Cette définition est récursive parce que la factorielle de N est N fois la factorielle de
N-1. Essayons la fonction Fact :
{Browse {Fact 10}}
Ce code affiche 3628800 comme avant, ce qui nous confirme que Fact fait le bon
calcul. Essayons un argument plus grand :
{Browse {Fact 100}}
Un nombre énorme est affiché (que nous écrivons ici en groupes de cinq chiffres pour
améliorer la lisibilité) :
933 26215
44394 41526 81699 23885 62667 00490 71596 82643 81621 46859
29638 95217 59999 32299 15608 94146 39761 56518 28625 36979
20827 22375 82511 85210 91686 40000 00000 00000 00000 00000
C’est un exemple d’un calcul arithmétique avec une précision arbitraire, parfois appelée précision infinie, même si la précision n’est pas vraiment infinie. Elle est limitée
par la quantité de mémoire dans votre système. Un ordinateur personnel avec 1 Go de
mémoire peut traiter des entiers avec des centaines de milliers de chiffres.
Le lecteur sceptique se posera la question : ce nombre énorme est-il vraiment
la factorielle de 100 ? Comment le saurait-on ? Faire le calcul à la main sera long
et donnera probablement un résultat erroné. Nous verrons plus tard comment nous
pouvons avoir confiance dans le système.
Les combinaisons
Écrivons une fonction qui calcule le nombre de combinaisons de k objets pris dans un
ensemble de n objets. C’est aussi le nombre de sous-ensembles de taille k pris dans un
ensemble de taille n. On l’écrit
n
k
ou C
k
n en notation mathématique. Nous pouvons
définir cette opération avec la factorielle :
n
k
=
n!
k! (n − k)!
ce qui nous amène de façon naturelle à la fonction suivante :
declare
fun {Comb N K}
{Fact N} div ({Fact K} * {Fact N-K})
end
Par exemple, {Comb 10 3} est 120, qui est le nombre de manières de prendre trois
objets d’un ensemble de dix. Ce n’est pas la définition la plus efficace de Comb, mais
c’est probablement la plus simple.
i
i
i
i
i
i
i
i
4
1
• Introduction aux concepts de programmation
Cette définition est récursive parce que la factorielle de N est N fois la factorielle de
N-1. Essayons la fonction Fact :
{Browse {Fact 10}}
Ce code affiche 3628800 comme avant, ce qui nous confirme que Fact fait le bon
calcul. Essayons un argument plus grand :
{Browse {Fact 100}}
Un nombre énorme est affiché (que nous écrivons ici en groupes de cinq chiffres pour
améliorer la lisibilité) :
933 26215
44394 41526 81699 23885 62667 00490 71596 82643 81621 46859
29638 95217 59999 32299 15608 94146 39761 56518 28625 36979
20827 22375 82511 85210 91686 40000 00000 00000 00000 00000
C’est un exemple d’un calcul arithmétique avec une précision arbitraire, parfois appelée précision infinie, même si la précision n’est pas vraiment infinie. Elle est limitée
par la quantité de mémoire dans votre système. Un ordinateur personnel avec 1 Go de
mémoire peut traiter des entiers avec des centaines de milliers de chiffres.
Le lecteur sceptique se posera la question : ce nombre énorme est-il vraiment
la factorielle de 100 ? Comment le saurait-on ? Faire le calcul à la main sera long
et donnera probablement un résultat erroné. Nous verrons plus tard comment nous
pouvons avoir confiance dans le système.
Les combinaisons
Écrivons une fonction qui calcule le nombre de combinaisons de k objets pris dans un
ensemble de n objets. C’est aussi le nombre de sous-ensembles de taille k pris dans un
ensemble de taille n. On l’écrit
n
k
ou C
k
n en notation mathématique. Nous pouvons
définir cette opération avec la factorielle :
n
k
=
n!
k! (n − k)!
ce qui nous amène de façon naturelle à la fonction suivante :
declare
fun {Comb N K}
{Fact N} div ({Fact K} * {Fact N-K})
end
Par exemple, {Comb 10 3} est 120, qui est le nombre de manières de prendre trois
objets d’un ensemble de dix. Ce n’est pas la définition la plus efficace de Comb, mais
c’est probablement la plus simple.