Voila je vais vous exposer mon problème .

Imaginons que vous ayez un escalier devant vous et que vous ne puissiez le monter d'une marche par une marche ou sauter 2 marches etc ...

Par exemple pour 3 marches vous aurez 3 possibilité : faire les marches une par une ; une marche puis un bon pour sauter les 2 marches restantes ; un bon pour sauter 2 marches puis une marche simple .

Donc voila je cherche des idées d'hypothese pour savoir combien y aurait-il de possibilité pour 4 marches 5 marches ou meme 19 marches mais sans qu'on ai à compter ou faire un quelconque schemas

Vous pouvez me dire toutes vos idées qui vous passe par la tete meme si sa vous parait faux .

Je cherche le chemin

Le mot exact est algorithme

Y'a toujours la possibilité de tout monter 1 par 1.

Ensuite pour 2 marches et plus, si on a le droit de faire qu'un seul saut de 2, y'a n-1 possibilités de placer le saut ( si n marches ), il restera ensuite n-2 marches à monter 1 par 1

Si on veut placer 2 sauts c'est plus compliqué...
Il ne faut pas que les 2 sauts soient au même endroit ( logique ) et il ne faut pas que les 2 sauts se superposent. Par contre je peut te dire que pour n marches, si on fait 2 sauts, il restera n-4 marches à monter en 1 par 1

Ainsi de suite pour la suite, si 3 sauts: n-6 etc

En fait le nombre de possibilités que tu cherches est égal au nombre des différentes façon de placer le saut.

En prenant en compte que pas de saut=Une possibilité

Non justement le pas de saut ne compte pas dans ma démarche

on a le droit de faire le nombre de saut que l'on veut et de monter la marche partout .

Ouè ouè je comprend bien, mais faut décomposer le problème

Pour n marches, tu peux faire n/2 sauts au maximum si n est pair ou n/2-1 si n est impair.

Il faut donc faire tout les cas, il faut voir pour un nombre de sauts donnée, pour un nombre de marches donné, comment tu peux organiser ces sauts

Houla sa me parait compliquer quand meme cette histoire

1 marche = 1 possibilité

2 marches = 2 possibilités

3 marches = 3 possibilités

4 marches = 5 possibilités
(1= 1 par 1
2= 2 par 2
3= 2 puis 1 puis 1
4= 1 puis 1 puis 2
5= 1 puis 2 puis 1)

5 marches = 8 possibilités
(1= 1 par 1
2= 2 puis 2 puis 1
3= 1 puis 2 puis 2
4= 1 puis 2 puis 1 puis 1
5= 1 puis 1 puis 2 puis 1
6= 1 puis 1 puis 1 puis 2
7= 2 puis 1 puis 1 puis 1
8= 2 puis 1 puis 2)

6 marches = 13 possibilités
(1= 1 par 1
2= 2 par 2
3= 1 puis 1 puis 2 puis 2
4= 1 puis 2 puis 1 puis 2
5= 1 puis 2 puis 2 puis 1
6= 2 puis 2 puis 1 puis 1
7= 2 puis 1 puis 2 puis 1
8= 2 puis 1 puis 1 puis 2
9= 1 puis 1 puis 1 puis 1 puis 2
10= 1 puis 1 puis 1 puis 2 puis 1
11= 1 puis 1 puis 2 puis 1 puis 1
12= 1 puis 2 puis 1 puis 1 puis 1
13= 2 puis 1 puis 1 puis 1 puis 1)

On dirait une suite de Fibonacci, mais je suis pas sûr, j'ai pu oublier des possibilités

Polynome de Tchebitchev

Ca n'a rien à voir avec un algorithme. Tout ce dont on a besoin, c'est de renifler par des moyens plus ou moins conventionnels la formule générale, puis de la démontrer par récurrence.

Si on regarde les petits valeurs que Yaggo a justement calculé :
1->1
2->2
3->3
4->5
5->8
6->13

Effectivement, la suite de Fibo saute aux yeux, on va donc montrer que U_n+2=U_n+1+U_n avec U_n le nombre de possibilités pour n marches.
Finalement, on oublie la réccurence pour ce cas particulier : on va simplement considérer un escalier possédant n+2 marches. On a alors deux cas : soit on arrive tout en haut en gravissant une marche, soit on arrive tout en haut en gravissant 2 marches. Si c'est le premier cas, on a avant gravi n+1 marches, ce qu'on a pu faire de U_n+1 manières distinctes, et si c'est le second cas, on a gravi n marches, donc U_n manières distinctes. D'où notre résultat.