Программы перебора

Квант 1988, №1 с. 3-6 Тег UDLQ

ПРОГРАММЫ ПЕРЕБОРА

Член-корреспондент АПН СССР
В. Г. ВОЛТЯНСКИЙ

Не правда ли, паровоз «бегает» лучше человека — во всяком случае, быстрее? И если нужно попасть в другой город, вы с удовлетворением прибегете к его помощи. Есть у человека и много других помощи. Роботы переносят тяжелые детали к месту обработки, средства связи помогают передать информацию, часы ответа на вопрос «сколько времени?» и т. д.

А есть новые, сравнительно недавно появились помощники, облачанные человека интеллектуально деятельности. Это — компьютеры. Они не только могут быстро произвести расчет, но и справляются с задачими, при размышлении над которых человека производит перебор вариантов, осуществляет поиск путей решения, выполняет логическое операции. Конечно, компьютер не в буквальном смысле «мыслит» так же, как человека (ведь и паровоз «бегает» по-своему, а не шагает, как мы). Хотя свою «мыслительную» деятельности компьютер послушно выполняет в соответствии с программим, заранее составленной человеком, но, благодаря огромному быстроейство, со многими задачими он справляется горздо быстрое человека. И не только с вычислительными задачими, но и с таким, для решения которых приходится подумать и поломать голову. Расмотрим пример.

Задача 1. Сколько существует двухначных чисел, сумма квадратов цифр которых делится на 13?

Конечно, для решения можно осуществить «тупой» перебор: двухначных чисел не так уж много, и если он за другим перебор и проверить, для каких из них сумма квадратов цифр делится на 13, то мы сможем найти ответ. Однако это долго и скучно. И мы применяем логическое рассужждение, позволяющее более легко и красиво получить решение. Для этого составим следующую таблицу:

| цифра | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| ее квадрат | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 |
| остаток | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 |

В нижней строке записаны остатки от деления чисел второй строки на 13. Надо подобрать две цифры, сумма квадратов которых делится на 13, т. е. две цифры, стоящие в верхней строке, для которых сумма соответствующих чисел нижней строки равна 13. Например, можно взять цифры 1 и 5 (подними в нижней строке стоит 1 и 12); получаем два двухначных числа 15 и 51, удовлетворяющих требуемому условию. Можно также взять цифры 1 и 8 (под которым также подписаны 1 и 12) — это дает еще два искомых числа (18 и 81). Еще одну комбинацию цифр составляют 2 и 3 (подними записаны 4 и 9), что дает еще два числа (23 и 32). Наконец, можно комбинировать одну из цифр, под которой записано число 3, с цифрой, под которой записано число 10. Всего получаем 14 искомых чисел:

15 и 51, 18 и 81, 23 и 32, 46 и 64, 47 и 74, 69 и 96, 79 и 97.

Хотя здесь надо было немного подумать и сообщить, как найти пути решения, но, конечно, такое решение лучше, чем «тупой» перебор.

А что если бы мы, подобно компьютеру, могли выполнять сотни тысяч или даже миллионы операций в секунд? Целесообразно ли было бы в этом случае ломать голову над поиском пути решения? Не прошел ли было бы при таком быстрое процессе переработчи числа от 10 до 99? Видимо, прошел!

Рассмотрим заранее 1, как с помощью компьютера решаются задачи перебора. Мы приведем программу на весьма распространном и употребительном языке программи-

рования Бейсик (см. учебник информаники для 10 кл., с. 71). Но прежде даим описание имеющейся в Бейсикестроенной функции INT. Вот пример записи:

A=INT(56/13)

Она означает, что переменной A присваивается значение, равное целой части дроби 56/13 (от англійского слова integer — целый). Так как 56/13==4,30769…, будем иметь A=4.

Тепер приведем программу *) решения задачи 1:

FOR N=10 TO 99
A=INT(N/10)
B=N-10*A
S=A*A+B*B
R=S-13*INT(S/13)
IF R=0 THEN PRINT N;
NEXT N
END

Комментарий. Строки программы пропусеваны, причем не подряд, а через 10 номеров. Этот пример очень удобен: если в процессе записи программы обнаружится, что вы пропустили какие-либо операции, нужные для решения, то их можно будет потом записать в виде строк с промежуточными номерами.

