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)
4 comments:
Bonjour !
J'ai également trouvé une formule permettant de trouver directement la somme des diagonales du carré de dimension n :
S = (4*n^3+3*n^2+8*n-9)/6.
Effectivement les résultats sont corrects, et la vitesse d'exécution est forcément plus rapide. Cependant j'avoue ne pas saisir le raisonnement derrière cette expression... c'est moi qui suis stupide ou le chemin est tordu? :-)
Bonjour,
Une autre formulation simple pour le carré de dim n (forcement impaire):
N = 3:2:n
S = 1 + sum(4*N.^2-6*(N-1))
On additionne :
1
9+7+5+3 = 3²*4 - (3-1)*(0+1+2+3)
a chaque sous-carré, on additionne le carré de la taille de la matrice, n² moins n-1 (coté haut gauche du sous carré), n² moins 2 fois n-1 (coté bas gauche) et n² moins 3 fois n-1 (côté bas droit).
Enregistrer un commentaire