Задача
Если записать числа от 1 до 5 английскими словами (one, two, three, four, five), то используется всего 3 + 3 + 5 + 4 + 4 = 19 букв.
Сколько букв понадобится для записи всех чисел от 1 до 1000 (one thousand) включительно?
Примечание: Не считайте пробелы и дефисы. Например, число 342 (three hundred and forty-two) состоит из 23 букв, число 115 (one hundred and fifteen) - из 20 букв. Использование "and" при записи чисел соответствует правилам британского английского.
Решение
Посчитаем всё в группах, которые можно комбинировать друг с другом.
Счёт от 1 до 9 назовём sum_1_9.
Затем считаем от 10 до 19. Назовём это sum_10_19.
Затем считаем десятками: 20, 30, 40, ..., 90. Назовём это sum_20_90.
В каждом десятке повторяется sum_1_9: 21, 22, ..., 29; 31, 32, ..., 39; ...; 91, 92, ..., 99. Всего повторений: sum_1_9 * 8
В каждом десятке также по 10 раз повторяется название десятка: sum_20_90 * 10
Считаем сумму от 1 до 99:
sum_1_9 + sum_10_19 + sum_20_90 * 10 + sum_1_9 * 8
Назовём её sum_1_99.
Чтобы досчитать до 1000, нужно sum_1_99 повторить 10 раз.
Осталось только прибавить названия сотен и тысячи. Числительные 1..9 перед словом "сотня" повторяются по 100 раз каждое, значит прибавляем сумму sum_1_9 100 раз. Прибавляем сумму повторов самих слов "сотня", союз "и", и наконец "одна тысяча".
Длину слов можно посчитать заранее. В языке C строка заканчивается нулевым байтом, поэтому чтобы узнать длину, нужно перебирать все символы строки до нулевого байта. Стоимость такой операции O(N). В других языках длина строки хранится в её начале, поэтому стоимость её получения O(1).
В данном случае я всё-таки считаю длину строк средствами C, так как это нужно только один раз.
И вышеописанный подсчёт:
Ссылка на онлайн-компилятор языка C с текстом программы
Что не так с решением?
Оно рассчитано на конкретные условия задачи. Так как оно даёт правильный ответ, то нет проблем. Но можно ли адаптировать данное решение для произвольного числа?
Конечно, можно. Базовыми единицами счёта здесь являются sum_1_9 и sum_1_99. Для манипуляций с тысячами можно посчитать сумму sum_1_999 (собственно, она уже посчитана). Количество повторений той или иной суммы легко вывести, разгруппировав число на тысячи, сотни, десятки и хвост от 1 до 19. Придётся изменить только подсчёт хвоста, который может быть неполным, и подсчёт префиксов перед сотнями и тысячами. Там должны быть индивидуальные суммы для каждого случая от 1 до 19. Их нужно посчитать заранее и хранить в массиве, далее брать из массива по индексу.
Подборка всех задач: