読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Project Euler Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

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

http://projecteuler.net/problem=17

 

1から1000までの数を表す英単語の総文字数を求める問題。

----

def number_to_word(num):
    if num == 1:
        return len("one")
    elif num == 2:
        return len("two")
    elif num == 3:
        return len("three")
    elif num == 4:
        return len("four")
    elif num == 5:
        return len("five")
    elif num == 6:
        return len("six")
    elif num == 7:
        return len("seven")
    elif num == 8:
        return len("eight")
    elif num == 9:
        return len("nine")

    elif num == 10:
        return len("ten")
    elif num == 11:
        return len("eleven")
    elif num == 12:
        return len("twelve")
    elif num == 13:
        return len("thirteen")
    elif num == 14:
        return len("fourteen")
    elif num == 15:
        return len("fifteen")
    elif num == 16:
        return len("sixteen")
    elif num == 17:
        return len("seventeen")
    elif num == 18:
        return len("eighteen")
    elif num == 19:
        return len("nineteen")

    elif num == 20:
        return len("twenty")
    elif num == 30:
        return len("thirty")
    elif num == 40:
        return len("forty")
    elif num == 50:
        return len("fifty")
    elif num == 60:
        return len("sixty")
    elif num == 70:
        return len("seventy")
    elif num == 80:
        return len("eighty")
    elif num == 90:
        return len("ninety")
    elif num == 100:
        return len("hundredand")
    elif num == 1000:
        return len("onethousand")
    else:
        return 0

ans = 0
for word in xrange(1,1001):
    if len(str(word)) == 1:
        ans += number_to_word(word)
    elif len(str(word)) == 2:
        if word < 20:
            ans += number_to_word(word)
        else:
            ans += number_to_word(map(int,list(str(word)))[0]*10)
            ans += number_to_word(word - map(int,list(str(word)))[0]*10)
    elif len(str(word)) == 3:
        ans += number_to_word(map(int,list(str(word)))[0])
        ans += number_to_word(100)
        if map(int,list(str(word)))[1] == 0 and map(int,list(str(word)))[2]==0:
            ans -= 3
        tmp = word - map(int,list(str(word)))[0]*100
        if tmp < 20:
            ans += number_to_word(tmp)
        else:
            ans += number_to_word(map(int,list(str(tmp)))[0]*10)
            ans += number_to_word(tmp - map(int,list(str(tmp)))[0]*10)
    elif len(str(word)) == 4:
        ans += number_to_word(word)
    else:
        ans = ans
print ans
----

場合分けを落ち着いて行えば何とかなる。

まずは数の桁数で場合分け。2桁の場合は19以下と20以上では読み方が異なるので場合分け。3桁も同様に行うが間に"and"が入ったり入らなかったりするのでさらに場合分け…。

 

グラフ理論の定理では背理法と場合分けのみで証明できる定理がいくつかあるがその場合わけはこの比ではないと思う。