Project Euler : solution au problème 15, en Python
Dans l'enchaînement, ou presque, une solution au problème 15. Le problème 15 est un peu effrayant puisqu'il a un énoncé du genre qui déroute à priori, à savoir "Il y a 6 chemins (sans retour en arrière) pour aller du coin supérieur gauche au coin inférieur droit dans une grille de 2x2; combien y a-t-il de chemins dans une grille de 20x20?".
Ouch.
Papier, crayon...
Sur une grille de dimension 1, il y a 2 chemins possibles. Sur une grille de dimension 2, il y a 6 chemins possibles. Sur une grille de dimension 3, il y a 20 chemins possibles. Sur une grille de dimension 4, il y a 70 chemins possibles (non je ne les ai pas énumérés sur papier ceux-là). ...
Ces valeurs ne sont forcément pas innocentes. Plus précisément, ce sont les valeurs centrales du triangle de Pascal, pour les lignes où "valeur centrale" a un sens.
Mon algorithme se base là-dessus.
#! /usr/bin/env python
# 2009/02/20 - euler015.py
# Solution au Probleme 15 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=15
# Jean Karim Bockstael - jkb@jkbockstael.be
def pascaltrirow(row):
if row == 1:
return [1]
else:
upper = pascaltrirow(row - 1)
current = [1]
for i in range(1, len(upper)):
current.append(upper[i] + upper[i - 1])
current.append(1)
return current
def pascaltricell(row, col):
currow = pascaltrirow(row)
return currow[col - 1]
def euler15(size):
centralvalue = pascaltricell((size * 2) + 1, size + 1)
return centralvalue
print euler15(20)