Chemins brisés (problème de logique)

Ce problème a été publié sur le site Web de la Newton School, "Question du jour 9/jan/2023".

Énoncé du problème :

Newton veut atteindre le haut d'un escalier qui a des marches cassées (il ne peut pas visiter ces marches). Il peut monter 1 ou 2 marches à la fois.

Exemple d'un escalier de 15 marches avec les marches 3 et 9 cassées. Les pas valides à visiter sont : 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Une manière possible d'atteindre le sommet de cet escalier est de visiter les marches : 2,4,5,7,8,10,12,14,15 (parfois Newton a gravi 1 marche et d'autres il a gravi 2 marches).

L'objet du problème est de trouver le nombre de chemins différents que Newton peut atteindre en haut de l'escalier.

Ici, je montre une solution:

Ce problème rappelle la "Suite de Fibonacci". Mais pourquoi? Parce que puisque vous ne pouvez atteindre une étape qu'à partir de l'étape 1 ou de l'étape 2, le nombre de façons d'atteindre une étape est la somme des « façons d'atteindre l'étape 1 » + « façons d'atteindre l'étape 2 ». ”.

Ainsi, pour atteindre l'étape 1, vous n'avez qu'un seul chemin (monter du sol à l'étape 1) ; pour atteindre l'étape 2 vous avez 2 voies (monter du sol directement à l'étape 2 ou monter à partir de l'étape 1), pour atteindre l'étape 3 vous avez 3 voies (1 voie à partir de l'étape 1 + 2 voies à partir de l'étape 2), pour atteindre l'étape 4 vous avoir 5 voies (2 voies à partir de l'étape 2 + 3 voies à partir de l'étape 3), pour atteindre l'étape 5 vous avez 8 voies (3 voies à partir de l'étape 3 + 5 voies à partir de l'étape 4) et ainsi de suite jusqu'à la dernière étape.

Mais c'est exactement la suite de Fibonacci ! Oui, mais ce problème a une tournure, des "étapes cassées" ont été ajoutées. D'accord, pas de problème, puisque Newton ne peut pas visiter les marches cassées, définissez simplement 0 façons de les atteindre.

Revenons à notre exemple, avec les étapes 3 et 9 brisées, nous avons cette « Séquence brisée de Fibonacci » : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Donc, à cet escalier, Newton a 80 façons différentes de le monter.

Maintenant, vous pouvez implémenter l'algorithme de séquence brisée de Fibonacci dans votre langage de programmation préféré et le télécharger sur le site Web de la Newton School , qui contient de nombreux problèmes intéressants à résoudre lors de la session Question du jour.

Amusez-vous bien!