ÉNIGME JOYSTICK #130
Description
Ce code permet de résoudre l'énigme proposée dans le numéro
130 de Joystick (Octobre 2001) :
Une grenouille
doit gravir un escalier de 25 marches.
Sachant qu'elle peut à tout moment de son ascension, sauter 1 ou 2 marches
en même temps, combien a-t-elle alors de possibilités de le monter
?
Méthode
1 : A La Barbare
La méthode
la plus bourrine, qui utilise à fond les capacités du CPU (chargé
à 100% pendant 30 secondes...)
C'est pas compliqué, on crée une fonction récurrente qui
teste toutes les possibilités :
A chaque appel de la fonction, la grenouille saute de 1 ou 2 barreaux, et ainsi
de suite jusqu'à ce que le nombre de barreaux soit égal à
25 (nombre total de barreaux).
A ce moment là le programme revient sur ses pas et teste une autre possibilité
Méthode
2 : A La Bogosse
Nettement
plus intéressante et plus RAPIDE !
Ingrédients : un peu de réflexion et connaissance de formules
de combinaisons
On considère les solutions comme une suite de "1" et de "2"
dont la somme fait 25
Cas
général
: Échelle à n barreaux
m = Nombre maximum de "2" = Partie entière(n/2)
Dans l'ensemble des combinaisons, il peut donc y avoir de 1 à m sauts
de 2 barreaux.
On répète l'opération suivante pour toutes les valeurs
entières (qu'on appellera Nbre2) de 1 jusqu'à m :
Pour chaque valeur
de Nbre2, on connaît le nombre de "1", le nombre de "2"
et le nombre de sauts faits par la grenouille... On peut donc calculer le nombre
de possibilités d'effectuer T sauts de 1 ou 2 barreaux dans le désordre
(Par exemple, si on a 3 sauts, dont 2 de 2 barreaux et 1 d'1 barreau, la grenouille
peut d'abord effectuer un saut de 2, puis un saut de 1, puis un saut de 2. Ou
bien elle peut effectuer deux fois de suite 2 sauts de 2 puis un saut de 1,
etc...)
Ce nombre de combinaisons est donné par la formule :
c = Factorielle(T) / ( Factorielle(Nbre1) * Factorielle(Nbre2) )
Et voilà
! Une fois qu'on a calculé c pour toutes les valeurs de Nbre2 ( de 1
à m ), il ne reste plus qu'à additionner toutes ces valeurs et
ajouter 1 (Cas ou la grenouille n'effectue que des sauts de 1)
Exemple
: Échelle de 5 marches, n = 5
m = Int(5/2) = 2
La grenouille pourra effectuer au maximum 2 sauts de 2 barreaux
On boucle pour Nbre2 = 1 jusqu'à m
Le nombre total
de combinaisons est donc égal à 4 + 3 + 1 = 8
Hop hop, maintenant amusez vous à calculer pour n = 25 ;-)
Ou utilisez le prog ça sera plus rapide !