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. image 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! pe15.png

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

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

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]

Recommended Posts

Projet Euler15 "Chemin du treillis"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler 37
Projet Euler 7
Projet Euler 47
Projet Euler 4
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
Qu'est-ce que Project Euler 3 Acceleration?
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 10 "Somme des nombres premiers"
[Note] Projet Euler en Python (problème 1-22)
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs
Projet Euler # 3 "Maximum Prime Factors" en Python
Projet Euler # 11 "Produit maximum dans la grille" en Python
Projet Euler # 7 "1000 1er nombre premier" en Python
Projet Euler # 16 "Somme des pouvoirs" en Python
Projet Euler # 9 "Numéro spécial Pitagolas" en Python
J'ai écrit Project Euler 1 en une seule ligne.
Projet Euler # 2 "Even Fibonacci Number" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python