Lucas Willems

LUCAS WILLEMS

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

English

Project Euler 19 : solution Python

Article

Voici un résumé de l'énoncé du problème 19 "Counting Sundays" du Project Euler (traduction complète en français ici) :

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000) ?

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de dimanches qui tombent le premier du mois dans tout le XXè siècle.

Pour résoudre ce problème, 2 méthodes existent (sûrement plus). La première est relativement simple et est réalisable sur Python, ce qui n'est pas le cas pour tous les langages : cette méthode consiste à lister toutes les dates qui correspondent à un premier du mois (01/01/1901, 01/02/1901, 01/03/1901...) et à demander à Python, en important au préalable la bibliothèque datetime, le jour de la semaine qui correspondait à cette date, permettant de compter facilement le nombre de dimanches.

La seconde méthode est plus compliquée, mais par contre est implémentable sur n'importe quel langage. Cette méthode consiste, non plus à trouver le jour de la semaine en fonction de la date, mais à trouver la date en fonction du jour de la semaine, c'est à dire que si nous savons que le 07/01/1900 est un dimanche (information donnée dans l'énoncé du problème), nous pouvons en déduire que le 14/01/1900, puis le 21/01/1900 et 28/01/1900 sont aussi des dimanches. En d'autres termes, si nous connaissons une date correspondant à un dimanche, ainsi que les différentes informations (fournies dans l'énoncé) au sujet des dates, alors nous pouvons trouver toutes les dates correspondant à un dimanche ou un autre jour de la semaine.

Dans notre cas, il nous faut donc, en partant du dimanche 07/01/1900, lister les dates de tous les dimanches postérieurs et regarder ceux qui tombent, durant le XXème siècle, un 1er du mois.

Le programme

Voici donc les programmes Python correspondant aux 2 méthodes et utilisables pour résoudre ce problème :

Il est clair que le 1er programme est bien plus simple et court que le second. Cela est dû au fait que Python possède nativement une fonction retournant le numéro du jour de la semaine en fonction d'une date, ce qui n'est pas le cas de tous les langages de programmation.

Le résultat

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

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.