Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

Escalier 17

Posté par
flight
15-07-19 à 20:02

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.

Posté par
lg124
re : Escalier 17 16-07-19 à 00:25

Bonsoir,

    a,b,c = 1,1,2
    for _ in range(17):
        a,b,c = b,c,a+b+c
    print(a) #19513


Pour un escalier à N marches avec des pas de [|1..m|], avec programmation dynamique


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]

Posté par
dpi
re : Escalier 17 16-07-19 à 07:54

Bonjour,

Une telle montée est-elle possible ?
1+2+3+1+2+3+1+3+2

Posté par
LittleFox
re : Escalier 17 16-07-19 à 08:24


Un exercice de programmation dynamique classique

 Cliquez pour afficher


J'ajoute un algorithme matriciel, plus efficace pour les très grands escaliers (mais de petites jambes ).

 Cliquez pour afficher


Le même algorithme en utilisant la librairie numpy "calculs scientifiques avec python"

 Cliquez pour afficher


Voilà voilà. C'est plutôt rare qu'on me demande explicitement du code

Posté par
LittleFox
re : Escalier 17 16-07-19 à 08:44


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 x^3 - x^2 - x - 1. Mais deux d'entre elles sont complexes.

En utilisant une approximation () on obtient :

 Cliquez pour afficher

Posté par
dpi
re : Escalier 17 16-07-19 à 12:59

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..............

 Cliquez pour afficher

Posté par
LittleFox
re : Escalier 17 16-07-19 à 15:37


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:

 Cliquez pour afficher


En utilisant tout ça, il est facile de calculer le nombre de façons de monter un escalier d'un million de marche. C'est ce nombre de 264651 chiffres
 Cliquez pour afficher

Posté par
flight
re : Escalier 17 16-07-19 à 16:06

bravo a ceux qui on trouvé 19513 :)

Posté par
derny
re : Escalier 17 17-07-19 à 08:56

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.

Posté par
dpi
re : Escalier 17 17-07-19 à 12:44

Posté par
carpediem
re : Escalier 17 17-07-19 à 14:13

salut

pour le fun :

flight @ 15-07-2019 à 20:02

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.
il n'y a qu'une seule façon de monter les 17 marches une par une
il n'y a aucune façon de monter les marches deux par deux uniquement  ou trois par trois uniquement car 17 n'est ni multiple de 2 ni multiple de 3 ...



 Cliquez pour afficher


à part ça je vois que les pro sont des ... pro ...mais auraient-ils l'amabilité de m'expliquer (pour le néophyte que je suis donc en terme "relativement simples) les lignes suivantes :

lg124 @ 16-07-2019 à 00:25

    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


LittleFox @ 16-07-2019 à 08:24

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


merci par avance

Posté par
LittleFox
re : Escalier 17 18-07-19 à 09:36

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)
    ...

La variable '_' va prendre les valeurs de 0 à 16. On aurait pu mettre n'importe quelle variable à la place de '_' mais par convention la variable '_' est une variable poubelle, on a pas besoin de sa valeur dans la boucle. C'est une manière standard en python de faire une boucle un certain nombre de fois.

if __name__ == "__main__":
    ... 


C'est un idiome standard pour dire "ici commence le programme". En fait __name__ va prendre le nom du module s'il est importé dans un import. S'il est lancé directement (python.exe script) alors __name__ prend la valeur "__main__" par convention.
C'est un peu l'équivalent de la fonction main en java, c, c++, ... qui va être appelée par convention quand on lance le programme.

En espérant que c'est plus clair.

Posté par
LittleFox
re : Escalier 17 18-07-19 à 09:40


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).

Posté par
carpediem
re : Escalier 17 18-07-19 à 13:08

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

Citation :
En fait __name__ va prendre le nom du module s'il est importé dans un import.
quand tu importes qu'est-ce que tu importes exactement ?

merci par avance


quant aux couleurs j'utilise les balises rouge/verte/bleu en dessous de ce cadre ... tout comme les autres balises de mise en forme

Posté par
LittleFox
re : Escalier 17 18-07-19 à 14:39


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é

Citation :
mais je ne comprends pas ce que tu appelles le module dans
Citation :

Citation :
En fait __name__ va prendre le nom du module s'il est importé dans un import.

quand tu importes qu'est-ce que tu importes exactement ?


Exemple, ce code dans l'interpréteur:

Citation :
>>> __name__
'__main__'
>>> import time
>>> time.__name__
'time'
>>> import time as tps
>>> tps.__name__
'time'
>>>


On voit que __name__  vaut '__main__' pour le code racine, celui qui est exécuté en premier. Par contre il vaut 'time' pour le module time car on l'a importé avec un import. Même si on a renommé localement le module avec as.

Avec un fichier test.py dans le dossier courant contenant:
Citation :

print(f"Test : mon nom est {__name__}")

if __name__ == "__main__":
    print("Je ne suis pas un module, je suis __main__ ")


Citation :
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>


On voit qu'on peux exécuter du code lorsqu'on lance un script et ne pas l'exécuté quand on import un script (qui devient un module).

Désolé pour ceux que python n'intéresse pas

Posté par
carpediem
re : Escalier 17 18-07-19 à 15:07

merci pour toutes ces info et le lien ... j'étudierai cela plus en détail plus tard



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !