Project Euler 019を解いてみる。「日曜日の数え上げ」
Project Euler 019
次の情報が与えられている.
1900年1月1日は月曜日である.
9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
2月は28日まであるが, うるう年のときは29日である.
うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.
20世紀(1901年1月1日から2000年12月31日)中に月の初めが日曜日になるのは何回あるか?
->次の問題
考え方
力技でやる方法とZellerの公式を用いる方法をやってみました。
設問的にZellerの公式を用いるのはちょっとずるいかな。
設問で1900年1月1日が月曜日と言っていて、数えるのは1901年1月からなのですが、勘違いして少しハマりました(;・∀・)
コード
def main():
"""
[日, 月, 火, 水, 木, 金, 土]で考える。
dayの合計が7で割り切れる場合は日曜日
:return:
"""
# 1月~12月の日数を入れたリストを作る
monthes_day_list = [31, ] * 13
monthes_day_list[0] = 0
monthes_day_list[2] = 28
monthes_day_list[4] = 30
monthes_day_list[6] = 30
monthes_day_list[9] = 30
monthes_day_list[11] = 30
# リストをコピー、2月を29日間にして閏年のリストを作る
leap_monthes_day_list = monthes_day_list.copy()
leap_monthes_day_list[2] = 29
# それぞれの月より前までの日数を合計したリストを作る(その月の1日より以前に何日あるか)
monthes_day_list = [sum(monthes_day_list[:i]) for i in range(1, len(monthes_day_list) + 1)]
leap_monthes_day_list = [sum(leap_monthes_day_list[:i]) for i in range(1, len(leap_monthes_day_list) + 1)]
day = 1 # 1900年1月1日は月曜日から開始
day = (day + 365) % 7 # 数えるのは1901年からなので365日すすめる。1901年1月1日は火曜日。
answer = 0
# 1901年から2000年までループで回す。
for year in range(1901, 2001):
temp_monthes_day_list = []
# 閏年なら閏年のリストを使う
if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
temp_monthes_day_list = leap_monthes_day_list
else:
temp_monthes_day_list = monthes_day_list
# その年の初めの曜日(0~6)にそれぞれの月の初めまでの日数を足し、割り切れる(=日曜日)の数をカウント
answer += sum([((monthes_day + day) % 7 == 0) for monthes_day in temp_monthes_day_list][:-1])
day += temp_monthes_day_list[-1]
# 次の年の初めの曜日を出す
day = day % 7
print(answer)
if __name__ == '__main__':
from time import time as t
st = t()
main()
print(t() - st, 'sec')
paizaにて実行
結果
171
0.0001633167266845703 sec
Zellerの公式を用いる方法
使ったのはこの式です。
コードに入れるならこっちで良かったですね。
$w = y + \lfloor y/4 \rfloor + \lfloor y/400 \rfloor - \lfloor y/100 \rfloor + ( ( 13 * m + 8 ) / 5 + d ) \mod 7 $
コード
def main():
answer = 0
for year in range(1901, 2001): # 1901年~2000年
for month in range(1, 13): # 1月~12月
if weekday(year, month, 1) == 1: # 各年・月の1日の曜日が日曜(1)に一致すれば
answer += 1 # 答えのカウントに+1
print(answer)
def weekday(year: int, month: int, day: int):
"""
Zellerの公式を用いて曜日を判定する関数
[0:土, 1:日, 2:月, 3:火, 4:水, 5:木, 6:金]に対応
:param year:
:param month:
:param day:
:return:
"""
if month <= 2: # 1月・2月は前年の13月・14月として計算する
month += 12
year -= 1
j = year // 100 # jはyearの上2桁
k = year % 100 # kはyearの下2桁
h = (day + int(2.6 * (month + 1)) + k + int(k / 4) + int(j / 4) - 2 * j) % 7
return h
if __name__ == '__main__':
from time import time as t
st = t()
main()
print(t() - st, 'sec')
paizaにて実行
結果
171
0.0006840229034423828 sec
こっちのほうがスッキリしていいですね。
Author And Source
この問題について(Project Euler 019を解いてみる。「日曜日の数え上げ」), 我々は、より多くの情報をここで見つけました https://qiita.com/radiol/items/bdfa88f68bf946fb8f5a著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .