Реферат: Программирование различных типов задач
Рассмотрим искомое равенство:
n = a1 + a2 + ... + am ,
где каждый ai состоит только из цифр 0 и k .
Разделим обе части на k . Понятно, что при этом в числах ai все цифры k заменятся на единицы, а нули останутся нулями.
Получается новая формулировка задачи: представить число n / k как сумму чисел, состоящих только из цифр 0 и 1. Утверждается, что ответ на нее таков: минимальное количество слагаемых равно максимальной цифре в десятичной записи числа n / k .
Докажем сначала, что меньшим числом слагаемых обойтись нельзя. Будем действовать от противного: предположим, что можно обойтись меньшим числом слагаемых. При этом, так как максимальная цифра в n / k не превышает 9, то мы предполагаем, что можно обойтись не более чем восемью слагаемыми. Выпишем эти слагаемые друг под другом (даже если они бесконечные) и сложим «в столбик». При этом переносов не будет (все цифры 0 или 1, и цифр в каждом столбце не больше 8). Рассмотрим тот столбец, в котором при суммировании должна получиться максимальная цифра из десятичной записи n / k . Даже если во всех слагаемых в этом столбце стоят единицы, все равно нужная сумма не набирается. Получили противоречие; утверждение доказано.
Теперь, пожалуй, понятно, как добиться описанного выше ответа: надо просто в каждом столбце расставить столько единиц, сколько нужно получить в сумме – это соответствующая цифра из n / k .
Пример. Пусть n = 15, k = 7.
15/7 = 2,(142857)
Максимальная цифра — 8. Подберем соответствующие восемь слагаемых.
1,(111111)
1,(011111)
0,(010111)
0,(010111)
0,(000111) +
0,(000101)
0,(000101)
0,(000100)
----------
2,(142857)
Теперь умножим эти числа на 7, и получим следующее верное равенство:
15 = 7,(7) + 7,(077777) + 0,(070777) + 0,(070777) + 0,(000777) + 0,(000707) + 0,(000707) + 0,(000700)
Таким образом, правильное решение состоит из следующих этапов: представление числа n / k в удобном для обработки формате (с аккуратным учетом периода), составление искомых слагаемых и их вывод с учетом имеющихся требований.
Список используемой литературы:
1. Стивен С. Скиена, Мигель А. Ревилла Олимпиадные задачи по программированию, Москва Кудиц-Образ, 2005
2. Немнюгин С.А. TurboPascal, издательский дом «Питер», 2004