Строка 10 содержит оператор цикла, который как раз предназначен для осуществления перебор всех натуральных чисел от 10 до 99 (т. е. всех двух чисел) и для каждого из них осуществить дейтельность, указанную в последующих строках. Строка 70 — окончание дейтельности, проводимой с очередным дузначным числом, т. е. приказ перейти к следующему числу.

Тепер рассмотрим промежуточные строки 20—60, описывающие дейтельность, проводимую с числом N. Строка 20 содержит встроенную функцию INT, о которой было сказано выше. Таким образом, переменной A присваивается значение, равное целой части числа N/10, т. е. A — цифра

*) Программы в этой статье написаны на языке Бейсик MSX.

Квадрат трехзначного числа окачивается трея цифрами, которые как раз составляют вягое число. Найдите все такие числа.
Найдите четырехзначное число, которое при делении на 133 дает в остатке 125, а при делении на 134 дает в остатке 111.
Пришите к 523*** три такие цифры справа, чтобы полученное шестизначное число делилось на 7, на 8 и на 9.
Пришите к ***999 три такие цифры справа, чтобы полученное шестизначное число делилось на 13, на 17 и на 19.

Рассмотрим теперь еще одну задачу, решение которого позволяет нам позначить с дальнейшими приемами программирования на языке Бейсик.

Задача 8. Должитель (т. е. целоеек, произвший болееста лет) заменил, что если к сумме квадратов цифр его возраста прибавить число его дня рождения (т. е. какое-то из чисел от 1 до 31), то получится как раз его возраст. Сколько лет должно?

Вот программа для решения этой задачи:

FOR K=1 TO 9
FOR L=0 TO 9
FOR M=0 TO 9
N=100*K+10*L+M
S=K*K+L*L+M*M
IF N&lt;S+1 GO TO 90
IF N&lt;S+32 THEN PRINT N;
NEXT M
NEXT L
NEXT K
END

Комментарий. Здесь вместо одного использующая три вложенных друг в друга цикла. Рассмотрим строки 10, 20, 90, 100:

FOR K=1 TO 9
FOR L=0 TO 9
NEXT L
NEXT K

Начав деятельности при K=1, мы сразу же попадем во внутренний цикл (строки 20 и 90), и пока он не закончится, мы не перейдем через строку 90 дальше, т. е. не перейдем к следующему значению K. Таким образом, при K=1 мы переберем все значения L=0,1, …, 9, затем перейдем к K=2 и снова переберем все значения L=0,1, …, 9 и т. д. Отсюда ясно, что строки 10, 20, 90, 100 обеспечивают перебор всех пар K, L (в указанных пределах). Далее, внутри имеется еще третий цикл по M (строки 30, 80). Вместе эти три цикла дают перебор всех трех K, L, M (в указанных пределах). Тепер строка 40 показывает, что в результате этого мы перебираем все трехзначные числа от 100 до 999.

Строки 50—70 предназначены для проверки, годится ли исследуемое трехзначное число в качестве возраста долговителя. Прежде всего вычисляется S — сумма квадратов цифр этого трехзначного числа (строка 50). Если N<S+1, то рассматриваем трехзначное число не годится и, более того, увеличивая цифру единиц M, мы подавно будем получить непригодные числа. Поэтому в строке 60 применен оператор условия перехода: если N<S+1 то ПЕРЕЙТИ к строке 90. Если же условие N<S+1 не выполнено, т. е. N>S, то надо еще проверить, на сколько единиц число N больше S. Если N превыходит S на 32 или более, то разность N—S не может быть числом дня рождения. Поэтому лишь при условии N<S+32 число N годится в качестве возраста долговителя (и тогда его следует напечатать).

Введите эту программу в компьютер, и вы узнаете возраст долговителя: ему 109 лет.

Задание 9. Найдите трехзначное число, квадрат которого окачивается трея цифрами, отличными от нуля.

Подставьте в записи 424 вместе звездочек такие цифры, чтобы полученное пятизначное число делилось на 72.
Найдите четырехзначное число, являющееся точным квадратом, у которого две первыые цифры одинаковы и две последние тоже одинаковы.

