Suite de Fibonacci
La suite de Fibonacci célèbre en mathématiques est la suite des nombres entiers dans laquelle chaque terme est la somme des deux termes qui précèdent. Elle commence par 0 et 1.
En notant f0, f1 etc. les termes de cette suite, affichez toutes les valeurs jusqu'à fN où est N est un entier fourni.
Après avoir programmé votre solution, regardez celle proposée ci-contre.
Notez la façon commode d'affecter plusieurs variables dans une même instruction : u,v = ...
N.B. Pour simplifier, nous écrivons les solutions en donnant les entêtes en gras suivies immédiatement du corps de la fonction.
fibo (N:int);
var u,v = 0,1;
write "f0 = 0";
for var i=1 to N do
write "f" ++ i ++ " = " ++ v;
u,v = v,u+v
done
Calcul de factorielle
La factorielle d'un nombre entier naturel n est le produit des entiers allant de 1 à n. On l'écrit : n! Et on convient en particulier que 0! = 1
1. Définissez une fonction entière (dont le résultat est un entier) facto pour calculer la factorielle d'un nombre donné.
Notez dans la solution proposée l'opérateur composé *= qui permet de raccourcir l'écriture de l'affection,
res *= i étant équivalent à res = res * i
De la même façon, on dispose des opérateurs +=, -=, /= (pour la division) et quelques autres.
2. Rendez votre fonction plus robuste en vérifiant d'abord que l'argument donné est bien un entier naturel.
3. Jamais 2 sans 3 !
Cette 3ème version est l'occasion de présenter une démarche élégante couramment utilisée en informatique qui s'appelle la récursivité et qui consiste à définir une fonction en faisant appel à elle-même !
C'est un peu comme un serpent qui se mord la queue mais ça marche... sous certaines conditions toutefois qu'il faut bien respecter !
Dans le cas du calcul de factorielle, on exprime la relation suivante, vraie pour n>0 : n! = n * (n-1)!
Il est important avec cette démarche de bien prévoir une "condition d'arrêt", ici, le cas n==0 qui donne le résultat 1 (sans effectuer d'appel récursif).
Attention, une "boucle" est si vite arrivée quand on utilise la récursivité ! On a alors un programme qui ne sait pas s'arrêter et qui finit souvent par entraîner un plantage sévère.
Conseil : au cas où il vous arriverait de tomber une telle boucle sans fin, vous pouvez ouvrir le Gestionnaire de tâches Windows (accessible par Ctrl+Alt+Suppr) et interrompre la tâche Java.
Voyez ci-contre la solution jolie et concise que cela donne. (On vous laisse toutefois ajouter le test de robustesse comme en 2.)
facto (n:int):int
var res : int = 1;
for var i=2 to n do
res *= i
done;
res
facto (n:int):int
var res : int;
if n<0 then
write "Attention facto n'est définie que pour les nombres entiers naturels !"
else
res = 1;
for var i=2 to n do
res *= i
done
fi;
res
facto (n:int):int
if n<=1 then
1
else
n * facto(n-1)
fi
Calcul du pgcd
Le PGCD est le plus grand commun diviseur de deux nombres entiers naturels non nuls c'est-à-dire le plus grand entier naturel qui les divise tous les deux.
1. L'une des méthodes de calcul du pgcd de deux nombres a et b consiste à procéder par soustractions : tant que a et b sont différents, on remplace le plus grand des deux nombres par leur différence et on continue.
Ecrit de façon récursive, cela donne la solution ci-contre.
2. Mais l'algorithme d'Euclide qui utilise la division euclidienne des deux nombres converge beaucoup plus rapidement (en effectuant moins d'appels récursifs). A chaque pas, on prend le reste de la division plutôt que la différence des deux nombres.
A noter dans la solution proposée la notation '%' pour obtenir le reste de la division euclidienne. L'opérateur correspondant (non utilisé ici) donnant le quotient euclidien est noté '//'.
pgcd (a:int, b:int):int
if a==b then
a
elif a<b then
pgcd(a,b-a)
else
pgcd(a-b,b)
fi
pgcd (a:int, b:int):int
if a==0 then
b
elif b==0 then
a
elif a<b then
pgcd(a,b%a)
else
pgcd(a%b,b)
fi
Nombre premier
Vous le savez, on appelle nombre premier tout nombre entier naturel qui admet exactement deux diviseurs, ces diviseurs étant 1 et le nombre considéré. Les nombres premiers sont donc : 2, 3, 5, 7, 11 etc.
Cet exercice est simple : il s'agit de déterminer si un nombre donné est premier. Pour cela, on peut simplement essayer de diviser le nombre donné par tous les nombres compris entre 2 et la racine carrée de celui-ci. Si on trouve un diviseur, au moins, alors le nombre n'est pas premier. Si on n'en trouve aucun, alors il est premier.
La solution ci-contre nous donne pour la première fois à utiliser une variable booléenne qui représentera le résultat attendu : true si le nombre est premier, false sinon. La fonction premier définie est elle-même booléenne puisqu'elle rend un résultat de ce type.
L'itération (boucle "for") s'arrête à Math.round(Math.sqrt(n)), l'entier le plus proche de la racine carrée de n. En effet, si le nombre a un diviseur supérieur à sa racine carrée alors il en possède également un inférieur qu'on trouvera donc.
Avant l'itération, la variable résultat prem est positionnée à true et dès qu'on trouve un diviseur (pour lequel le reste de la division donne 0), s'il y a en a un, cette variable passe à false. Dès lors, il n'est pas nécessaire de continuer à chercher. C'est à cela que sert la nouvelle instruction break qui permet de sortir immédiatement de la boucle avant d'avoir atteint la valeur de fin de l'indice de boucle.
Une fois définie cette fonction premier, on peut par exemple dresser la liste de tous les nombres premiers inférieurs à 100 par la commande :
-
for var i=1 to 100 do
if premier(i) then write i fi
done
premier (n:int):bool
var prem:bool = false;
if n>1 then
prem = true;
for var d=2 to Math.round(Math.sqrt(n)) do
if (n%d == 0) then
prem = false;
break
fi
done
fi;
prem