|
P.53.1.
Пояснение. Простым перебором мы не можем решить эту задачу, требуется слишком много вычислений. Упростим задачу. Если число кратно 18, то оно будет кратно 2 и 9. Поэтому, из критерия делимости мы можем исключить число 18. Аналогично, исключаем числа 16=2*8, 15=3*5, 14=2*7, 12=2*6, 10=2*5. Цифру 9 мы не можем исключить, поскольку тут требуется две тройки. Аналогично, мы не можем исключить цифру 8 и другие младшие цифры. Следовательно, нам нужно найти число, которое делилось бы на 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 17. Найдем произведение этих чисел. Получается 882161280. Теперь, мы можем перебирать все числа, кратные 882161280, и смотреть, входят ли в это число все цифры от 0 до 9 ровно по одному разу. Также заметим, что искомое число всегда будет заканчиваться на цифру 0, поэтому мы можем из набора цифр исключить цифру 0 и вместо числа 882161280 использовать числа 88216128. Затем к найденному числу припишем цифру 0. Все числа, состоящие из 9-ти цифр входят в диапазон длинных целых чисел (Longint), так что у нас тут не должно быть никаких проблем.
Шаг 1. Для проверки вхождения цифр создадим массив Digit, содержащий 10 элементов - целых чисел с индексами от 0 до 9.
Шаг 2. Заносим в переменную Pr значение ложь, а впеременную A значение 88216128.
Шаг 3. Выполняем в цикле Шаги 4, 5 до тех пор, пока значение Pr не станет истинным.
Шаг 4. A=A+88216128.
Шаг 5. Проверяем, входят ли в число A все цифры от 1 до 9 ровно по одному разу. Эта проверка заключается в выполнении Шагов 6, 7, 10.
Шаг 6. B=A. Обнуляем массив Digit.
Шаг 7. Десять раз выполняем в цикле Шаги 8, 9, 10.
Шаг 8. Делим число B на 10 и в переменную Ost заносим остаток от деления, в B заносим частное от деления.
Шаг 9. Увеличиваем значение элемента массива Digit с индексом Ost на 1.
Шаг 10. Если значение элементов с индексами 1, 2, 3, ..., 9 равняется 1, то в Pr заносим значение истинно.
Шаг 11. Преобразуем число A в символьный вид и справа к нему приписываем символ «0».
Шаг 12. Конец.
P.53.2.
Шаг 1. Создадим массив масок цифр искомого числа. Обозначим его через S. Цифра 0 в элементе массива будет обозначать цифру 3 в искомом числе, цифра 1 в элементе массива будет обозначать цифру 7 в искомом числе. Этот массив масок облегчит нам перебор всех чисел, содержащих только цифры 3 и 7. Мы будем перебирать все элементы массива, содержащие только нули и единицы, и по ним генерировать реальные перебираемые числа. 1-ый элемент массива будет соответствовать самой младшей цифре искомого числа, 2-ой элемент - предпоследней цифре и так далее.
Шаг 2. Присваиваем переменной Len значения 1, 2, 3 и так далее, до максимальной размерности массива S, и для каждого значения Len в цикле выполняем Шаги 3,4, 19. Переменная Len будет указывать, числа какой длины мы перебираем в данный момент.
Шаг 3. Обнуляем массив S.
Шаг 4. Выполняем в цикле Шаги 5, 6, 7, 8, 13, 14, 15, 16 до тех пор, пока значение одной из переменных Pr или Prr не станет истинным. Переменная Pr будет указывать на то, что искомое число найдено. Переменная Prr - на то, что мы перебрали все числа длины Len.
Шаг 5. Заносим в переменную Prr значение истинно, если все первые Len элементов массива S имеют значение 1.
Шаг 6. Строим по массиву масок S число LL и одновременно заносим в переменную MM сумму цифр этого числа, в переменную Num3 число троек в этом числе, в переменную Num7 - число семерок в этом числе. Для этого выполняем Шаги 7, 8.
Шаг 7. LL=0. MM=0. Num3=0. Num7=0.
Шаг 8. В цикле проходим переменной i по всем значениям от 1 до Len и для каждого значения i в цикле выполняем Шаго 9, 10.
Шаг 9. Умножаем переменную LL на 10.
Шаг 10. Если i-ый элемент массива S равняется 0, то выполняем Шаг 11, иначе Шаг 12.
Шаг 11. LL=LL+3. MM=MM+3. Num3=Num3+1.
Шаг 12. LL=LL+7. MM=MM+7. Num7=Num7+1.
Шаг 13. Заносим в переменную Pr значение истинно, если выполняются все следующие условия: 1) остаток от деления LL на 3 равняется 0; 2) остаток от деления LL на 7 равняется 0; 3) остаток от деления MM на 3 равняется 0; 4) остаток от деления MM на 7 равняется 0; 5) Num3 больше 0; 6) Num7 больше 0.
Шаг 14. Изменяем содержимое массива масок для следующего перебираемого числа. Для этого выполняем Шаги 15, 16.
Шаг 15. В переменную Per заносим значение 1.
Шаг 16. В цикле проходим переменной i все значения от 1 до Len и для каждого значения выполняем в цикле Шаги 17, 18.
Шаг 17. S[i]=S[i]+Per. Per=0.
Шаг 18. Если i-ый элемент массива S равняется 2, то в этот элемент массива заносим 0, а в переменную Per значение 1.
Шаг 19. Если Pr является истинным, то переходим на Щаг 21. (это последний шаг в цикле, начавшегося с шага 2).
Шаг 20. Заносим в переменную LL значение 0 (число не найдено).
Шаг 21. Выводим значение LL. Конец.
P.53.3.
Пояснение. Сэкономим время на анализе задачи и напишем в лоб переборный алгоритм. Нахождение решения задачи отнимет несколько десятков минут на составление алгоритма и нескольо часов на его выполнение на компьютере. Заметим только, что искомое число всегда будет заканчиваться на цифру 9.
Шаг 1. Заносим в переменную BB значение 100000009.
Шаг 2. Повторяем в цикле Шаги 3, 4, 5, 6, до тех пор, пока значение Pr станет истинным или число BB станет 10-значным.
Шаг 3. CC=BB*123456789.
Шаг 4. Заносим в переменную R2 остаток от деления CC на число 10000000000.
Шаг 5. Заносим в переменную Pr значение истинно, если R2 равняется 987654321, иначе заносим в Pr ложь.
Шаг 6. Если Pr содержит ложь, то увеличиваем значение BB на 10.
Шаг 7. Если Pr является ложным, то в BB заносим 0.
Шаг 8. Выводим значение BB.
Шаг 9. Конец.
|