Указание e. В языке Бейсик имеется встроенная функция SQR, которая преобразна для извлечения квадратного корня; иначе говоря, оператор M=SQR(A) присаивает переменной M значение, равное квадратному корню из значения переменной A.

В магазина имеется мастика в ящиках по 16 кг, 17 кг, 21 кг. Как неокоторий организации получить 185 кг мастики, не вскрывая ящики?
Великий математик Пьер Ферма, много занимающийся вопросами теории чисел, высказал гипотезу, что все числа вида

(п натуральное) являются простыми. При $n=1, 2, 3, 4$ справедливо этого утверждения несложно проверяется, а при $n=5$ проверка «вручную» становится сликом трудной. Однако другой великий математик, Леонард Эйлер, остроимым искусственным приемом установил, что как раз при $n=5$ утверждение Ферма является ошибочным, т. е. число () оказывается в этом случае составным. Напишите программу, позволяющую при $n=5$ убедиться в правильности утверждения Эйлера, т. е. найти делитель числа (), отличный от этого числа и единицы.

Указание. По общной программе, написанной на языке Бейсик, компьютер производит расчеты с шестю значцами цифрами. Между тем число (*), получающей при $n=5$ , имеет 10 значших цифр. Учитите это при составлении программы. Запись 2^16 означает: возввести 2 в 16-ю степень.

Найдите все трехзначные числа, равные сумме кубов своих цифр.
В трехзначном числе зачеркнуты первую цифру слева; когда полученное двузначное число умножили на 7, получилось исходное трехзначное число. Найдите его.
В трехзначном числе, все цифры которого нечетны, зачеркнуты среднюю цифру. Оказаюсь, что полученное двузначное число является делителем исходного числа. Найдите все такие трехзначные числа.

Указание: строка

10 FOR A=1 TO 9 STEP 2
означает, что A пробегает числа с шагом 2 (т. е. 1, 3, 5, …).

Сумма цифр трехзначного числа кратна 7. Само число также делится на 7. Найдите все такие числа.

Указание: запись R<>0 означает, что R не равно нулю.

Четырехзначное число, а также число, записанное теми же цифрами в обратном порядке, оба являются точными квадратами. Найдите эти числа.
Решите следующие арифметические решения (вместо каждого буквы надо подставить неокторую цифру, причем одинаковые буквы означают одинаковые цифры, а различные буквы — различные цифры):

a) КТО + КОТ = ТОК;
b) ABBA = AA² + BB²;
b) КИО * ИО = ТОКИО.

Найдите все двухначные числа, сумма цифр которых не меняется при умножении числа на 2, 3, 4, 5, 6, 7, 8, 9.

Нередко при решении задач на компьютере применяются работы переменные, которые в программе ответятся роль «счетчиков», «накопитель», «хранителей» промежуточных результатов. Рассмотрим это на следующих примерах.

Задача 21. Найдите наиболее значение суммы $M^2+N^2$ , когда M и N пробегают все значения от 1 до 100,

Комментарий. Здесь использованастроенная функция ABS, предназначенная для нахождения модуля (или, как раньше говорили, абсолотной величины) числа; иначе говоря, оператор H=ABS(Q) присваивает переменной H значение |Q|. Далее, P, K, L — рабочие переменные («хранители»), предназначенные для того, чтобы в процессе работы программы неокторое время сохранять полученные промежуточные результаты. Переменная P предназначена для хранения доступного значения $M^2+N^2$ : первоначально P=0 (строка 10), а каждый раз, когда (при наложенных на M, N условиях) получается сумма квадратов, большая, чем она была равна, переменной P присваивается новое значение, равное этой сумме квадратов. Однако временно переменные K, L получают (и хранят до следующого изменения) те значения M, N, при которых это больше значения суммы квадратов было получено. После всего перебора печатается наиболее значение суммы квадратов и те M, N, при которых оно больше доступного. Заметим, что между буквами P, K, L поставлены в строке 110 запятые (а не точки с запятыми): при таком способе печати выносимые на дисплей числа отстоят друг от друга дальше (какое число занимает 15 позиций).

Задача 22. Сколько существует «счастливых» шестизначных билетков (т. е. таких, у которых сумма