Project Euler : solution au problème 16, en Python
Le problème 16 est un petit coquin, qui ressort le joker récurrent des problèmes de Project Euler: la très grande dimension du problème. En soi la question est bête comme chou: il s'agit de calculer la somme des chiffres d'une nombre.
Facile! On voit d'elle-même sortir la boucle du genre:
tant que nombre > base:
somme = somme + nombre mod base
nombre = nombre div base
D'ailleurs j'ai commencé par implémenter cet algorithme somme toute fort naturel. Je le teste sur l'exemple (2^15), il fonctionne bien, je l'applique au problème demandé. Et bardaf.
Faut dire que ce qu'on demande c'est de donner la somme des chiffres du nombre 2^1000. Pour ceux qui n'auraient pas suivi, 2^1000 est un grand nombre. Genre grand. Genre 302 chiffres. Genre les types de base s'étranglent un peu face à ce genre de grandes valeurs.
Donc il va falloir opérer de façon plus "école primaire", chiffre par chiffre.
En partant de ce principe-là:
2^n = 2 * 2^n-1
= 2 * 2 * 2^n-2
= 2 * 2 * 2 * 2^n-3
= ...
= 2 * 2 * ... * 2 * 2
C'est bien la définition d'un exposant non?
Et:
2^n = 2^n-1 + 2^n-1
= (2^n-2 + 2^n-2) + (2^n-2 + 2^n-2)
= ...
= 2 + 2 + 2 + ... + 2 + 2 + 2
Donc mon algorithme commence par calculer 2^1000 par doubles successifs en partant de 2^1, en n'effectuant que des sommes, en gardant les chiffres dans une liste pour ne pas souffrir des problèmes de dimension; puis effectue le plus naïvement possible la somme de ces chiffres.
#! /usr/bin/env python
# 2009/02/24 - euler016.py
# Solution au Probleme 16 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=16
# Jean Karim Bockstael - jkb@jkbockstael.be
def sumofdigits(num):
sum = 0
for i in range(0, len(num)):
sum = sum + num[i]
return sum
def doubleof(num):
sum = []
carry = 0
for i in range(len(num) - 1, -1, -1):
tmp = (num[i] * 2) + carry
lastdigit = tmp % 10
carry = (tmp - lastdigit) / 10
sum = [lastdigit] + sum
if carry != 0:
sum = [carry] + sum
return sum
def euler16(expo):
bignum = [2]
for i in range(1, expo):
bignum = doubleof(bignum)
return sumofdigits(bignum)
print euler16(1000)
Et un joli résultat en 3 secondes!