retour en arrière n escaliers au maximum k pas en un seul saut

Question

Vous devez monter un escalier à n degrés et vous décidez de faire un peu d'exercice en montant les marches. Vous pouvez couvrir au maximum k étapes dans un seul saut. Retourne toutes les séquences possibles de sauts que tu pourrais prendre pour monter l'escalier, triés.

Ma mise en œuvre me donne évidemment la mauvaise réponse.

def climbingStaircase(n, k): 
    final_res=[] 
    final_res.append(CSR(n,k,[])) 
    return final_res 

def CSR(n,k,res): 
    if n == 0: 
     return res   
    else: 
     for i in range(1,k+1): 
      if n-i>=0: 
       res.append(i) 
       n=n-i 
       res=CSR(n,i,res) 
     return res 

Pour n = 4 et k = 2, la sortie doit être

[[1, 1, 1, 1], 
[1, 1, 2], 
[1, 2, 1], 
[2, 1, 1], 
[2, 2]] 

sortie actuelle:

[[1,1,1,1,2,1]] 

Quelqu'un peut-il indiquer quelle partie je suis absent?

Answer 1

Un énorme problème est dans le code ci-dessous: vous déduisez la quantité d'étapes pour chaque possibilité dans la plage d'étapes.

n=n-i 
res=CSR(n,i,res) 

Lorsque vous avez terminé d'explorer ce que vous pouvez faire avec un saut 1 étape, vous devez backtrack et essayez de la même point de départ (valeur d'origine de n de cette instance) avec un 2 saut d'étape. Modifiez le code à:

res = CSR(n-i, i, res) 

Cela permet de maintenir intact valeur n que vous passez par la boucle.

En outre, vous ne pouvez pas limiter les futurs sauts au maximum de ce que vous venez de prendre. Changer ce deuxième paramètre, aussi:

res = CSR(n-i, k, res) 

Cela devrait vous aider à bouger. Essayez également ce joli blog debug pour obtenir de l'aide. Au moins insérer une ou deux instructions de suivi, telles que

print n, k, res 

en haut de votre routine.

CAVEAT

Ce n'est pas tous vos problèmes. Le plus gros problème restant est que CSR renvoie une seule solution: chaque étape que vous prenez est ajoutée à la liste . Vous avez besoin d'un moyen de rassembler les solutions complétées sous forme de listes séparées; le append en climbingStaircase est exécuté une seule fois, après CSR est entièrement terminé.

Vous devez reconnaître une solution terminée à n==0.

DEBUGGING AIDE

Voici une version de votre programme avec les paramètres de récursion fixes, et des traces de débogage insérés.

indent = "" 

def climbingStaircase(n, k): 
    final_res = [] 
    final_res.append(CSR(n, k, [])) 
    return final_res 

def CSR(n, k, res): 
    global indent 
    indent += " " 
    print indent, n, k, res 
    if n == 0: 
     print "SOLUTION", res 
    else: 
     for i in range(1, k+1): 
      if n-i >= 0: 
       CSR(n-i, k, res + [i]) 
    indent = indent[:-2] 

print climbingStaircase(4, 2) 

Notez l'utilisation de "indent" pour aider à visualiser votre récursion et retour arrière.La partie critique ici est que, au lieu de mettre à jour res globalement, je l'ai laissé comme une variable locale. J'ai également retiré la valeur de retour pour l'instant, tout simplement dumping pour sortir les solutions comme ils sont trouvés. Vous pouvez voir comment cela fonctionne:

4 2 [] 
    3 2 [1] 
     2 2 [1, 1] 
     1 2 [1, 1, 1] 
      0 2 [1, 1, 1, 1] 
SOLUTION [1, 1, 1, 1] 
     0 2 [1, 1, 2] 
SOLUTION [1, 1, 2] 
     1 2 [1, 2] 
     0 2 [1, 2, 1] 
SOLUTION [1, 2, 1] 
    2 2 [2] 
     1 2 [2, 1] 
     0 2 [2, 1, 1] 
SOLUTION [2, 1, 1] 
     0 2 [2, 2] 
SOLUTION [2, 2] 
[None] 

Avec ce genre de choses en place, je suis plein d'espoir que vous pouvez suivre votre logique et comprendre comment capturer la séquence de solutions à un niveau de votre choix.

Answer 2

La réponse de Prune a été implémentée avec succès.

def climbingStaircase(n, k): 
    res=[] 
    CSR(n,k,[],res) 
    return res 

def CSR(n,k,str_, res): 
    if n == 0: 
     res.append(str_) 
    else: 
     for i in range(1,k+1): 
      if n-i>=0: 
       CSR(n-i,k,str_+[i],res)