3

几个小时前我发布了这个问题，但我想我删除了它！真的很抱歉...我正在研究 Project Euler 问题 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?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two)
contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of
"and" when writing out numbers is in compliance with British usage.
"""

import collections
import re


SMALLS =       [(0,     "zero"),
                (1,     "one"),
                (2,     "two"),
                (3,     "three"),
                (4,     "four"),
                (5,     "five"),
                (6,     "six"),
                (7,     "seven"),
                (8,     "eight"),
                (9,     "nine"),
                (10,    "ten"),
                (11,    "eleven"),
                (12,    "twelve"),
                (13,    "thirteen"),
                (14,    "fourteen"),
                (15,    "fifteen"),
                (16,    "sixteen"),
                (17,    "seventeen"),
                (18,    "eighteen"),
                (19,    "nineteen")]

MULTS_OF_TEN = [(20,    "twenty"),
                (30,    "thirty"),
                (40,    "forty"),
                (50,    "fifty"),
                (60,    "sixty"),
                (70,    "seventy"),
                (80,    "eighty"),
                (90,    "ninety")]

HUNDRED =      [(100,   "hundred")]

BIGS =         [(1000,  "thousand"),
                (10**6, "million"),
                (10**9, "billion")]

# other bigs: trillion, quadrillion, quintillion, sextillion, septillion, octillion, nonillion, decillion,
#             undecillion, duodecillion, tredecillion, quattuordecillion, quindecillion, sexdecillion,
#             septendecillion, octodecillion, novemdecillion, vigintillion

SMALLS = collections.OrderedDict(reversed(SMALLS))
MULTS_OF_TEN = collections.OrderedDict(reversed(MULTS_OF_TEN))
HUNDRED = collections.OrderedDict(reversed(HUNDRED))
BIGS = collections.OrderedDict(reversed(BIGS))


def int_to_words(num, follows_hundreds=False):
    """Retuns the text-equivelent of num, using recursion for distinct
    pieces.
    """
    def do_chunk(n,
                 num_text_map,
                 include_quotient=True,
                 is_hundreds=False):

        for x in num_text_map:
            quotient = n // x
            remainder = n % x

            if n == x: return num_text_map[x]

            if quotient and remainder:
                quotient_text = (int_to_words(quotient) + " " + num_text_map[x]) \
                                if include_quotient else \
                                (num_text_map[x])
                remainder_text = int_to_words(remainder, follows_hundreds=True) \
                                if is_hundreds else \
                                int_to_words(remainder)
                return quotient_text + " " + remainder_text

            elif quotient:
                quotient_text = (int_to_words(quotient) + " " + num_text_map[x]) \
                                if include_quotient else \
                                (num_text_map[x])
                return quotient_text

        return False

    result = do_chunk(num, BIGS)
    if result: return result

    result = do_chunk(num, HUNDRED, is_hundreds=True)
    if result: return result

    result = do_chunk(num, MULTS_OF_TEN, include_quotient=False)
    if result and follows_hundreds: return "and " + result
    if result: return result

    result = do_chunk(num, SMALLS)
    if result and follows_hundreds: return "and " + result
    if result: return result

def count_letters(string):
    looking_for = "[a-z]"
    instances = re.findall(looking_for, string)
    return len(instances)

def tally_letters(start, end):
    total_letters = 0
    for i in range(start, end + 1):
        total_letters += count_letters(int_to_words(i))
    return total_letters

这是程序的输出，与预期的解决方案进行比较。

>>> answer = tally_letters(1, 1000)
>>> assert answer == 21124
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    assert answer == 21124
AssertionError
>>> answer
1: 21118

让我感到困惑的是，我的差距为 6。提前感谢您的帮助。

4

1 回答 1

7

我想如果有人给我九个气球，然后再给我一个，我会说我有十个气球。另一方面，如果我有九十九个气球，然后我又收到一个，我会说“我有一百个气球”，而不是“我有一百个气球”：

>>> int_to_words(10)
'ten'
>>> int_to_words(100)
'hundred'
>>> int_to_words(1000)
'thousand'

len("one")*2 == 6.

于 2012-08-28T04:13:06.557 回答