25/02/2009

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!


Tags:

cc-by-nc | code (python) | project euler


Project Euler : solution au problème 17, en Python (25/02/2009)Litanie contre la peur (23/02/2009)