Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 17 : solution Python

Article

Voici un résumé de l'énoncé du problème 17 "Number letter counts" du Project Euler (traduction complète en français ici) :

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used ?

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de lettres à utiliser, sans compter les espaces et les tirets, pour écrire tous les nombres de 1 à 1000 en  mots.

Comme vous le savez, en français comme en anglais, pour écrire littéralement tous les nombres de 1 à 1000, il nous faut connaître les quelques mots qui les composent et qui sont :

Mais, en plus de connaître ces mots, il nous faut aussi savoir quand les utiliser. Voici donc les 4 conditions à suivre pour savoir de quoi sera composée l'écriture littérale d'un nombre \(n\) compris entre 1 et 1000 :

Maintenant que nous savons quels mots utiliser et quand les utiliser, passons au programme.

Le programme

Voici donc le programme Python que nous pouvons utiliser pour résoudre ce problème :

#Création des listes contenant les mots
unites = ['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
dizaines = ['twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']
autre = ['hundred', 'thousand', 'and']
resultat = 0
#Calcul du nombre de lettres à utiliser pour écrire les nombres de 1 à 1000
for i in range(1, 1001):
    #Stockage du chiffre des unités, dizaines, centaines, milliers dans des variables
    unite = i%10
    dizaine = (i//10)%10
    centaine = (i//100)%10
    millier = (i//1000)%10
    #Testes pour savoir à quelles conditions (vues plus haut dans l'article)
    #le nombre répond
    if millier != 0:
        resultat += len(unites[0]) + len(autre[1])
    if i%1000 != 0:
        if centaine != 0:
            resultat += len(unites[centaine-1]) + len(autre[0])
            if i%100 != 0:
                resultat += len(autre[2])
        if i%100 != 0:
            if dizaine < 2:
                resultat += len(unites[i%100-1])
            else:
                resultat += len(dizaines[dizaine-2])
                if unite != 0:
                    resultat += len(unites[unite-1])
print(resultat)

Le résultat

La réponse à ce problème est 21124.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.