26/06/2009
Project Euler: solution au problème 28, en Python
Ça faisait longtemps que je n'avais pas gratifié mon blog d'un des si particulièrement passionnants problèmes de Project Euler. Il était grand temps d'y remédier, donc voici une solution au problème 28.
L'idée est de remplir une grille carrée de nombres, de dimension impaire, qui est remplie des entiers successifs en spirale partant du centre et allant vers la droite et le bas. Aga? En gros, ayant ce genre de chose:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
La somme des éléments de deux diagonales de ce carré de dimension 5 vaut 101. Que vaut la somme pour un carré de dimension 1001?
Je vous avais présenté mon pote Récursion?
#! / usr/bin/python
# 2009/06/26 - euler028.py
# Solution au Probleme 28 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=28
# Jean Karim Bockstael - jkb@jkbockstael.be
def sum_of_diagonals(dimension):
if (dimension == 1):
return 1
else:
corner_tr = dimension ** 2
corner_tl = corner_tr - dimension + 1
corner_bl = corner_tl - dimension + 1
corner_br = corner_bl - dimension + 1
corner_sum = corner_tr + corner_tl + corner_bl + corner_br
return corner_sum + sum_of_diagonals(dimension - 2)
print sum_of_diagonals(1001)