Bonjour
un petit défit ; écrire un algo dans le langage de votre choix qui permet de trouver le nombre de façons de monter un escalier de 17 marches en montant les marches soit , une par une , soit par deux ou soit par trois uniquement.
Bonsoir,
a,b,c = 1,1,2
for _ in range(17):
a,b,c = b,c,a+b+c
print(a) #19513
def escalier2(N,m):
esc = [0]*(N+1)
esc[0] = esc[1] = 1
for i in range(2,N+1):
for j in range(1,min(i,m)+1):
esc[i] += esc[i-j]
return esc[N]
Un exercice de programmation dynamique classique
def escalier(nb_marches, pas):
""" Retourne le nombre de façons de monter un escalier avec nb_marches marches.
pas étant la liste des enjambées possibles """
facons = [1]
for marche in range(1, nb_marches + 1):
facons.append(0)
for marches in pas:
if marches <= marche:
facons[marche] += facons[marche-marches]
return facons[nb_marches]
if __name__ == "__main__":
print(escalier(17, (1, 2, 3))) # 19513
def escalier(nb_marches, pas):
""" Retourne le nombre de façons de monter un escalier avec nb_marches marches.
pas étant la liste des enjambées possibles """
m = max(pas)
# Creation de la matrice de transition
transition = [[0 for _ in range(m)] for _ in range(m)]
for marche in range(m-1):
transition[marche + 1][marche] = 1
for marche in pas:
transition[0][marche-1] = 1
# Exponentiation rapide de la matrice
def mul(A, B):
C = [[0 for j in range(len(B[0]))] for i in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
C[i][j] = sum(A[i][k]*B[k][j] for k in range(len(B)))
return C
def exp(A, e):
C = [[1 if i == j else 0 for j in range(len(A[0]))] for i in range(len(A))]
while e > 0:
if e&1 == 1:
C = mul(C,A)
e >>= 1
A = mul(A,A)
return C
return exp(transition, nb_marches)[0][0]
if __name__ == "__main__":
print(escalier(17, (1, 2, 3))) # 19513
import numpy as np
def escalier(nb_marches, pas):
""" Retourne le nombre de façons de monter un escalier avec nb_marches marches.
pas étant la liste des enjambées possibles """
m = max(pas)
# Creation de la matrice de transition
transition = np.zeros((m, m), dtype='object')
for marche in range(m-1):
transition[marche + 1][marche] = 1
for marche in pas:
transition[0][marche-1] = 1
return np.linalg.matrix_power(transition, nb_marches)[0][0]
if __name__ == "__main__":
print(escalier(17, (1, 2, 3))) # 19513
Notez qu'avec les enjambées données on retrouve la suite de Tribonacci. Celle-ci peut être calculée à partir des racines du polynôme . Mais deux d'entre elles sont complexes.
En utilisant une approximation () on obtient :
def escalier(nb_marches):
n = nb_marches + 2
a, b = (19 + 3 * 33**0.5)**(1/3), (19 - 3 * 33**0.5)**(1/3)
return int(3*((a+b+1)/3)**n/(a*a+b*b+4)+0.5)
if __name__ == "__main__":
print(escalier(17)) # 19513
Bonjour,
Il se trouve que j'ai un escalier de 17 marches que je montais une par une et peu
souvent deux par deux ,ce qui me donnait 2 solutions.....
Au vu des valeureux Littlefox et lg124 ,j'ai décidé de le monter en variant de 1à 3
chaque jour..............
En continuant sur les nombres de Tribonacci et la forme matricielle que j'ai utilisée plus haut on obtient une récurrence plus efficace:
def get_trib(n):
""" Return T(n), T(n-1) and T(n-2) where T(n) is the nth Tribonacci number """
if n == 0:
return (0, 0, 1)
t0, t1, t2 = get_trib(n//2)
a, b, c = t0*t0+t1*t1+2*t0*(t1+t2), t0*t0+t1*t1+2*t1*t2, t2*t2-t1*t1+2*t1*t0
if n%2 == 0:
return a, b, c
else:
return a+b+c, a, b
def escalier(nb_marches):
return get_trib(nb_marches+1)[0]
if __name__ == "__main__":
print(escalier(17)) # 19513
A dpi
Malgré ton âge et avec les progrès de la médecine tu peux peut-être arriver au bout. Le plus dur est de tenir la comptabilité de tous ces cas ! Bon courage.
salut
pour le fun :
a,b,c = 1,1,2
for _ in range(17): je ne comprends pas ce _
a,b,c = b,c,a+b+c
print(a) #19513
def escalier(nb_marches, pas):
""" Retourne le nombre de façons de monter un escalier avec nb_marches marches.
pas étant la liste des enjambées possibles """
facons = [1]
for marche in range(1, nb_marches + 1):
facons.append(0)
for marches in pas:
if marches <= marche:
facons[marche] += facons[marche-marches]
return facons[nb_marches]
if __name__ == "__main__": je ne comprends pas toute cette ligne
print(escalier(17, (1, 2, 3))) # 19513
carpediem tu maitrises mieux l'éditeur de texte de ce forum que moi, je ne sais pas comment tu as mis des couleurs mais je peux te répondre .
for _ in range(17)
...
if __name__ == "__main__":
...
Note que pour le main, j'aurais pu l'enlever et écrire directement les lignes suivantes mais elles auraient été exécutées à chaque fois et on aurait pas pu réutiliser la fonction escalier dans un autre programme via un import sans calculer et afficher la valeur de escalier(17).
LittleFox : merci pour ces explications ... je ne pensais pas qu'on puisse utiliser ce symbole _ tout seul : je me doutais bien qu'il jouait le rôle de la variable de boucle ... mais tout seul comme ça ...
effectivement on ne s'en sert pas dans la boucle ... mais si on avait du s'en servir devrait-on choisir un "vrai" nom ?
par exemple si dans la boucle on avait a = a + _ pourrait-on le faire ?
quant au deuxième truc ok : je voyais souvent cela et je ne comprenais pas le principe ...
mais je ne comprends pas ce que tu appelles le module dans
Ah tiens, oui hahaha
Pour le a = a + _, oui tu peux le faire mais ce n'est pas très conventionnel et pas très lisible. De plus '_' au début où à la fin d'un identifiant a différentes significations associées mais là on rentre dans du python avancé
>>> __name__
'__main__'
>>> import time
>>> time.__name__
'time'
>>> import time as tps
>>> tps.__name__
'time'
>>>
print(f"Test : mon nom est {__name__}")
if __name__ == "__main__":
print("Je ne suis pas un module, je suis __main__ ")
PS D:\Projects> python3
Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import test
Test : mon nom est test
>>> ^Z
PS D:\Projects> python3 test.py
Test : mon nom est __main__
Je ne suis pas un module, je suis __main__
PS D:\Projects>
Vous devez être connecté pour poster :
Connexion / Inscription Poster un nouveau sujetVous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :