É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 !

Télécharger la source du projet