Текст
                    V. Dagiene G. Grigas
K. Augutis
100
programavimo uzdaviniy
KNYGA MOKINIAMS
KAUNAS SVIESA 1986


В.А.ДАГЕНЕ ГК.ГРИГАС К.Ф.АУГУТИС 1\J\J3AW4 ПО ПРОГРАММИРОВАНИЮ КНИГА ДЛЯ УЧАЩИХСЯ ПЕРЕВОД С ЛИТОВСКОГО А. Д. ШМЕЛЕВА МОСКВА «ПРОСВЕЩЕНИЕ» 1993
ББК 32.973-01 ДН Рецензент, ведущий научный сотрудник Института программных систем АН России доктор педагогических наук Ю А Первин Дагене В. А. и др. 100 задач по программированию: Кн. для учащихся: Пер. с лит. / В. А. Дагене, Г. К. Григас, К. Ф. Аугу- тис— М.: Просвещение, 1993.— 255 с: ил.— ISBN 5-09-003864-3. В книге рассмотрены конкретные задачи по программированию. Все задачи интересны или своей формулировкой, или неожиданным результатом, или алгоритмом решения. Программы написаны на языке Паскаль. Книга будет интересна всем, кто желает практически, по примерам, научиться составлять программы разнообразных задач и решать их при помощи ЭВМ. ISBN 5-09-003864-3 (С) Lcidykla «Sviesa», 1986 (С) Дагччн» В. Л. и другие. Псромод Шмелева А. Д., 1993
ПРЕДИСЛОВИЕ Чтобы стать программистом, необходимо преодолеть пропасть, разделяющую математическую задачу и программу, т.е. уметь находить решение каждой задачи и выражать его на языке программирования. А научить этому может только практика, поэтому необходимо самому составить много программ и разобрать очень много программ, составленных другими. Мы полагаем, что приведённые в этой книге программы окажутся для читателя полезными. Задачи подобраны разнообразные. Для многих из них мы заимствовали идеи из популярных книг по математике, часть составили в процессе работы с учащимися Литовской заочной школы молодых программистов. Все программы написаны на языке Паскаль. Мы старались подобрать программы таким образом, чтобы они были понятны начинающему программисту, знакомящемуся с основами программирования и с языком Паскаль. Мы думаем, что приводимые программы помогут читателю найти ключ к решению многих других задач, здесь не разбираемых. Задачи излагаются таким образом, чтобы их можно было читать в произвольном порядке. Тесно связанные между собой задачи мы старались дать рядом. В книге есть и такие программы, которые служат для решения ранее решённых задач или задач, которые легко решаются без помощи ЭВМ. Подобные программы приводятся потому, что в них есть интересные моменты (оригинальный способ решения, алгоритм, употребление разнообразных конструкций языка программирования), что может пригодиться и для решения других задач. Почти после каждой задачи приводятся задания для самостоятельной работы. В конце книги (в разделе «Заключение») содержится краткое обсуждение практических вопросов, касающихся выполнения программы на ЭВМ.
Приведённый в книге список литературы включает не только цитируемые, но и другие книги, которые пригодятся читателям, заинтересованным в более широком и глубоком знакомстве с различными вопросами программирования. За замечания и предложения авторы благодарят рецензента книги доцента Вильнюсского университета Владаса Тумасониса, сотрудника университета Римантаса Дагиса, учащихся Литовской заочной школы молодых программистов Видаса Стаугайтиса и Айдаса Жандариса (они читали рукопись, будучи десятиклассниками). Особо ценные замечания, советы и предложения авторы получили от учащегося Литовской заочной школы молодых программистов, также десятиклассника Витолиса Бендин- скаса. Авторы благодарны также сотрудникам Викторасу Да- гису и Зите Куралавичюте за выполнение приводимых в книге программ на вычислительной машине;. Для решения одной и той же задачи можно составить много программ. Мы старались составить и здесь представить лучшие (те, которые короче, яснее, естественнее отражают суть задачи). Однако думаем, что и эти программы не самые совершенные. Будем благодарны читателям за замечания, новые решения, а также интересные задачи. Наш адрес: Литва, г. Вильнюс, ул. Академиёс, 4, Институт математики и информатики.
ВВЕДЕНИЕ Для того чтобы решить задачу, мы должны прежде всего знать, что дано (исходные данные), а также формулировку задачи (условие.) Решив задачу, мы получаем то, что требуется по условию,— результат. Если задача решается при помощи электронно-вычислительной машины (ЭВМ), то работа разделяется на две части. Человек (программист) пишет программу, а машина выполняет эту программу и исходя из предъявленных ей исходных данных получает результат. Всё решение задачи можно изобразить при помощи схемы, приведённой на рисунке 1. Из схемы видно, что результат работы ЭВМ и является результатом решения задачи. А результат работы программиста — программа. Создавая программу, он решает задачу по программированию, а машина, выполняя программу,— задачу на вычисление. Для одной и той же задачи можно составить очень много эквивалентных программ, выполняя которые ЭВМ будет получать один и тот же правильный результат. Какую же программу выбрать, какую считать самой лучшей? Из схемы (см. рис. 1) можно сделать вывод, что программа пишется для машины, т. е. программу пишет (составляет) человек, а читает (использует) её машина. Так полагали прежде. От программиста не требовалось, чтобы он раскрывал содержание программы. Достаточно было, чтобы машина Рис 1. Схема решения задачи.
в соответствии с этой программой решила задачу. Критерии оценки программы были чисто «машинными». Лучшей программой считалась та, которая экономно использовала ресурсы ЭВМ: время и память. Поскольку самые первые ЭВМ производили вычисления достаточно медленно и обладали небольшим объёмом памяти, то эти критерии были действительно очень важными. С течением времени положение изменилось. Выросли быстродействие и объём памяти ЭВМ. Поэтому экономичность программы утратила решающее значение. С другой стороны, практика показала, что машина не единственный читатель программы. Очень часто её читает и разбирает человек. Тем самым он знакомится с идеями и опытом других программистов, учится программировать, самостоятельно составлять программы: ведь не стоит изобретать велосипед. Кроме того, при том или ином видоизменении задачи легче модифицировать старую программу, нежели создавать новую. Приходится читать и свои собственные программы. Чаще всего их усовершенствованием и занимается сам автор. Когда программа только что написана и ещё остаётся свежей в памяти, читать её совсем легко. Однако с течением времени она забывается. Во всех упомянутых случаях необходимо вникать в смысл программы. Поэтому она должна быть написана ясно и понятно. Таким образом, появляется новый критерий оценки программы — степень её ясности. Приведённые в книге тексты программ — это результаты решения задач по программированию, аналогичные ответам математических задач. А для того чтобы получить ответ, нам часто приходится как следует поработать, испытать различные пути решения. Поэтому часто важен не только результат программирования — программа, но и способ, посредством которого нам удалось её получить. Это особенно интересно для тех, кто сам собирается составлять программы. Пути составления многих программ в книге не описываются во всех подробностях. Это заняло бы немало места и было бы скучно повторно писать одни и те же пояснения, поскольку почти везде применяется одинаковая методика программирования. Большая задача обычно распадается на части, каждую из которых можно программировать отдельно. Часто для более крупных частей пишется функция или процедура. Если функция или процедура также оказывается слишком сложной, то она программируется так же, как и вся задача: разложением на меньшие части. Методика программиро-
нания детально описана в «Началах программирования» [1], а здесь мы только поясним её на одном примере. Тем самым мы покажем, как по тексту программы можно догадаться о том, каким образом она была составлена. Например, вычислим, какое наименьшее число почтовых марок по 10, 4 и 1 к. надо наклеить на простую бандероль, вес которой представляет собой исходное данное. (Плата за посылку бандероли вычисляется следующим образом: за бандероль весом до 50 г взимается 10 к., за каждые следующие полные или неполные 50 г — ещё по 5 к.) Составим программу для решения этой задачи. Разобьём задачу на четыре следующие части: 1. Ввод исходных данных. 2. Вычисление платы за посылку бандероли. 3. Подсчёт числа марок. 4. Печать результатов. Составим схему программы: На схеме в законченном виде отражена только 1-я часть. Она записана при помощи одного из операторов языка
Паскаль — read (гр). Три прочие части не закончены. Вместо них на схеме приведены прямоугольники с описанием их действий словами. Предполагается, что 2-я часть будет выражена функцией, 3-я часть — процедурой (заголовки для них мы уже создали), а 4-я часть будет внесена непосредственно в текст программы. Детализируем действия, записанные в прямоугольниках. Действия первого прямоугольника (функция плата) записываются так: Действия по печати результатов совсем просты, поэтому мы не выписываем их отдельно, а непосредственно включаем в текст программы. Теперь, написав функцию плата и процедуру марки, мы получим законченную программу: Действия второго прямоугольника (процедура марки) может быть записана таким образом:
Вот мы и составили программу. Обратим внимание на то, что во всей книге, как и в приведённом примере, действия, соответствующие незапрограммированным частям, формулируются в сжатом виде и приводятся в прямоугольниках. Прямоугольники могут находиться в любой части программы (на месте процедур, группы операторов, даже на месте условия в операторе if и т.д., если эта группа является хоть в какой-то степени более сложной и самостоятельной по сравнению с другими частями). Теперь представим себя на месте читателя программы, у которого перед глазами только окончательный текст программы бандероль и который хочет выяснить, каков был путь составления программы. Прежде всего познакомимся с описаниями переменных, заголовками функций и процедур (пока мы не будем вдаваться в выполняемые ими действия). Как следует разберемся в действиях основной части программы. Оператор ввода данных ясен сам по себе. Далее идет обращение к функции плата. Прочтём только комментарий после заголовка функции и, не рассматривая сами действия, поверим, что функция действительно вычисляет плату за посылку бандероли. Следовательно, переменной коп приписывается значение платы. Далее — обращение к процедуре марки. Снова, прочитав комментарий после заголовка процедуры, поверим результатам процедуры. Печать результатов также совершенно очевидна. Вот мы и получили представление об общем виде программы. Мы уяснили себе именно ту часть программы, которая была составлена прежде других. Каким образом программа составлялась дальше, показывают функция и процедура. Разберёмся теперь в них. Если бы в их составе были ещё
какие-то функции и процедуры, то мы сначала только познакомились бы с их заголовками и лишь затем стали бы вникать в их содержание. Тем самым, разбирая программу, мы идём тем же путём, каким программа была составлена. Если читателя заинтересует не вся программа, а лишь какая-то её часть, он может и не разбирать всю программу. Предположим, читатель интересуется только тем, как плата выражается в почтовых марках (например, он обдумывает, как записать действия, при помощи которых можно данную сумму выразить в монетах или банкнотах). Тогда ему достаточно разобраться в процедуре марки. Он обнаружит, что в ней отдельно записаны все интересующие его действия. Обратим внимание на то, что составитель программы одновременно может составлять какой-то небольшой блок (процедуру, функцию, группу операторов). Точно так же и читатель программы может сразу охватить взглядом небольшой блок программы. Поэтому обычно стремятся программные блоки делать небольшими, чтобы можно было сразу же разобраться во всём блоке. Его текст не должен превышать страницы. В программах много места уделяется вводу и выводу данных, особенно если требуется при печати красиво расположить результаты. Однако для любознательного читателя программ более интересны алгоритмы, относящиеся к существу задачи. Мы часто можем избежать углубления в детали ввода и вывода данных, составляя и для всей задачи вместо программы функцию или процедуру. Например, для рассматриваемой задачи вместо программы бандероль можно было бы составить процедуру, имеющую такую схему: Программист, стремящийся полностью решить задачу, должен сам написать программу, обрамляющую такую процедуру. В ней должны быть предусмотрены ввод исходных данных, обращение к процедуре и печать результатов.
Обратим внимание на то, что в книгах и журналах очень часто решение задачи оформлено при помощи функций и процедур, поскольку именно так можно в сжатом виде передать существо задачи, а всякий программист сможет включить эту процедуру или функцию в программу, которую он составит в соответствии со своими потребностями. В данной книге мы также часто прекращаем составление программы для той или иной задачи на этапе создания функции или процедуры. Вообще, в программах, для которых ввод или вывод данных не относится к существу дела, мы стремимся записать эти действия как можно проще и лаконичнее. Мы не будем программировать и контроль исходных данных. Например, в программе бандероль входным данным может быть любое целое (в том числе отрицательное) число, а вес бандероли должен принадлежать некоторому интервалу (скажем, от 1 г до 3 кг). Проще всего проверить принадлежность исходных данных указанному интервалу, если переменные, соответствующие данным, описываются при помощи типа отрезка. Например: var гр:: 1..3000 Каким образом будет реагировать ЭВМ на недопустимые данные и как она об этом проинформирует пользователя, зависит от конкретной ЭВМ и её транслятора. Между тем ситуация будет значительно более ясной для пользователя, если ЭВМ напечатает сообщение об ошибке исходя из условия задачи. Для того чтобы сделать это, надо записать в программе проверку значений переменной гр, а изменять её описание не надо. Например: Как видим, исчерпывающий анализ исходных данных и печать сообщений об ошибках занимают немало места. Поэтому мы не включаем эти действия в программы, хотя они очень важны, особенно если программой пользуются многие люди.
1. Факториал Функция вычисления факториала хорошо известна программистам. Она приводится почти в каждой книге по программированию. Поэтому с нее мы и начнем. Факториалом числа п называется произведение чисел от 1 до п включительно: /г! = Ь2-3-...-/г. Кроме того, принимается, что 0! = 1. Факториал определяется еще и таким образом: |0! = 1, \п\=п-(п— 1)!, л>1. Это рекурсивное определение. Опираясь на него, легко написать рекурсивную функцию: Факториал можно вычислить и посредством нерекурсивной функции. Она могла бы выглядеть так: Эту функцию мы включим в программу, которая печатает первые десять натуральных чисел и их факториалы:
Выполнив данную программу, ЭВМ напечатала бы такие результаты: 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 При внимательном рассмотрении можно заметить, что эта программа нерациональна: факториал каждого числа вычисляется заново с самого начала. Этих повторных вычислений следовало бы избегать, особенно когда важно беречь машинное время. Перенеся действия функции в основную часть программы и соединив их с печатью, мы получили бы значительно более быстродействующую программу:
Возникает вопрос: а нельзя ли было бы сделать наоборот — включить печать в функцию? Тогда функция выглядела бы так: Обращаясь к этой функции, мы получаем не только факториал числа п (который в данном случае, возможно, и не понадобится), но и все числа от 1 до* п, напечатанные вместе с их факториалами. В таком случае говорят, что функция имеет побочный эффект (в рассматриваемом примере побочным эффектом является печать). Вообще говоря, посредством функций принято описывать такие действия, результатом которых является одно определенное значение. В языке Паскаль значение функции может быть только простым числом, скалярным, логическим, символьным значением или указателем. А все прочее относится к побочным продуктам. В силу сказанного, если одного значения недостаточно, обычно используют процедуру. Так, упомянутые действия по печати факториалов лучше описать посредством процедуры: 0 Входное данное — натуральное число а. Составьте функцию /, значение которой удовлетворяло бы такой системе неравенств: ff(a)!<a, |(f(a)+l)!>a.
2. Осторожно: maxintl Самым большим целым числом, с которым может иметь дело ЭВМ, в языке Паскаль является стандартная константа maxint. Если диапазон чисел симметричен, то наименьшим числом будет — maxint. Когда при выполнении арифметических операций получаем слишком большое или слишком маленькое число, создается аварийная ситуация и фиксируется ошибка, именуемая переполнением. В таком случае ЭВМ чаще всего печатает сообщение о том, что имеет место аварийная ситуация, и прекращает вычисление. Конечно, польза от этого невелика, так как результаты остаются не- подсчитанными. Поэтому, если грозит опасность переполнения, целесообразно заранее предусмотреть в программе действия, помогающие избежать этого. Чаще всего мы сталкиваемся с переполнением при вычислении факториала. Если 10! можно вычислить при помощи почти всякой ЭВМ, то 20! не «уместится» в большинстве ЭВМ. Перестроим приведенную в задаче 1 программу факториалы таким образом, чтобы она печатала самое большое натуральное число и его факториал, который еще может быть вычислен на имеющейся электронно-вычислительной машине. ЭВМ ЕС, используя транслятор языка Паскаль, предназначенный для обучения, напечатала следующий результат: F{ 12) = 479001600. Если при решении задачи появляются и отрицательные числа, то переполнение угрожает с обеих сторон и избежать его труднее. Составим программу, которая бы проверяла, не приведет
ли суммирование двух исходных данных — целых чисел а и b — к переполнению. Если будет переполнение, то напечатаем соответствующее сообщение. Для проверки, нет ли переполнения, создадим функцию переполи: Подчеркнем, что в процессе проверки выражения, значения которых не попадают в допустимый интервал \ — maxint\ maxint], появиться не могут. Включим созданную функцию в программу: Здесь мы продемонстрировали, как избежать переполнения, отказываясь от действий, результатами которых являются слишком большие числа. Но иногда все же бывает необходимо выполнить такие действия (скажем, мы хотим вычислить 100!). Можно сделать это, представляя (кодируя) большие числа через посредство нескольких меньших. Об этом мы будем говорить в задаче 47. © Составьте функцию, которая проверяла бы, не происходит ли переполнения при перемножении двух данных целых чисел.
0 0 Составьте функцию, которая проверяла бы, не происходит ли переполнения при возведении данного числа н п-ю степень. 3. Размещения и сочетания Число размещений без повторений А* и число сочетаний без повторений Скп подсчитывается по таким формулам [20]: Применяя функцию вычисления факториала (см. задачу I), мы могли бы записать подсчет числа размещений или сочетаний при помощи одного оператора присваивания: A:=f(n) div f(n — k) или C:=f(n) div (f(k)*f(n-k)\ где / — функция вычисления факториала. Однако факториал представляет собой быстровозрастаю- щую функцию, и поэтому уже при вычислении числителя или знаменателя дроби может возникнуть переполнение (когда п — большое число), хотя результат — число размещений или сочетаний — еще не превосходил бы максимального допустимого числа maxint. Это типичный случай, когда переполнение возникает на промежуточном этапе. Чтобы уменьшить вероятность переполнения, создадим функции, непосредственно подсчитывающие число размещений и сочетаний. Кроме того, подсчитывая число сочетаний, мы будем опираться на известное тождество С* = = Cn~k (например, вместо того, чтобы вычислять СЦ, можем вычислить C?g):
При вычислении функции размещений а переполнение может возникнуть только тогда, когда конечный результат превышает maxint, а при вычислении функции сочетаний С перевыполнение может возникнуть и вследствие того, что промежуточный результат (числитель дроби) превышает maxint. Однако вероятность переполнения будет все же меньшей, нежели при вычислении по формуле, которая вычислителе содержит п\ 0 Составьте функцию, подсчитывающую число сочетаний с повторениями [20]. Примените формулу r*„_(/i + fe-i)i ^n~k\ (я-1)Г © © Составьте функцию, подсчитывающую число перестановок с повторениями [20]. Примените формулу Р (/г,, л2, ..., nk) = ——[^ где nl+n2 + ... + nk = n. П\\ 'П2\ •.. 'tiki 4. Числа Фибоначчи В 1202 г. итальянский математик Леонард Пизанский (Leonardo Pisanto, около 1170 — около 1228), известный под именем Фибоначчи (Fibonacci), предложил такую задачу: Пара кроликов каждый месяц дает приплод — двух кроликов (самца и самку), от которых через два месяца уже получается новый приплод. Сколько кроликов будет через год, если в начале года мы имели одну пару молодых кроликов? Обратим внимание на то, что числа, соответствующие количеству кроликов, которые имеются через каждый месяц, составляют последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Каждый из членов этой последовательности, начиная с третьего, равен сумме двух предыдущих членов. Эта последовательность называется рядом Фибоначчи, а ее члены — числами Фибоначчи. Числа Фибоначчи имеют много интересных свойств. С ними, например, связано так называемое золотое сечение. Подчеркнем, что нет единого мнения о первых числах Фибоначчи. Одни математики начинают ряд числами 1, 1, другие — числами 1, 2, третьи — 0, 1. Однако это не меняет существа задачи: дело в том, что правила вычисления прочих членов ряда и сами эти члены во всех случаях остаются одни и те же. Мы будем считать, что /7(1) = /7(2)= 1. Обозначив /2-й член ряда Фибоначчи посредством символа F(n), мы получим следующую рекурсивную зависимость: f(n)=F(n—\)+F(n — 2)9 /2>3, F(l)=l и F(2)=l. При наличии этой зависимости легко создать рекурсивную функцию, позволяющую найти п-е число Фибоначчи: Когда /2=1 или я = 2, получаем значение функции, выполнив функцию один (первый) раз. Когда /2 = 3, выполняется вторая (else) ветвь условного оператора и значение функции находится из выражения фиб(2)-\-фиб (1). Для того чтобы вычислить значение выражения, следует еще два раза (рекурсивно) обратиться к функции фиб. Когда /2 = 4, функция будет выполняться пять раз, а когда /2 = 5 —девять раз (рис. 2). Таким образом, при возрастании значения параметра функции очень быстро возрастает и число обращений к функции, а тем самым увеличивается время вычисления. Это происходит вследствие того, что вторая ветвь условного оператора содержит сразу два рекурсивных вызова. (Во многих других рекурсивных функциях или процедурах, приведенных в этой книге, например в задаче 1, рекурсивная ветвь содержит один вызов, а число рекурсивных вызовов чаще всего прямо пропорционально значению параметра.) Поэтому рекурсивная функция, вычисляющая числа Фибоначчи, часто приводится как наглядный пример неэффективности.
Рис. 2 Создадим более эффективную функцию, не прибегая к рекурсии: Программа бывает более компактной, когда все члены ряда вычисляются в соответствии с одними и теми же правилами. В ряду Фибоначчи исключение составляют первые два члена. Если мы хотим вычислять и их в соответствии с теми же самыми правилами, следует в функции фибо искусственно продолжить ряд влево, пополнив его двумя фиктивными членами: F(—1)=1 и F(0) = 0. Тогда ряд примет следующий вид: , 10 1 12 3 5... Фиктивные члены ряда | Подлинные члены ряда При наличии этих двух фиктивных членов все подлинные члены ряда вычисляются по тем же правилам. Обе функции, приведенные в этом разделе, предназна-
чены для того, чтобы находить п-е число Фибоначчи. Если мы хотим напечатать последовательность чисел Фибоначчи, т. е. числа Фибоначчи от 1 до я-го, можно включить в программу любую из упомянутых функций. Приведем фрагмент такой программы: for /: = 1 to n do writeln (фибо (/)) Однако подобная программа неэкономна. В соответствии с ней числа Фибоначчи вычисляются, печатаются и... забываются. При поиске нового, большего числа приходится повторять те же самые действия. Поэтому программы, которые должны печатать следующие друг за другом члены ряда, могли бы использовать процедуру, не только вычисляющую произвольный член ряда, но и печатающую его. Создадим такую процедуру: В этой процедуре прежде всего вычисляются фиктивные члены ряда. Если превратить эти члены в параметры, то получим процедуру, которая печатает п членов ряда, идущих за двумя данными членами. Модифицировать, таким образом, процедуру фибон очень просто — надо только переменные fn\ и fn превратить в параметры и не приписывать им начальных значений. Приведем более интересную рекурсивную процедуру:
Если мы захотим напечатать п первых членов ряда Фибоначчи, то должны будем прибегнуть к этой процедуре, указав в качестве параметров два фиктивных члена: фибоначни (я, 1, 0). Если необходимо напечатать десять членов ряда Фибоначчи, начиная с шестого, следует написать обращение: Фибоначчи (10, 3, 5). Если два других параметра не были бы соседними членами ряда Фибоначчи, то процедура напечатала бы не последовательность чисел Фибоначчи, а некоторую другую последовательность, члены которой вычисляются в соответствии с тем же правилом, что и члены ряда Фибоначчи. 0 Составьте программу, позволяющую найти все числа Фибоначчи, меньшие данного числа. 0 © Интересно представить ряд Фибоначчи графически. Например: * * ** *** Составьте программу, которая бы печатала ряд Фибоначчи в виде звездочек. Строки печатаются до тех пор, пока число звездочек умещается в строке. 5. Суммы рядов Многие из математических величин или значений функций могут быть выражены как суммы бесконечных последовательностей. Например:
Чем больше членов ряда участвует в сложении, тем более точным получается искомое значение. Составим программу вычисления е — основания натурального логарифма: Выполнив эту программу, ЭВМ напечатала такие результаты: 1 2.0000000 2 2.5000000 3 2.6666667 4 2.7083333 5 2.7166667 6 2.7180556 7 2.7182540 8 2.7182788 9 2.7182815 10 2.7182818 Значение числа е: е = 2.718281828... Мы видим, что при увеличении числа членов последовательности получающаяся сумма приближается к значению е. Разность полученной суммы ряда и действительной суммы называется погрешностью сложения. Эту погрешность можно оценить различными способами, однако большинство из них достаточно сложны. Встречаются последовательности, для которых можно установить связь между значениями последнего из складываемых членов и величиной погрешности. Поэтому чаще всего оценивается п~й член: если он достаточно мал, т. е. меньше некоторого данного числа е, то считается, что найденная сумма удовлетворяет требованиям. Создадим функцию для нахождения значения числа я, складывая члены ряда, приведенного в начале задачи:
© Составьте функции для нахождения с указанной точностью числа я путем сложения членов следующих рядов: © © Составьте функции для вычисления с указанной точностью значений тригонометрических функций путем сложения членов следующих рядов:
6. Возведение в квадрат без операции умножения Квадрат любого натурального числа п равен сумме п первых нечетных чисел: 12=1 22=1+3 32=1+3 + 5 42=1 4-3 + 5 + 7 52=1+3 + 5 + 7 + 9 Основываясь на данном свойстве, составим программу, позволяющую напечатать квадраты натуральных чисел от 1 до п: Поскольку мы не применяем умножения, это свойство чисел было особенно важным для вычисления на старых, электромеханических вычислительных машинах (например, на табуляторах), так как на них операция умножения не выполнялась или выполнялась очень медленно. © Куб любого натурального числа п равен сумме п нечетных чисел, следующих по порядку за числами, сумма которых составила куб числа п — 1: 13= 1 23= 3 + 5 33= 7 + 9+11 43= 13+15+17+19 53= 21+23 + 25 + 27 + 29
Основываясь на этом свойстве, создайте программу, позволяющую напечатать таблицу кубов натуральных чисел. 7. Извлечение корня из действительных чисел Известно много различных методов извлечения корня. В программировании удобнее всего пользоваться универсальным методом, т. е. таким методом, в соответствии с которым одни и те же, хотя бы и более продолжительные, вычисления выполняются при любых исходных данных. Таким методом является метод итерации. Корень с натуральным основанием y = rfx, *>0, где т — натуральное число, извлекается по формуле Поясним^каким образом по этой формуле можно получить корень у=а\[х. Сначала примем, что корень равен произвольному числу (например, (/о=1; доказано, что получающееся в результате значение корня не зависит от того, какое значение у0 мы избрали в качестве исходного), вычисляем новое значение корня у\, затем опять новое значение корня у2 и т. д. Каждое новое значение уп оказывается все ближе к подлинному значению корня. Когда разность между значением уп и предыдущим значением уп-\ становится весьма малой — меньшей, нежели допустимая погрешность, принимаем, что полученное значение уп является корнем, и вычисление заканчивается. Приведем ряд примеров, показывающих, как извлекается кубический корень из 125 при различных исходных значениях: у0 = х= 125.0; j/o=1.0; у0=Ю.О; (/1=83.3; «/1=42.3; «/i=7.1; у2 = 55.6; у 2 = 28.2; у2 = 5.6; 1/3 = 37.1; (/з=18.9; (/з = 5.1; у4 = 24.7; у4 =12.7; уА = 5.0; (/5=16.6; (/5 = 8.7; (/5 = 5.0. Написав уу вместо уп и у вместо уп-\ (где л = 1, 2 ...), составим следующий фрагмент программы извлечения корня m-й степени из неотрицательного числа х:
Здесь степень (у, пг) — функция, которая возводит число у и пг-ю степень, а эпсилон — допустимая погрешность при извлечении корня. Этот правильный на первый взгляд фрагмент программы практически не очень хорош. Извлекая корень более высокой степени, можно получить очень большой результат функции степень. Например, если мы будем извлекать корень '°VЮ000.0, т. е. выполним программу при т = 100 и х = 10000.0, то при первом прохождении цикла получим г/г/ ^г 100. При повторном прохождении цикла необходимо будет это число возвести в 99-ю степень. Хотя интервал действительных чисел в вычислительной машине весьма велик, однако в данном случае мы получим значение, не попадающее в этот интервал, т. е. произойдет переполнение. Это выглядит неестественным: если число, из которого мы извлекаем корень, находится в допустимом интервале, то и значение корня будет находиться в том же самом интервале. Поэтому для пользователя данной программы будет совершенно непонятно, почему машина прекратила вычисления вследствие переполнения, тогда как исходное число не очень велико. Чтобы избежать переполнения, не будем возводить число уу в степень; вместо этого будем много раз делить число х на уу. Составим функцию извлечения корня m-й степени (где пг — натуральное число) из неотрицательного числа х с точностью до Ю-5:
Обратим внимание на два момента: 1. Формулу извлечения корня мы разбили на две части. Одну часть действий мы вынесли из цикла, а другую часть оставили в цикле. Это было сделано из соображений экономии. Значения (часть значений), которые не изменяются при прохождении цикла, достаточно вычислить один раз, до начала цикла. В цикле остаются только те значения, которые изменяются в процессе прохождения цикла. Такое преобразование вычислений называется чисткой цикла. 2. Когда требуется извлечь корень более высокой степени, то при вычислении w:=w/yy частное может оказаться весьма малым, еще прежде чем деление будет произведено т—\ раз. Поэтому цикл может быть закончен раньше, т. е. когда частное станет меньшим, нежели эпсилон. Это сокращает время работы машины. Однако здесь есть еще более существенный момент. Когда получаются очень малые действительные числа, может возникнуть странное на вид явление — переполнение в сторону малых чисел. Ведь, чем меньше число, тем больше абсолютная величина его порядка (например, IE —60, IE —70, IE —89 и т. д.). В результате число, выражающее порядок, может не уместиться в отведенное для него место. Прерывая цикл раньше, мы избегаем этого явления. 0 Составьте отдельную функцию для нахождения значений кубического корня у=\[х с заданной погрешностью е (где е — некоторая заданная константа). 0 0В языке Паскаль содержится немало стандартных функций. Упомянем следующие: 1п(х) — натуральный логарифм числа х; ехр (х) — еху здесь е = 2.71828...— основание натуральных логарифмов. Применяя тождество
составьте функцию, позволяющую найти корень m-й степени из х. 8. Корни из натуральных чисел Извлечение корня из натурального числа не всегда дает целое число. Этим извлечение корня из целого числа похоже на целочисленное деление. При делении целого числа на целое получаем два результата — частное и остаток. Похоже извлекаем корень m-й степени из целого числа ху получаем два результата — целая часть корня у и остаток г. Они связаны таким образом: | х=ут + г, \ х<(у-\- \)т, х>0у где т — натуральное число. Например, при извлечении кубического корня из 26 получаем i/ = 2 и г = 18, а из 27 получаем у = 3 и г = 0. Условимся, что корень будем извлекать только из натуральных чисел. Для корня из натуральных чисел можно использовать ту же итерационную формулу, как и для корня из действительных чисел (см. задачу 7). Однако затруднительно определить, когда следует окончить вычисления и как предупредить переполнение. Поэтому корень из натуральных чисел будем извлекать иначе. Возьмем два натуральных числа а и 6, между которыми должен быть искомый корень, т. е. удовлетворяющий неравенству: Этот интервал делим пополам и берем его среднее число: ab = (a + b) div 2. Искомый корень будет в одном из промежутков: [a; ab] и [ab; b]. Возникает вопрос: в каком промежутке находится искомый корень? Проще всего проверить таким образом. Натуральное число, из которого извлекаем корень m-й степени, надо разделить т — \ раз на среднее число промежутка [а; Ь\ т. е. на ab. Если частное меньше чем aby то корень будет в промежутке [a; ab\ в противном случае — в промежутке (ab; b). Промежуток, содержащий корень, опять разделим пополам. Так будем делить до тех пор, пока оба конца интервала примут значения смежных (рядом стоящих) чисел. Тогда искомым корнем будет левый конец промежутка (так как концы промежутка подбирали так, что а<:У<Ь).
Как подобрать начальный промежуток, т. е. концы промежутка? Так как условились корень извлекать только из натуральных чисел (х>0), то ясно, что а=\. Число b возьмем такое, что Ь = х-\-\у потому, что, извлекая корень первой степени (не забудем и про такую возможность), результат должен быть равен х. Составим функцию для извлечения корня любой степени из натуральных чисел: Данным методом можно не только извлекать корни, но и решать любые алгебраические уравнения. © Составьте процедуру для определения целой части и остатка кубического корня из натурального числа. © © Составьте функцию rootmodm для определения остатка корня m-й степени из натурального числа. 9. Извлечение квадратного корня из натуральных чисел Мы сталкиваемся с квадратными корнями значительно чаще, нежели с корнями какой-либо другой степени. Поэтому во многих языках программирования имеется стандартная функция извлечения квадратного корня. В языке Паскаль и во множестве других языков параметром этой стандартной функции может быть не только действительное, но и
целое число, а результатом — только действительное число. Например: sqrt (4.0) = 2.0; sqrt (4) = 2.0; sqrt (2.0)= 1.414; sqrt (2)= 1.414. Из результата, выраженного в действительных числах, нетрудно получить результат в целых числах — следует только отбросить дробную часть числа. Например: trunc (sqrt (4)) = 2; trunc (sqrt (2))=1. Часто эти стандартные функции используются, когда надо извлечь натуральный квадратный корень. Так как операции с действительными числами выполняются приближенно, мы не уверены, что всегда получим верный результат. Кроме того, не очень логично в задаче, в которой и исходные данные, и результат — целые числа, использовать более сложный и менее надежный тип данных — действительные числа. Будем извлекать квадратный корень тем же самым методом, каким извлекается корень т-й степени из натурального числа (см. задачу 8). Приведем законченную функцию извлечения квадратного корня:
Часто надо бывает найти остаток при извлечении квадратного корня из натуральных чисел. Составим функцию, находящую его: 10. Арифметический квадрат Известно, что многие насекомые ориентируются по солнцу. Предположим, что у нас есть поверхность в форме квадрата, поделенная на клетки. В одной из угловых клеток сидит паук, а солнце светит из противоположного угла (рис. 3). Паук идет по направлению к солнцу. Из одной клетки в другую он может переходить только через отверстия, направленные снизу вверх или справа налево. Меняя направление движения, паук может пройти в противоположный угол квадрата различными путями. Записав число путей ведущих в указанную клетку, получим соответствующую таблицу 1. Эта таблица называется арифметический квадрат [20J. Рис. 3. Один из возможных путей паука к солнцу. Таблица I Арифметический квадрат 11 1 1 1 1 12 3 4 5 6 13 6 10 15 21 1 4 10 20 35 56 1 5 15 35 70 126 1 6 21 56 126 252
Из таблицы мы видим, что каждое записанное в ней число равно сумме двух чисел: находящегося непосредственно сверху и ближайшего слева. Представив арифметический квадрат в виде массива, мы можем легко составить процедуру нахождения значений элементов квадрата: Включив процедуру в программу и написав обращение к ней, мы получим результат — арифметический квадрат, с которым можно будет производить любые действия, в частности печать. Если арифметический квадрат нужен только для того, чтобы его напечатать, то можно составить процедуру или программу, которая потребует меньше места в памяти ЭВМ. Дело в том, что элементы квадрата вычисляются по очереди. Следовательно, можно сразу печатать только что вычисленный элемент. Тогда в памяти будет храниться только одна строка квадрата, поскольку ее элементы нужны для вычисления элементов другой (нижней) строки. Составим программу печати арифметического квадрата размером с шахматную доску:
П. Треугольник Паскаля Числа расположены следующим образом: 1 1 1 1 2 1 13 3 1 14 6 4 1 1 5 10 10 5 1 Первый и последний члены в каждой строке равны 1, а каждый из прочих членов равен сумме двух ближайших находящихся сверху чисел. Такое расположение чисел называется треугольником Паскаля, хотя до Б. Паскаля (Pascal, 1623— 1662) оно было известно итальянскому математику Н. Тар- талье (Tartaglia, 1500—1557), а еще раньше этот треугольник был описан в работах арабских математиков. Таблица 2 Треугольник Паскаля, представленный в виде массива array [1..5] of array f —5..5I of Integer -5-4-3-2-1012345 111 0 0 0 0 0100000 2 0 0 0 0 1010000 3 0 0 0 1 0201000 4 0 0 1 0 3030100 5 0 1 0 4 0604010
Естественно представить треугольник Паскаля в виде двумерного массива так, как это показано в таблице 2. Места, в которых нет чисел, в массиве помечаются нулями. Определим такой массив и составим процедуру вычисления треугольника Паскаля: Элементы треугольника Паскаля вычисляются очень просто. Однако составленная процедура неэкономна. Массив требует много места в памяти, а используется она нерационально: имеется много пустых элементов, помеченных нулями. Поэтому попытаемся представить в массиве элементы треугольника Паскаля более экономно: каждую строку треугольника начнем писать с самого начала строки массива. В этом случае достаточно будет вдвое меньшего массива. Определим его: type треуг = array [1..л] of array [l../i] of integer Обратим внимание на то, что в i-и строке треугольника Паскаля / элементов, а сами элементы /-й строки вычисляются суммированием элементов (/—1)-й строки так, как это показано на рисунке 4. 4-# строка 5-я строка Рис. 4. Схема вычисления пятой строки треугольника Паскаля.
Составим новую процедуру: Для того чтобы напечатать треугольник Паскаля, необходимо снова развести «сжатые» в массиве элементы. Составим процедуру печати: Поскольку в треугольнике Паскаля должны быть оставлены пробелы между числами, то для печати каждой строки мы выделяем вдвое больше позиций, нежели занимает самое длинное число (число, в котором больше всего цифр). Его длина устанавливается функцией чсцф, описанной в задаче 34. Если на месте чисел треугольника Паскаля, которые без остатка делятся на какое-нибудь число ky напечатать символ пробела, а на месте всех остальных чисел — букву М, то мы получим интересный симметричный узор. Составим процедуру, в соответствии с которой производится такая печать, и включим ее вместе с процедурой паск в программу, печатающую узор, представленный на рисунке 5.
Рис. 5. Орнамент треугольника Паскаля.
© Составьте программу, которая сохраняла бы только одну строку треугольника Паскаля — вычисляла бы по очереди все строки и тотчас же печатала бы их. 12. Треугольник Исходные данные — три натуральных числа, выражающих длины отрезков. Требуется определить, можно ли из этих отрезков построить треугольник. Составим логическую функцию для решения этой задачи. Будем опираться на известное положение: из трех отрезков можно построить треугольник тогда и только тогда, когда сумма длин любых двух отрезков превосходит длину третьего: Эту задачу можно решить и в случае, если используются исходные данные вещественного типа. Тогда во всех функциях целый тип следует заменить на вещественный тип. Поскольку операции с действительными числами выполняются приближенно, то в пограничных случаях можно получить неверный результат. Например, если \a-\-b — с\ =е (где е — весьма малое число, сравнимое с погрешностями, которые допускает ЭВМ), то результат функции может оказаться каким угодно.
© Составьте программу, которая определяла бы и вид треугольника (если данные отрезки позволяют его построить) равносторонний, равнобедренный, разносторонний, прямоугольный, тупоугольный, остроугольный. © © Исходные данные — натуральные числа min и max. Составьте программу, которая находила бы все возможные треугольники, длины сторон которых (a, b и с — натуральные числа) удовлетворяли бы неравенству min ^ а ^ Ь ^ с ^ max. Длины сторон каждого треугольника печатайте на отдельной строке. © 0 © Составьте функцию, которая определяла бы, можно ли из данных четырех отрезков (a, 6, с и d — натуральные числа) составить прямоугольник. 13. Пифагоровы числа Сумма квадратов длин катетов а и Ь прямоугольного треугольника равна квадрату длины гипотенузы с: а2 + Ь2 = с2. Тройка натуральных чисел, удовлетворяющих этому равенству, называется Пифагоровыми числами. Например, 3,4 и 5 являются Пифагоровыми числами, поскольку 32 + 42 = 52. Эта тройка Пифагоровых чисел была известна уже в Древнем Египте. Говорят, что строители пирамид, чтобы начертить прямой угол, пользовались веревкой, разделенной на 12 равных частей. Сгибая ее, получали треугольник, стороны которого составляли 3, 4 и 5 частей. Составим программу для нахождения и печати всех Пифагоровых чисел, не превышающих 20:
Тройка Пифагоровых чисел, не имеющих общих делителей, называется основной. Умножив каждое из чисел, входящих в основную тройку, на какое-нибудь натуральное число, снова получим тройку Пифагоровых чисел, называемую производной тройкой. Например: 3 4 5 основная тройка Пифагоровых чисел 6 8 10 1 9 12 15 \ производные тройки Пифагоровых чисел 15 20 25 J Приведенная программа пифагор печатает все тройки: и основные и производные. Если бы мы искали Пифагоровы числа на большем интервале, то интереснее было бы печатать только основные тройки чисел. Проверить, является ли тройка основной, можно, используя функцию наибольшего общего делителя под (см. задачу 21) или функцию взаимно простых чисел взаимпрост (см. задачу 22). Кроме того, в программе пифагор много времени тратится на поиск гипотенузы треугольника — по очереди перебираются все числа. Мы бы нашли гипотенузу прямоугольника быстрее, если бы использовали функцию извлечения квадратного корня из натуральных чисел sqroot (см. задачу 9). При помощи названных функций составим программу, которая будет находить основные тройки Пифагоровых чисел, не превышающих max:
В обеих программах мы искали Пифагоровы числа, по очереди перебирая все тройки чисел и проверяя, удовлетворяют ли они указанным условиям. Можно было бы сделать программу более эффективной, если бы мы знали более быстрый способ получать тройки чисел. Такой способ есть [13] — все основные тройки Пифагоровых чисел можно получить по следующим формулам: где и и v — взаимно простые нечетные натуральные числа и u>v. Составим программу, используя эти формулы:
© Составьте программу, которая будет находить все решения уравнения x2 + y2 = zn (n — исходное данное) в промежутке [2; 100]. 0 0 Треугольники, у которых длины сторон и площадь представляют собой целые числа, называются треугольниками Герона. Например, таков треугольник, длины сторон которого равны 13, 14 и 15, а площадь — 84. Составьте функцию, определяющую, является ли треугольник, длины сторон которого а, 6, с, треугольником Герона. © © © Треугольников Герона очень много. Составьте программу для нахождения самых интересных треугольников Герона, у которых: а) стороны выражены соседними числами (например, длины сторон таких треугольников 3, 4, 5 или 13, 14, 15), б) площадь равна периметру (например, таков прямоугольный треугольник, длины сторон которого 6, 8, 10). В обоих случаях ищутся треугольники, длины сторон которых находятся в указанном интервале. 14. Разрезание прямоугольника на квадраты Дан прямоугольник, длины сторон которого а и Ь представляют собой натуральные числа. Составим программу, которая будет находить, на сколько квадратов, стороны которых выражены натуральными числами, можно разрезать данный прямоугольник, если от него каждый раз отрезается квадрат максимально большой площади. Например, прямоугольник 7X12 следовало бы разделить так, как это показано на рисунке 6. Было бы хорошо, если бы ЭВМ напечатала ре зультаты таким образом: ДАН ПРЯМОУГОЛЬ НИК: 7*12 КВАДРАТЫ: 7*7 1 5*5 1 2*2 2 1*1 2 ВСЕГО КВАДРАТОВ: Рис. 6. Разрез прямоугольника 7X12 на квадраты.
Нетрудно видеть, что, для того чтобы найти число квадратов, надо большее число (более длинную сторону) разделить на меньшее. Законченная программа выглядит так: Теперь решим более простую задачу. Составим функцию для нахождения числа квадратов, на которые можно разрезать прямоугольник. Составить функцию можно, пользуясь текстом предыдущей программы: объявить параметрами функции исходные данные (положим, что а^Ь), а также исключить оператор печати. Однако, хорошенько подумав, можно составить намного более простую рекурсивную функцию. Вот она:
15. Равновеликие прямоугольники Составим программу для нахождения всех прямоугольников указанной площади (площадь — исходное данное, выраженное натуральным числом), стороны которых — натуральные числа. Например, если площадь равна 12, то получим три разных прямоугольника: 1X12 2X6 3X4 Будем считать одинаковыми прямоугольники, получающиеся один из другого, если поменять ребра местами. Обозначим площадь буквой р, а стороны прямоугольника — буквами а и Ь. Приравнивая одну сторону (например, а) к 1, 2, 3, 4 и т. д. до тех пор, пока а^Ь (Ь получим, разделив площадь на а), мы сможем получить все прямоугольники, площади которых равны р. На языке Паскаль мы записываем это так: Поскольку всегда можно образовать по крайней мере один прямоугольник указанной площади, то лучше использовать цикл repeat. Приведем законченную программу:
© Исходное данное — натуральное число v. Составьте программу для нахождения всех различных прямоугольных параллелепипедов, объем которых равен v, а ребра выражены натуральными числами. Параллелепипеды, получающиеся один из другого, если поменять ребра местами, считаются одинаковыми. 16. Равновеликие треугольники Рассказывают, что английская королева Виктория, придя в восторг от книги Льюиса Кэрролла (Carroll) «Алиса в стране чудес», однажды приказала принести ей другие произведения этого автора. Как же удивилась королева, когда ей вручили несколько математических трудов! Оказалось, что эту чудесную сказочную книгу под псевдонимом Л. Кэрролл написал профессор математики Оксфордского университета Чарльз Латвидж Доджсон (Dodgson, 1832— 1898). В его дневнике мы находим интересную задачу, которую и попытаемся решить. Ч. Л. Доджсон пишет, что он тщетно трудился, пытаясь найти хотя бы три прямоугольных треугольника равной площади, у которых длины сторон были выражены натуральными числами. Составим программу для решения этой задачи (будем искать треугольники возможно меньшей площади). Следовало бы просмотреть прямоугольные треугольники, стороны которых выражены натуральными числами, и установить, найдутся ли хотя бы три треугольника равной площади. Однако таких треугольников может быть много. Поэтому мы будем исследовать площадь треугольника, т. е. проверять, могут ли данную площадь иметь хотя бы три треугольника, стороны которых — натуральные числа. По-
скольку площадь прямоугольного треугольника равна 1/2 a-b (где а, Ь — катеты), то удобнее исследовать удвоенную площадь s = a-b. В этом случае значение S будет любым натуральным числом: S=l, 2, 3, ... Итак, переформулированная задача звучала бы так: установить, можно ли представить рассматриваемое натуральное число в виде произведения двух натуральных чисел по крайней мере тремя различными способами. Кроме того, следует еще проверить, может ли каждая из пар чисел представлять катеты удовлетворяющего условию треугольника, т. е, выражена ли гипотенуза натуральным числом. Например, удвоенную площадь, равную 12, можно представить в виде произведения двух чисел тремя способами: 1X12 2X6 3X4 Однако в треугольниках, у которых а=1, 6 = 12 и а = 2, 6 = 6, гипотенузы с = -^\2-\-122 и c = V22^f-62 не являются натуральными числами. Таким образом, число 12 не будет представлять собой удвоенную площадь, удовлетворяющую условию задачи. Подчеркнем, что следует отбросить те треугольники, у которых катеты меняются местами. Алгоритм решения задачи очень похож на алгоритм «Равновеликие прямоугольники» (см. задачу 15). Приведем схему программы:
Детализируем действия, записанные в первом прямоугольнике. Нетрудно проверить, действительно ли а^Ь и a*6=s. Гипотенуза вычисляется по теореме Пифагора, так как ищутся прямоугольные треугольники. Проверив, выражена ли гипотенуза натуральным числом, применим функцию sqrootmod (см. задачу 9). Посмотрев на приведенную схему программы, мы видим, что цикл repeat выполняется до тех пор, пока мы не найдем хотя бы три интересующих нас треугольника (до тех пор, пока значение k не станет равно 3). А что будет, если такие треугольники вообще не существуют? Раз их не нашел Л. Кэрролл, может быть, и ЭВМ не найдет? Из осторожности напишем еще дополнительное условие s = maxint, в соответствии с которым не следует проверять треугольники, удвоенная площадь которых превышает максимально допустимое натуральное число. Если мы найдем три искомых треугольника (k = 3), то останется только их напечатать. Поскольку мы знаем площадь этих треугольников, мы без труда найдем их, повторив действия, аналогичные только что произведенным. Можно было бы, найдя какой-нибудь треугольник, удовлетворяющий условию задачи, запомнить длины его сторон, но экономнее (подумайте почему!), зная площадь, заново вычислить стороны. Проведя такую корректировку, напишем законченную программу:
Выполнив эту программу, ЭВМ напечатала такие три треугольника: 15 112 113 24 70 74 40 42 58 0 Измените программу так, чтобы она находила и печатала не только три треугольника наименьшей площади, но и все прочие треугольники, площадь которых не превышает s (s — исходное данное) и которые удовлетворяют вышеуказанному условию. 17. Уравнение fl3 + 63 = c3 + d3 Вот что рассказывают об индийском математике С. Ра- мануджане (Ramanujan, 1887—1920). Как-то раз больного математика навестил его друг-европеец. Гость пожаловался,
что прибыл в кэбе с очень скучным номером, и сообщил четырехзначное число. Рамануджан ему возразил: названное число очень интересно. Это наименьшее натуральное число, которое можно представить в виде суммы кубов двух натуральных чисел не единственным способом. Составим программу, которая бы нашла это число и напечатала бы две пары чисел, сумма кубов которых равна найденному числу. Иными словами, требуется найти наименьшее натуральное решение уравнения a* + b3 = c3 + d\ причем афс и аф(1. При прочтении условия задачи возникает мысль проверить подряд все числа, пока не будет найдено решение. Однако такое простейшее решение нерационально. Ведь каждое проверяемое число надо будет представлять в виде суммы двух слагаемых и проверять, не являются ли эти слагаемые кубами каких-нибудь чисел. Поскольку число N можно разбить на два слагаемых N— 1 способом то, чтобы проверить N первых чисел, необходимо произвести ' ~ '~— действий. Таким образом, число действий пропорционально квадрату числа, являющегося решением; поэтому, если решением является большое число (а какое число будет решением в действительности, мы не знаем, составляя программу), даже быстродействующая вычислительная машина будет решать эту задачу слишком долго. Будем искать лучшее решение, рассмотрев аналогичную, но более простую задачу. Вместо суммы кубов возьмем сумму квадратов, т. е. будем искать наименьшее число, равное двум суммам, каждая из которых является суммой квадратов двух натуральных чисел, различных в первом и втором случае. Составим таблицу сумм квадратов для первых одиннадцати натуральных чисел (табл. 3). Левую нижнюю часть таблицы мы не заполняли из-за того, что при перемене мест слагаемых мы получили бы ту же самую сумму. Чтобы сделать разбор задачи (а позднее и составление программы) более простым, упорядочим слагаемые в парах таким образом, чтобы первое слагаемое не превосходило второе {а^Ь). Выберем из таблицы суммы квадратов и запишем их в порядке возрастания: 2, 5, 8, 10, 13, 17, 18, 20, 25, 26, 29, 32, 34, 37, 40, 41, 45, 50, 50, 52, ,..
Наименьшее число, которое повторяется в этой последовательности дважды, и будет искомым решением. Таким числом в данной последовательности является 50. Из таблицы 3 находим, что 12 + 72 = 50 и 52 + 52 = 50. Таблица 3 Таблица чисел а2-\-Ь2 b \ а 12345678 9 10 11 1 2 5 10 17 26 37 50 65 82 101 122 + 2 8 13 20 29 40 53 68 85 104 125 + 3 18 25 34 45 58 73 90 109+ 130 4 32 41 52 65 80 97 116+ 137 5 50 61 74 89 106* 125 146 6 72 85 100 117+ 136 157 7 98 113+ 130 149 170 8 128+ 145 164 185 9 162 181 202 10 200 221 11 242 Таким образом, для того чтобы решить задачу, надо уметь найти члены упомянутой последовательности, следующие по порядку друг за другом. Первые два равных члена этой последовательности и будут представлять собой искомое решение. Предположим, что у нас есть процедура, посредством которой мы по предъявлении любого члена последовательности могли бы получить другой, непосредственно следующий за ним член этой последовательности. Тогда для решения задачи мы бы могли составить такую схему программы:
Эта программа печатает не вполне исчерпывающий результат. Следовало бы напечатать не только сумму квадратов, но и сами квадраты, а еще лучше — числа, возводимые в квадрат. Эти числа мы могли бы найти из суммы квадратов, но их можно получить и проще: требуется, чтобы процедура новое производила действия не с суммами, а с возводимыми в квадрат числами. Внесем изменения в программу и в заголовок процедуры новое] для вычисления суммы квадратов двух чисел введем функцию f: Остается составить процедуру новое, которая будет находить новую пару чисел. Проще всего было бы просмотреть все пары чисел и из них выбрать ту, которая удовлетворяет предъявляемым требованиям. Поскольку таких пар бесконечно много, то попы-
таемся ограничить область, в которой может находиться пара, удовлетворяющая условию. Заглянем в таблицу 3. Допустим, что старая пара: а = 5, Ь = 9. Сумма их квадратов /(5, 9) =106 в таблице помечена звездочкой. В каждой строке таблицы (а^.Ь) можно выделить только по одному кандидату на новую пару — сумму квадратов. Они помечены знаком «плюс». Числа, находящиеся слева от 106, не подходят из-за того, что они меньше 106, а справа — больше, чем обозначенная сумма. В строках, номера которых больше b (в данном случае больше 9), также не стоит искать нового кандидата, поскольку он будет больше, нежели уже подобранные. Обнаружив самого подходящего кандидата, т. е. сумму квадратов двух чисел, получим новую пару чисел. Из этого рассуждения вытекает, что новая пара (с, d) должна удовлетворять одному из следующих условий: 1) 1<с<а и d>b\ 2) a + l<c<d<6. Приведем схему процедуры, ищущей новую пару: Запишем на языке Паскаль действия, заключенные в прямоугольники:
Остается только соединить все части, и мы получим законченную программу, решающую уравнение а2-\-Ь2 = = c2-\-d2. Чтобы решить задачу, сформулированную вначале, т. е. найти наименьшее число, служащее решением уравнения a3 + ft3 = c3 + d3, достаточно только изменить функцию / — вместо суммы квадратов вычислять сумму кубов: f: =a*a*a-\-b*b*b. Обратим внимание на то, что аналогичным образом мы могли бы получить и решения уравнений a4 + 64 = c4 + d4, аъ + Ьъ = съ + (Г и т. д. Законченная программа выглядит так:
Выполнив эту программу, ЭВМ напечатала 1 12 9 10 1729 Значит, число, которым восхитился С. Рамануджан, было 1729, так как 1729=103 + 93=123+13. © Эту задачу можно решить подобно тому, как решались задачи о равновеликих прямоугольниках или треугольниках (см. задачи 15 и 16). Воспользовавшись идеями упомянутых задач, составьте другой вариант программы кубы. Какой из вариантов эффективнее? 18. Задача Антанаса Баранаускаса Автор поэмы «Аникщайский бор» А. Баранаускас (1835— 1902) был не только поэтом, но и математиком-любителем. Особенно интересовался он теорией чисел: он исследовал свойства простых чисел. Приведем одну из самых любимых задач его детства, над которой, как он сам позднее писал, бился недели две, пока не нашел решения: сколько можно купить быков, коров и телят, платя за быка 10 р., за корову — 5 р., а за теленка — полтинник, если на 100 рублей надо купить 100 голов скота? Условие этой задачи можно описать при помощи системы уравнений: / 10 6 + 5 /с + 0,5 г=100, \ б + /с + г=100, где б — число быков; к — число коров; т — число телят. Обе части первого уравнения умножим на 2 (т. е. деньги будем считать в полтинниках): /20 б+Ю /с + г = 200, \б + к + т=Ю0. Мы имеем систему двух уравнений с тремя неизвестными. В общем случае такая система уравнений имеет бесконечное число решений. Однако в данном случае число решений конечно. Во-первых, решениями могут быть только неотрицательные числа. Во-вторых, возможные значения неизвестных ограничены и сверху: за 100 р. нельзя купить более 10 быков (даже если покупать только одних быков), более 20 коров и более 200 телят.
Таким образом, 0<б<10, 0<к<20, 0<г<200. Поэтому задачу можно без труда решить, перебрав все возможные значения неизвестных и проверив, удовлетворяют ли они уравнению. Чтобы программа была более экономной, число телят, пользуясь вторым уравнением, выразим через два других неизвестных: т=Ж—(б + к) и будем проверять, перебирая значения переменных б и к, только первое уравнение. Мы составили программу: Выполнив эту программу, ЭВМ напечатала такие результаты: БЫКОВ: 1 КОРОВ: 9 ТЕЛЯТ: 90 Для этой задачи можно написать более экономную программу: из внутреннего цикла можно вынести часть действий, а кроме того, уменьшить число повторений циклов, поскольку можно доказать, что 0<б<5, 0</с<11.
Однако тогда программа станет несколько менее наглядной, а экономия машинного времени будет невелика, поскольку программа рассчитана на однократное выполнение. © Составьте программу для нахождения всех натуральных решений уравнения i3 + j3 + k3 = z3 в интервале [1; 20]. Решения, которые получаются, если поменять местами /, /, k, следует отбросить. Каждое решение уравнения (четыре числа) напечатайте на отдельной строке. 19. Считалка Многие игры, например прятки, салочки, дети начинают со считалок. Для того чтобы выяснить, кому придется водить, кто-либо из играющих произносит недлинный стихотворный текст — считалку. Играющий, на которого попадает последнее слово текста, выходит из круга. Кто последним останется в кругу, тот и должен водить. Предположим, что в кругу стоит п детей, а в считалке т слов. Составим программу, которая напечатает номера детей в том порядке, в каком они выходят из круга. Детей в кругу опишем как множество var tcpyaistt of L.nmax где константа птах — максимальное число играющих. Перед тем как начинать считалку, имеем следующий круг детей: круг: = [1 ..я] Когда i-й ребенок выходит из круга, круг: = круг — [/] Считалка заканчивается только тогда, когда в кругу никого не останется, т. е. круг=[ ] Если номер играющего, только что вышедшего из круга, /, то следующим выходит играющий, номер которого вычисляется следующим образом:
Когда дети в кругу от 1 до я-го, то переход от одного игрока к другому можно выразить таким оператором: i:=i mod n -f 1 Однако может случиться так, что играющий, номер которого следует за i (/+1 или 1, если / = п), уже вышел из круга. В этом случае номер вышедшего из круга участника надо пропустить: Приведем законченную программу: © Б. Кордемский приводит [12] такую задачу: коту снится, что его окружили тринадцать мышей. Двенадцать из них серые, а одна белая. Слышит кот, что кто-то говорит ему: «Мурлыка, ты можешь съедать каждую тринадцатую мышку. Считай их по кругу в одном направлении. Белую мышку ты должен съесть последней». Задумался кот: с какой мышки начинать счет? Составьте программу для решения этой задачи.
20- Дележ Аня нарвала яблок и поровну раздала своим сестрам Оле, Маше и Тане, а что осталось, съела. Оля свои яблоки поделила между тремя сестрами, а что осталось, съела. То же самое сделали Маша и Таня. Сколько яблок оказалось у каждой сестры? Составим программу для решения этой задачи. Каждую из четырех раздач можно выразить посредством процедуры, имеющей четыре параметра. Обозначим их именами а, 6, с, d. Это число яблок, которые имеют сестры: до раздачи — при обращении к процедуре и после раздачи — по выполнении процедуры. Процедура очень простая. Составим ее. Будем считать, что первый параметр означает число раздаваемых яблок. Одни и те же параметры соответствуют и исходным данным, и результатам. Остается только включить процедуру в программу:
Обратим внимание на одну интересную деталь: результат для последнего участника дележа всегда будет равен нулю. © Составьте программу для решения задачи о дележе в общем случае, т. е. для дележа яблок между п лицами (п — входное данное). Дележ осуществляется в соответствии с теми же правилами, что и дележ между четырьмя лицами. Укажите число лиц (максимальное число лиц определите при помощи константы), а количество яблок у каждого из них сохраните в массиве. 21. Наибольший общий делитель Алгоритм получения наибольшего общего делителя, называемый алгоритмом Евклида, изложил в своей знаменитой работе «Начала» Евклид (330—320 гг. до н. э.). Он остался едва ли не самым популярным алгоритмом и в эпоху электронно-вычислительных машин. Его можно обнаружить во многих учебниках программирования. Уже десять лет, как он изображается на обложке журнала «Программирование». Понадобится он и нам, поскольку функцию наибольшего общего делителя двух чисел мы будем использовать во многих задачах. Приведем два варианта функции (подробнее см. [1]):
Оба параметра функции должны представлять собой неотрицательные числа. Когда оба параметра равны нулю, их наибольший общий делитель обозначаем нулем. © Исходные данные — последовательность натуральных чисел. В конце последовательности — нуль. Составьте программу для нахождения наибольшего общего делителя всех членов этой последовательности. Наибольшим общим делителем последовательности считается наибольшее натуральное число, на которое делятся все члены последовательности. 22. Взаимно простые числа Числа, у которых наибольший общий делитель равен единице, называются взаимно простыми. Составим функцию, устанавливающую, являются ли два числа взаимно простыми: Эту функцию мы применим в задаче о шестеренках. Одна из важнейших характеристик пары шестеренок — это соотношение между оборотами шестеренок, например 3:1, 2:5, которое обратно соотношению числа зубцов. Наиболее прочной шестеренкой является та, у которой все зубцы изнашиваются равномерно. А для того чтобы все зубцы стирались равномерно, каждый зубец одной шестеренки должен с одинаковой частотой соприкасаться со всеми зубцами другой шестеренки. Нетрудно убедиться, что это условие удовлетворяется, когда числа зубцов двух шестеренок являются взаимно простыми. Соотношение всегда можно упростить так, чтобы его члены были взаимно простыми (например, соотношение 9:12 можно заменить на соотношение 3:4). Между тем соответствующим образом уменьшить число зубцов в шестеренках можно не всегда, посколь-
ку число зубцов не может быть слишком мало (ясно, что, например, не бывает шестеренок, имеющих 1 или 2 зубца). Однако можно найти выход, дополнив такую передачу третьей паразитической шестерней (рис. 7), у которой число зубцов является взаимно простым с числом зубцов каждой из двух других шестеренок. Составим функцию, значением которой будет наименьшее число зубцов паразитической шестерни z (z^ 10) при данных двух других числах — количестве зубцов двух (истинных) шестеренок. Если данная пара шестеренок удовлетворяет условию равномерного износа, то паразитическая шестерня не нужна и значение функции должно быть равно нулю: 0 Составьте функцию, которая проверяла бы, являются ли три числа взаимно простыми. © © Исходные данные — передаточное число пары шестеренок и минимальное число зубцов в шестеренке. Требуется составить функцию, которая установит, можно ли подобрать шестеренки, удовлетворяющие условию одинакового износа и имеющие число зубцов, не меньшее, чем минимально допустимое. 0 © © В ведущем зубчатом колесе велосипеда а зубцов, а в ведомом — b зубцов. Составьте программу, которая будет вычислять и печатать последовательный ряд из 20 чисел, соответствующих возможному количеству звеньев в ве»
лосипедной цепи, которое удовлетворяло бы условию равномерного износа. Минимальное число звеньев п = а-\-Ь. © © © © В шестеренке А а зубцов, а в шестеренке В Ъ зубцов. По одному зубцу в той и другой шестеренке специально помечено. В данный момент помеченные шестеренки соприкасаются. Составьте функцию, которая вычисляла бы, через какое минимальное число оборотов помеченные зубцы снова (т. е. во второй раз) коснутся друг друга. 23. Наименьшее общее кратное В одной из египетских пирамид на каменной надгробной плите было обнаружено высеченное иероглифическое обозначение числа 2520. Трудно сказать, почему этому числу была оказана такая честь. Быть может, потому, что оно без остатка делится на все натуральные числа от 1 до 10 (является наименьшим общим кратным всех чисел от 1 до 10). Используя функцию наибольшего общего делителя, легко составить функцию для нахождения наименьшего общего кратного двух чисел: Сначала осуществляется деление, а затем — умножение, чтобы уменьшить вероятность переполнения. Применяя приведенную функцию ноку составим программу для печати таблицы наибольших общих кратных всех идущих по порядку натуральных чисел от I до л (п — входное данное):
0 Исходные данные — последовательность натуральных чисел. В конце последовательности — нуль. Составьте программу для нахождения наименьшего общего кратного всех членов ряда. Кратным ряда считается наименьшее натуральное число, которое делится без остатка на все члены ряда. 0 © Составьте функцию, значением которой было бы наименьшее общее кратное всех натуральных чисел от 1 до п включительно (п — параметр функции). © © 0 Составьте программу для нахождения максимального вмещающегося в ЭВМ числа, которое без остатка делится на как можно большее количество следующих друг за другом натуральных чисел. 24. Бильярд Замечено, что математики любят играть на бильярде. Возможно, это потому, что траекторию шара, отскакивающего от краев бильярдного стола, можно вычислить достаточно точно. Приведем задачу, тесно связанную с бильярдом. Предположим, что дан прямоугольник, длины сторон которого выражаются натуральными числами а и Ь. Из одной вершины прямоугольника проводится линия, которая составляет угол в 45° со сторонами прямоугольника. Дойдя до стороны прямоугольника, линия, не пересекая ее, изламывается под углом в 90°. Дойдя до другой стороны, она снова изламывается под углом в 90° и т. д. до тех пор, пока она не дойдет до какой-либо из вершин прямоугольника. (Убедитесь, что это произойдет во всех случаях, когда
Рис. 8. Схема установления числа отрезков траекторий бильярдного мяча, вычитая короткую сторону. длины сторон прямоугольника выражены натуральными числами.) Получающаяся ломаная напоминает траекторию бильярдного шара на прямоугольном столе. Составим функцию бильярд, которая будет устанавливать, из скольких отрезков состоит ломаная (концы отрезков должны находиться на сторонах прямоугольника). Можно составить эту функцию несколькими способами. Каким образом производятся вычисления, показано на рисунке 8. (Чтобы не загромождать чертеж, мы не провели ломаную до конца.) Длинную сторону заданного прямоугольника обозначим max, короткую — mln. Тогда функция бильярд будет выглядеть следующим образом:
Рис. 10 Разложение траектории бильярдного мяча. Тогда ломаная, вместо того чтобы отражаться от короткой стороны, пересекает ее. Получаются отрезки одинаковой длины. Их число равно (убедитесь!): нок (min, max) div min Чтобы получить упоминаемое в задаче число отрезков, остается прибавить внутренние короткие отрезки, которых всего имеется нок {min, max) div max—\ Значит, траектория бильярдного шара состоит из нок (min, max) div т1п-\-нок (min, max) div max—1 отрезков. Поскольку, поменяв местами длины сторон min и max, мы просто поменяем местами первые два слагаемых (при перемене мест слагаемых сумма не меняется), то приведен- Рис. 9. Пример траектории бильярдного мяча. Значительно лучший вариант функции можно составить, если использовать наименьшее общее кратное длин сторон — нок (см. задачу 23). Разберем пример, приведенный на рисунке 9. Развернем этот чертеж таким образом, чтобы ломаная шла только слева направо (рис. 10).
ную выше формулу можно упростить, если не обращать внимания на то, какая из сторон длиннее: нок (a, b) div а + нок (а, Ь) div b—\ Таким образом, вся функция выглядит так: 25. Делители Самый простой способ найти все делители числа п — это проверить по очереди делимость п на каждое из чисел 1, 2, 3, ..., п. Легко убедиться, что в интервале [п div 2 + 1; п — 1 ] делителей числа п нет. Для нахождения делителей числа п составим такую процедуру: Например, когда п = 30. Выполнив эту процедуру, ЭВМ напечатает следующие результаты — делители числа п: 1 2 3 5 6 10 15 30 Обратим внимание на то, что, для того чтобы найти делитель числа л, достаточно обнаружить делители, не превышающие sfn. Все остальные делители получаются в результате деления числа п на найденные делители. Например, если я = 30, то достаточно найти делители 1, 2, 3, 5 (натуральный квадратный корень из 30 равен именно 5), а все прочие делители получаем следующим образом:
30 div 1=30; 30 div 2=15; 30 div 3=10; 30 div 5 = 6. Составим процедуру, которая будет находить только что рассмотренным способом делители любого данного числа. При составлении можем использовать либо цикл for (в этом случае придется для извлечения квадратного корня из натуральных чисел использовать функцию sqroot — см. задачу 9), либо цикл while. Выберем последнюю возможность: Чтобы не печатать два одинаковых делителя, когда число является точным квадратом (например, 4 и 4, когда д=16), следует ввести дополнительный условный оператор: if d*d = n then write (d) Эта процедура эффективнее, нежели приведенная выше, поскольку цикл выполняется меньшее число раз. Однако она печатает результаты в другом порядке, нежели предыдущая. Например, когда п = 30, результаты процедуры будут напечатаны следующим образом: 1 30 2 15 3 10 5 6 Чтобы делители были напечатаны в порядке возрастания, надо было бы печатать только делители от 1 до У/г и запоминать их — сохранять в массиве или в файле. Все прочие делители можно получить (или сразу напечатать), разделив число п на каждый из имеющихся в памяти делителей, начиная с конца (прежде всего надо делить на последний из имеющихся в памяти делителей и т. д.). Однако этот метод обладает недостатком: мы не можем заранее определить размер массива (предельный), поскольку
мы не знаем, сколько будет делителей. А просмотреть файл в обратном порядке достаточно сложно. Еще один способ запомнить значения и позже использовать их в обратном порядке — это рекурсия. Составим рекурсивную процедуру: Эта процедура печатает первый найденный делитель d и запоминает его двойника — число п div d. Если двойник не равен делителю, то снова происходит рекурсивное обращение к той же самой процедуре. Чтобы при очередном обращении к процедуре обнаружить делитель, надо при каждом новом обращении указывать, с какого места начинать поиск делителей. Для этой цели служит второй параметр процедуры. Нецелесообразно требовать, чтобы пользователь процедуры при обращении к ней должен был каждый раз писать одно и то же значение второго параметра. Поэтому надо «спрятать» от пользователя второй параметр. Сделаем это, заключив приведенную процедуру в другую процедуру, в которой есть только один параметр:
Теперь, когда процедура дел спрятана от пользователя и он не видит ее параметров, можно сократить эту процедуру, добавив еще один параметр: © Составьте функцию, находящую, сколько делителей имеет данное натуральное число. Например, когда дано число 10, значение этой функции должно быть 4, поскольку у числа 10 четыре делителя: 1, 2, 5, 10. © © Составьте функцию, которая будет находить сумму делителей данного натурального числа. 26. Простые числа Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число. Хотя многие задачи, связанные с простыми числами, формулируются достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не
открыты. Это побудило Г. Вейля (Wayl, 1885—1955) так охарактеризовать простые числа: «Простые числа — это такие существа, которые всегда склонны прятаться от исследователя». Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются ЭВМ. Это может представить интерес для любителей рекордов. Мы не будем гнаться за рекордами, а только продемонстрируем, как составить программу, которая будет проверять, является ли число простым. Самый простой путь решения этой задачи — проверить, имеет ли данное число п (п^2) делители в интервале [2; п — \). Учитывая, что все четные числа, делящиеся на 2, являются составными и что в интервале [п div 2 + 1; п — 1J не могут находиться делители числа я, составим такую функцию: Чтобы найти все простые числа в заданном интервале, следовало бы проверить каждое число, находящееся в данном интервале,— простое оло или нет. Однако для этого машине пришлось бы потратить очень много времени. Более совершенный способ обнаружения простых чисел мы опишем в задаче 29. © Дано простое число. Составьте функцию, которая будет находить следующее за ним простое число (т. е. ближайшее простое число, большее данного,— параметр функции). Например, если дано число 11, то значение функции должно быть 13, если дано 23, то значение 29. Если входное
данное не является простым числом, т. е. не выполняется условие, то значение функции считайте равным нулю. 27. Числа Мерсенна Видный французский физик и популяризатор науки М. Мерсенн (Mersenne, 1588—1648) заметил, что многие простые числа имеют вид 2Р—1; здесь р также является простым числом. Все числа упомянутого вида называются числами Мерсенна. Однако не все числа Мерсенна являются простыми. В течение почти 200 лет математики считали, что число Мерсенна 267 —1 является простым. И только в 1903 г. было доказано, что оно представляет собой произведение двух простых чисел: 193 707 721 и 761 838 257 287. До сих пор неясно, бесконечно много простых чисел. Мерсенна или же их число конечно. Составим программу для нахождения.всех чисел Мерсенна, «умещающихся» в памяти ЭВМ. Приведем схему программы:
Было бы неразумно при каждом новом значении р заново вычислять значение 2Р—1. (Сколько потратим времени на возведение в степень!) Докажем, что каждое следующее число Мерсенна мы можем получить таким образом: удвоить имеющееся число Мерсенна и прибавить 1. В самом деле, 2p+i _ 1 =2^.2-1 =2 (2'-1)+1. имеющееся число Мерсенна Новый кандидат в числа Мерсенна подбирается достаточно осторожно, чтобы не было превышено максимально допустимое число maxint. Итак, запишем операторы для нахождения нового кандидата в числа Мерсенна: Законченная программа выглядит следующим образом:
Приведем числа Мерсенна, найденные ЭВМ: 3,7,31,127, 2047, 8191, 131071, 524287, 8388607, 536 870 911, 2 147 483 647. В приведенной программе переменная р принимает значения всех натуральных чисел подряд (2, 3, 4, 5, ...). Однако, чтобы искомое число было числом Мерсенна, р должно быть простым. Поэтому сразу можно отбросить хотя бы четные числа (за исключением 2). Учитывая это, усовершенствуйте программу. 28. Разложение на простые множители Каждое составное число можно единственным способом представить в виде произведения простых чисел. Например: 20 = 2-2.5; 21=3-7. Такое разложение на множители осуществляется следующим образом. Заданное число делится поочередно на следующие друг за другом по порядку простые числа. Если на какое-либо из них оно делится без остатка, то данное простое число является множителем. Чтобы найти другие простые множители, надо полученное частное разделить на это же число или на следующее по порядку простое число и т. д. Поскольку найти простые числа нелегко, то проще сначала делить на 2, а затем — подряд на все нечетные числа. Простое число нельзя разложить на простые множители. Приведем составленную нами программу, которая печатает все простые множители любого данного числа (если число простое, то печатается оно само).
0 Измените программу разложения числа на простые множители таким образом, чтобы результат печатался в такой форме: где и — входное данное; i\, .. ., in — простые множители. © © Составьте функцию для нахождения наименьшего нечетного неравного единице натурального делителя любого заданного числа. 0 © © Составьте функцию, значение которой будет равно числу различных простых множителей заданного числа. 0 © © © Составьте программу для проверки, можно ли заданное натуральное число представить в виде: а) произведения двух простых чисел; б) произведения трех простых чисел; в) квадрата какого-либо простого числа; г) куба какого-либо простого числа. Следует напечатать ответ ДА или НЕТ. 29. Эратосфеново решето Греческий математик Эратосфен (275—194 гг. до н. э.) предложил интересный метод нахождения простых чисел в интервале [2; п]. Он написал на папирусе, натянутом на рамку, все числа от 1 до 1000 и прокалывал составные числа. Папирус стал как решето, которое «просеивает» составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Поясним этот метод. Пусть написаны все числа от 2 до я: 2 3 4 5 6 7 8 9 10 11 12 .. . Первое неперечеркнутое число в строке является простым. Таким образом, 2— простое число. Начинаем «просеивание» с него, перечеркивая все числа, которые делятся на 2, т. е. каждое второе число: 23^507091/) 11 1,2 .. .
Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми: 2 3 £ 5 0 7 £ ? 1/) И 1/2 .. . Естественно будет все числа указанного интервала рассматривать как множество и в дальнейшем из этого множества исключать (отсеивать) все составные числа. Определим тип такого множества: const az = ...; (* верхняя граница интервала*) type «шел = set of 2..n\ (* решето *) Составим процедуру, которая будет формировать множество простых чисел: Обратим внимание на то, что наименьшее число, на которое делится некоторое еще неперечеркнутое число я, не превышает целой части квадратного корня из числа п. Это нетрудно доказать. Попытайтесь сделать это! Поэтому цикл for /:=2 to n div 2 do лучше заменить на цикл for /: =2 to sqroot (n) do (опираясь на описанную в задаче 9 функцию извлечения квадратного корня из натуральных чисел). В языке Паскаль не определено максимально допустимое число элементов множества — все зависит от того, на чем реализуется язык. Чаще всего в целях экономии памяти для всего множества выделяется только одно слово ЭВМ. Тогда число элементов в множестве ограничено числом бит в слове, а их бывает немного (около 30—80). Поэтому,
для того чтобы расширить интервал искомых простых чисел, можно заменить тип множества на тип логического массива или разбить одно большое (математическое) множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Разберем оба случая. Логический массив. Определим тип массива: const п = . . .; (* верхняя граница интервала *) type числа = array [2..n] of boolean; (* решето *) Для каждого числа данного интервала выделяется один элемент массива. Процедура решето должна присвоить значение true тем элементам массива, индексы которых представляют собой простые числа, и значение false — элементам, индексы которых — составные числа. Составим такую процедуру: Это простая процедура. Однако для массива s требуется много места в памяти. Массив множеств. Определим тип массива множеств:
Рис. 11. Множество s: set of 2..13 изображено массивом множеств ss: array [0 .2] set of 0..3. Каждый элемент большого множества set of 2..я должен иметь аналог в массиве 55 малых множеств. Пример соответствия (при п=13 итах = 2у vtnax = 3) показан на рисунке 11. Нетрудно найти и общее выражение зависимости между элементами обоих типов. Элемент i большого множества изображается посредством элемента (/—2) mod (vmax-\-\) малого множества, который находится в элементе массива (/ — 2) div (vmax+l). Чтобы в массиве нашлось место для всякого элемента большого множества, должно выполняться условие (итах-\- 1) * (vmax-\- \)^n — 1. Составим процедуру, результатом которой будет массив ] множеств:
Это более сложная процедура, зато для нее требуется меньше места в памяти, поскольку почти во всех ЭВМ значения, относящиеся к типу множеств, кодируются экономно. Включим эту процедуру в программу, печатающую все простые числа, находящиеся в интервале [2; 10 000]: Когда при решении каких-либо других задач нам понадобится найти простые числа в каком-нибудь определенном интервале, то мы прибегнем к помощи приведенной здесь процедуры решето (в которой используется логический массив), поскольку она проще. Если же требуется экономить память ЭВМ, эту процедуру нетрудно заменить на процедуру рш. 0 Известно новое решето для нахождения простых чисел: 4 7 10 13 16 19 . . . 7 12 17 22 27 32 . . . 10 17 24 31 38 45 . . . 13 22 31 40 49 58 . . .
Это таблица, состоящая из бесконечного множества бесконечных арифметических прогрессий; заметим, кроме того, что каждый член первой прогрессии 4, 7, 10, 13, 16, 19, . . . начинает новую прогрессию. Разностью прогрессий являются поочередно все нечетные числа начиная с 3: di=3, d2 = 5, ^з = 7, d4 = 9 и т. д. Если в этой таблице есть какое-либо число N, то 2N+1 всегда является составным числом. Если же числа N нет, то 2N+1— простое число. Таким образом, подставляя в формулу 2N-\-\ на место N подряд все числа, которых нет в таблице («просеянные» числа), мы можем получить все простые числа, за исключением числа 2. Например, в таблице нет числа N = 5, значит, 2№+1 = = 11 —простое число; в таблице нет числа N = 6, значит, 2N+ 1 = 13 — простое число и т. д. Сообразуясь с этим решетом составьте программу для нахождения и напечатания всех простых чисел от 2 до 20 000. Примените для этого решета массив множеств array [0..199] of set of 0..49 30. Близнецы Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются; например, числа 5 и 7, 11 и 13, 17 и 19 и т. д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, но мы обнаруживаем их все реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему. Составьте программу, которая будет находить все числа близнецы в интервале [2; 1000]:
Выполнив эту программу, ЭВхЭД нашла в первой тысяче целых 35 пар близнецов. Чтобы находить близнецов в большем интервале, следовало бы увеличить константу п. Однако, увеличивая ее, можно быстро превысить пределы возможностей ЭВМ: массив числа не уместится в памяти. Значительно больший числовой интервал можно обследовать при помощи процедуры рш, использующей множества (см. задачу 29). 0 Составьте функцию, которая будет проверять, являются ли числа находящиеся по обе стороны от заданного четного числа, близнецами. 31. Скатерть Улама Однажды математик Станислав Улам (Шат, род. 1909) слушал какое-то очень длинное и скучное сообщение. Желая как-то отвлечься, он разделил лист бумаги на клетки и уже собирался заняться составлением шахматных этюдов, но передумал и, написав в центре 1, начал писать по спирали против часовой стрелки все натуральные числа подряд, обводя простые числа в кружок (рис. 12). Скоро, к его удивлению, простые числа выстроились в довольно-таки закономерном порядке, образуя интересный узор. Этот узор позже стал объектом исследования и получил название скатерть Улама. Составим программу, позволяющую нарисовать скатерть Улама размером 100X100 клеток. Не будем печатать числа, а только поставим звездочку (*) на месте простых чисел, Чтобы решить эту задачу, прежде всего надо найти все простые числа в интервале [1; 10 000]. Для этой цели
используем процедуру решето, составленную по методу Эра- тосфенова решета (см. задачу 29). Кроме того, надо образовать спираль, состоящую из элементов одномерного массива. Подчеркнем, что для этой задачи можно составить различные программы. Рассмотрим некоторые способы. 1. Геометрический Клетки скатерти заполняются в том же порядке (т. е. элементы решета разворачиваются начиная от центра скатерти), как рисовал их Улам. В этом случае мы моделируем в программе геометрические действия. 2. Вычисление координат скатерти Составляется процедура, в которой входное данное — индекс элемента решета, а результат — координаты соответствующей этому индексу клетки скатерти. Если мы, будем просматривать элементы решета по порядку, начиная с самого малого индекса, то будем заполнять клетки скатерти в том же самом порядке, что и при первом способе. 3. Вычисление индекса (координаты) элемента решета Составляется функция (или процедура), в которой исходные данные — координаты клетки скатерти, а результат — индекс элемента решета, соответствующего данной клетке. При наличии такой функции можно заполнять клетки скатерти, просматривая эти клетки в каком угодно порядке. Просматривая клетки слева направо и сверху вниз, т. е. в том порядке, в каком символы печатаются, можно вовсе не запоминать клетки скатерти, а просто печатать их. Таким Рис. 12. Спираль Улама.
Рис 13. Схема вращения спирали Улама. образом, если используется этот способ, в памяти нужно меньше места, нежели при способах, описанных выше. Составим программу для геометрического способа образования скатерти. Поскольку у нас есть процедура решето, которая находит все простые числа в интервале [2; п] и сохраняет результаты в массиве array [2..n] of boolean (напомним, что значение true присваивается, когда индекс элемента явлется простым числом, a false — в противном случае), то наиболее сложная часть решения — упомянутый одномерный массив (точнее, его индексы) скрутить в виде спирали. Как мы будем скручивать его, изображено на рисунке 13. Рассмотрим его. Скатерть разделена на квадраты, вписанные один в другой. В каждом квадрате все четыре линии (стрелки) имеют одинаковую длину. Длина стрелки зависит от квадрата, которому она принадлежит. Эти длины равны соответственно 1, 3, 5, 7, ..., 99 клеткам. Составим схему программы:
Первые четыре (центральные) клетки удобнее заполнить отдельно. Дальше клетки заполняются в соответствии со специальным законом. Разобрав схему вращения, приведенную на рисунке 13, мы можем описать заполнение клеток скатерти следующим образом: (вниз вправо вверх влево ( вниз г I вправо по 5 клеток< пп^ ] вверх ( влево Следовательно, цикл repeat в первых четырех прямоугольниках можно было бы детализировать так: В прямоугольнике шаг вниз нам нужно записать также действия: В прямоугольнике шаг вправо выполняются такие действия:
Аналогичные действия мы должны были бы выполнить и с другими прямоугольниками: шаг вверх и шаг влево. Поскольку действия во всех четырех прямоугольниках очень похожи, мы можем все их соединить в один общий цикл. Самое трудное место в процессе заполнения клеток — это переход из одного (малого) квадрата в другой (больший). Это можно запрограммировать различным образом. В приведенном здесь варианте программы движение начинается из левой верхней (угловой) клетки квадрата: сначала мы передвигаемся на одну клетку (делается один шаг), а затем заполняем клетку. Переход из одного квадрата в другой записывается при помощи следующих операторов присваивания: Подчеркнем еще, что перейти в правый квадрат удобнее всего в цикле repeat — еще до всякого вращения. Поэтому наша программа несколько отличается от приведенной выше схемы. Приведем составленную программу:
Вот и вся программа. Обратим внимание на то, что при некотором изменении программы можно было бы скрутить в виде спирали любой одномерный массив независимо от того, что в нем хранится. © Составьте процедуру для вычисления координат скатерти (см. второй способ). © © Составьте функцию для вычисления индекса (координат) решета (см. третий способ).
32. Совершенные числа Совершенным числом называется число, равное сумме всех своих делителей, меньших,чем оно само. Например: 28=1+2 + 4 + 7+14. Древним грекам были известны только четыре первых совершенных числа. Выдающийся греческий философ и математик Никомах из Герасы (I в.) писал: «Совершенные числа прекрасны. Однако известно, что прекрасные вещи редки, негодных же всюду полно». Совершенные числа чрезвычайно высоко ценились. Недаром в Библии сказано, что мир был сотворен за 6 дней: ведь это первое совершенное число. Даже в XII в. церковь утверждала, что для спасения души достаточно найти пятое число. Это число было найдено только в XV в. Добавим, что совершенные числа еще не полностью исследованы: так, неизвестно, имеется ли конечное число совершенных чисел или их число бесконечно, до сих пор не найдено ни одно нечетное совершенное число (и не доказано, что таких чисел не существует). Составим функцию, которая будет проверять, является ли заданное число совершенным: Чтобы найти совершенные числа в некотором указанном интервале, следовало бы применить функцию совершенное к каждому числу в этом интервале. Если интервал большой, поиск даже при помощи ЭВМ оказался бы долгим. Поэтому мы хотим напомнить тот путь, которым мы шли при изучении простых чисел. Для того чтобы проверить, является ли конкретное число простым, мы составили логическую функцию (см. задачу 26). Для поиска же простых чисел на промежутке [2; п\ мы прибегли к значительно лучшему способу, имеющему в качестве основания Эратосфеново решето. Оказывается, идею Эратосфенова решета можно применить и для данной задачи. Только вместо логического массива (см. задачу 29) нужно взять массив чисел, а в
качестве его элементов — суммы делителей. Итак, мы составили такую программу: Выполнив эту программу, ЭВМ напечатала числа: 6 28 496 8128 0 С совершенными числами тесно связаны числа Мер- сенна (см. задачу 29). Еще Евклид доказал, что каждое число, которое можно представить в виде произведения 2Р_1(2Р—1), является совершенным числом при условии, что 2Р — 1—простое число. Л. Эйлер (Euler, 1707—1783) доказал, что по формуле Евклида можно найти все четные совершенные числа. (Как выглядят нечетные совершенные числа и существуют ли они вообще, неизвестно до сих пор.) Таким образом, если у нас есть простые числа Мерсенна, нетрудно находить и совершенные числа. Составьте программу, которая найдет все совершенные числа Мерсенна, помещающиеся в ЭВМ. Быть может, среди них окажется и пятое совершенное число?
Есть легенда, которая гласит, что, когда Пифагора спросили, что такое дружба, он ответил: «220 и 284». Так возник термин «дружественные числа». Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Действительно, 220 и 284 являются дружественными числами, поскольку сумма делителей числа 220 — это 1+2 + 4 + 5+10+11+20 + 22 + 44 + 55+110 = 284, а сумма делителей числа 284 — это 1+2 + 4 + 71 + 142 = 220. Можно дать и такое определение дружественных чисел: сумма всех делителей одного и другого такого числа равна сумме обоих чисел. На протяжении веков 220 и 284 были единственной известной парой дружественных чисел. Только в середине XX в., проверяя числа до 1 000 000, нашли 42 пары дружественных чисел [15]. Поэтому в средние века полагали, что талисманы с этими числами укрепляют любовь. Мы будем искать в указанном интервале дружественные числа тем же способом, что и совершенные числа. Мы даже используем некоторую часть программы совершенные, а именно ту, в которой отыскивается сумма делителей. Законченная программа выглядит следующим образом:
Выполнив эту программу, ЭВМ нашла пять пар дружественных чисел: 220 284 1184 1210 2620 2924 5020 5664 6232 6368 © Составьте программу, которая нашла бы в интервале [1; 1000] число, имеющее больше всего делителей. 34. Цифры Взглянув на число, мы сразу можем сказать, из каких цифр оно состоит. Так что для человека нетрудно определить, из каких цифр состоит число. Но для ЭВМ сделать это непросто. Мы пользуемся десятичной системой счисления, а в машинной памяти хранятся числа в иной записи, чаще всего в двоичной системе. (Относительно систем счисления см. задачу 43.) Нет прямого соответствия между привычными нам десятичными цифрами и цифрами прочих систем счисления. К тому же как в основах математики, так и в теории программирования число рассматривается как одно неделимое значение. А тот факт, что число состоит из цифр, обусловлен только принятым у нас способом записи чисел. Сразу определить, из каких цифр состоит число, мы не можем ни пользуясь языком Паскаль, ни при помощи каких- либо других языков программирования. Во всех языках программирования с числами можно производить определенные арифметические операции. С их помощью придется выразить и действия над цифрами. Установить, из каких цифр состоит число, можно, используя операцию деления. Например, если известно, что число х является трехзначным, то его цифры a, b и с мы сможем найти следующим образом: а: =х div 100; b:=x div 10 mod 10; с: =х mod 10.
Составить число из цифр мы можем при помощи операций умножения и сложения. Например: х: = Ш*а+10*Ь + с. Опишем некоторые универсальные функции, имеющие дело с цифрами. Будем рассматривать только натуральные числа. Поэтому параметр п всех трех приведенных ниже функций — натуральное число. 1. Сколько цифр в данном числе 2. Нахождение суммы цифр числа 3. Запись числа в обратном порядке Эта функция записывает заданное число в обратном порядке (справа налево). Например, число 50 410 будет записано как 1405 (незначимые нули вначале опускаются).
Все три приведенные функции осуществляют простые действия, с которыми мы легко справляемся и без помощи ЭВМ. Однако они потребуются при составлении программ для многих интересных задач с цифрами. 0 Числа, одинаково читающиеся и слева направо, и справа налево, называются палиндромами. Например, числа 42 324 или 1331 —палиндромы. Составьте функцию, которая будет проверять, является ли заданное число палиндромом. © 0 Числа, запись которых состоит из двух одинаковых последовательностей цифр, называются симметричными. Например, 357 357 или 17 421 742 — симметричные числа. Составьте функцию, которая будет проверять, является ли заданное число симметричным. 0 0 0 Если мы сложим все цифры какого-либо числа, затем — все цифры найденной суммы и будем повторять это много раз, мы наконец получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 561 равен 3 (5 + 6+1 — 12; 1+2 = 3). Составьте функцию для нахождения числового корня натурального числа. 35. Автоморфные числа Автоморфным называется такое число, которое равно последним цифрам своего квадрата. Например: 52 = 25; 252 = 625. Для нахождения всех автоморфных чисел в интервале [т\ п] составим такую программу:
Выполнив приведенную программу, ЭВМ нашла в интервале [1; 1000] следующие автоморфные числа (в первом столбце напечатаны автоморфные числа, во втором — их квадраты): 1 1 5 25 6 36 25 625 76 5776 376 141 376 625 390 625 © Приведенная программа проверяет подряд все числа в интервале [т\ п\. Однако некоторые числа не надо даже проверять: итак ясно, что они не являются автоморфными. Это зависит от последней цифры. Чтобы число было авто- морфным, оно должно оканчиваться либо на 1, либо на 5, либо на 6. Убедитесь в этом. Поэтому программу можно усовершенствовать — уменьшить число переборов. Усовершенствуйте составленную программу. © © Аналогичным образом мы могли бы определить «кубические» автоморфные числа. Они равны последним цифрам своих кубов. Например: 63 = 216; 513= 132 651; 763 = 438 976. Составьте программу для нахождения «кубических» авто- морфных чисел в интервале [т\ п\. 36. Нумерация книжных страниц В книге п страниц (п — входное данное). Составим функцию, которая будет находить, сколько цифр понадобится для того, чтобы занумеровать все страницы этой книги. Сколько нужно цифр для всех /г-значных (£=1, 2, 3, ...) чисел, мы можем выяснить, рассуждая таким образом: для однозначных чисел требуется 9X1 цифр
для двузначных 90X2 цифр для трехзначных 900X3 цифр для &-значных чисел требуется 900 ... 00Х& цифр к — I нулей ИЛИ (999 ... 9 —J000 ... 00+1)Х& цифр к цифр к— I и\jcii Иначе говоря, следует вычислить значение выражения (наибольшее — наименьшее-\- \) Х&> где k обозначает число цифр (£=1, 2, 3, ...), а переменные наименьшее и наибольшее — соответственно наименьшее и наибольшее £-значное число. Для того чтобы установить, сколько цифр в числе я, применим функцию числоцф, описанную в задаче 34: Составленные функции можно включить в программу (или процедуру) двумя способами: 1) функция числоцф является внешней функцией по отношению к функции страницы, т. е. обе упомянутые функции включаются в программу параллельно; 2) функция числоцф является внутренней, включаемой внутрь функции страницы.
© Составьте функцию для решения обратной задачи: для нумерации страниц книги потребовалось k цифр (k — входное данное). Сколько страниц в книге? Если указанное число цифр не может служить для нумерации какого-либо количества страниц, то результат функции считайте равным 0. 37. Счастливые троллейбусные билеты Номера троллейбусных билетов представляют собой шестизначные числа. Счастливым считается тот билет, у которого сумма первых цифр равна сумме трех последних цифр. Например, билет 627 294 считается счастливым, так как 6 + 2 + 7 = 2 + 9 + 4=15. Условимся, что номера билетов принадлежат промежутку [100 000; 999 999]. Можно придумать много интересных задач, связанных с номерами счастливых билетов. Опишем одну из них, предоставив читателям самостоятельно решить еще несколько таких задач. Прежде всего составим очень простую функцию, которая будет устанавливать, является ли рассматриваемое число счастливым: Далее мы составим программу (в ней мы используем и функцию снаст) для решения следующей задачи: найдите все номера счастливых билетов, такие, что из них можно извлечь натуральный корень какой-либо (превышающей 1) степени. Например, л/720 801=849. Эту задачу можно решить, перебирая по очереди все шестизначные числа и проверяя, удовлетворяют ли они условию задачи: является ли число счастливым и извлекается ли из него корень 2, 3, 4-й и т. д. степени. Шестизначных
чисел много, да и счастливых среди них немало (более 50 000 — [20]). Таким образом, вычисление здесь будет долгим. Поищем какой-нибудь другой способ решения. Попробуем пойти в обратном направлении — поочередно возводить натуральные числа то в одну, то в другую степень. Если полученное число оказывается шестизначным, то надо проверить, является ли оно счастливым. Самое большое из подвергаемых проверке натуральных чисел должно быть меньше чем 1000, так как в противном случае его квадрат будет иметь более шести знаков: 10002>999 999. Поскольку каждое число надо будет возводить в степень не более чем 20 раз (2020 — это уже семизначное число), то для решения задачи этим способом надо рассмотреть около 1000-20 = 20 000 чисел (в действительности намного меньше, так как, чем больше число, тем меньше раз придется его возводить в степень). Приведем законченную программу: 0 Составьте программы, печатающие все такие номера счастливых билетов, которые равны: а) квадрату какого-либо натурального числа; б) кубу какого-либо натурального числа; в) квадрату какого-либо натурального числа и одновременно кубу какого-либо другого натурального числа.
©0 Составьте программу для нахождения всех, номеров счастливых билетов, у которых сумма первых (последних) трех цифр, будучи возведенной в какую-либо степень, равна номеру счастливого билета. 38. Сумма кубов цифр Существуют натуральные числа, равные сумме кубов своих цифр. Таково, например, число 370, ибо 33 + 73 + 03 = 370. Составим программу для нахождения всех таких чисел. Эта задача интересна тем, что позволяет найти все числа, обладающие названным свойством. Но ведь ЭВМ не может проверить все числа. Значит, прежде всего надо попытаться определить интервал, в котором можно надеяться встретить такие числа. Возможно, он окажется конечным. Самая большая цифра — это 9. Поэтому самая большая сумма кубов цифр однозначных чисел — это 93 = 729, двузначных — 93 + 93 = 1458, трехзначных — 93 4- 93 + 93 = =2187, четырехзначных — 93 + 93 + 93 + 93 = 2916. Самая большая сумма цифр пятизначных чисел — это 3645, т. е. четырехзначное число. Значит, пятизначные и более чем пятизначные числа не удовлетворяют указанному условию, и поэтому можно их не проверять. Точно так же можно не проверять и четырехзначные числа, превосходящие 2916. Еще более вникнув в суть дела, увидим, что из чисел, меньших чем 2916, но больших чем 2000, наибольшую сумму кубов цифр имеет число 2899. Эта сумма равна 23 + 83 + + 93 + 93= 1978, т. е. меньше чем 2000. Следовательно, числа, превосходящие 2000, нас не интересуют — достаточно проверить числа в промежутке [1; 2000]. Теперь приведем составленную программу:
Выполнив эту программу, ЭВМ напечатала следующие числа: 1 153 370 371 407 0 Составьте программу, которая будет находить все натуральные числа, равные кубу суммы своих Цифр. 39. Числа Армстронга Число, состоящее из п (я>1) цифр, называется числом Армстронга, если сумма его цифр, возведенных в п-ю степень, равна самому этому числу. Например, числами Армстронга являются 153 и 1634, так как 153=13 + 53 + 33; 1634=14 + 64 + 34 + 44. Составим программу, которая будет находить все я-знач- ные числа Армстронга (п — входное данное, причем п< 10). Чтобы программа была более экономной, цифры от 0 до 9 мы возведем в нужную степень один раз и результаты сохраним в массиве var степ:array [0..9] of integer Составим схему программы:
Детализируем действия, записанные в прямоугольниках. Массив степ можно заполнить следующим образом: Действия второго прямоугольника элементарны. Рассмотрим третий прямоугольник. Для того чтобы установить, какие цифры образуют п- значное число, и найти сумму п-х степеней — сумма, следует написать такой цикл: Соединив все части, получим законченную программу:
При входном данном п = 5 ЭВМ напечатала такие числа Армстронга: 54 748 92 727 93 084 © Обобщите данную программу таким образом, чтобы она напечатала все числа Армстронга, меньшие миллиарда.
0 0 Составьте программу, которая обнаружит самое большое число Армстронга, еще помещающееся в ЭВМ. 40. Квадраты, состоящие из разных цифр Б. Кордемский пишет [12], что среди всех десятизначных натуральных чисел, у которых все цифры различны, имеется 10 полных квадратов, т. е. 10 таких чисел, из которых можно извлечь точный квадратный корень. Было бы интересно исследовать меньшие я-значные числа (ai<10). Составим программу, которая должна найти все я-знач- ные (п — входное данное, причем 2<я<9) числа, обладающие названным свойством: число должно состоять из разных цифр и быть полным квадратом какого-либо натурального числа. Один из самых интересных моментов составления программы — установить, состоит ли рассматриваемое число из различных цифр. Для этого мы составим логическую функцию различные. Алгоритм таков: каждая цифра рассматриваемого числа вносится в множество — если встретится цифра, которая уже имеется в множестве, то ясно, что цифры рассматриваемого числа не будут различными, и это число отбрасывается. Является ли рассматриваемое n-значное число (л = 2, 3, ..., 9) полным квадратом какого-либо натурального числа, можно проверить двумя способами. Первый способ: перебрать все я-значные числа, цифры которых различны, и извлечь из них квадратный корень — если извлекается точный корень, то рассматриваемое число обладает сформулированным выше свойством. Второй способ: перебрать все натуральные числа, квадраты которых представляют собой /г-знач- ные числа, и тогда проверить, состоят ли квадраты из различных цифр. Эта задача решается аналогично задаче 37. Нетрудно понять, что второй способ намного превосходит первый (проверяется меньше чисел). Поэтому мы выбираем второй способ. Прежде всего надо установить, у какого наименьшего натурального числа квадрат представляет собой дг-значное число. Для этого составим функцию min кЬ Самое большое число тахкв, квадрат которого представляет собой /2-значное число, можно найти, применив функцию тткв: тахкв: = тткв (п -f- 1) — 1
Составив все названные функции и соединив их, получаем законченную программу:
0 Составьте функцию, которая будет вычислять, сколько различных букв содержится в заданном слове. © © Составьте аналогичную программу для нахождения кубов, состоящих из различных цифр. 41. 1!+4! + 5! = 145 Б. Кордемский [12] указывает одно интересное число 145, которое равно сумме факториалов своих цифр: 145=1! + + 4!+ 5!. Он пишет, что неизвестно, есть ли еще такие числа, удовлетворяющие названному условию. Самый простой способ поиска таких чисел — проверять все числа подряд. Но ведь множество натуральных чисел бесконечно, так что мы не смогли бы таким образом найти все возможные решения. Однако в данном случае можно заметить, что должно существовать такое число, превосходить которое интересующие нас числа не могут. Тогда мы составили бы программу для проверки конечного числового интервала. Будем рассуждать следующим образом. Факториал самой большой цифры (9) представляет собой шестизначное число. Значит, среди шестизначных чисел еще могут встретиться искомые числа. Максимальная сумма факториалов цифр семизначного числа — это 7X9! = = 2 540 160. Мы видим, что это семизначное число невелико. Максимальная сумма факториалов цифр восьмизначного числа также представляет собою всего лишь семизначное число. Следовательно, достаточно проверить числа, меньшие чем 2 540 160. Составляем программу:
Для того чтобы программа была экономной, факториалы цифр (от 0 до 9) вычисляются один раз и сохраняются в массиве фциф. Второй цикл в основной части программы повторяется более чем 2,5 млн. раз. В цикле содержится обращение к функции сумф, а в этой функции — еще один цикл. Так что даже быстродействующая ЭВМ долго билась бы с этой программой, поэтому стоит поискать способы ускорения вычислений. Попытаемся уменьшить число повторений в основной части программы. Быть может, какие-то числа можно отбросить заранее? Посмотрим, как изменяется сумма факториалов цифр у чисел, принадлежащих одному десятку от 0 до 9. В одном случае и у числа ... О, и у числа ...1 —сумма факториалов цифр одинакова, поскольку факториал и нуля, и единицы равен единице. Еще в одном случае — при замене числа ... 1 числом ... 2 — сумма факториалов цифр увеличивается на единицу — на столько же, на сколько увеличилось и само число. Во всех прочих случаях эта сумма растет быстрее чем число. Из этого мы можем сделать вывод, что если сумф (я)>/2+1, то в данном десятке точно не найдется чисел, превышающих п (т. е. таких, у которых последняя цифра больше последней цифры числа л, а все остальные цифры совпадают с цифрами числа п) и удовлетворяющих условию задачи. Составим новый вариант программы, в котором будет учтено рассмотренное свойство чисел.
Во втором варианте программы меньше содержится и обращений к функции сумф. Обращение к ней происходит только во внешнем цикле «десяток». Во внутреннем цикле сумма факториалов цифр пересчитывается путем коррекции предыдущей суммы. Выполнив эту программу, ЭВМ напечатала результаты:
1 2 145 40 585 0 Составьте программу, еще быстрее производящую вычисления, необходимые для данной задачи. Используйте в ней закон перестановки слагаемых (от перемены мест слагаемых сумма не меняется). Поэтому достаточно проверить, состоит ли сумма факториалов цифр рассматриваемого числа из тех же цифр, что и само число. Если да, то число, равное сумме факториалов цифр, удовлетворяет условию задачи, если нет — то условию задачи не удовлетворяют и все прочие числа, которые получаются из рассматриваемого числа путем перестановки цифр. Например, 2!+4! + 5! = 14б. Из цифр 2, 4 и 5 нельзя составить число, равное сумме факториалов этих цифр, а именно числу 146. Следовательно, все трехзначные числа, состоящие из цифр 2, 4 и 5 (245, 254, 425 и т. д.), не удовлетворяют условию задачи. 42. Наименьшее число не всегда мало Было бы интересно найти наименьшее число, оканчивающееся на пять, такое, что, если перенести его последнюю цифру в начало, число увеличится в пять раз. Для многих задач, в которых требовалось найти числа, обладающие каким-либо свойством, мы составляли очень простые программы — проверяли все числа в заданном интервале и рассчитывали на быстродействие ЭВМ. Поскольку здесь требуется найти только одно минимальное число, удовлетворяющее указанному условию, то возникает идея проверять подряд все числа, оканчивающиеся на пять: 5, 15, 25, 35, ...— до тех пор, пока мы не найдем то, которое нужно. К сожалению, ЭВМ будет биться над решением долго и тщетно — искомое число столь велико, что даже самая быстрая машина искала бы его невероятно долго. Поэтому приходится искать другое, лучшее решение. Предположим, что цифры искомого числа — это х\> х2, ..., хп. Мы знаем, что хп — 5. Поэтому условие задачи можно записать так:
^.Х[Х2Хз--.Хп—\ 5 Х 5 5 Х\Х2Х2>...Хп— 1 Попытаемся поискать отдельные цифры. Умножив любую цифру Xi (Х[>\) на пять, получим двузначное число abt состоящее из цифр а к Ь. Поскольку пос- ледняя цифра умножаемого числа известна, получим ab = = 25, т. е. а = 2 и Ь = Ь. Таким образом, последняя цифра произведения «в уме» такова: хп-\ =6 = 5. Но эта цифра тем самым является и предпоследней цифрой множимого. Следовательно, теперь можно умножить на пять уже ее и получить новую, предпоследнюю цифру произведения хп-2- Так надо умножать до тех пор, пока мы не получим а6 = 5. Таким образом, для получения всех цифр результата мы должны создать процедуру. Поскольку мы получаем цифры в обратном порядке (единицы, десятки, сотни и т. д.), то вначале надо их запомнить, а затем напечатать в порядке, обратном по отношению к тому, в котором они были получены. Поэтому мы составляем рекурсивную процедуру: Обращение к этой процедуре должно происходить так: р (0,5). Второй параметр показывает, что число оканчивается на пять, а первый — что при выполнении умножения «в уме» ничего нет, так как умножение начнется с последней цифры. Приведем результат, напечатанный ЭВМ: 510204081632653061224489795918367346938775. Это фактически не искомое число, а число, которое получается из искомого перенесением в начало последней цифры. Попытаемся найти искомое число, пойдя в обратном направлении: будем искать наименьшее число, которое уменьшится в пять раз, если его первую цифру перенести в конец числа.
Цифры числа, получающегося в результате, можно печатать сразу же, не запоминая их, поскольку цифры частного мы получаем в обычном порядке — слева направо. Поэтому можно составить нерекурсивную программу. Между прочим, этот же результат нетрудно получить и без помощи ЭВМ. Попытайтесь сделать это. 0 Составьте программу для нахождения двух наименьших чисел, которые начинаются на пять и из которых, перенеся первую цифру в конец, мы получим новое число, в пять раз меньшее, нежели искомое. 0 © Составьте программу, в которой входное данное — число п в интервале [2; 9], а результат — наименьшее число, у которого первая цифра — п и из которого, перенеся первую цифру в конец, мы получим новое число, в п раз меньшее, нежели искомое. 43. Двоичные числа В настоящее время почти во всем мире используется десятичная система счисления. Когда-то использовались и другие системы. Их реликты можно обнаружить и сейчас. Сюда относится шестидесятеричное исчисление времени (в часе 60 мин, в минуте 60 с). На основе различных систем счисления образованы старинные единицы измерения (см. задачу 53). Вольтер, например, пишет, что шведский король Карл XII хотел ввести двенадцатеричную систему, по-видимому, желая таким образом увековечить свой династический номер. Десятичная система счисления удобна для начального обучения арифметике при помощи счета на пальцах, поскольку на обеих руках вместе у нас 10 пальцев. А для счета при помощи машин значительно удобнее двоичная система. Ведь многие физические объекты имеют два четко различи-
мых состояния. Они используются для изображения цифр двоичной системы — 0 и 1. Например, если по проводу течет электрический ток — единица, если не течет — нуль; если железный сердечник намагничен — единица, если не намагничен — нуль и т. д. Хотя почти все ЭВМ оперируют двоичными числами, программист их не видит, так как десятичные числа, которые записываются в исходных данных или в тексте программы, ЭВМ автоматически переводит в двоичные, производит с ними действия, а полученные результаты опять переводит в десятичную систему счисления. Как числа переводятся из одной системы в другую, можно прочесть в книгах Г. Бермана и А. Доморяда [9, 10]. Число п можно однозначно выразить в р-ричной системе счисления при помощи цифр г/г, гк-\, ..., Г\у г0 так: n=pkrk + pk~lrk-[+ ... +рг{+г0 и записать его таким образом: Например, число 25 можно записать десятичными цифрами: 10'-2+10°-5. Это же число цифрами двоичной системы можно записать так: 2М+23.1+22-0 + 21.0 + 2°.1. Поэтому в двоичной системе оно записывается таким образом: п 001 Составим процедуру для ввода натурального числа, записанного в двоичной системе:
Составим процедуру для печати заданного натурального числа в двоичной системе: Цифры двоичной системы получаются при делении заданного числа на два (основание двоичной системы). Они представляют собой последовательность остатков от деления на два, расположенную в обратном порядке. Для того чтобы последовательность цифр была напечатана в обратном порядке, используется рекурсия. 0 Составьте процедуру, которая читала бы число, записанное в двоичной системе, и печатала бы его также в двоичной системе счисления. © 0 Составьте программу, которая прочитывала бы два целых числа, записанных в двоичной системе, складывала их и результат печатала бы также в двоичной системе. 44. Шестнадцатеричная система При проектировании или эксплуатации вычислительной техники приходится иметь дело и с двоичными числами. Для человека они неудобны тем, что для представления числа требуется длинный ряд цифр. Например, число 1990 в двоичной системе записывается так: 11111000110. Такое число трудно как прочесть, так и запомнить. Числа 2"-рич- ных систем удобно представлять в виде последовательности единиц и нулей, переводя в, число двоичной системы каждую цифру 2Л-ричной системы. (Каждая цифра числа 2"-рич- ной системы соответствует п цифрам двоичной системы.) Например, число, записываемое в четверичной системе как 133 002, можно записать при помощи диад: 01 jj, д оо оо w 13 3 0 0 2 а восьмеричное число 3702 — при помощи триад: 011 111 000 £10, 3 7 0 2
Поэтому в вычислительной технике часто используется восьмеричная, а также шестнадцатеричная системы счисления. Поскольку основание шестнадцатеричной системы превышает 10, то для цифр 10, 11, 12, 13, 14 и 15 надо ввести специальные обозначения. Принято обозначать их при помощи букв А, В, С, D, E, F. Составим программу для ввода и печати шестнадцате- ричного числа так, чтобы его цифры были представлены в виде тетрад:
© Составьте процедуру для: а) ввода; б) печати — заданного шестнадцатеричного числа. © © Составьте программу, которая читала бы предъявляемое двоичное число и печатала бы его в шестнадцате- ричной системе. 45. Палиндром Слово, фраза или стихотворная строка, одинаково читаемые слева направо и справа налево, называются палиндромами. Например: ИДИ ПОТОП ИСКАТЬ ТАКСИ То же самое можно сказать и о числах. Палиндромами являются, например, числа 121 1331 42 524 Является ли десятичное число палиндромом, человек может заметить сразу. Было бы интересно знать, является ли конкретное число палиндромом в какой-нибудь другой системе счисления. Например, число 45 является палиндромом в двоичной (101101) и в восьмеричной (55) системах. (Относительно систем счисления см. задачу 43.) Составим программу для нахождения палиндромов заданного натурального числа во всех системах счисления с основаниями 2, 3, ..., 10. Прежде всего определим тип данных для представления числа в любой системе счисления: const t= ... type Цифры = а.ттау [1 ... t\ of 0..9 Каждой цифре в новой системе счисления выделяется по одному элементу массива. Следовательно, константа t ограничивает количество цифр в самом большом числе. Если, например, мы имеем дело с двоичной системой счисления (записанные в ней числа имеют больше всего цифр), а £ = 50, то в массив можно поместить числа до 250 —1. Составим процедуру, которая будет представлять натуральное десятичное число п при помощи цифр заданной р- ричной системы счисления и проверять, является ли оно
палиндромом: Включим составленную процедуру в программу, нахо дящую палиндромы заданного натурального числа в систе мах счисления с основаниями 2, 3, ..., 10:
При исходном данном п = 100 ЭВМ напечатала ПАЛИНДРОМЫ ЧИСЛА 100 10201[3] 202 [7] 121[9] (В квадратных скобках указывается система счисления.) 46. Большое произведение Перемножая большие числа, можно быстро получить переполнение. Поэтому, для того чтобы напечатать произведение, превышающее maxint, надо применить искусственные средства. Составим программу для печати произведения двух чисел, которое может превышать максимально допустимое целое число maxint (см. задачу 2):
Процедура умножение умножает число а на каждую цифру числа Ьу начиная с единиц. Последняя цифра полученного произведения, сложенная с последней цифрой имеющегося в памяти частичного произведения, печатается, а все прочие цифры запоминаются — передаются как параметры при рекурсивном обращении к процедуре умножение. В самом конце производится умножение на первую (левую) цифру числа Ь. На этом умножение заканчивается. Тогда печатается начало результата — накопившееся частичное произведение без последней цифры (s div 10), а после него при возвращении из рекурсии — все остальные цифры произведения (s mod 10) в обратном порядке по сравнению с тем, как они вычислялись при входе в рекурсию. В соответствии с этой программой ЭВМ перемножила числа 123 456 789 и 123 456 789 и напечатала такой результат: 123456789*123456789 =15241578750190521 Значения параметров процедуры умножение ограничивают максимально возможное частичное произведение. Поскольку на множитель (второй параметр) умножаются отдельно взятые цифры, то он может находиться в интервале [0; maxint]. Убедитесь в этом! Для того чтобы мы могли вычислить промежуточный результат a*(b mod 10), значение а не должно превышать maxint div 9, а оператор присваивания s: = s-\-a*(b mod 10) мы сможем выполнить в том случае, если значение а будет вдвое меньшим, т. е. если максимальное значение множимого (первого параметра) будет примерно в 20 раз меньшим чем maxint. © Составьте программу умножения числа, не превышающего maxint div 20, на число, превышающее maxint.
47. Большие числа Иногда результат операций, выраженный большим числом, необходимо не только напечатать, но и сохранить в памяти ЭВМ^ с тем чтобы с ним можно было производить какие-то другие действия. Можно сгруппировать цифры числа и представить эти группы в виде отдельных чисел, объединенных в запись или массив. Тогда операции с большими числами можно выразить в виде последовательности операций с числовыми компонентами. Проще всего (хотя и неэкономно) для каждой цифры числа выделить отдельный элемент массива. Так и сделаем. Определим массив для представления больших натуральных чисел: const /=100; type большое = array [l..t] of 0..9 Каждая цифра большого числа представлена отдельным элементом массива. Это естественное, но неэкономное представление (в один элемент массива уместилось бы и большее количество цифр). При помощи такого массива можно представить число, не превышающее 10100. Этот предел установлен не случайно. Ведь 10100 часто рассматривают как пример очень большого числа (иногда в популярной литературе его называют гугбл). Составим процедуру для сложения двух чисел типа большое: Составим программу, которая напечатает факториалы чисел от 1 до 50:
Действия с большими числами поясняются в комментариях. Там указываются такие операции, которые надо было бы выполнять, если бы число / не было большим. © В программах, оперирующих с очень большими числами, было бы удобно иметь набор процедур, выполняющих арифметические операции ( + , —, *, div, mod) и операции сравнения (<, ^, >, ^, =, Ф). Составьте набор таких процедур. Большие числа представьте при помощи типа большое. © © Составьте программу для нахождения такого числа /2, факториал которого близок числу 10100, т. е. такого, что /г!<10,0°; ("+!)!> 10100.
48. Точность действительных чисел Действительные числа в вычислительной машине представлены приближенно. Для того чтобы оценить точность вычисления, необходимо знать, сколько знаков (цифр) выделено для представления числа. В языке Паскаль, как и почти во всех прочих языках, нет констант (аналогичных константе maxint), которые бы непосредственно указывали точность действительных чисел. Поэтому спрашивать у машины, сколько цифр выделено для действительного числа, приходится окольными путями. Приведем программу, которая печатает число десятичных знаков, выделяемых для представления действительного числа: Цикл заканчивается, когда 1.0= 1.0...01. Это означает, что последняя цифра числа 1.0...01 исчезла. Значит, ЭВМ выделяет для представления действительного числа п—\ десятичных знаков. Выполнив эту программу, ЕС ЭВМ напечатала число 7, а БЭСМ-6 — число 6. Если мы хотим выразить точность при помощи числа знаков в какой-либо другой системе счисления, следует изменить константу система 49. Точное частное Как разделить одно целое число на другое так, чтобы получить частное (действительное число), имеющее столько точных цифр после запятой, сколько мы хотим? Попытаемся составить программу решения этой задачи.
Операция деления действительных чисел (ее знак /) в данном случае нас не устраивает, поскольку ее результат оказывается приближенным. Хорошенько подумав, нетрудно найти выход: получив очередную цифру частного, стоящую после запятой, сразу печатаем ее. Цифры частного мы получаем тем же способом, что и при делении столбиком: остаток умножаем на 10, а затем делим на делитель. При а = 22, Ь = 7, с = 20 ЭВМ напечатала 22:7 = 3.14285714285714285714. 50. Деление с большой точностью Есть любители получать возможно более точные значения различных математических величин. Например, в XVI в. житель города Дельфт (Голландия) Лудольф ван Койлен вычислил значение л с точностью вплоть до 35-го знака после запятой и завещал высечь это число на своем надгробье. Как составить программу, которая получила бы много точных десятичных знаков числа е? Будем опираться на такую последовательность: e=1+Tr+i+i+-+i+- Если бы мы использовали вещественный тип данных, программа была бы такой:
Эта программа вычисляет значение е, суммируя члены ряда до тех пор, пока они не станут меньше, чем константа эпсилон (const эпсилон = 0.00001). Чем меньше константа, тем больше членов ряда складывается и тем точнее получается значение е. Однако эту константу можно уменьшать только до определенного предела. В зависимости от типа ЭВМ константа может быть от Ю-6 до Ю-9 (см. задачу 48). Поэтому, для того чтобы найти число е с большой точностью, поступим так, как в случае больших чисел (см. задачу 47) — цифры числа е сохраним в массиве, тип которого мы определим так: const / = ...; type послед = array [0../] of [0..9] Условимся также, что место запятой фиксируется после первой цифры, т. е. дробная часть находящейся в массиве последовательности начинается с элемента, индекс которого равен 1. Итак, при наличии такого массива мы сможем выразить значение е с точностью до / десятичных знаков, т. е. эпсилон= 10_/. Составим программу для нахождения числа е с большой точностью. В ней мы будем использовать тип послед. Справа в комментариях мы будем указывать, как действия данной программы соответствуют прежней программе натлог. Поскольку программа, которую мы составим, будет осуществлять действия с числами, представленными в виде массива, то сложение, деление, сравнение, печать и получение еди-
ницы запишем в виде отдельных процедур или функций:
Выполнив эту программу, ЭВМ напечатала Е = 2.71828182845904523526. 0 Составьте программу, которая получит число я с большой точностью. Используйте любую последовательность, выражающую данное число (см. задачу 5). 51. Простые дроби Типа данных, предназначенного для простых дробей, не существует. Их можно определить при помощи записи:
Чтобы выполнять действия с простыми дробями, необходим набор процедур, выражающих эти действия. Поскольку результат арифметических операций с простыми дробями часто выражается сокращенной дробью, то прежде всего составим процедуру для выполнения данного действия: Для сложения и умножения двух простых дробей опишем такие процедуры: © Составьте процедуры вычитания и деления двух простых дробей. 0 0 Если числитель и знаменатель представляют собой большие числа, то при выполнении процедур сложение и умножение может получиться переполнение, хотя числи - тель и знаменатель результата — сокращенной дроби — не превышают максимально допустимого числа maxint.
Составьте процедуры сложения и умножения, в которых бы избегалось переполнение в тех случаях, когда числитель и знаменатель результата находятся в допустимых пределах. 52. Десятичные дроби Любое рациональное число (следовательно, и любую простую дробь) можно представить в виде конечной или периодической десятичной дроби. Период принято заключать в скобки. Например, мы пишем 0,(3), 1,3(18), 2,7(136). Составим программу, которая будет положительную простую дробь превращать в десятичную и печатать ее (если дробь окажется периодической, то период будет напечатан в скобках). Эта задача похожа на задачу о точном делении (см. задачу 49). Только в данном случае необходимо предварительно выяснить, является ли дробь периодической, и если да, перед тем как производить деление, надо установить, где начало и конец периода, чтобы было ясно, где напечатать скобки и когда прекратить деление. Является ли правильная дробь (т. е. такая дробь, у которой числитель меньше знаменателя) периодической, можно установить, умножив числитель на 10, а затем разделив на знаменатель. Затем полученный остаток снова умножается на 10 и делится на знаменатель. Этот процесс повторяется до тех пор, пока остаток не станет равным нулю (в этом случае очевидно, что дробь является конечной) или же какому-либо ранее полученному остатку (в этом случае дробь является периодической, так как с этого момента снова будут повторяться и цифры частного, и остатки). Равные остатки устанавливают начало и конец периода. Таким образом, надо запоминать не частные, а остатки. Максимальный остаток показывает, каково может быть максимальное количество различных (неравных нулю) остатков: он на единицу меньше, чем знаменатель дроби (частное). Значит, максимальное значение знаменателя устанавливает размер массива, необходимого для хранения остатков, и максимальную длину периода. И наоборот, max — максимальное число десятичных знаков в десятичной дроби — и принятый размер массива остатков ограничивают знаменатель дроби. Определим тип дроби и составим процедуру для установления начала и конца ее периода:
В процедуре период есть ряд непривычных моментов. 1. У массива ост тип индексов и тип элементов совпадают. Вместо того чтобы нумеровать элементы массива посредством их номеров в последовательности и остатков и присваивать элементам значения остатков, мы можем с тем же успехом сделать наоборот: элементу, у которого значение индекса равно остатку, присваивать номер данного остатка в последовательности. Тогда намного проще проверить, имеется ли уже в массиве новый остаток. 2. В цикле repeat конечная дробь неотличима от периодической. Формально конечные дроби рассматриваются как частный случай периодических: их период равен нулю. Благодаря этому верхний предел массива ост оказывается больше, чем должен был бы быть. 3. Процедура период не дает прямого ответа на вопрос, является ли дробь конечной. Если по окончании работы процедуры получается конечная дробь, то значение параметра начало равно константе max. При наличии данной процедуры мы без труда составим и всю программу:
Эту программу можно без труда применить и к отрицательным дробям. 0 Измените программу таким образом, чтобы в ней не было ограничений на знаменатель дроби: если мы узнали 100 первых десятичных знаков и не обнаружили периода,
после сотого десятичного знака следует напечатать многоточие. © 0 Полным периодом называется период, состоящий из максимально возможного числа цифр, т. е. период дроби — является полным, если в нем b — 1 цифра. ь Например, полный период имеют дроби J-= 0,(142857); -|-= 0,(285714); -L=0,(0588235294117647). Составьте программу, которая печатала бы все; дроби вида —, где п£[\\ 100], имеющие полный период. 53. Старинные меры В настоящее время чаще всего используется метрическая система мер. Она основана на десятичной системе счисления (1 м=10 дм, 1 дм=10 см и т. д.). Старинные меры основаны на различных системах счисления. Еще и теперь в некоторых местах используют дюймовую систему измерения: 12 дюймов составляют фут, 3 фута равны 1 ярду. Рассказывают, что эталон ярда был установлен в Англии в 1101 г. Это было расстояние от кончика носа короля Генриха I до кончика большого пальца его вытянутой руки. Определим тип данных, пригодный для описания длин посредством дюймовой системы измерения: Составим функцию для замены дюймовых единиц длины на метрические. Мы знаем, что 1 дюйм ^2,54 см.
Составим процедуру для сложения двух расстояний, измеренных в дюймовой системе измерения: 0 Составьте процедуру, заменяющую метрические единицы на единицы дюймовой системы измерения. 0 © При использовании дюймовой системы площадь измеряют в квадратных дюймах, квадратных футах и квадратных ярдах. Составьте процедуру для сложения двух площадей, выраженных в дюймовой системе, и функцию для замены дюймовых единиц измерения площади на квадратные метры. © 0 © В старину жидкости и сыпучие тела измерялись в мерах (например, мера овса). В одной мере умещалось 6 гарнцев, а в гарнце — 4 кварты. Старинный гарнец, использовавшийся в Великом княжестве Литовском, был равен 5,6 л, а с 1765 г. был введен новый гарнец, равный 2,82 л. Точно такая же система мер использовалась и у других народов, только различной оказывалась величина единиц: старинный русский гарнец — 3,28 л, а польский гарнец равен 3,77 л. Составьте процедуру, подходящую для того, чтобы перевести количество жидкости из любого упомянутого вида единиц в любой другой. © 0 0 0 В Великобритании жидкости измеряют в галлонах и бушелях. Один галлон равен 4,54609 л, 8 галлонов составляют бушель. Составьте процедуру для сложения двух объемов жидкости, измеренных в английских единицах, и функцию для перевода количества жидкости, измеренного в галлонах и бушелях, в литры. 54. Действительные числа и бухгалтерия Пусть сберегательные банки по бессрочным вкладам выплачивают 2% годовых от суммы вклада, присоединяемых к вкладу. Если вкладчик не снимает денег с вклада, то проценты ежегодно начисляются со все большей суммы.
Составим программу, которая будет вычислять, какой величины достигнет бессрочный первоначальный вклад через т лет, если вкладчик не будет ни снимать, ни вносить деньги: При исходных данных вклад = 100.0 и т = 1 ЭВМ; выполняя программу, напечатала 101.99, т. е. первоначальный вклад в 100 р. через год увеличится на 1.99 р. Одна копейка «пропадает» из-за того, что операции с действительными числами ЭВМ производит приближенно. Чтобы получить возможно более точный результат, необходимо округлить число — изменить оператор печати так: write (вклад + 0.005:10:2) В этом случае ЭВМ напечатала бы правильный результат. Абсолютно точный результат может быть получен только при использовании целых чисел. Поэтому в бухгалтерии лучше производить вычисления в копейках и только окончательный результат печатать в рублях. Составим новую программу, в которой первоначальный вклад выражается в копейках: Выполнив эту программу при вклад = 10 000 (в копейках) и т= 1, ЭВМ напечатала 102 РУБ. ОКОП. Для интереса приведем напечатанный «ЭВМ результат, который показывает, какой величины стал бы бессрочный вклад в 100 р. через
100 лет: 724 РУБ. 38 КОП. 0 Составьте программу, которая бц напечатала таблицу, показывающую, на сколько процентов возрастет бессрочный (двухпроцентный) и срочный (трехпроцентный) вклады через т лет (1^т^20). 0 © Составьте функцию, которая бы устанавливала, через сколько лет первоначальный вклад удвоится (станет больше примерно вдвое). Параметр функции — годовой процент. 55. Высота музыкального звука Высота звука в физике определяется частотой колебаний и измеряется в герцах (Гц) — числом колебаний в секунду. В музыке звуки распределены по октавам. Самые употребительные октавы: субконтроктава, контроктава, большая, малая, первая, вторая, третья, четвертая, пятая октавы. В каждой октаве имеются следующие основные звуки: до, ре, ми, фа, соль, ля, си. В музыке соотношение частот звуков имеет большее значение, нежели абсолютная частота. Тот же самый звук более высокой октавы имеет частоту вдвое больше. Например? частота до второй октавы в 2 раза больше, чем частота до первой октавы, и в 4 раза больше, чем частота до малой октавы. Октава равномерно разделена на 12 интервалов (полутонов), так что соотношение частот двух соседних звуков равно [л/2ж 1.05946. Интервал между звуками ми — фа и си — до (более высокой октавы) составляет полутон, а между прочими основными звуками — тон (т. е. два полутона). Только 7 звуков октавы (из 12 возможных) имеют названия. Прочие звуки обозначаются при помощи названия соседнего звука вместе со специальным знаком: диезом — при повышении тона или бемолем — при понижении тона. Определим тип данных, характеризующих высоту звука в музыке:
Принято, чтобы частота звука ля первой октавы была равна 440 Гц. Составим функцию для нахождения высоты любого тона: Сначала принимается, что частота 4 = 440 Гц. Затем от стандартной точки «опоры» — звука ля первой октавы — передвигаемся вниз или вверх на октаву и делим или умножаем на 2. Затем передвигаемся на один тон вверх (после звука ля идет только один звук си) или вниз на требуемое число тонов. 0 Составьте функцию для нахождения интервала между двумя музыкальными звуками, выраженного числом полутонов. Если первый звук ниже, чем второй, результат должен быть отрицательным. 0 © Составьте процедуру транспонирования звуков, которая заменяла бы тон указанного музыкального звука, «передвигая» его на указанное число полутонов п вверх (если п>0) или вниз (если я<0). 56. Случайные числа Мы не можем сразу сказать, какая сторона монеты или игральной кости окажется сверху, какую карту мы вытащим из колоды. Говорят, что результат такого эксперимента явля-
ется случайным. Повторяя эксперимент много раз, получаем последовательность случайных значений. Интересно, что невозможно предвидеть значение нового члена ряда — он не зависит от предшествующих членов. В задачах, в которых моделируются жизненные ситуации (например, игры, эпидемии заболеваний и т. д.), требуются случайные значения. Значение любого числового типа можно получить из целых чисел, поэтому достаточно было бы иметь только генератор случайных целых чисел, т. е. такую функцию или процедуру, обращаясь к которой мы каждый раз получали бы все новые и новые члены последовательности случайных чисел (принадлежащие указанному интервалу). Случайные числа можно получать различными методами, наиболее распространенный из них — рекуррентный, суть которого заключается в следующем: каждое случайное число rk находится из предыдущего числа rk-\ по формуле rk = ={rk-\ * сомножитель + прибавка) mod делитель. В этой формуле в качестве г0 выбирается любое число. Числа г\, г2, ..., г*, ..., получаемые по этой формуле, строго говоря, не будут случайными числами в теоретико-математическом смысле, так как гь-е число зависит от значений rk-\> rk-2, ..., го. Поэтому числа, получаемые таким способом, принято называть псевдослучайными [4]. В соответствии с упомянутой формулой получаются числа на отрезке [0; делитель—1]. Когда в ряду будет делитель чисел, ряд повторится заново. Какой величины будет повторяемая часть ряда, зависит от констант сомножитель и прибавка. Чтобы таких повторений было меньше, т. е. получалась достаточно длинная последовательность случайных чисел, необходимо надлежащим образом подобрать упомянутые константы. В книге [4] предложены такие константы: делитель = 216 = 65 536; сомножитель = 25 173; прибавка = 13 849. Составим функцию для получения псевдослучайного натурального числа на отрезке [1; 65536):
Эта функция вычисляет 65 536 случайных чисел — после этого расположение чисел повторится. Обратим внимание на то, что функция псевдо использует глобальную переменную член. Если бы мы объявили ее параметром функции, то она должна была бы быть переменным параметром (поскольку каждый раз эта функция должна передавать различные значения, а это было бы нежелательным побочным эффектом функции). При первом обращении к функции переменной член следует приписать какое-нибудь исходное значение. Часто бывает нужно получать псевдослучайные числа в каком-либо интервале. Для этого строится отображение результатов функции в тот интервал, в какой необходимо. Например, бросание игральной кости моделируется таким оператором: очки: = псевдо mod 6+ 1 Для того чтобы получить псевдослучайные действительные числа, удобнее всего порождать их из интервала [0; 1), видоизменив саму функцию порождения псевдослучайных чисел: Чтобы получать псевдослучайные действительные числа в большем интервале, надо умножить значение данной функции на соответствующую константу. 57. Вычисление значения л путем бросания иглы Мы опишем интересный и неожиданный способ вычисления числа п. Берется короткая швейная игла (лучше с обломанным острием), имеющая на всем протяжении одина-
Рис. 14 Рис 15. ковую толщину. На листке бумаги чертится несколько тонких параллельных прямых линий так, чтобы расстояние между соседними прямыми было вдвое большим, нежели длина иглы. После этого с одной и той же высоты бросают иглу на бумагу и смотрят, пересекает ли она какую-либо из проведенных прямых или нет (рис. 14). При этом пересечением считается и тот случай, когда игла касается прямой лишь концом. Чтобы игла не отскакивала, под лист бумаги можно положить лоскуток ткани, поролон или что-либо подобное. Иглу бросают много раз, например сто или тысячу, и каждый раз отмечают, пересекла ли она прямую. Разделив число бросков иглы на число пересечений, получим приблизительное значение я: число бросков л = с — • число пересечении Чем больше число бросков, тем более точным оказывается полученное значение п. Этот эксперимент осуществил в 1733 г. французский естествоиспытатель Жорж де Бюффон (de Buff on, 1707—1788). Интересно, какое значение л мы бы получили, если бы иглу «бросала» ЭВМ. Составим программу бросания иглы. Для того чтобы определить положение иглы на плоскости, достаточно знать координаты (сх, су) какой-либо точки иглы и угол а, который игла составляет с осью абсцисс (рис. 15). Условимся, что начерченные прямые параллельны оси абсцисс, а угол а острый. Для получения случайных чисел воспользуемся составленной в задаче 56 функцией псевдо, значения которой представляют собой действительные числа на промежутке [0; 1) и при этом точность всех значений одинакова. Иначе
обстоит дело, когда иглу бросают рукой на лист бумаги. Вероятность того, что игла упадет на край листа, много меньше, чем вероятность падения на середину листа. Так что в этом случае мы не можем применить функцию псевдо. Но ведь нам безразлично, около какой прямой упадет игла. Важны не координаты центра иглы, а расстояние от ее центра до ближайшей прямой. Обозначим это расстояние буквой с. Тогда положение иглы мы можем определить при помощи двух случайных чисел с и а. Длину иглы примем равной 1 см, тогда расстояние от ее центра до ближайшей прямой представляет собой число, находящееся в промежутке [0; 1). (Если центр находится на одинаковом удалении от обеих прямых, выберем нижнюю прямую.) Фактически мы ограничиваемся одной прямой, совпадающей с осью абсцисс, и считаем, что игла падает недалеко от нее, т. е. ординату центра иглы мы можем случайным образом выбирать из промежутка [—1; 1). В программе положение центра иглы мы будем определять так: с: =псевдо*2.0— 1.0 Теперь необходимо получить случайный угол а. На квадратном поле обозначим две точки (xl, у\) и (х2, у2) и найдем угол, который прямая, соединяющая эти две точки, образует с осью абсцисс. Поскольку размеры поля не играют роли, то мы можем считать его высоту и ширину равными 1 см. Имея случайные числа х\, у\, х2, у2, мы следующим образом определяем угол а и его синус: Теперь мы уже в состоянии проверить, пересекает ли игла прямую. Для этого необходимо найти ординаты концов иглы и проверить, находится ли прямая, совпадающая с осью абсцисс, между концами иглы. Для такой проверки составлена функция пересек. Приведем окончательный вид программы:
© Ж. де Бюффон сформулировал и решил такую задачу: найдите вероятность того, что игла пересечет проведенные прямые, если лист бумаги разлинован параллельными прямыми не только в горизонтальном, но и в вертикальном направлении (расстояния между всеми прямыми одинаковы). Вероятность вычисляется по формуле число пересечений число бросков Составьте программу для нахождения этой вероятности.
58. Площадь фигуры Покажем, каким образом можно приближенно вычислить площадь фигуры, ограниченной какой-либо кривой,, методом Монте-Карло. Название метода связано с городом Монте- Карло, славящимся на весь мир своими игорными домами. В Основании этого метода лежат случайные числа. Он особенно пригоден для тех случаев, когда уравнение кривой оказывается сложным, трудноинтегрируемым. Кратко поясним его сущность. Исследуемую фигуру вписывают в какую-либо другую фигуру, площадь которой вычислить легко (например, в квадрат или в прямоугольник). Выбираются случайные точки (т. е. порождаются случайные числа, определяющие координаты точек), находящиеся в пределах фигуры известной площади, и вычисляется, сколько точек попало внутрь исследуемой фигуры и сколько оказалось снаружи. Соотношение числа точек, оказавшихся внутри фигуры, к общему числу имеющихся точек будет пропорционально соотношению площадей фигур. Чем больше точек мы исследуем, тем более точной окажется данная пропорция. Из нее нетрудно вычислить площадь исследуемой фигуры. Для того чтобы проиллюстрировать данный метод, составим программу, которая будет вычислять площадь фигуры, ограниченной синусоидой (т. е. КрИВОЙ (/ = 5Ш X При 0^*^л) и линией у = 0. Данную фигуру впишем в прямоугольник (рис. 16). Рис. 16. Вычисление площади фигуры, ограниченной половиной синусоиды.
Выполнив данную программу, ЭВМ напечатала 1.98. Площадь такой фигуры, вычисленная при помощи интегралов, равняется 2: л \ sin х dx= —cos x л = 2. Jo ' ° © Аналогичным образом мы можем применить метод Монте-Карло и для нахождения объемов фигур. Составьте программу для нахождения объема шара х2-\-у2-\-z2= 1 методом Монте-Карло. 59. Даты Едва ли не ежедневно мы пользуемся календарями и даже не замечаем, что это, вообще говоря, непростая вещь. Человечество потратило тысячелетия на то, чтобы создать такой календарь, какой мы сейчас имеем. Приведем несколько интереснейших фактов. Создать календарь — это значит соединить в красивую, удобную, правильную комбинацию три астрономических периода: сутки, лунный месяц и солнечный год. Но сделать это не так просто: все три числа, как нарочно, не желают сочетаться друг с другом — год не делится ни на месяцы, ни на сутки. Попытаемся уяснить себе такие простые понятия, как год, месяц, сутки. Год (тропический) — это промежуток от одного момента, когда центр Солнца проходит точку весеннего равноденствия, до следующего такого момента. Этот промежуток длится 365 суток 5 часов 48 минут и почти 46 секунд, т. е. примерно 365,2422 суток.
Месяцем считается так называемый синодический месяц, или месяц лунных фаз, т. е. время от одного соединения Луны с Солнцем (новолуния) до другого. Месяц длится 29 суток 12 Часов 44 минуты и почти 3 секунды, или около 29,53059 суток. Солнечные сутки длятся 24 часа. Эти периоды представляют собой основание календаря. Таким образом, как мы видим, вовсе немыслимо связать воедино все три периода: сутки, месяц и год — в календаре, удовлетворяющем всем требованиям. Мы пользуемся солнечным календарем, созданным римлянами. Всем известен календарь Юлия Цезаря, или, как принято говорить, юлианский календарь (созданный в 46 г. до н. э.). В нем год состоит из 12 месяцев, 365 дней. Каждый четвертый год — високосный — продолжается 366 дней. Однако в юлианском календаре год был на 11 минут 14 секунд более долгим, нежели тропический год, из-за чего весеннее равноденствие к XVI в. сместилось с 21 марта на 11 марта. Поэтому потребовалось усовершенствовать календарь: отбросить излишек дней так, чтобы в будущем такая ошибка не повторилась. В 1582 г. папа Григорий XIII повелел 5 октября считать 15 октября 1582 г. (т. е. отбросить излишек в десять дней) и последний год любого столетия считать високосным (366 дней) только в том случае, если его номер делится на 400 (например, 1600, 2000). Юлианский год за четыре столетия забегал вперед на три дня. Чтобы удержать его, астрономы Григория и отказались от трех високосных лет в четыре столетия. Григорианский год лишь на 26 секунд дольше, нежели тропический, и поэтому ошибка в 1 день набегает только за 3280 лет. В этом нет ничего страшного. Вскоре григорианским календарем стали пользоваться и в Литве. Однако с 1800 г. в Литве (за исключением Зане- манского края) снова стал использоваться старый календарь. Вторично в Литве григорианский календарь был введен 15 ноября 1915 г.— этот день стали считать 28 ноября. Григорианским календарем мы пользуемся и в настоящее время. Теперь составим несколько функций, которые нам будут часто нужны для программ других задач с датами. Прежде всего определим типы год, месяц, день:
Эти типы мы будем использовать для решения других задач, связанных с датами. Мы будем пользоваться григорианским календарем, поэтому годы мы определили начиная с 1583-го (верхняя граница отрезка — 5000-й год; надеемся, что этого будет достаточно...). 1. Определение високосных лет Это очень простая функция, поэтому приведем ее без пояснений: Эта функция подходит только для григорианского календаря (последний год столетия считается високосным, только если его номер делится на 400). 2. Определение числа дней в месяце Это тоже достаточно несложная функция: В этой функции мы используем функцию определения високосных лет високос. Иногда удобно называть месяцы не посредством чисел 1, 2, ..., 12, а при помощи слов январь, февраль, ..., декабрь. Для этого потребуется вышеприведенный тип месяц определить как скалярный тип: Перепишем функцию дмес для случая, когда месяцы определены по скалярному типу:
Почти во всех задачах мы будем использовать для обозначения месяцев тип месяц, определяемый через числовой отрезок, а тем самым и функцию дмес. Если где-либо нам понадобится определить месяцы по скалярному типу (например, для того, чтобы непосредственно выводить на печать названия месяцев — см. задачу 67), то мы применим функцию дмц и в этом случае подчеркнем, что тип мес является скалярным. 3. Проверка правильности обозначения даты Здесь и далее мы будем применять определение даты как запись следующего типа: Значение типа день определено отрезком 1..31. Но не в каждом месяце есть 29, 30 или 31 день. Поэтому значением записи может быть и несуществующая дата, например 30.02.1986. Составим функцию, которая будет проверять, является ли данное обозначение даты правильным: В дальнейшем, составляя программы, в которых исходные данные — даты, мы будем считать, что они обозначены правильно и не будем заниматься такой проверкой. 0 Составьте функцию для определения високосных лет по юлианскому календарю.
© 0 Составьте процедуру для печати заданной даты (значения типа данного дата), например 04.03.1986. 60. Дата следующего дня Составим процедуру для установления даты завтрашнего дня, т. е. такую процедуру, результатом которой будет дата, следующая за датой данного дня: Дата определяется как тип записи (см. задачу 59), а функция дмес устанавливает, сколько дней содержится в месяце (также см. задачу 59). Если бы мы передали исходное данное (сегодняшнюю дату) и результат (завтрашнюю дату) при помощи одного и того же параметра, мы получили бы несколько более краткую процедуру:
Это очень простая процедура. Она может быть использована в электронных часах для установления даты. © Составьте процедуру для установления даты вчерашнего дня. 61. Будущая дата Нетрудно выяснить дату, которая наступит через несколько дней или даже через несколько десятков дней. Однако, если число дней велико, вычисления окажутся утомительными. Составим процедуру, которая будет определять дату, наступающую после того, как пройдет дн дней после указанной даты. Чтобы продвинуться вперед на один день, можно использовать процедуру завтдень (см. задачу 60). Само собой разумеется, что продвигаться по одному дню — это слишком мало, если число дней дн велико. Поэтому рациональнее сначала передвигаться шагами величилой в год, затем — величиной в месяц, а далее — величиной в день.
Для того чтобы шаги были равны целым годам и целым месяцам, в начале процедуры указанная дата «отодвигается» назад к началу года, а указанное число дней дн соответственно увеличивается. В процедуре будущее используются функции из предыдущих задач (см. задачу 59): високос (гд) — является ли год гд високосным — и дмес (гд, мц) — сколько дней в месяце мц года гд. Дата определяется по типу записи (также см. задачу 59). 0 Составьте процедуру для нахождения даты в прошлом, т. е. даты, которая была за дн дней до указанной даты. 62. Число дней между датами Составим функцию, которая будет находить, сколько дней прошло от одной даты до другой. Условимся, что во всех случаях вторая дата является более поздней, нежели первая. Если обе даты совпадают, искомое число дней равно нулю. Например, от 5 октября 1990 г. до 11 октября того же года пройдет 6 дней, а от 1 декабря до 2 декабря одного и того же года — 1 день. Даты определим по типу записи (см. задачу 59). Опять проще всего было бы применить для решения этой задачи процедуру завтдень (см. задачу 60) — вычислять дату следующего дня до тех пор, пока она не станет равна второй (более поздней) из указанных дат. Однако если расстояние между двумя датами велико (несколько лет), то такая функция оказывается очень неэффективной — к процедуре завтдень придется обращаться много раз! Поищем более короткий путь.
Рис. 17. Схема нахождения числа дней от даты д\ до даты д2. Как можно было бы найти число дней между двумя датами д\ и д2, представим графически (рис. 17). Из приведенной схемы видно, что искомый результат будет равен Д-д' + д". Таким образом, необходимо вычислить три результата: 1) Д — число дней от начала д\.г до начала в2.гд\ 2) д' — число дней от начала года д\.гд до даты д\\ 3) д" — число дней от начала года д2.гд до даты 62. Эти результаты мы могли бы получить, имея такие две функции: функцию днг (dly д2:дата) — для нахождения числа дней от начала года dl.ad до начала года д2.гд (результат Д) и функцию днд (дт:дата) —для нахождения числа дней от начала года дт. гд до указанной даты дд (обращаясь к ней при параметрах д\ и д2у мы получим соответственно результаты д' и д").
Напомним еще раз, что в функции дни используются результаты функции високос (устанавливающей, является ли указанный год високосным) и функции дмес (находящей число дней в указанном месяце). Эти функции были разобраны в задаче 59. Поэтому, чтобы использовать где-либо функцию дни, надо не забыть включить и упомянутые функции. Использование функции дни связано с одной трудностью: иногда бывает нелегко установить, какая из дат является более ранней, а какая — более поздней (если, например, даты задаются промежуточными результатами). В этом случае следует составить функцию, проверяющую, которая из дат является более поздней. Например, если первая дата является более поздней, нежели вторая, то при обращении к функции дни надо только поменять параметры местами, чтобы более поздняя дата стала второй. Приведем функцию позже, которая устанавливает, является ли дата д2 более поздней, нежели д\: 0 Исходные данные — дата вашего рождения. Составьте программу, которая нашла бы, когда вам исполнилось (исполнится) 4000, 5000, 6000 и 7000 дней. 63. День недели Составьте функцию, которая устанавливала бы, каким днем недели является указанная дата (дата определена по типу записи — см. задачу 59). Для того чтобы решить эту задачу, надо знать день недели какой-нибудь даты. Выберем какую-нибудь воскресную дату, например 07.01.1990 (можно было бы взять дату и для какого-нибудь другого дня недели, но вычисление оказывает-
ся более естественным, когда в качестве точки отсчета выбирается воскресенье). Для того чтобы установить день недели, применим функцию дни (см. задачу 62), которая находит число дней от одной даты до другой. Поскольку мы не знаем, является ли указанная дата более поздней, нежели известная дата 07.01.1990, то нам придется прибегнуть к функции позже (см. задачу 62). Составим функцию днинед, результат которой будет относиться к типу днед.Оп определяется следующим образом: type днед=(пн, вт, ср, чт, пт, сб, ее) Функция для определения дня недели указанной даты будет выглядеть так: Чтобы использовать функцию днинед, следует включить в программу другие необходимые фунции: дни и позже (см. задачу 62), а кроме того, не забыть, что в функции дни используются функции високос и дмес (см. задачу 59). © Составьте программу, печатающую все годы нашего столетия, которые начинаются и заканчиваются в воскресенье. 0 0 Составьте программу, которая напечатала бы все годы нашего столетия, содержащие максимальное число воскресений.
64. День рождения Исходные данные — день вашего рождения. Мы составим программу, которая будет печатать все те годы и ваш возраст в эти годы, когда вы праздновали (будете праздновать) день своего рождения в тот же день недели, когда вы родились. Мы составим такой календарь на период, пока вам не исполнится 100 лет. Самый простой способ составить программу для этой задачи — применить функцию днинед, устанавливающую день недели (см. задачу 63): для каждого года проверяется, совпадает ли день недели дня рождения с тем днем, когда вы родились; если — да, производится печать. Однако можно составить и другой, более краткий вариант программы, в котором даже не ищется, в какой день недели празднуется день рождения. Поскольку 365 делится на 7 с остатком 1 (соответственно 366 mod 7 = 2), то в каждом следующем году дни недели продвигаются вперед на один (соответственно два). Например, 07.11.1989 — вторник, 07.11.1990 — среда, 07.11.1991 — четверг, 07.11.1992 — суббота. Таким образом, вместо того чтобы для каждого года обращаться к функции днинед (которая является не столь уж короткой), мы можем суммировать названные остатки: как только полученная сумма будет делиться на 7, мы получаем искомый результат. Приведем более эффективную программу деньрожд:
65. Сто лет семье Немногим суждено отметить столетний юбилей. Значительно большая вероятность того, ч"то сто лет исполнится семье. Надо только сложить возрасты всех членов семьи и дату, когда мы получим сто лет, объявить семейным юбилеем. Сколько дней длится столетие? Столетие состояло бы из 36 500 дней, если бы не было високосных годов. В течение ста лет бывает 24 или 25 високосных лет (см. задачу 59). Поскольку столетий, в которых 24 високосных года, больше, то мы будем считать, что в столетии бывает 24 високосных года. Следовательно, сто лет у нас будут равны 36 524 дням. Число членов семьи может быть различно. Даты их рождения можно было бы сохранить в массиве. При определении массива пришлось бы как-то ограничить число членов семьи. Однако, немного подумав, мы можем не прибегать к массиву дат рождения. Будем рассуждать так. Допустим, ЭВМ прочитала лишь часть всех дат рождения. Среди них можно найти Дм — дату рождения младшего члена семьи. Тогда мы посчитаем S — сумму возрастов всех членов семьи на данную дату. Найдя ее, мы можем забыть все даты рождения, за исключением Дм. Вводя новую дату рождения Дч, прежде всего мы должны проверить, является ли она более ранней, нежели Дм. Если — да, то надо найти разность дат Дч и Дм и прибавить ее к сумме S. Если — нет, то значит, что новый член семьи младше, чем все прежние. Тогда разность дат Дм и Дч надо умножить на число уже обрабо-
тайных дат и произведение прибавить к сумме S, а дату Дм заменить на дату Дч. Если введены все даты, а сумма S меньше чем 36 524, можно найти дату будущего юбилея. Она наступит тогда, когда самому младшему члену семьи исполнится ^ = 36 524-5дней п Для того чтобы программа была проще, все эти действия можно начать с первой даты, считая ее датой рождения младшего члена семьи. Мы обсудили алгоритм достаточно исчерпывающе. Теперь осталось только написать программу:
0 Измените программу юбилей таким образом, чтобы найти и напечатать все юбилеи семьи, кратные ста: 100, 200, 300-летние и т. д., которые будут иметь место начиная с даты рождения самого младшего члена семьи и до того момента, когда самому старшему члену семьи исполнится 100 лет. 0 © В этой задаче мы вычисляли, сколько в среднем дней содержится в одном столетии. Можно было бы наметить юбилей и по-другому, например суммируя только полные годы, прожитые каждым членом семьи. Тогда все юбилеи семьи будут совпадать с днем рождения кого-то из членов семьи, а в отдельных случаях (например, среди членов семьи есть родившиеся в один и тот же день года) юбилеев может вообще не быть.
Составьте программу для нахождения столетнего юбилея семьи, суммируя только полные годы, прожитые каждым членом семьи. 66. Биологические ритмы В жизни человека бывают творческие и бесплодные, счастливые и несчастливые дни, дни, когда он бывает в приподнятом или в подавленном настроении. Замечено, что возможности человеческого организма изменяются периодически. По прошествии определенного числа дней (периода) организм возвращается в то же самое состояние. Часто биологические ритмы вычисляют, основываясь на гипотезе, что существуют три цикла: физический (его период равен 23 дням), эмоциональный (период — 28 дней) и интеллектуальный (период — 33 дня). Кривые биологических ритмов могут быть представлены в виде синусоид (рис. 18). Начало всех трех кривых — день рождения. В первой половине каждого периода значения синусоиды положительны — это дни рабочего, приподнятого настроения; в дни второй части периода (когда значения синусоиды отрицательны) человек находится в пассивном, плохом настроении. В самом начале (после дня рождения) все биологические ритмы попадают в отрицательную часть периода. В каждом периоде имеется четыре критических дня: два раза синусоида находится в нулевой точке и по одному разу получает максимальное и минимальное значения. В Рис. 18. Цикл биологических ритмов.
критические дни состояние организма и психики человека неустойчиво, легкоранимо. Действительно ли циклы биологических ритмов являются точно такими и одинаково ли они подходят для каждого человека, пока еще окончательно не установлено. Биологическими ритмами стали особенно интересоваться в последние десятилетия, поскольку соответствующие календари очень легко получить при помощи ЭВМ. Составим программу, которая будет печатать календарь биологических ритмов на один год. Ее исходные данные — день рождения и год, для которого мы хотим получить биологические ритмы. Для краткости мы приведем программу, результаты которой печатаются расположенными достаточно простым образом — для каждого дня каждого месяца указывается состояние физического, эмоционального и интеллектуального циклов: « + » — положительная (хорошая) половина цикла; «—» — отрицательная (плохая) половина цикла; «*» — критический день. Это несложная, хотя и довольно длинная программа. Для того чтобы напечатать биологические циклы на один месяц, составлена процедура биомесяц. Если период цикла делится на два (таков эмоциональный цикл), то кривая пересекает ось абсцисс между двумя точками, помечающими два соседних дня. Поэтому мы вводим два критических нулевых дня (null и пиЩ. Аналогичным образом и по той же причине мы ввели два максимума (тах\ и тах2) и два минимума (mini и т'тТ). Приведем законченную программу и часть результатов, напечатанных ЭВМ (рис. 19): Рис. 19. Часть результатов, напечатанных программой биоритмы
0 Если у каких-либо двух (или у всех трех) биологических ритмов совпадают критические дни, то такой день называется дважды (трижды) критическим. Дополните программу биологических ритмов таким образом, чтобы она находила и печатала дважды и трижды критические дни.
0 0 Сторонники селенобиологической гипотезы (селено- биология исследует влияние Луны на земные организмы) утверждают, что периоды многодневных ритмов, зависящие от Луны, не должны были бы представлять собой точно определенные отрезки времени. По их мнению, Луна диктует некоторый ритм, который не является таким уж регулярным. В соответствии с этой гипотезой продолжительность периодов такова: физический период — 23,688437 суток, эмоциональный период — 28,426124 суток и интеллектуальный период — 33,163812 суток. Составьте программу для печати селенобиологического календаря биологических ритмов, если исходные данные — день рождения лица, о котором идет речь, и год, для которого требуется найти биоритмы,— известны. (>7. Настенный календарь Составим программу для печати календаря произвольного года. Дни месяца мы расположим, как обычно, столбцами, так что каждый столбец соответствует одной неделе. Месяц может иметь самое большее 6 столбцов. Например: 2 9 16 23 30 3 10 17 24 31 4 И 18 25 5 12 19 26 6 13 20 27 7 14 21 28 1 8 15 22 29 Календарь одного месяца определим следующим образом: type жесж{ = аггау[1..6, пн..вс] of 0..31 При помощи нулей мы помечаем несуществующие дни, при печати вместо нулей мы оставим пробелы. Теперь весь календарь мы можем определить при помощи массива, который составляют двенадцать массивов типа месяц: type календ = array [январь..декабрь] of месяц Итак, задача программы — сформировать массив типа календ и напечатать его в соответствии с определенными правилами. Поскольку для всех месяцев массивы формируются сходным образом, составим процедуру form для образования массива одного месяца, т. е. массива типа месяц.
Для того чтобы образовать массив месяца, необходимо знать, с какого дня недели начинается месяц и сколько в этом месяце дней. Для нахождения числа дней в месяце мы имеем функцию дмц (см. задачу 59). День недели можно было бы установить с помощью функции днинед (см. задачу 63), однако она является длинной, а нам достаточно знать только, каким днем является первый день первого месяца (т. е. с какого дня недели начинается новый год). С каких дней недели начинаются прочие месяцы, мы будем устанавливать из непосредственно предшествующего месяца. Для этого составим особую краткую функцию новый. Алгоритм, устанавливающий день недели нового года, сходен с алгоритмом, находящим день рождения (см. задачу 64), поэтому мы не будем объяснять его более подробно. Массив мц типа месяц формируется следующим образом: Сначала заполним нулями пустые клетки в столбце месяца, т. е. элементы массива месяц. Подчеркнем, что нули могут быть только в первом, пятом или шестом столбце. Календарь формируется посредством двенадцатикратного (каждый раз для нового месяца) обращения к процедуре form, алгоритм которой мы только что описали. При наличии сформированного календаря остается только красиво его напечатать. Для этого составим процедуру печать. Можно расположить месяцы различным образом: на одной горизонтали по 2, или по 3, или по 4, или по 6. В высоту, календарь в этих случаях имел бы соответственно 6, 4, 3, 2 месяца. Площадь календаря определим при помощи константы чсмц. Следовательно, для процедуры печать мы должны указать, начиная с какого и до какого месяца производить печать. Мы составим процедуру печать таким образом, чтобы она печатала строку высотой в один месяц. Приведем законченную программу:
Календарь 1987 г., напечатанный ЭВМ, которая выполнила данную программу, приведен на рисунке 20. 68. Лунный календарь Мы пользуемся солнечным календарем, основанием которого является цикл видимого движения Солнца по небу — год. Календарь составлен таким образом, что важные моменты движения Солнца — дни весеннего и осеннего равноденствия, самый длинный и самый короткий день — попадают на один и тот же (или почти один и тот же) день года. Между тем роль лунного цикла оказывается второстепенной. Месяц длиннее, чем лунный цикл. Поэтому фазы Луны не связаны с определенными днями месяца. В мусульманских странах используется лунный календарь. Лунные годы считают начиная с 16 июля 622 г. по юлианскому календарю (дата бегства Магомета из Мекки в Медину). Таким образом, в лунном календаре эта дата представляет собой первый день первого месяца первого года. Календарь составлен таким образом, что год всегда начинается с новолуния. Поскольку лунный период составляет 29,5306 суток, то месяцы лунного календаря (всего их 12)
Рис. 20. Календарь 1987 года
содержат 29 или 30 дней. Нечетные месяцы содержат по 30 дней, а четные — по 29 дней. Год по этому календарю отстает от подлинного лунного года на 0,0306X12=0,3672 суток. За 30 лет эта разница составляет 11 суток. Поэтому в каждом 30-летнем цикле 11 лет считаются високосными. Принято считать високосными 2, 5, 7, 10, 13, 16, 18, 21, 24, 27 и 29-й год цикла. Дополнительный день прибавляется к последнему месяцу, который в високосные годы вместо 29 дней содержит 30 дней. Обычный лунный год содержит 354 дня, високосный — 355. Лунный год на 11 дней короче, нежели солнечный год. Поэтому было бы интересно составить программу, которая будет вычислять, например, какая сегодня дата по лунному календарю. Составим программу, которая будет превращать указанную дату григорианского календаря в соответствующую ей дату лунного календаря. Прежде всего приведем схему программы:
Процедура Магомет очень похожа на процедуру будущее солнечного календаря (см. задачу 61). Поскольку нам остается только приложить записанные в ней вычисления к лунному календарю, мы не будем пояснять ее детальнее. Действия, указанные во втором прямоугольнике, записываются на языке Паскаль следующим образом: Действия третьего прямоугольника совсем просты —, печать дат солнечного календаря и соответствующих им дат лунного календаря. Соединив все части, получим законченную программу:
После того как этой программе были предъявлены исходные данные — дата 1 января 1987 г., ЭВМ напечатала 1.1.1987 ПО ЛУННОМУ КАЛЕНДАРЮ 29.4.1407 © Составьте программу, которая бы устанавливала дату солнечного календаря, соответствующую указанной дате лунного календаря. 0 0 Составьте процедуру для нахождения числа дней от одной даты лунного календаря до другой. 69. Рисование геометрических фигур Можно без труда составлять программы, в соответствии с которыми ЭВМ при помощи своих символов будет «рисовать» различные геометрические фигуры. Приведем программу, которая печатает прямоугольник, состоящий из символов +, —, 1. Исходные данные — вы-
сота и длина прямоугольника (выражены числом символов). При а = 5, а 6 = 8 ЭВМ напечатала прямоугольник, приведенный на рисунке 21. 0 Составьте программу, которая печатала бы ромб, заполненный звездочками. Входное данное — длина стороны ромба. 0 0 Составьте программу, которая бы печатала равнобедренный треугольник, заполненный звездочками. Входное данное — высота треугольника в звездочках. 70. Квадрат из цифр Интересным в своем роде является квадрат, составленный из чисел от 0 до п (рис. 22). Составим программу для печати этого квадрата чисел (п — входное данное, причем м^9). Прежде всего обратим внимание вот на что. Если бы мы начертили систему координат, центр которой совпадал бы с цифрой 0 (центром квадрата), а оси были бы параллельна сторонам квадрата, то в точке (/, /) надо было бы печатать число, представляющее собой больший из модулей коорди-
Рис. 21. Рис. 22. Квадрат цифр Рис. 23. Ромб цифр. нат (/, /). Это можно выразить посредством такого условного оператора: Все позиции (/, /), в которых —n^i^n, — n^j^tiy просмотрим при помощи двойного цикла: Таким образом, вся программа выглядит так: 0 Напишите программу, которая печатала бы шахматную доску такую, чтобы у нее черные поля представляли собой квадраты из цифр указанного вида, а белые состояли из пробелов. Входное данное — максимальное число п. 0 0 Составьте программу для печати ромба из цифр (рис. 23). Входное данное — цифра п(п^9). 71. Симметричные фигуры Из отдельных символов можно составить различные рисунки. Программы, печатающие такие рисунки, совсем простые. Достаточно записать символы, входящие в рисунок, в оператор печати. Если же в расположении символов в ри-, сунке наблюдаются определенные закономерности, то открывается возможность составлять более интересные программы печати рисунка.
Рис. 24. Симметричная фигура. Рис. 25. Фигура (а) и зеркальное ее отражение по отношению к оси ординат (б) Например, интересно составлять программы печати симметричных рисунков. В этом случае необходимо ввести только часть рисунка, а весь рисунок можно получить при помощи соответствующих трансформаций (отражений, повторов) введенной части. Например, для того чтобы нарисовать фигуру, изображенную на рисунке 24, достаточно было бы располагать только его частью, находящейся внутри квадрата, а всю фигуру целиком мы получили бы, поворачивая эту часть вокруг центра на 90°, 180°, 270° или же посредством зеркального отражения ее относительно оси ординат, а затем зеркального отражения обеих полученных частей относительно оси абсцисс и т. д. Таким образом, для того чтобы рисовать симметричные фигуры, важно уметь отражать имеющуюся часть фигуры и поворачивать ее на какой-нибудь угол. Составим процедуры для выполнения этих действий. Входное данное — квадратная картинка (она проще, нежели прямоугольная). Определим тип картинки: type строка = array [\..n] of char; картинка = array [l../г] of строка Размер картинки п представляет собой определяемую константу. Составим процедуру для получения зеркального отражения заданной фигуры относительно оси ординат. Зеркальное отражение фигуры приведено на рисунке 25.
Теперь составим процедуру, поворачивающую фигуру на 90° против часовой стрелки: Различные комбинации этих процедур позволяют нам получить разнообразные симметричные рисунки. 0 Используя процедуры отражение и поворот, составьте процедуру зеркального отражения относительно оси абсцисс. 0 © Составьте процедуру, которая получала бы из картинки (входного данного) ее негатив, т. е. вместо символа оставляла бы пробел, а вместо пробела печатала бы какой-нибудь другой символ (например, 'н'). © 0 © Составьте процедуру, которая увеличивала бы заданный рисунок в п раз. 72. Орнаменты Путем многократного повторения небольшой фигуры и ее разнообразных отражений можно получить красивые орнаменты. Они могут пригодиться, в частности, любителям рукоделия. Составим программу, которая из небольшого исходного рисунка будет создавать орнамент. Будем придерживаться следующего порядка: сначала осуществляется зеркальное отражение исходной фигуры относительно оси абсцисс, затем — зеркальное отражение полученной фигуры относительно оси ординат. После этого получившаяся фигура повторяется пг раз по горизонтали (вправо) и п раз — по вертикали (вниз). Исходные данные программы — фигура размером hh символов и числа тип (причем 1^т^7, 1^п^5).
Мы приняли такие ограничения, чтобы была возможной распечатка (листинг) результатов программы. Определим тип исходной фигуры (трафарета): type строка = array [1../] of char; трафарет = sltray [1..A] of строка; (/— ширина трафарета, а А — высота). Для того чтобы напечатать первую строку орнамента, необходимо m раз напечатать элементы массива е, относящегося к типу строка: е{\\ е[2\ ..., *[/], *[/], е[1-\\ ..., в [1], и повторить это m раз. Аналогичным образом печатаются и остальные строки орнамента. Приведем законченную программу:
Рис. 26. Орнамент. Выполнив эту nporpaMiMy при заданной исходной фигуре (рис. 26, а) и при п = 2, m = 5, ЭВМ напечатала орнамент, приведенный на рисунке 26, б.
Рис. 27. Большие цифры, изображенные звездочками. Подчеркнем, что исходные данные лучше всего представить наглядно: трафарет изобразить естественным образом и восьми строках. Для того чтобы перейти к новой строке, используется оператор readln. 73. Символы большого формата Алфавитные печатные устройства печатают все символы одного размера (формата). Большие символы, при помощи которых иногда печатается текст (например, заголовки), бывают составлены из отдельных маленьких символов, подобно тому как из различных лампочек образуются символы световой рекламы. Составим программу, которая будет читать натуральные числа и печатать их при помощи больших цифр, как показано на рисунке 27. В программе надо будет иметь сформированные образцы цифр. После этого можно читать строку за строкой исходные данные (числа) и печатать их при помощи больших цифр. Составим такую схему программы:
Образцы символов можно «нарисовать» при помощи констант — строк символов — и присвоить их элементам массива, изображающим эти образцы Например, число 4 образуется так: Аналогичным образом можно образовать и остальные цифры. Мы получим длинную и неинтересную процедуру. Другой способ сформировать образцы цифр состоит в том, чтобы изображать их в виде исходных данных, предшествующих действительным исходным данным (числам, которые требуется напечатать), и эти данные сохранять в массиве. Такое формирование цифр приносит пользователю программы больше хлопот (необходимо вводить и образцы цифр), но больше и свободы (можно выбрать и другие образцы цифр). Приведем программу, составленную вторым способом:
0 Составьте программу для печати букв большого формата. 74. Частота повторения букв В каждом языке одни буквы алфавита употребляются чаще, другие — реже. Например, установлено, что в английском языке чаще всего встречается буква еу второе место занимает буква /. Установить частоту употребления букв можно посредством анализа написанного на данном языке достаточно длинного текста. Составим программу, позволяющую установить частоту повторений букв для русского языка. Запишем в массив, сколько раз каждая буква алфавита повторяется в тексте: var d:array ['А'./я'] of integer; Частоту повторений букв представим в процентах: для этого число повторений в тексте каждой буквы разделим на общее число всех букв из текста и умножим на 100. Приведем составленную программу:
0 Измените представленную программу так, чтобы буквы (и их повторяемость в процентах) печатались в соответствии с числом их повторений в рассматриваемом тексте: первая — буква, встречающаяся в тексте чаще всего, вторая — та, что по частоте употреблений занимает второе место, и т. д. Если несколько букв в тексте встретилось одинаковое число раз, то безразлично, какая буква будет написана первой. 0 © Составьте программу, которая подсчитывает частоту повторений двубуквенных сочетаний. Печатайте только те пары букв, частота которых не менее 10%. © © 0 Составьте программу, которая бы подсчитывала частоту повторений слов той или иной длины в выбранном тексте: подсчитывала бы, сколько слов состоит из одной буквы, из двух, из трех и т. д. 75. Частота повторения слов Было бы интересно установить, сколь часто в поданном на вход тексте встречаются одинаковые слова. Составим программу, позволяющую решить эту задачу, опираясь на результаты задачи 74. Будем считать, что в тексте не более тахчсл различных слов, а самое длинное слово в тексте имеет длину не более чем тахдсл букв. Для того чтобы поместить слово, определим упакованный массив — строку символов: type слово = packed array [1.. тахдсл] of char Слова и их частота (число повторений в тексте), записываемые в массив, состоят из записей. Тип массива определяется следующим образом: type частота= array [I..тахчсл] of record х: слово; d: integer end Приведем составленную программу:
© Приведенную программу измените так, чтобы она печатала слова в порядке уменьшения их частоты. Слова, частота которых меньше 10%, не печатайте. 76. Пилообразный текст Интересно располагать текст непривычным образом, например в форме пилы, елочкой или даже в виде спирали. Составим программу, которая печатала бы тексты в форме пилы. Печать будет происходить таким образом: в первой строке — одно слово, каждая следующая строка должна быть хотя бы несколько длиннее предыдущей. Когда очередная строка имеет заранее указанную максимальную длину, а текст не поместился в ней, снова повторяется то же самое начиная со строки, состоящей из одного слова,— печатается новый зубец «пилы». Приведем составленную программу:
0Н Рис. 28. Пилообразный текст. вступил в темные широкие сени, от которых подуло холодом, как из погреба. Из сеней он попал в комнату, тоже темную, чуть-чуть озаренную светом, выходившим из-под широкой щели, находившейся внизу двери. Отворивши эту дверь, он наконец очутился в свету и был поражен представшим беспорядком. Казалось, как будто в доме происходило мытье полов и сюда на время нагромоздили всю мебель. На одном столе стоял даже сломанный стул, и рядом с ним часы с остановившимся маятником, к которому паук уже приладил паутину. Тут же стоял прислоненный боком к стене шкаф с старинным серебром, графинчиками и китайским фарфором. На бюре, выложенном перламутною мозаикой, которая местами уже выпала и оставила после себя одни желтенькие желобки, наполненные клеем, лежало множество всякой всячины: куча исписанных мелко бумажек, накрытых мраморным позеленевшим прессом с яичком наверху, какая-то старинная книга в кожаном переплете с красным обрезом, лимон, весь высохший, ростом не более лесного ореха, отломленная ручка кресел, рюмка с какою-то жидкостью и тремя мухами, накрытая письмом, кусочек сургучика, кусочек где-то поднятой тряпки, два пера, запачканные чернилами, высохшие, как в чахотке, зубочистка, совершенно пожелтевшая, которою хозяин, может быть, ковырял в зуьах своих еще до нашествия на Москву французов. (Гоголь Н.Б. Мертвые души) Эта программа печатает весьма несовершенную "пилу" — "зубья" имеют неодинаковую длину и ширину На рисунке 28 приведена форма, в которой программа "пила" расположила заданный текст.
© Составьте программу, которая будет печатать вводимый текст следующим образом: в первой строке было бы одно слово, во второй — два, в третьей — три и т. д. Если текст не закончится, когда мы дойдем до строки заранее определенной длины, начните опять с начала. Знаки препинания набираются непосредственно рядом со словом без пробела. Например: человек живет настоящую жизнь, если счастлив счастьем других (Гёте). © © Составьте программу, которая будет печатать вводимый текст елочкой, т. е. так, чтобы "зубья" "пилы" были с обеих сторон. 77. Билистинг Иногда весьма удобно напечатать текст программы в двух расположенных рядом экземплярах, т. е. получить билистинг. Условимся: длина строки исходных данных (программы или какого-нибудь другого текста) не более 55 символов (чтобы оба экземпляра листинга поместились на листе бумаги). Второй экземпляр программы начнем печатать с 61-й позиции. Приведем составленную программу:
Выполнив данную программу, когда исходные данные — это сама программа билист, ЭВМ напечатала билистинг, приведенный на рисунке 29. © Составьте программу, которая печатала бы я-листинг (определите константу п и соответствующую ей длину строки). 78. Техническое редактирование текста Следует позаботиться, чтобы напечатанный текст выглядел красиво: чтобы пробелы между словами были одинаковыми, заголовки находились посередине текста и т. д. Для этого создаются программы технического редактирования текста. Приведем программу, которая разделяет текст на строки Рис 29 Билистинг
желаемой длины и последнее слово в каждой строке подтягивает к правому краю, делает одинаковыми пробелы между словами. Таким образом текст располагается во всех газетах и журналах. Для простоты не будем требовать, чтобы программа переносила слова из одной строчки в другую. Группы символов, между которыми в исходном тексте (в исходных данных) нет пробелов, будем считать неделимыми словами. Например, в тексте: «О, какой счастливый 1990 год!» — будет 5 слов. Запятая принадлежит первому слову «О,», а восклицательный знак — последнему: «год!». Какое слово будет последним в строке и на сколько позиций его следует сдвинуть вправо, выясняется только по прочтении строки указанной длины. Однако, чтобы сделать одинаковыми пробелы между словами, иногда необходимо сдвинуть вправо не только последнее, но и другие слова в данной строке. Часть прочитанного текста (строку указанной длины) следует сохранить в буфере — в массиве символов, после этого можно подсчитать пробелы между словами, сдвинуть к краю строки слова и напечатать их. Сдвигать слова с одного края на другой можно и в процессе печати, вставляя между словами дополнительные пробелы.
Так мы и будем делать. Таким образом, выясняется схема программы. Она должна была бы состоять из двух процедур: одна читает исходный текст и заполняет буфер, другая печатает текст, находящийся в буфере, и вставляет пробелы. В основной части программы к этим процедурам следует обращаться попеременно до тех пор, пока не закончится исходный текст. Приведем программу:
Обе процедуры (чтение и печать) используют одни и те же данные (переменные). Поэтому мы описали их в основной части программы, а процедуры составили без параметров. Процедура чтение собирает прочитанный текст в буфере, оставляя только по одному пробелу между соседними словами. Поскольку буфер на один символ длиннее, нежели печатаемая строка, то, взглянув на буфер, мы можем сказать, прочтено ли последнее слово полностью (тогда последний символ буфера — пробел) или только частично. Процедура печать печатает все находящиеся в буфере символы: от первого до последнего символа последнего целого (вошедшего полностью) слова. Кроме того, между словами вставляются дополнительные пробелы.
Если в конце буфера была часть слова, она не печатается, а переносится в начало буфера. После этого процедура чтение читает конец слова, новое слово и т. д. Текст отредактирован красиво, если в строке помещается по крайней мере два соседних слова. Если в строке поместилось только одно слово, то пробелы остаются после него. Если слово не помещается в строке, то оно переносится как угодно. Исходные данные и результаты (технически отредактированный текст) данной программы приведены на рисунке 30. 79. Голландский флаг Это довольно популярная задача по программированию [5], формулировка которой связана с цветами голландского флага. Камешки: красные, белые, синие — располагаются в столбик. Надо упорядочить камешки таким образом, чтобы их цвета шли в том же порядке, что и цвета голландского флага — красные, белые, синие. Предположим, что камешки пронумерованы в порядке их следования сверху вниз. Камешками ведает робот. Он может выполнять две команды: 1) определить цвет /-го (1^/^/г) камешка и 2) поменять местами 1-й и /-й камешки (1 <л\ j^n), n — число камешков в столбике. Роботом управляет вмонтированный в него микропроцессор. Напишем процедуру, посредством которой робот мог бы расположить камешки в порядке цветов голландского флага. В процедуре мы будем использовать обращение к функции цвет и процедуре замена, которые соответствуют упомянутым командам робота. Их заголовки таковы: function цвет (l:integer):uy b\ procedure замена (/, j: integer); Тип цвета камешка определяется следующим образом: type цв= (красный, белый, синий); Вмонтированный в робота микропроцессор имеет небольшой объем памяти. Поэтому в ней могут храниться цвета лишь небольшого числа камешков. Кроме того, установление цвета продолжается долго, поэтому недопустимо много раз «смотреть» на один и тот же камешек. Как же лучше рассортировать камешки? Прежде всего следовало бы определить область тех камешков, которые
Я пошел в направлении леска, повернул направо, забирал, все забирал, как мне советовал старик, и добрался наконец, до большого села с каменной церковью в новом вкусе, то есть с колоннами, и обширным господским домом, тоже с колоннами. Еще издали, сквозь частую сетку дождя, заметил я избу с тесовой крышей и двумя трубами, повыше других, по всей вероятности жилище старосты, куда я и направил шаги свои, в надежде найти у него самовар, чай, сахар и не совершенно кислые сливки. В сопровождении моей продрогшей собаки взошел я на крылечко, в сени, отворил дверь, но вместо обыкновенных принадлежностей избы, увидал несколько столов, заваленных бумагами, два красных шкафа, забрызганные чернильницы, оловянные песочницы в пуд веса, длиннейшие перья и прочее. На одном из столов сидел малый лет двадцати, с пухлым и болезненным лицом, крошечными глазками, жирным лбом и бесконечными висками. Одет он был, как следует, в серый нанковый кафтан с глянцем на воротнике и на желудке. (Тургенев И.С. Записки охотника) а) Я пошел в направлении леска, повернул направо, забирал, все забирал, как мне советовал старик, и добрался наконец, до большого села с каменной церковью в новом вкусе, то есть с колоннами, и обширным господским домом, тоже с колоннами. Еще издали, сквозь частую сетку дождя, заметил я избу с тесовой крышей и двумя трубами, повыше других, по всей вероятности жилище старосты, куда я и направил шаги свои, в надежде найти у него самовар, чай, сахар и не совершенно кислые сливки. В сопровождении моей продрогшей собаки взошел я на крылечко, в сени, отворил дверь, но вместо обыкновенных принадлежностей избы, увидал несколько столов, заваленных бумагами, два красных шкафа, забрызганные чернильницы, оловянные песочницы в пуд веса, длиннейшие перья и прочее. На одном из столов сидел малый лет двадцати, с пухлым и болезненным лицом, крошечными глазками, жирным лбом и бесконечными висками. Одет он был, как следует, в серый нанковый кафтан с глянцем на воротнике и на желудке. (Тургенев И.С. Записки охотника) б) Рис. 30. Первоначальный текст (а) и тот же самый технически отредактированный текст (б)
Область красных камней Камни неопределенного цбета Область белых камней Область синих камней Рис. 31. Схема сортировки камешков. не надо менять, поскольку они находятся на своих местах. Это все красные камешки, находящиеся вверху столбика, и все синие камешки — внизу столбика. Номер первого сверху не красного камешка обозначим нк(пг), а номер первого снизу не синего камешка — не(nm). Тем самым эти номера определяют область красных и синих камешков. Сверху от синих камешков должны быть белые. Первый не белый камешек, находящийся сверху от синих, обозначим нб(пЪ). Камешки, начиная с нб и кончая я/с, составляют четвертую область — неясного цвета (рис. 31). Меняя друг с другом камешки нк, нб, не и тем самым сокращая область камешков неясного цвета, можно постепенно решить задачу. Приведем схему соответствующей процедуры:
Записав указанные в прямоугольниках действия на языке Паскаль, получаем всю процедуру:
© Составленная процедура флаг удобна тем, что нет необходимости запоминать установленные цвета камешков. Но у нее есть и недостаток. Цвета некоторых камешков приходится устанавливать по два раза. Составьте более совершенную процедуру, устанавливающую цвет каждого камешка лишь по одному разу. 0 © Для задачи «Голландский флаг» составьте процедуру, которая управляла бы роботом, способным менять местами только два соседних камешка. 80. Сортировка данных Часто удобно иметь данные (особенно когда их много) расположенными в порядке возрастания или в порядке убывания. Такое упорядочение в программировании зовется сортировкой. Сортировать можно любые данные — важно только, чтобы их можно было тем или иным образом сравнивать (устанавливать, какое из них является наименьшим). Сортировать можно, например, значения скалярных типов, символы, упакованные массивы символов (строки). Сортировка применяется во множестве задач. Например, слова в словаре или фамилии в списке располагаются в алфавитном порядке. И вообще, для того чтобы легче находить то или иное данное в большом массиве данных, следует их рассортировать (см. задачу 75). Поэтому в программах часто применяют сортировку. Есть различные методы сортировки. Одни из них простые, но более медленные, другие быстрые, но более сложные. Одни сортируют каждый массив заново, другие распознают уже упорядоченные части массива и потому работают быстрее. Видный специалист по программированию Д. Кнут посвятил сортировке и поиску данных почти весь второй том «Искусства программирования» [7]. Составим процедуру, годную для того, чтобы данные любого типа рассортировать в неубывающем порядке. Важно, чтобы на этом типе были заданы операции сравнения
(хотя бы одна, например <). Предназначенные для сортировки данные следует записать в массив следующего типа: type массив = array [l../тсал:] of данное Результатом процедуры сортировки должен быть тот же самый массив — только его элементы должны быть расположены в порядке от наименьшего к наибольшему. Применим один из самых простых методов сортировки — метод отбора. Его суть: находится наименьший (точнее, не превышающий всех прочих) элемент массива и меняется местами с первым; затем в части массива, начинающейся со второго элемента, снова ищется наименьший элемент и обменивается со вторым и т. д. Когда обменяется последний элемент, массив считается упорядоченным. Записав эти действия на языке Паскаль, получим следующую процедуру:
Использование в процедуре параметра длина составляет условие того, чтобы сортировать не весь массив, а только его часть (когда длинсКтах). Чтобы был рассортирован весь определенный массив, к процедуре отбор следует обращаться следующим образом: отбор (х, max) Если мы захотим использовать эту процедуру для упорядочения массива целых чисел, то тип данное в программе надо будет определить следующим образом: type данное = Integer Если захотим упорядочить слова по алфавиту, то тип данное надо будет определить так: type данное = packed array [I..длин] of char (константа длин определяется таким образом, чтобы она была не меньше чем число букв в самом длинном слове). 0 Составьте процедуру, которая бы упорядочивала массив анкет так, чтобы фамилии были расположены в алфавитном порядке. Тип анкеты в программе определяется так: type данное = record фамилия имя: packed array [1..15] of char; годрожд: 1900 .. 2000 end © © Исходные данные — последовательность целых чисел, содержащая не более 1000 членов. Создайте программу чтения этих чисел и печати их в неубывающем порядке. 81. Сортировка методом «пузыря» При выполнении программы, приведенной в задаче 80, в неотсортированной части массива находится наименьший элемент и переносится в начало этой части — словно бы погружается под большие. Можно поступить и противоположным образом — наибольшие элементы поднимать на поверхность. Так и происходит при сортировке методом «пузыря». Поочередно сравниваются соседние элементы: л:[1] с х[2], х[2] с х[3], jc[3] с х[4] и т. д. Если x[i—\\>x[i], то элементы меняются местами: /-м элементом становится (I— 1)-й элемент, который опять сравнивается уже с элементом *[£+!]. Таким образом, как пузыри в воде, большие
элементы быстрее всплывают на поверхность, а самый большой — быстрее всех. Тип массива определим так же, как и в задаче 80. Составим процедуру: Особенно важна переменная обмен. Если массив уже упорядочен, то во внутреннем цикле не меняется местами ни одна пара элементов и значение этой переменной остается false. Это значит, что можно закончить сортировку. Если применить процедуру к уже упорядоченному циклу, внешний цикл будет применяться только один раз, а внутренний — длина — один раз. Если массив неупорядочен — столько же раз, сколько и в задаче 80. В этой программе мы упорядочили элементы от наименьшего к наибольшему, с тем чтобы нагляднее было сравнение с пузырем. Можно упорядочить массив от наибольшего элемента к наименьшему (тогда на поверхность всплывали бы меньшие элементы). © Рассмотрев приведенную процедуру «пузырь», вы заметите вот что: если при каком-либо просмотре не надо было сдвигать элементы, находящиеся в конце просматриваемой части, то и во время всех дальнейших просмотров их не надо будет сдвигать. Учитывая это, усовершенствуйте приведен-
ную процедуру (необходимо запомнить место последнего обмена, так как следующий просмотр достаточно будет выполнить лишь до этого места). 82. Быстрая сортировка Сортировать данные приходится часто. Поэтому надо искать самые быстрые способы сортировки. Составим процедуру, применяя так называемый метод быстрой сортировки. Применением этого метода неупорядоченный массив сортируется намного быстрее, чем упорядоченный. Если мы исследуем, каким образом упорядочивают массив уже рассмотренные процедуры сортировки, то заметим, что при первом «обороте» внешний цикл ставит на свое место (в начало массива в процедуре отбор или в конец массива в процедуре «пузырь») один — наименьший или наибольший — элемент данного массива. После этого массив как бы распадается на две части: отсортированную (содержащую один элемент) и неотсортированную (которую составляют все прочие элементы). Когда цикл выполняется снова, то аналогичным образом сортируется (и снова разбивается на две части) неотсортированная часть массива. Продолжительность цикла прямо пропорциональна числу сортируемых элементов. Таким образом, она уменьшается медленно. Продолжительность цикла уменьшалась бы быстрее, если бы, вместо того чтобы отщеплять от массива один элемент, мы разбивали бы массив на две примерно равные части, например пополам. Как это сделать? Выберем не наименьший и не наибольший элемент массива. Назовем его средним. Средний элемент действительно находится на своем месте, если все прочие элементы, находящиеся слева, не превосходят его, а находящиеся справа — не меньше его. После такого упорядочения массива средний элемент можно больше не трогать, а часть массива, находящуюся слева, и часть, находящуюся справа, сортировать отдельно. Таким образом, самое важное — найти место для среднего элемента. Это можно выполнить посредством следующей процедуры:
Мы считаем, что массив определен так, как и в предыдущих задачах на сортировку (см. задачу 80): const тах = . . .; (* максимальная длина массива *) type данное = . . .; (* любой простой тип *) массив = array [\..max\ of данное Как работает процедура середина, можно проиллюстрировать на таком примере: 25 20 13 37 12 92 86 33 25 20 13 37 12 92 86 33 25 20 13 37 12 92 86 33 25 20 13 37 12 92 86 33 12 20 13 37 Щ 92 86 33 12 20 13 37 25 92 86 33 12 20 13 37 25 92 86 33 12 20 13 37 25 92 86 33 12 20 13 © © 92 86 33 12 20 13 25 37 92 86 33 В первой строке приведены восемь чисел — это исходный массив х. В последней строке тот же самый массив, когда процедура заканчивает работу. Подчеркнутые элементы — это те, на которые указывают индексы лв и пру а обведенные — элементы, только что поменявшиеся местами. Ввиду того что две полученные части массива, в свою очередь, могут быть длинными, каждая из них снова может быть подвергнута делению на две части.
Такую сортировку удобно программировать, применяя рекурсию. Приведем процедуру быстрый, которую мы получили, перестроив программу середина: При обращении к процедуре быстрый следует указывать индексы первого (лев) и последнего (прав) элементов массива ху например быстр (1, max, x). Переставляемый на свое место элемент мы называем средним с известными оговорками: попадет ли он в середину массива, зависит от его значения. Когда исходный массив неупорядочен, то можно надеяться, что значения его элементов располагаются случайным образом и упомянутый элемент окажется в различных местах массива. Если исходный массив упорядочен, то мы всегда будем попадать на тот или другой край массива и в таком случае данный метод будет работать ничуть не быстрее, нежели предыдущие методы (см. задачи 80 и 81). 0 Измените процедуру метода быстрой сортировки таким образом, чтобы на свое место попадал элемент массива, находящийся в середине массива. Можно ли утверждать, что измененная таким образом процедура всегда работает быстрее, чем процедура быстр} 83. Поиск Есть шуточный совет, как поймать в Африке льва. Разделим Африку пополам. Ясно, что лев будет находиться только в одной половине. Та половина, в которой находится лев,
снова делится пополам и т. д. Площадь Африки равна приблизительно 30 млн. км2. Следовательно, после примерно 45 делений мы получим площадку, не превышающую 1 м2. Теперь на такой площадке льва поймать нетрудно. Идею, воплощенную в данном совете, можно использовать при поиске элемента в упорядоченном массиве. Делим массив пополам. Далее пополам делится та часть, в которой находится элемент и т. д. Поскольку данные упорядочены (в порядке возрастания или наоборот), то, сравнивая искомый элемент со средним элементом массива, мы в состоянии сказать, в какой половине находится искомый элемент. (К сожалению, установить, в какой из частей, полученных при делении Африки, находится лев, невозможно.) Составим функцию, которая проверяла бы, содержится ли искомая фамилия в представленном списке (массиве) фамилий, отсортированном по алфавиту. Значение функции будет равно номеру фамилии по списку; если фамилия не обнаружена, значение функции равно нулю. Каждая фамилия — это строка (упакованный массив) символов, длину которой определяет константа длинафам. Длину массива (списка) фамилий определяет константа сдлина. Таким образом, типы исходных данных определяются следующим образом:
84. Римские цифры Для записи римскими цифрами используются символы (латинские буквы) I, V, X, L, С, D, М, обозначающие соответственно числа 1, 5, 10, 50, 100, 500, 1000. При их помощи можно обозначать натуральные числа. Если большая цифра находится перед меньшей, то они складываются, а если меньшая — перед большей (в этом случае она не может повторяться), то меньшая вычитается из большей. Например, XL = 50-10 = 40; MCXXIV= 1000 + 100+ 10 + + 10 + 5—1 = 1124. Цифры М, С, X и I могут повторяться не более трех раз подряд. Все остальные цифры (D, L и V) — только по одному разу. Таким образом, самое большое число, обозначаемое римскими цифрами,— это MMMCMXCIX, т. е. 3999. Римляне записывали и большие числа. Буква т отмечала начало тысяч. Но мы будем рассматривать числа, не превышающие 3999. Таблица 4 Римские цифры и их пары и соответствующие числа, записанные арабскими цифрами Если бы считали самостоятельными римскими цифрами не только вышеупомянутые отдельные символы, но и их пары IV, IX, XL, XC, CD и СМ (см. табл. 4), то для перевода записи числа римскими цифрами в десятичную запись (арабскими цифрами) мы получили бы весьма простое правило: число, записанное римскими цифрами, было бы равно сумме своих цифр. Составим программу, которая запись любого данного
числа арабскими цифрами переводила бы в запись римскими цифрами: Приведем другую, более сложную, но интересную программу. В ней используются только основные римские цифры. Процедура рим записывает фрагмент данного числа п при помощи букв х, у, z в соответствии с правилами записи чисел римскими цифрами. Мы оставляем читателю самому удостовериться, что эта программа эквивалентна предыдущей:
© Составьте программу, которая переводила бы запись числа римскими цифрами в десятичную запись (арабскими цифрами). 85. Почтовые индексы Посылая письмо, в указанном месте на конверте мы пишем индекс. Каждое отделение связи имеет свой индекс, не совпадающий с индексами других отделений. Поэтому письма может сортировать автомат. Он прочитывает цифры и устанавливает, куда послано письмо. Предположим, что автомат просматривает линии, образующие цифры в таком порядке, как показано на рисунке 32. Затем он передает в ЭВМ номера проведенных линий. Например, при прочтении единицы в ЭВМ попадают числа 4, 5, 9. Составим функцию, которая бы в соответствии с обнаруженными автоматом проведенными линиями устанавливала бы цифру. Иными словами, исходными данными функции должны
быть образующие цифру линии (номера линий), а результатом — опознанная цифра. Тип образа цифры на конверте определим так: type индекс = set of 1..9 Опознанная цифра будет принадлежать интервалу 0..9; если комбинация проведенных линий не образует никакой цифры, тогда условимся считать значение функции равным — 1. Следовательно, функция может принимать значения следующего типа: цифра= — 1 ... 9 Составим функцию: Рис. 32. Трафарет индекса почты © Когда мы пишем индексы на конверте, мы можем ошибиться: провести ненужные линии или не провес™ их там, где необходимо. Предположим, что мы можем сделать только одну ошибку: провести одну лишнюю черту или не прозести одну нужную черту (но не обе ошибки одновременно). Посмотрим, в каких случаях можно обнаружить или даже исправить ошибку. 1. Коды двух цифр отличаются одной позицией, например коды цифр 0 и 8 — только одной чертой. Если сделана ошибка как раз в этой позиции (при написании нуля проведена 8-я линия или при написании восьми эта линия не проведена), получается правильная, но не та цифра.
2. Коды двух цифр различаются двумя позициями. В таком случае, сделав одну ошибку, мы не сможем превратить одну цифру в другую. Если коды различаются смежными позициями, мы не сможем сказать, от какой цифры мы попали в эту позицию, т. е. не сможем исправить ошибку. 3. Коды двух цифр, например цифр 4 и 5, различаются тремя позициями. Тогда, если сделана одна ошибка, новый код отличается от правильной цифры одной позицией, а от другой цифры — двумя позициями. В таком случае можно исправить ошибку. Следовательно, для того чтобы можно было исправить одну ошибку в цифре индекса, любые две цифры кода должны различаться не менее чем тремя позициями. © Измените кодирование цифр индекса, но так, чтобы можно было исправить одну ошибку (не меняя при этом 9-линейный трафарет). Составьте функцию, опознающую коды образуемых цифр и исправляющую одну ошибку. 86. Азбука Морзе Составим программу, которая кодировала бы текст, передаваемый русскими буквами, посредством азбуки Морзе. Между соседними символами азбуки Морзе надо оставлять по одному пробелу, а между соседними словами — дополнительно столько пробелов, сколько их было в переданном тексте.
© Составьте программу, которая расшифровывала бы текст, записанный азбукой Морзе. 87. Шифр Цезаря ЭВМ очень подходит для зашифровки и расшифровки тайнописи. Есть много способов шифровки. Один из самых простых — шифр Цезаря. Его суть — скачок через две буквы: i-я буква алфавита заменяется на (/ + 2)-ю букву (предпоследняя буква алфавита заменяется на первую, а последняя — на вторую букву алфавита). Например, русская пословица КОНЧИЛ ДЕЛО, ГУЛЯЙ СМЕЛО была бы зашифрована следующим образом: МРПЩКН ЕЖНР ЕХНБЛ УОЖНР Составим программу зашифровки русского текста кодом Цезаря. Знаки препинания и другие символы шифровать не требуется. Чтобы найти шифр буквы с, следует выполнить следующий оператор: Удостоверьтесь, что то же самое можно осуществить при помощи одного оператора присваивания:
где п — число букв в алфавите. Последний оператор более универсален: написав вместо константы 2 какую-либо другую константу, мы получим новый шифр. Законченная программа выглядела бы так: Последний оператор включен в цикл для того, чтобы программа располагала шифрованным текстом в таких же строках, что и исходный текст. Эта программа подходит для шифровки текста только на тех языках, алфавит которых совпадает с алфавитом ЭВМ, выполняющей программу. 0 Составьте программу расшифровки текста, зашифрованного при помощи кода Цезаря. 88. Шифр Гронсфельда Подобен шифру Цезаря, но куда более сложен шифр Гронсфельда. Его ключ — пятизначное число. Буквы текста разбиваются на группы по пять (цифры и специальные символы не будем шифровать). Первая группа каждой цифры шифруется по способу шифровки Цезаря с ключом, роль которого играет первая цифра пятизначного числа (через столько букв делается скачок), вторая — с ключом, равным второй цифре пятизначного числа, и т. д. Таким образом, можно сказать, что поочередно используется пять ключей — цифры данного пятизначного числа. Текст может быть зашифрован шифром Гронсфельда 100 000 способами, поэтому методом проб найти ключ очень трудно. Поскольку ключ — пятизначное число, а нам нужны только цифры этого числа, то цифры ключа удобнее всего хранить в массиве:
Функцию шифр составить несложно. Написав ее и поместив цифры указанного пятизначного числа в массив ключ, а также запрограммировав действия, названные в третьем прямоугольнике, получим законченную программу:
© Исходные данные — два длинных текста на русском языке. Один из них зашифрован кодом Гронсфельда. Составьте программу, которая в соответствии с частотой повторений букв (см. задачу 74) в незашифрованном тексте установила бы ключ шифра Гронсфельда. 89. Король Исходные данные — координаты х, у шахматного поля, на котором стоит король. Координаты обозначаются так, как принято в шахматах: х— буквами а, 6, с, ..., А, а у — цифрами от 1 до 8. Создадим программу, которая печатала
бы все поля, на которые может пойти король. Например, если король стоит на поле al, то ЭВМ должна напечатать А2 В1 В2 Эта задача очень простая. Хотя ее несложно решить без помощи ЭВМ, все же продемонстрируем, какую красивую программу можно составить для решения этой задачи. Сперва попытайтесь составить ее самостоятельно, а затем сравните с приведенной здесь. Похожую ли программу вы составили? Или, быть может, еще более совершенную? Мы ввели в программу тип координат хх и ууу посредством которых определили доску больших размеров (рис. 33). Она необходима, чтобы мы могли решать задачу одним и тем же методом, не принимая во внимание, где стоит король: на середине или на краю доски. Лишь позже, печатая результаты, мы отбрасываем те поля, которые находятся за пределами стандартной шахматной доски. Рис. 33. Расширенная шахматная лента для нахождения ходов короля.
0 Составьте аналогичную программу, которая печатала бы все поля, на которые может пойти конь (исходные данные — координаты шахматного поля, на котором стоит конь). 90. Ханойские башни Эту задачу, иллюстрирующую рекурсию, очень любят программисты. Ее можно найти едва ли не в каждой книге по программированию. Вкратце и мы опишем ее. Эта задача связана с легендой. Рассказывают, что когда-то в Ханое стоял храм и рядом с ним — три башни (столба). На первую башню надеты 64 диска различного диаметра: самый большой диск — внизу, а самый маленький — вверху. Монахи этого храма должны были переместить все диски с первого столба на третий, соблюдая следующие правила: 1) можно перемещать лишь по одному диску; 2) больший диск нельзя класть на меньший; 3) снятый диск нельзя отложить — его необходимо сразу же надеть на другой столб. Когда дисков много (64), решение этой задачи оказывается необычайно долгим. (Легенда утверждает: когда монахи закончат свою работу — а они перемещают диск за одну секунду! — наступит конец света. И в настоящее время они работают и еще долго будут работать...) Поэтому эту задачу (как игру) решают с меньшим количеством дисков. Желая составить программу, будем рассуждать так. Предположим, с первого столба (А) надо перенести на третий (С) п дисков (рис. 34). Диски пронумерованы в порядке возрастания их диаметров. Рис. 34 Предположим, что мы умеем переносить п—1 дисков. В этом случае п дисков перенесем посредством следующих шагов:
1) верхние п— 1 дисков перенесем с первого на второй, пользуясь свободным третьим столбом; 2) последний п-и диск наденем на третий столб; 3) п — \ дисков перенесем на третий, пользуясь свободным первым столбом. Аналогичным образом можно перенести п— 1, п — 2 и т. д. дисков. Когда я=1, осуществить перенос очень просто: непосредственно с первого столба на третий. Таким образом, задача решается рекурсивно. В программе столбы обозначены буквами: А — первый столб, В — второй столб и С — третий столб. На рисунке 35 приведены результаты программы для случая, когда число дисков /2=4. 0 Другой интересный и очень простой способ решения задачи о ханойских башнях состоит в следующем. Диски нумеруются начиная с 1 (наименьший) и до N (самый большой), а столбы устанавливаются в круг. При перемещении дисков следует придерживаться следующих правил: 1. Диски, номера которых нечетны, можно перемещать только по часовой стрелке, а диски, номера которых четны,— только против часовой стрелки. Рис. 35. Найденный ЭВМ порядок переноса дисков.
2. Один и тот же диск нельзя перемещать два раза подряд. 3. Больший диск нельзя класть на меньший. Составьте программу решения задачи о ханойских башнях в соответствии с этими правилами. 91- Игра «Жизнь» Эта игра создана в 1970 г., ее автор — английский математик Дж. Конвей (Conway). Игру «Жизнь» достаточно исчерпывающе, приведя множество примеров, описал М. Гарднер [11]. Поэтому мы не будем пространно говорить о ней — только определим правила игры и в соответствии с ними составим программу игры для ЭВМ. В этой игре партнер не нужен — в нее можно играть одному. Правила игры. Вообразите бесконечное поле, разделенное на клетки. На каждой клетке поля живет, рождается или погибает животное. Это зависит от условий среды, т. е. от того, сколько соседей у него на ближайших восьми клетках (четырех по сторонам и четырех по углам). Действуют три правила существования животных: 1. Каждое животное, у которого два или три соседа, живет и сохраняется до следующего поколения. 2. Животное погибает, если у него более нежели три соседа (от недостатка места), совсем нет соседей или только один сосед (от одиночества). 3. Когда рядом с какой-нибудь клеткой есть три животных (соседа), на этой клетке рождается новое животное. 4. Важно понять, что животные погибают и рождаются одновременно. Они образуют одно поколение. За один ход в игре в соответствии с упомянутыми правилами осуществляется переход от одного поколения к другому. Дж. Конвей рекомендует следующий способ осуществления ходов (при наличии клетчатой доски и косточек двух цветов): 1) начать с желаемой конфигурации (колонии животных), состоящей из черных косточек; 2) найти все косточки, которые должны «погибнуть», и на каждую из них надеть по одной черной косточке; 3) найти все свободные клетки, на которых должно «родиться» животное, и положить на них по одной белой косточке; 4) удалить с доски всех «погибших» животных (т. е. столбики из двух косточек), а «новорожденных» (белые косточки) заменить черными.
Выполнив эти операции, т. е. после первого хода, получим второе поколение. Аналогичным образом происходят и все остальные ходы в игре. Так получаются все новые поколения. Составим программу, которая вводила бы исходную конфигурацию (состояние) и печатала бы k поколений — этапов эволюции. В программе нельзя определить бесконечно большое поле. Должно хватать поля некоторой известной величины тХп. Что делать, если эволюция достигает границ поля? Один из возможных выходов — прервать эволюцию. Однако эволюция могла бы продолжаться, если бы мы устранили границы поля: соединили бы любые два противоположных края поля, затем — концы полученного цилиндра. Полученная фигура, имеющая форму бублика, называется тор (рис. 36). Составим программу осуществления эволюции животных на поле, имеющем форму тора. Поле определим как тип массива: type поле = array [1../A, 1.. //] of boolean, где //, lh — измерения поля (до того, как поле превратили в тор). Составим схему программы: Рис. 36. Тор.
Чтобы определить число соседей у какой-нибудь клетки, следует просмотреть все находящиеся рядом клетки (слева, справа, сверху, снизу). Однако выбранная клетка может находиться на краю поля. В этом случае и требуется «склеить» края — получить тор. Это осуществляется функцией соседи. Все прочие функции и процедуры просты, поэтому мы приводим законченную программу:
Когда исходное состояние было 000 0 0 000 и k = 5, то ЭВМ, выполняя программу жизнь, напечатала приведенные на рисунке 37 состояния — этапы эволюции. Приведенную программу жизнь измените таким образом, чтобы печать прекращалась, как только эволюция останавливалась или погибали все животные. 92о Игра в спички Уже давно ЭВМ «обучается различным играм»: создаются программы по шахматам, шашкам и другим играм. Рис. 37. Начальная фигура и пять поколений ее эволюции.
Программы игр стали особенно популярны с появлением персональных компьютеров. Ведь каждому приятно иметь не капризного и никогда не устающего партнера. Игры различаются правилами, степенью сложности. Однако все они имеют много общего. Играющие по очереди делают ходы. Каждый играющий старается из всех возможных ходов выбрать самый лучший, т. е. такой, который обеспечивает победу. Если игра простая, то ее можно полностью проанализировать и наметить лучший ход в любой ситуации. Одна из самых популярных простых игр — это игра в спички (палочки). Игроки поочередно берут спички из кучки. За один ход можно взять одну или две спички. Проигрывает тот, кто берет последнюю спичку. Таким образом, в данной игре ситуация — это количество спичек, находящихся в кучке перед ходом, а ход — количество берущихся спичек (одна или две). Составим функцию, исходным данным (параметром) которой была бы ситуация (количество спичек в кучке), а результатом — ход (число берущихся спичек). Можно подразделить все ситуации на выигрышные и проигрышные. Когда в кучке лежит одна спичка, создается проигрышная ситуация. Когда в кучке — две спички, создается выигрышная ситуация, так как, взяв одну спичку, создадим для соперника проигрышную ситуацию. Последующая ситуация (три спички в кучке) также является выигрышной, так как, взяв две спички, мы оставим сопернику одну. Проигрышная ситуация создается, когда в кучке будет четыре спички, так как, взяв одну или две спички, мы «подарим» сопернику выигрышную ситуацию. Рассуждая далее аналогичным образом, мы получим ряд следующих ситуаций (выигрышные ситуации отмечены плюсами, проигрышные — минусами): 1 2 3 4 5 6 7 8 9 10 11 ... - + + - + + - + + - + Таким образом, выигрывает игру тот, кто может оставить сопернику кучки, состоящие соответственно (считая с «конца») из 1,4, 7, 10, 13, 16 спичек и т.д. вплоть до числа, близкого к числу спичек в кучке. Несложно установить закономерность. Теперь остается только записать функцию (перед этим определим типы данных):
Когда создалась проигрышная ситуация, берется одна спичка («Если проиграю, то хоть не так скоро...»). © Составьте функцию, позволяющую определять ходы в обобщенной игре в спички (когда за один раз разрешается брать от 1 до р спичек, причем р намного меньше, чем число спичек в кучке). © © Кто первый скажет сто? Играют двое. Игроки по очереди говорят по числу из интервала [1; 10]. Все сказанные числа складываются. Игра продолжается до тех пор, пока окончательная сумма не станет равна 100. Выигрывает тот, кто первый произнесет эту сумму. Составьте функцию, позволяющую определять ходы в этой игре. 93. Судья соревнований Играть могут не только человек на ЭВМ, но и две ЭВМ или две программы одной и той же машины между собой. Игра между двумя программами одной ЭВМ выявляет качество программ и работу их авторов. С 1974 г. организуются даже международные турниры по выявлению лучших шахматных программ. Соревнования проводит судья. Когда игроки — программы, то, естественно, и судит программа. Составим программу, которая проводила бы соревнования между двумя функциями игры в спички.
Как и в любом соревновании, прежде всего бросается жребий — выясняется, сколько спичек в кучке и кто дeлaet первый ход. Далее по очереди действуют две игровые функции — первый и второй: устанавливается, кому брать, сколько спичек осталось в кучке и, наконец, кто выиграл. Печатается и протокол игры: количество спичек, сколько и (в скобках) кто брал, сколько спичек оставалось. В этой программе функция первого игрока первый выбирает абсолютно лучшие ходы, а второй игрок еще не осмыслил игру, поэтому его функция делает случайные ходы. Ясно, что функция первого играющего не пропускает ошибок, допущенных вторым, и выигрывает чаще. Результаты, напечатанные программой судья, могут выглядеть так:
ПРОТОКОЛ ИГРЫ В СПИЧКИ 10— 1 (1) = 9 9_2(2) = 7 7—1 (1) = 6 6—1 (2) = 5 5—1 (1) = 4 4_2(2) = 2 2-1(1)=1 1 — 1 (2) = 0 ВЫИГРАЛ ПЕРВЫЙ 0 Измените программу судья таким образом, чтобы она позволяла функциям сыграть п раз (п — исходное данное) и печатала бы только конечный результат соревнования, выраженный в виде соотношения (и не печатала бы протокол). 94. Лабиринт Во многих книгах, журналах и газетах приводятся головоломки, интересные тем, что для их решения не требуется особых математических или каких-либо других специальных научных знаний. К таким задачам относятся поиск пути в сложном лабиринте, чтение текста ходом шахматного коня, расстановка фигур на шахматной доске таким образом, чтобы удовлетворить известным условиям. Такие задачи можно решить, научившись систематично рассматривать и оценивать все возможные варианты решения задачи. В этом большую помощь может оказать ЭВМ. Приведем достаточно универсальный метод решения головоломок, который часто называют методом проб. Проиллюстрируем его на примере. На 38 рисунке приведен очень простой лабиринт. Попадают в него в пункте А. Следует найти путь из пункта А до единственного выхода, расположенного в другом конце лабиринта (он обозначен буквой Е). Находясь в точке А, мы не знаем, какой выход открыт и как к нему пройти. Поэтому на каждом из «перекрестков» лабиринта нужно выбирать одну из двух дорог. Договоримся сначала испытывать левую дорогу. Из пункта А мы тогда попадаем в пункт В, из В — в С, из С — в D. Отсюда дороги нет. Мы снова возвращаемся на ближайший «перекресток» С и из него пробуем пройти по новой (правой) дороге в пункт Е. Здесь мы обнаруживаем выход. Задача решена. Ее решение — путь АВСЕ.
Рис. 38. Пример лабиринта. 4 Рис. 39. Все возможные пути лабиринта (а) из центра на окраину (б). Обратим внимание на то, что, узнав, что мы пошли неверным путем, мы не начинаем решать задачу заново, а делаем лишь один шаг назад и снова пытаемся идти с этого места. Если, сделав шаг назад, обнаруживаем, что нет новых неисследованных путей, делаем назад еще один шаг и т. д. до тех пор, пока мы не* доходим до места, из которого можно пойти новым, не- испробованным путем. Если, возвращаясь, мы дошли до исходной точки и из нее нет новых путей, то задача не имеет решения. Приведем несколько задач (помимо данной, также см. задачи 95, 96 и 97), которые решаются методом проб. Решим задачу о лабиринте. Поле состоит из нечетного числа клеток. Одни клетки черные, другие — белые, центральная клетка должна быть белой. Черные клетки обозначим посредством символа М, белые — символом пробела (рис. 39, а). Требуется найти все пути из центральной клетки на границу доски. Идти можно только по белым клеткам по горизонтали или по вертикали. По диагонали идти нельзя. Составим программу решения этой задачи. Напечатаем столько лабиринтов, сколько имеется различных путей. Путь будем помечать символом ' + ' (на рисунке 39,6 приведены все пути из рассматриваемого лабиринта). Условимся, что положение клетки лабиринта на поле определяется координатами (х, у), где х=1, 2, ..., п\ i/=l, 2, ..., п (размер поля — п*п клеток, причем п — нечетное число). Исходное положение — клетка (п div 2+1, п div 2+1).
Программа простая. Самое важное в ней — процедура идем, которая предназначена для того, чтобы найти все пути из центра лабиринта до самого края. Как же найти хотя бы один путь? Составить такую процедуру, которая сразу бы находила весь путь, очень трудно. Поэтому применим рекурсию. Составим процедуру, которая делала бы только один шаг, т. е. проверяла бы только одну клетку лабиринта. Перед тем как делать новый ход, процедура должна будет снова обратиться к самой себе. Такие обращения продолжаются до тех пор, пока мы не доходим до края доски или не попадаем в тупик. Если мы попали в тупик, возвращаемся на один шаг назад и пытаемся идти другим путем. Из одной клетки можно идти в четырех различных направлениях (влево, вправо, вниз, вверх). Установить, что мы дошли до края лабиринта, можно так: if (x=l) or (x = n) or (y=l) or (y = n) then... (* край *) В таком случае схема процедуры идем может выглядеть так:
Для печати найденных путей в лабиринте составим процедуру печать. Вся программа тогда будет выглядеть так:
В процедуре идем после слова else имеются четыре рекурсивных обращения, выполняя которые мы пытаемся идти всеми четырьмя направлениями. Обратим внимание на одну немаловажную деталь. В процедурах идем и печать массив лаб, в котором хранится лабиринт, передается параметрами-значениями, поскольку не надо восстанавливать результат: он печатается на самом глубоком уровне рекурсии. После каждого обращения к этой процедуре для массива лаб выделяется новое место в памяти. Это очень неэкономно (в особенности это касается рекурсивной процедуры идем, поскольку к ней приходится обращаться много раз и каждый раз создается новый экземпляр лабиринта). Для сбережения памяти следовало бы или считать массив лаб глобальной переменной, или передать его посредством параметров-переменных. (Параметрам- переменным в памяти не выделяется места, а их значения
хранятся вместе со значениями соответствующих фактических параметров.) Однако процедуру, в которой есть глобальные переменные, намного труднее читать. Объявление параметра-переменной, когда нужно только одно значение, вводит в заблуждение того, кто читает процедуру. 0 Измените приведенную программу лабиринт таким образом, чтобы на печать выводился бы лишь кратчайший путь из центра лабиринта до края. 95. Обход шахматной доски ходом коня Составим программу, в соответствии с которой шахматный конь мог бы обойти всю доску, побывав на каждом поле всего один раз. Исходное положение коня — на верхнем левом поле. Поля доски занумерованы так, как это показано на рисунке 40. Ходы коня занумеруем посредством чисел 1, 2, 3, ..., 64. Определим шахматную доску через: тип массива: type doc/ca = array [l..n, \..п\ of 0..64 Эта задача решается описанным выше методом проб (см. задачу 94). Самое важное — процедура, заполняющая все поля доски порядковыми номерами ходов. Создать процедуру, которая сразу бы решала задачу (т. е. заполняла бы все поля доски номерами ходов), очень трудно. Поэтому мы будем использовать процедуру, которая делала бы только один ход конем и заполняла бы только одно поле доски. Обращаясь к ней много раз, можно заполнить всю доску или зайти в тупик (доска еще не заполнена, а ходить некуда). Тогда надо вернуться и попытаться идти новым путем. Для этого удобно использовать рекурсивную процедуру. С одного поля у коня не более 8 различных ходов. Если конь стоит на поле (х, у), то любое (одно из восьми возможных) новое положение коня можно вычислить следующим образом: (x + cx[k], y + cy[k]\ здесь k — порядковый номер варианта (l<fe^8). Значения массивов сх и су можно установить по образцу, приведенному на рисунке 40. Рис. 40. Восемь ходов шахматного коня.
Приведем законченную программу:
Эта программа печатает результаты, представленные на рисунке 41. © Измените программу конь таким образом, чтобы с любого поля (его координаты будут исходными данными) конь мог обойти все поля доски. 96. Восемь ферзей Можно ли расставить на шахматной доске восемь ферзей так, чтобы они не угрожали друг другу (иначе говоря, чтобы никакие две фигуры не стояли ни на одной горизонтали, ни на одной вертикали, ни на одной диагонали)? Эта задача приводится во многих книгах по занимательной математике [11], поэтому мы не будем подробно говорить о ней, а только составим программу, которая находила бы конкретное расположение ферзей. Применим описанный выше метод проб (см. задачу 94). Поля доски занумерованы так, как это показано на рисунке 42. Составим схему программы:
Рис. 41. Отпечатанный результат программы конь — обход конем шахматной ленты. Начальное положение — верхняя левая клетка. Рис. 42. Установка ферзя в поле, помеченном точкой: надо проверить, нет ли ферзей под ударом в полях, через которые проходят стрелки. Рекурсивная процедура расстановка составлена с применением метода проб (см. задачу 94). Составив процедуры расстановка и печать, а также за-
писав действия, заключенные в прямоугольники в схеме программы ферзи, мы получим законченную программу:
Рис. 43 Распечатанный результат программы ферзи — расположение восьми ферзей на шахматной доске. Например, амазонка — это фигура, которая может ходить как ферзь и как конь. Составьте программы, которые на шахматной доске размером 10X10 полей расставляли бы 10 амазонок. Амазонки должны быть расставлены так, чтобы они не угрожали друг другу. 97. Раскраска карты Территории государств, имеющих общую границу, на политической карте раскрашиваются различными красками. Уже в прошлом столетии было установлено, что для раскраски любой карты достаточно четырех цветов. Эту так называемую гипотезу четырех цветов выдвинул в 1852 г. английский математик и логик О. де Морган (de Morgan, 1806—1871). К сожалению, он сам не смог доказать это утверждение. Только в 1976 г. быстродействующая ЭВМ Иллинойского университета установила, что четырех цветов достаточно для раскраски любой карты нашей планеты, любого участка глобуса. Составим программу, которая подбирала бы цвета (красный, желтый, синий и зеленый) для раскраски территорий районов на карте административного деления своей области. Для решения этой задачи очень важно иметь правильно подготовленные исходные данные (информацию об общих границах у районов). Условимся, что исходные данные, относящиеся к одному району, содержатся в одной строке данных и расположены в следующем порядке: 1) номер района; 2) название района; 3) номера тех районов, с которыми рассматриваемый район имеет общую границу; конец последовательности помечается нулем. Результаты этой программы представлены на рисунке 43. 0 Измените программу так, чтобы она находила все возможные способы расстановки ферзей. 0 0 Есть много вариантов шахматной игры: играют на досках различной формы, добавляют необычные фигуры и т. д. Новые фигуры можно получить, соединив возможности нескольких известных фигур.
Исходные данные будем хранить в одномерном массиве, каждый i-и член которого представляет собой множество соседних районов, т. е. множество районов, имеющих общую границу с районом под номером L Таким образом, информация об общих границах районов будет находиться в следующем массиве: var границы: array [районы] of набрай Здесь типы районы и набрай определены так: type районы = 1..44; набрай = set of районы Названия районов будем хранить отдельно (они понадобятся только при печати результатов) в следующем массиве: var имрай: array {районы] of array |1..20| of char Чтобы мы знали, какими цветами раскрашивать территории районов, мы создали массив о/ср, каждый элемент которого представляет собой множество районов, раскрашенных цветом соответствующего индекса. Тип цвета определяется так: type цвет = (красный, желтый, синий, зеленый), а сам массив описывается следующим образом: var окр: array [цвет] of набрай Уже из формулировки задачи ясно, что ее следует решать методом проб (см. задачу 94). Следовательно, придется составить рекурсивную процедуру, которая каждому району подбирала бы цвет. Нас интересует лишь один вариант раскраски: важно раскрасить указанными цветами карту области, а сколькими способами это можно сделать, не имеет никакого значения. Поэтому процедура должна прекращать работу, как только она обнаружит хотя бы одно решение. Приведем схему процедуры:
Действия, заключенные в прямоугольники, весьма просты. Мы запишем их на языке Паскаль и включим в программу. Кроме того, составим и включим в программу процедуры ввода исходных данных и печати результатов. Они длинноваты (особенно процедура ввод), но достаточно просты. Поэтому мы не будем пояснять деталей. Во всех процедурах массивы границы и окр представляют собой глобальные переменные. Приведем законченную программу:
Обратим внимание на то, что программа карта подходит для раскраски любой карты (например, политиуеской карты Европы, карты административного деления на области и т. п.),— надо только изменить число окрашиваемых территорий (константа max). 98. Лексический анализ Одной из самых сложных и интересных задач программирования является составление программ для транслятора (компилятора). Длина программ, используемых на практике трансляторов языков программирования (например, Паскаля, PL/1, Фортрана), может быть от нескольких тысяч до нескольких десятков тысяч операторов. Для того чтобы составлять или разбирать такие программы, требуется много времени и сил. Однако принципы составления и действия основных трансляторов можно проиллюстрировать, построив очень простой язык. Мы не будем создавать нового языка, а возьмем очень небольшое подмножество (микроподмножество) языка Пас-
Рис. 44. Синтаксические диаграммы микроподмножества языка Паскаль.
каль, в котором есть только целые неотрицательные числа и операторы только одного вида — присваивания. Синтаксические диаграммы этого подмножества показаны на рисунке 44. В подмножестве будем употреблять только заглавные буквы. Так написанная программа отчетливее выделится из других программ на языке Паскаль. Чтобы текст программы был удобен для машины, его нужно преобразовать — разделить на лексемы. Лексема — это символ, имеющий самостоятельное значение в программе: число, имя, служебное слово, символ операции. Определим лексему и массив лексем рассматриваемого подмножества языка Паскаль: type лексема= (плюс, минус, звездочка, лскобка, пскобка, присваивание, двоеточие, точка, запятая, точкасзапятой, programc, beginc, endc, varc, integerc, dive, mode, имя, число); лексемы = array [L./nax] of лексема К словам языка (например, program) мы прибавляли окончание с (символ), чтобы лексемы (константы) отличались от базовых слов языка Паскаль. Самая первая задача каждого транслятора — это лексический анализ. Для решения этой задачи составим процедуру лексика, предназначенную для того, чтобы прочитать текст программы, написанный на определенном нами подмножестве языка Паскаль, и сформировать массив лексем. Заголовок процедуры должен был бы выглядеть так: procedure лексика (var леке:лексемы) Например, процедуре предъявлен такой текст программы: PROGRAM MIKRO; VAR ALFA: INTEGER; BEGIN ALFA: =2 END. Тогда процедура формирует массив лек, состоящий из следующих элементов: programc имя точкасзапятой varc имя двоеточие integerc точкасзапятой beginc имя присваивание число endc точка Значение переменной k должно быть равно 14, поскольку в тексте программы содержится именно столько лексем. Составим схему процедуры:
Самая трудная часть — анализ слов. Прежде всего надо образовать (сформировать) слово. Это можно сделать, читая текст программы дальше, до тех пор пока следуют буквы или цифры. Определим тип слово и переменную z, относящуюся к этому типу: type слово = packed array [1..8] of char vur z:слово Предположим, что выделенное в тексте программы слово, уже является значением переменной г. Теперь надо проверить, является ли оно словом языка или именем. Для
этого мы создали массив слов языка: var слова:array [programc. mode] of слово В этот массив надо заранее записать слова языка: Здесь и далее в тексте знаком □ мы будем обозначать символ пробела (чтобы легче было подсчитать требующиеся пробелы), так как при предъявлении программы ЭВМ на этом месте должны быть настоящие пробелы (пустое место). Желая установить, какая лексема соответствует данному слову, надо найти его в массиве слова. Индекс элемента, который совпадет с искомым словом, и будет искомая лексема. Если такого слова в массиве нет, то, значит, это слово — имя переменной. Все прочие части процедуры более простые. Сразу включим их в программу:
Формирование слова заканчивается тогда, когда последний из прочитанных символов с не принадлежит слову. Если сфУ ', то он входит в другую лексему. Вследствие этого прерывается действие одного длинного условного оператора, содержащегося в схеме программы, и в том же самом цикле анализируется новая лексема. По той же причине условный оператор прерывается и после анализа лексем число, двоеточие, а также присваивание. Запись лексем в лек производится в нескольких местах, поэтому мы составили процедуру новая. В процедуре лексика все имена превращаются в одну и ту же лексему имя, а все числа — в одну и ту же лексему число. Если бы мы хотели транслировать программу до конца, то их значения следовало бы сохранить и записать в таблицы (массивы). Мы не делали этого, так как продолжим трансляцию только до синтаксического анализа (см. задачу 99), а идентификация значений чисел и имен для синтаксического анализа не нужна. Каждый программист хорошо знает, что редко удается сразу написать программу без ошибок. Хороший транслятор должен быть «другом» программиста: обработать и ошибочную программу, а об ошибках проинформировать программиста. Часть ошибок можно обнаружить уже во время лексического анализа. Для простоты мы не предусмотрели в программе сообщение об ошибках, а ошибки игнорировали. Например, если в тексте встретился символ, не принадлежащий подмножеству языка (например, Т, '<' и т. д.), то он пропускается (приравнивается к пробелу). Если лексем слишком много, то все прочие лексемы пишутся в последний элемент массива лексем. Конечно, тогда сохраняется только последняя лексема. Потерянные лексемы почти всегда являются причиной синтаксических ошибок, которые позднее обнаруживаются программой синтаксического анализа. 99. Синтаксический анализ Видный советский специалист по программированию М. Шура-Бура любит разнообразить серьезную работу программистов шуточными аксиомами. Первая из них гласит, что «в любой программе есть ошибка». В самом деле, предъявив новую программу машине, мы почти всегда вместо ожидаемого решения задачи получаем сообщение об ошибках в этой программе.
Программировать было бы легче, если бы машина находила и исправляла все ошибки. К нашему счастью (или несчастью), дело обстоит не так. Немало ошибок, особенно запрятанных поглубже, остается и на долю программиста. Однако машина всегда успешно находит синтаксические ошибки. Их можно обнаружить, анализируя текст программы при помощи синтаксических диаграмм. Прежде всего разберем, как нам самим, пользуясь диаграммами, искать ошибки в программе, а затем запрограммируем свои действия. Предположим, у нас есть программа, выраженная на подмножестве языка Паскаль (см. задачу 98): PROGRAM ОШИБКА; VAR A:INTEGER; А:=5 END. Вся программа должна удовлетворять диаграмме программа (см. рис. 44). Проверим это. Первый символ на этой диаграмме — служебное слово PROGRAM. Оно есть и в тексте программы. Значит, до сих пор программа правильна. Проверяем дальше. Согласно синтаксической диаграмме следующим символом (лексемой) может быть только имя. Так и обстоит дело в тексте программы. Дальше — точка с запятой. Она также есть в программе. А после нее на диаграмме идет заголовок другой диаграммы — описания. Запоминаем это место диаграммы программа и переходим к диаграмме описания. Первая лексема на ней — слово VAR. Оно есть и в программе. Идем дальше. И в программе, и на диаграмме — имя. Дальше. На диаграмме после имени может быть или двоеточие, или запятая. В программе — двоеточие. Диаграмма показывает, что дальше может идти только слово INTEGER, а затем — только точка с запятой. Эти самые лексемы находим и в программе. Значит, пока ошибок не обнаружено. Диаграмма описания закончилась. Возвращаемся на диаграмму программа и проводим анализ с того места, в котором мы покинули эту диаграмму. Теперь — диаграмма блок. Она показывает, что первой лексемой блока должно быть слово BEGIN. А в тексте программы — имя. Других альтернатив нет. Значит, мы нашли ошибку. Действительно, в этой программе пропущено служебное слово BEGIN. Теперь составим программу, которая бы проверяла, удовлетворяет ли анализируемый текст программы синтаксическим диаграммам. Каждую диаграмму естественно представить в виде
процедуры. Переход к новой диаграмме тогда будет изображаться обращением к ее процедуре, а возврат к прежней диаграмме — возвращением к процедуре прежней диаграммы. Будем считать, что перед тем уже проведен лексический анализ текста проверяемой программы (см. задачу 98), а ее лексемы содержатся в массиве лек. Составим процедуру для диаграммы программа: Аналогичным образом можно составить и процедуры для других диаграмм. В случае ошибки происходит обращение к процедуре ошибка. В ней должны быть предусмотрены все действия, связанные с ошибкой: какое сообщение напечатать, как исправить ошибку, как дальше анализировать программу и т. д. Именно эта процедура определяет, насколько хороша диагностика ошибок. Здесь мы составим самую простую процедуру, которая напечатает номер первой лексемы, не удовлетворяющей синтаксической диаграмме, и пропустит эту лексему: Логическая переменная ещенебыло должна быть описана в основной части программы, и ей присваивается значение true, означающее, чтр пока в программе не встретилось ошибок. Теперь составим процедуры для всех диаграмм и включим их в программу:
Процедуры мы расположили в обратном порядке по сравнению с порядком синтаксических диаграмм на рисунке 44. Ведь в языке Паскаль требуется, чтобы имена (в том числе и имена процедур) были описаны раньше, чем переменные. В этой задаче имеем цепь процедур (выражение — множитель — терм — выражение — ...), поэтому мы предварительно описали заголовок одной из них, используя директиву forward. Во всех процедурах синтаксических диаграмм используются одни и те же данные, поэтому удобнее обойтись без параметров. 100. Программа, печатающая самое себя На первый взгляд задача кажется очень простой — в программе нужно только написать операторы, печатающие ее текст. Недолго думая, пишем программу: Нам легко было написать два первых оператора, печатающих первые две строки программы. Однако надо напечатать и текст этих операторов. Для этого мы написали еще два оператора. Но для того чтобы напечатать тексты этих операторов, нам понадобятся еще два, уже более длинных оператора. И так без конца. Значит, мы идем не тем путем. Надо искать выход.
Причина неудачи заключается в том, что текст, который может быть напечатан оператором, составляет^ лишь часть этого оператора. Например, оператор writeln ('XXX') печатает текст XXX. А в оператор печати входит не только этот текст, но и имя процедуры печати writeln, скобки, а также ограничивающие строку апострофы. Значит, оператор печати должен напечатать текст более длинный, нежели его собственный текст. А это можно сделать, используя цикл или рекурсию. Программа, печатающая самое себя, в которой используется цикл, приведена, например, на рисунке 45. Это листинг, напечатанный ЭВМ, в котором можно точно определить число пробелов между символами (а это существенно для данной задачи). Приведенная программа составлена инженером Каунасского политехнического института Витаутасом Валайтисом. Попытайтесь осуществить все действия, записанные в программе, и удостоверьтесь, что программа в самом деле напечатает себя. Обратите внимание на то, как печатаются апострофы и конец текста программы, находящийся после операторов печати. © Составьте программу, печатающую самое себя, в которой нет циклов, а есть рекурсивная процедура. © 0 Составьте две программы: А и В. Программа А должна печатать текст программы В, а программа В — текст программы А. Тексты программ Л и В не должны быть идентичны. Рис. 45. Себя печатающая программа.
ЗАКЛЮЧЕНИЕ Читатель, у которого будет такая возможность, без сомнения, захочет выполнить некоторые наиболее интересные программы на ЭВМ. Программа, составленная на языке Паскаль, должна была бы хорошо подходить для любой ЭВМ, располагающей транслятором этого языка. Однако на практике встречаются небольшие отклонения. Они возникают из-за специфики конкретных ЭВМ, чаще всего связанной с вводом или выводом данных, а также из-за того, что язык Паскаль не весь является окончательно определённым, что он в какой-то степени видоизменяется, совершенствуется. Поэтому, прежде чем вводить программу в машину, надо познакомиться с описанием используемого в ней языка Паскаль. Здесь мы не будем рассматривать специфику конкретных ЭВМ или их трансляторов, а только упомянем то, на что программист должен обратить внимание при вводе программы в ЭВМ и знакомстве с её трансляторами. Почти во всех трансляторах алфавит Паскаля отождествляется с алфавитом ЭВМ. Многие ЭВМ располагают только заглавными латинскими буквами. В них нет букв русского алфавита. Буквы в алфавите (кодах) ЭВМ расположены в том же порядке, что и в латинском алфавите, однако между группами букв имеются неиспользуемые коды, вследствие чего результатом функций succy pred, chr может оказаться несуществующая буква. Символы операций <=, >= и <> кодируются в алфавите ЭВМ парами символов: <=, >= и <>. Во всех трансляторах предусмотрены ввод и вывод чисел и символов, а в некоторых — и других значений (логических, скалярных, строковых — упакованных массивов символов).
Словарь основных терминов языка Паскаль блок ввод вывод выражение данные запись знак операции значение имя индекс комментарий компилятор константа литера, символ массив множество область действия оператор — выбора — пустой операция описание определение отрезок параметр — фактический — формальный block input output expression data record operator value name index comment compiler constant symbol array set scope statement case statement empty statement operation declaration definition subrange parameter actual parameter formal parameter
переменная — глобальная — локальная поле присвоение пробел программа процедура — рекурсивная слово служебное строка тип — вещественный — литерный — логический — скалярный — стандартный — структурный — целый транслятор файл функция — рекурсивная — стандартная цикл цифра variable global variable local variable field assignment blank program procedure recursive procedure keyword string type real character boolean scalar type standard type structured type integer translator file function recursive function standard function loop digit
Основная литература 1. Григас Г. Начала программирования.— М.: Просвещение, 1987. 2. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ.— М., 1981. 3. Вирт Н. Систематическое программирование.— М., 1977. 4. Грогоно П. Программирование на языке Паскаль.— М., 1982. 5. Дейкстра Э. Дисциплина программирования.— М., 1978. 6. Йенсен К., Вирт Н. Паскаль: Руководство для пользователя и описание языка.— М., 1982. 7. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы.— М., 1977.— Т. 2. 8. Уэзерелл Ч. Этюды для программистов.— М., 1982. Дополнительная литература 9. Б е р м а н Г. Число и наука о нём.— М., 1972. 10. Доморяд А. Математические игры и развлечения.— К., 1972. 11. Гарднер М. Математические досуги.— М., 1972. 12. Кордемский Б. Математическая смекалка.—7-е изд., перераб.— М., 1963. 13. Литцман В. Теорема Пифагора.— М., 1960. 14. Литцман В. Весёлое и занимательное о числах и фигурах.— М., 1963. 15. Оре О. Приглашение в теорию чисел.— М., 1980. 16. Перельман Я. Занимательная алгебра.— М., 1978. 17. Перельман Я. Занимательная арифметика. Загадки и диковинки в мире чисел.— М., 1959. 18. Перельман Я. Занимательная геометрия.— М., 1959. 19. Штейнгауз Г. Математический калейдоскоп.— М., 1981. 20. Виленкин Н. Комбинаторика.— М., 1969.
Содержание Предисловие 5 Введение 7 1. Факториал 14 2. Осторожно: maxint! 17 3. Размещения и сочетания 19 4. Числа Фибоначчи 20 5. Суммы рядов 24 6. Возведение в квадрат без операции умножения 27 7. Извлечение корня из действительных чисел 28 8. Корни из натуральных чисел 31 9. Извлечение квадратного корня из натуральных чисел .... 32 10. Арифметический квадрат 34 11. Треугольник Паскаля 36 12. Треугольник 40 13. Пифагоровы числа 41 14. Разрезание прямоугольника на квадраты 44 15. Равновеликие прямоугольники 46 16. Равновеликие треугольники 47 17. Уравнение a3 + b3 = c3 + d3 50 18. Задача Антанаса Баранаускаса 57 19. Считалка 59 20. Делёж 61 21. Наибольший общий делитель 62 22. Взаимно простые числа \ 63 23. Наименьшее общее кратное 65 24. Бильярд 67 25. Делители 69 26. Простые числа 72 27. Числа Мерсенна 74 28. Разложение на простые множители 76 29. Эратосфеново решето 77 30. Близнецы 82 31. Скатерть Улама 83 32. Совершенные числа 90 33. Дружественные числа 92 34. Цифры 93 35. Автоморфные числа 95
36. Нумерация книжных страниц 96 37. Счастливые троллейбусные билеты 98 38. Сумма кубов цифр 100 39. Числа Армстронга 101 40. Квадраты, состоящие из разных цифр 104 41. 1! + 4! + 5! = 145 106 42. Наименьшее число не всегда мало 109 43. Двоичные числа 111 44. Шестнадцатеричная система 113 45. Палиндром 115 46. Большое произведение 117 47. Большие числа 119 48. Точность действительных чисел 121 49. Точное частное — 50. Деление с большой точностью 122 51. Простые дроби 125 52. Десятичные дроби 127 53. Старинные меры 130 54. Действительные числа и бухгалтерия 131 55. Высота музыкального звука 133 56. Случайные числа 134 57. Вычисление значения л путём бросания иглы 136 58. Площадь фигуры 140 59. Даты 141 60. Дата следующего дня 145 61. Будущая дата 146 62. Число дней между датами 147 63. День недели 149 64. День рождения 151 65. Сто лет семье 152 66. Биологические ритмы 155 67. Настенный календарь 159 68. Лунный календарь 163 69. Рисование геометрических фигур 168 70. Квадрат из цифр 169 71. Симметричные фигуры 170 72. Орнаменты 172 73. Символы большого формата 175 74. Частота повторения букв 178 75. Частота повторения слов 179 76. Пилообразный текст 181 77. Билистинг 183 78. Техническое редактирование текста 184 79. Голландский флаг 188 80. Сортировка данных 192 81. Сортировка методом «пузыря» 194
82. Быстрая сортировка 196 83. Поиск 198 84. Римские цифры 200 85. Почтовые индексы 202 86. Азбука Морзе 204 87. Шифр Цезаря 205 88. Шифр Гронсфельда 206 89. Король 208 90. Ханойские башни 210 91. Игра «Жизнь» 212 92. Игра в спички 217 93. Судья соревнований 219 94. Лабиринт 221 95. Обход шахматной доски ходом коня 226 96. Восемь ферзей 228 97. Раскраска карты 232 98. Лексический анализ 236 99. Синтаксический анализ 242 100. Программа, печатающая самое себя 247 Заключение 249 Словарь основных терминов языка Паскаль 250 Основная литература 252 Дополнительная литература —
Учебное издание ДАГЕНЕ ВАЛЕНТИНА АНТАНОВНА ГРИГ АС ГИНТАУТАС КЛЕМЕНСОВИЧ АУГУТИС КЯСТУТИС ФЕЛИКСОВИЧ 100 задач по программированию Зав. редакцией Т. А. Бурмистрова Редактор А. К. Компанец Художники Б. Л. Николаев, В. В. Костин Художественный редактор Ю. В. Пахомов Технический редактор Т. Е. Молозева Корректор И. Н. Панкова ИБ № 13897 Сдано в набор 1109 91 Подписано к печати 30 03 92 Формат 84Х Ю8'/з2 Бум тип № 2 Гарнит Литер Печать офсетная Уел печ л 13,44 Уел кр -отт 13,86 Уч -изд л Ю,()Г> Тираж 38 000 Заказ 329 Ордена Трудового Красного Знамени издательство «Просвещение» Министерства печати и информации Российской Федерации 127521, Москва, 3-й проезд Марьиной рощи, 41 Отпечатано с диапозитивов Саратовского ордена Трудового Красного Знамени полиграфичее кого комбината Министерства печати и информации Российской Федерации 410004, Саратон, ул Чернышевского, 59 на Ордена Трудового Красного Знамени Чеховском полиграфическом комбинате Министерства печати и информации Российской Федерации 142300, г Чехов Московской области
100 ЗАДАЧ ПО ПРОГРАММИРОВАНИЮ