Projet Euler15 "Chemin du treillis"

problème

Si vous partez du coin supérieur gauche du carré 2x2, il y a 6 itinéraires qui vont en bas à droite sans faire demi-tour. Alors, combien d'itinéraires y a-t-il dans le carré 20 × 20? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

Politique de réponse 1

Le nombre de combinaisons est également requis, mais je veux essayer un autre algorithme car c'est un gros problème. Le nombre de distances d'un certain carré au but est égal à la somme du nombre de distances au but de chacun des deux carrés dans la direction de déplacement adjacente au carré. → Il n'y a pas d'autre choix que de revenir!

Code 1

def f(L,a,b):
  if not L[a][b]:
    if a == len(L)-1 or b == len(L)-1:
      L[a][b] = 1
    else:
      L[a][b] = f(L,a+1,b) + f(L,a,b+1)
  return L[a][b]

def main():
  #(x,y) = (2,2)
  (x,y) = (20,20)
  L = [[0 for i in range(0,y+1)] for j in range(i,x+1)]
  ans = f(L,0,0)
  #print ans

Politique de réponse 2

Lorsque j'ai cherché sur le Web, j'ai trouvé un moyen de trouver le nombre de chemins à partir du point de départ, et non le nombre de chemins vers l'objectif, avec une instruction for. Je l'ai essayé, mais l'instruction for était beaucoup plus rapide. Après un peu de réflexion, cette méthode semble être plus efficace en tant qu'algorithme.

Comme c'est un gros problème, j'ai essayé de n'en trouver que la moitié en tenant compte de la symétrie.

Code 2

def g(L,a,b):
  if a == 0:
    return 1
  elif a == b:
    return L[a-1][b]*2
  else:
    return L[a-1][b]+L[a][b-1]
  
def main2():
  seq = range(21)
  L = [[0 for i in seq] for j in seq]
  
  for a in seq:
    for b in seq[a:]:
      L[a][b] = g(L,a,b)
  #print L[20][20]