Питер Макоуэн - Вычислительное мышление: Метод решения сложных задач

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

Итак, если робот-фокусник не справится с задачей, это не конец света. Но если бы речь шла об алгоритме сопоставления с образцом, который определяет, выполнены ли в правильном порядке все разнообразные действия, необходимые для выпуска посадочных шасси воздушного судна, и в нем возникла бы похожая проблема, случай был бы совсем другим. Продумать все вероятные ситуации и предусмотреть для них встроенное сопоставление с образцом сложнее, чем представляется, но программистам это необходимо, чтобы их программное обеспечение работало правильно.

В так называемых системах с особыми требованиями к безопасности эксплуатации есть целый ряд образцов, которые обязательно нужно найти и на которые нужно правильно отреагировать, — например, в ПО для больниц, для управления ядерными реакторами или самоуправляемых машин нового поколения. Если мы просто учтем массу возможных вариантов, то все равно нам не удастся охватить все. Поэтому в информатике используются логическоеи аналитическое мышлениеи создаются математические способы анализа таких систем — например, они могут базироваться на идеях, которые мы применили к решению головоломок в главе 4. Математика обеспечивает нам более мощный инструмент для поиска образцов в системе. Потом пишутся программы, реализующие логическое мышление, основанное на математике. Компьютеры гораздо лучше нас изучают возможности и ничего при этом не упускают. Компьютеры в огромных объемах занимаются за нас вычислительным мышлением.

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

Предложите трем друзьям ввести произвольное число в калькуляторы (или мобильные телефоны, если в них есть калькулятор). Скажите, что вы в точности предскажете, на какие числа будет делиться выбранное произвольное число. В калькуляторе можно указать абсолютно любое трехзначное число. Это их выбор. Однако этот выбор нужно держать в тайне от вас.

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

Вы напрягаете свои телепатические возможности и сразу же называете разные маленькие числа, на которые их личные шестизначные числа делятся без остатка. Вы ответственно заявляете, что, хотя совершенно не представляете, что за числа они ввели, у первого друга число точно делится на 7, у второго — на 11, а у третьего — на 13. Остатка не будет. Друзья выполняют деление на калькуляторе, проверяют результат и показывают, что вы правы. Как вы и предсказали, остатка нет.

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

Секрет в том, что три названных вами маленьких числа — это всегда 7, 11 и 13. В остальном фокус является алгоритмическим и работает сам — он основан на математическом факте. Если записать число из трех цифр и дописать к нему те же самые три цифры, то у нас получится тот же результат, что и при умножении этого трехзначного числа на 1001. Почему? Умножая число на 1000, нужно поставить в конце три ноля. Умножая на 1001, мы умножаем на 1000 и приписываем в конце изначальное трехзначное число вместо трех нолей.

Например, 345 345 — это 345 ×1001 (345 000 + 345). Маленькие числа, которые вы используете в предсказании, — 7, 11 и 13. Однако 7 ×11 ×13 = 1001. Это значит, что, когда вы таким образом дублируете число, например 345, вы умножаете его на эти три числа. То есть 345 345 = 345 ×1001 — это абсолютно то же самое, что 345 345 = 345 ×7 ×11 ×13. Отсюда следует, что полученное шестизначное число будет делиться без остатка на любой из этих множителей, а потом на два оставшихся.

Благодаря этому математическому факту фокус срабатывает всегда, если вы используете числа 7, 11 и 13. На них будут без остатка делиться любые шестизначные числа из повторяющегося сочетания трех цифр. В заключительной части фокуса, когда вы продемонстрируете ваши поразительные математические способности, просто нужно получить любое шестизначное число такого рода, например 765 765. Конечно, оно будет делиться на 7, 11 и 13. Это неизбежно благодаря все тому же математическому принципу. Таким образом, за фокусом стоит математика, но волшебным его делает ваше выступление.

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

Числа 7, 11 и 13 — это простые числа.То есть они делятся только на 1 и на самих себя. Проверьте: ни одно из них не делится на 2, на 3, на 4 и так далее. Эти три числа называются простыми множителямидля 1001. Простые множители положительного целого числа — это простые числа, на которые оно делится без остатка.