Книга для начинающих программистов
книга по информатике и икт по теме

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Казанский государственный технический университет им. А. Н. Туполева

Д.Г. Хохлов

Школа

юных программистов

Основы программирования

на примере олимпиадных задач

Учебное пособие

Казань 2007

УДК 681.3.06

Хохлов Д.Г.

Школа юных программистов. Основы программирования на примере  олимпиадных задач: Учебное пособие. – Казань: Изд-во Казан. техн. ун-та, 2008. – 99 с.

Рассматриваются основные понятия программирования на языках высокого уровня на примере языка Pascal.  Изложение  рассчитано на школьников, начинающих  изучать программирование. Приводятся многочисленные примеры решения типовых и олимпиадных задач, а также задания для самостоятельного решения и проверки усвоения материала.  

Для школьников и студентов, в том числе заочного обучения, а также их учителей и преподавателей.

Табл. - 5,  Ил. - 4,  Библиогр. - 22 назв.

© Хохлов Дмитрий Григорьевич, 2007

Предисловие

Учебное пособие призвано обеспечить начальную подготовку школьников и студентов по  программированию, включая заочное обучение, в том  числе для участия в олимпиадах по информатике и программированию.

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

Олимпиадные задачи отличаются от традиционно рассматриваемых в литературе большим разнообразием тематики, а также методов и приемов программирования, включающим в себя все области применения компьютеров.

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

В качестве базового языка программирования используется Pascal, разработанный специально для обучения программистов и прекрасно зарекомендовавший себя в практике всех уровней отечественного образования.

Особое внимание уделяется технике программирования и отладки программ, в том числе в условиях олимпиадных соревнований.

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

 1. ОСНОВНЫЕ ПОНЯТИЯ

2. Программное обеспечение

Программное обеспечение (ПО) - совокупность программ для ЭВМ - играет основную роль в успехе применения компьютеров.

Программное обеспечение делится на прикладное, системное и инструментальное. Иногда инструментальное ПО относят к системному ПО.

Прикладное ПО содержит программы и программные комплексы,  предназначенные для решения конкретных прикладных задач.

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

Основной частью системного ПО является операционная система - комплекс программ, управляющий устройствами вычислительной системы и выполнением всех остальных программ. К системному ПО относят также сервисные и антивирусные программы и т.п.

В инструментальное ПО входят средства для разработки программ: системы программирования, инструментальные комплексы и программы для создания программного обеспечения.

Система программирования включает язык программирования, транслятор для него, библиотеку программ, текстовый редактор, редактор связей, загрузчик, средства отладки и другие вспомогательные программы.

Текстовый редактор представляет собой программу для создания и изменения в памяти ЭВМ различных текстов: программ, писем, книг и т. п.

Язык программирования - это система обозначений для записи программ. Существуют тысячи языков программирования, из которых лишь десятки широко используются специалистами. Около десяти языков известны миллионам людей во всем мире: Basic, Pascal, C, C++, Java и др.

В данном пособии используется язык программирования Pascal. Перечисленные языки являются машинно-независимыми языками высокого уровня. Машинная независимость означает возможность использовать язык для ЭВМ разных типов. Уровень языка определяется степенью его близости к машинному языку, непосредственно воспринимаемому компьютером. Чем большее число машинных команд требуется в среднем для выполнения одной команды некоторого языка, тем выше уровень языка.

К машинно-зависимым (машинно-ориентированным) языкам относятся в основном языки ассемблера - для программирования на уровне машинных команд компьютеров определенного типа. Их называют языками уровня 1:1 ("один к одному"), т. к. команда такого языка обычно соответствует одной машинной команде.

Для использования языка программирования на ЭВМ его нужно реализовать на ЭВМ этого типа, т. е. разработать для него транслятор. Транслятор – это программа для перевода программ с одного языка на другой. Существуют различные виды трансляторов: компилятор, интерпретатор, ассемблер, редактор связей, загрузчик и др.

Компилятор – это транслятор для перевода программ с языка высокого уровня на язык, близкий к машинному языку (без их непосредственного выполнения). Последующее исполнение полученной машинной программы происходит без участия компилятора. Программу на языке программирования называют исходным модулем, а результат ее трансляции (компиляции) - объектным модулем (от английского слова object - цель).

Интерпретатор – это такой вид транслятора, который читает, анализирует и немедленно выполняет каждую команду исходной программы (без получения объектного модуля). В этом случае перевод программы и ее выполнение происходят параллельно.

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

В каждой операционной системе имеются свои правила именования файлов. Например, в распространенных на персональных компьютерах операционных системах UNIX, Windows или MS DOS, если исходный модуль, т. е. программа на языке Pascal, находится в файле p. pas, то файл с результатом ее компиляции (объектным модулем) обычно называется p.obj, а файл с исполнимым модулем - p.exe (execute – исполнять).

1.2. Программирование

Составление программ для ЭВМ называют программированием. В более широком смысле программирование - это наука, изучающая теорию, методы и средства разработки, производства и эксплуатации программного обеспечения ЭВМ. Наконец, в более узком смысле под программированием понимают также один из этапов разработки программы - перевод алгоритма на язык программирования.

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

До половины и более всех затрат на разработку программы уходит на ее отладку - обнаружение ошибок в программе, их локализацию (поиск причины и местонахождения) и исправление.

Основным методом обнаружения ошибок в программе является   тестирование - выполнение программы вручную или на ЭВМ для обнаружения в ней ошибки или изучения механизма ее работы. Для этого используются контрольные примеры (тесты). Тест - это пример исходных данных программы вместе с ожидаемым правильным результатом ее работы (или проверяющей программой).

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

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

1. Доказательство очень трудоемко, по объему превышает программу и может содержать ошибки.

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

Поэтому верификация не сможет полностью заменить тестирование и их необходимо сочетать.

Существуют десятки взаимосвязанных критериев оценки программ, основные из которых следующие.

1. Функциональность – выполняемые программой функции, ее полезность.

2. Надежность – это вероятность безошибочной работы программы в течение определенного времени.

3. Время решения задачи - эффективность по времени.

4. Требуемая память для программы и обрабатываемых данных -  эффективность по памяти.

5. Удобство эксплуатации определяется качествами самой программы и  ее документации и зависит от многих  факторов. Очень важна, например, дружественность программы - удобный и естественный для пользователя интерфейс (способ взаимодействия с программой), наличие в ней защиты от ошибок и развитых средств подсказки и диалоговой документации.

6. Затраты на разработку программы - время, труд, материальные и финансовые средства.

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

Очень характерна, например, закономерность время-память: обычно для ускорения работы программы требуется дополнительная память и наоборот: экономия памяти замедляет работу программы.

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

Основным понятием программирования является алгоритм. Алгоритм - это детальный план действий, описание точно определенной последовательности операций.

Примерами алгоритмов являются: компьютерная программа, правила выполнения арифметических операций "столбиком", правила геометрических построений определенных фигур с помощью циркуля и линейки, многочисленные правила решения других математических задач, инструкция по использованию телефона-автомата, сборке мебели или вязанию свитера,  кулинарный рецепт,  нотная запись музыки и т. п.

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

Алгоритм состоит из операторов.  Оператор - это  описание операции. Используют много синонимов этого понятия: команда, инструкция,  директива, приказ, предписание, шаг, предложение (языка программирования) и т.  п.,  основным из которых является команда.

Программа – это алгоритм, предназначенный для выполнения на ЭВМ.

Алгоритмический язык представляет собой систему обозначений для записи алгоритмов, например, язык программирования, обычный русский или другой естественный язык, нотная грамота и др.

1.3. Изучение программирования

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

Прежде, чем самому составлять программу, полезно  разобрать примеры  подобных программ. Таким же образом желательно начинать знакомство с новым для вас языком программирования.

При изучении программирования сначала ознакомьтесь с соответствующим разделом пособия и приведенными там  примерами.

Изучение имеющейся  программы (как и составление новой программы) начинайте с внимательного чтения условия задачи.

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

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

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

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

Для ознакомления с программой обычно недостаточно только читать ее текст и пояснения к нему. При этом многие важные детали работы программы могут остаться непонятыми. Поняв основные идеи и посмотрев программу, полезно через некоторое время попробовать самому составить аналогичную программу и сравнить ее с изученным вариантом.

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

При этом человек воспроизводит работу компьютера и вручную исполняет программу команда за командой с имеющимися тестами.

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

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

Чтобы лучше понять или проверить используемый в программе метод решения задачи, опробуйте его на имеющихся тестах. Конечно, для ручного тестирования используются сравнительно простые тесты, но они должны отражать основные варианты работы программы.

Результаты ручного тестирования записываются в виде трассировочной таблицы. В этой таблице показаны значения переменных величин и выражений программы в разные моменты ее исполнения. Степень подробности и форма таблицы могут быть различными в зависимости от целей тестирования.

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

При изучении программирования важную роль играет отладка и выполнение программы на ЭВМ. Желательно не  только вручную тестировать приводимые в книгах программы, но также проверять их работу на ЭВМ. При этом полезно экспериментировать с программой: изменять форму ввода и вывода данных, метод решения задачи и другие детали программы и наблюдать влияние этих изменений на работу программы.

Еще большее значение для обучения программиста имеет опыт отладки на ЭВМ своих собственных программ, в том числе для задач, приводимых в данном пособии.

Для начального обучения практическому программированию и отладке программ на языке Pascal удобна простая система программирования Turbo Pascal 7.0 фирмы Borland. Можно использовать и другие системы для персональных ЭВМ.

Рекомендуется следующая последовательность разработки и отладки программ.

1. Изучить условие задачи и составить для нее тесты.

2. Определить перечень величин, участвующих в решении задачи, выбрать имена для этих величин и составить описание данных.

3. Разработать алгоритм решения задачи на неформальном языке - псевдокоде (в трудных случаях - методом сверху вниз, как описано в разделе 3).

4. Выполнить ручное тестирование (трассировку) алгоритма.

5. Сделать перевод алгоритма на язык программирования.

6. Провести ручное тестирование программы (особенно, если она намного детальнее алгоритма).

7. Ввести программу в компьютер и отладить ее сначала на простых, а затем на сложных тестах, в том числе в пошаговом режиме.

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

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

1.4. Олимпиады по программированию 

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

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

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

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

Олимпиада проводится 4 – 5 часов, в течение которых участникам предлагается решить 4 – 5 задач. Решением задачи является файл с исходным текстом программы на одном из разрешенных языков программирования.

В большинстве случаев используется язык Pascal, наиболее популярный среди российских участников не только школьных, но и студенческих олимпиад, в том числе международного уровня.  В последние годы повысилось число приверженцев языков семейства С: С, С++, Java, но в России их доля невелика. Все эти языки примерно одинаковы по своим возможностям. Язык Basic не  способен конкурировать в подобных соревнованиях даже на школьном уровне.

Преимуществом языка Pascal являются удобные для начинающих cвободно распространяемые и доступные системы программирования, в частности, Turbo Pascal 7.0 и Delphi.

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

Тест представляет собой пример исходных данных с известным результатом их обработки. Для каждой задачи жюри готовит до нескольких десятков тестов и специальную проверяющую программу - чекер (от английского check – проверять), которая сравнивает выданный программой участника результат с эталонным ответом,  либо проверяет его правильность  иным способом.

Автоматическая система тестирования  многократно запускает программу участника, проверяя ее  на всех тестах этой задачи. За правильность прохождения каждого теста участник получает определенное количество  баллов, в сумме составляющих максимальную оценку задачи. В большинстве случаев эта оценка учитывает сложность задач, но иногда все задачи оцениваются одинаковым числом баллов (участники все равно находятся в равных условиях). Такая автоматическая проверка задач обеспечивает объективную оценку всех участников.

В этих условиях участникам имеет смысл представлять не только полное, но и заведомо неполное, частичное решение задачи для каких-то частных случаев, которое может получить определенное количество баллов.

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

Например, если в задаче требуется вывести слово YES (большими буквами), то считается неверным результатом выведенное программой участника слово Yes или правильно написанное  слово YES, но с дополнительной информацией, не предусмотренной условием задачи. Недопустимо также, чтобы программа очищала экран и выводила лишнюю информацию, не предусмотренную в задаче, например, приглашения «Введите данные…».

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

Кроме личных соревнований, проводятся также командные соревнования по программированию. С 1977 года проходит ежегодный чемпионат мира   по программированию среди сборных студенческих команд высших учебных заведений. В 2006-2007 учебном году в них участвовали 6099 команд из 1756 университетов 82 стран. Россия присоединилась к этим уникальным соревнованиям с 1996 г. и в последние годы лидирует в них. КГТУ-КАИ – единственный из казанских вузов, который участвует в этих соревнованиях ежегодно с 1996 г. Серьезную конкуренцию ему составляют команды КГУ. Два года принимали участие команды ТИСБИ.

По правилам студенческого чемпионата мира команде из трех участников предоставляется один компьютер и в течение 5 часов предлагается составить и отладить программы для решения от 6 до 12 задач из самых разных областей применения компьютеров.

Побеждает команда, правильно решившая наибольшее число задач. При равенстве числа  решенных задач выигрывает команда, затратившая меньше времени. Проверка решения производится автоматически за 1 - 2 минуты в ходе соревнований.  Когда программа участника, отправленная по вычислительной сети на компьютер жюри, выдает верный результат для всех подготовленных жюри тестов (содержание и количество тестов участникам не известно), команде засчитывается решение задачи, а к затраченному времени прибавляется время, прошедшее от начала турнира до этого момента, и дополнительно по 20 минут за каждую неудачную попытку команды сдать решение этой задачи.

Участники и зрители во время соревнования в любой момент могут видеть положение команд в турнирной таблице,  в том числе и через Интернет.

Соревнования по таким правилам становятся очень популярными как среди студентов, так и у школьников. Ежегодно организуются несколько региональных студенческих турниров российского уровня, заочные соревнования по Интернет, в том числе международные. Вот  уже 7 лет проводится Всероссийская командная олимпиада школьников, на которой в десятку лучших неоднократно попадали команды Казани.

Например, в ноябре 2007 г. все четыре команды школьников Казани в группе из  12 лучших команд регионального отборочного турнира в г. Кирове прошли в финал и завоевали дипломы победителей Всероссийской командной олимпиады школьников в г. С.-Петербурге.

По правилам студенческого чемпионата мира в  г. Казани с 2000 г. проводится представительный  открытый региональный турнир студентов и школьников Татарстана на призы компании ICL – КПО ВС с участием команд из более, чем 10 регионов России. Школьники Казани и Татарстана активно участвуют в этом соревновании и, по мнению автора, как председателя жюри этого турнира, выступают в нем, пожалуй, лучше казанских студентов, имея больший соревновательный опыт.

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

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

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

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

В комментариях после некоторых программ, для примера, приведены тесты для их проверки на олимпиаде с указанием баллов за каждый тест.

2. БАЗОВЫЕ СРЕДСТВА ЯЗЫКА

2.1. Пример простой программы

Знакомство с языком программирования удобно начинать с примера программы.

Пример 2.1. Площадь прямоугольника. Задача: составить программу, которая вводит два вещественных (действительных) числа: X и Y - длины сторон прямоугольника, а затем вычисляет и выводит их произведение.

Решением является программа 2.1.

{         Программа 2.1. Площадь прямоугольника                 }                 (1)

program P2_1;                        {  Заголовок программы          }                (2)

var   x, y, s: real;                {  Описание переменных         }                (3)

begin                                     {  Начало программы                }                (4)

   read(x, y);                  {  Ввод значений X и  Y         }                (5)

   s := x * y;                        {  Получение результата        }                (6)

   write (s);                     {  Вывод результата s        }                (7)

end.                                        {  Конец программы                }                (8)

Пояснения к программе 2.1 (номера строк в скобках справа используются для пояснений и не являются частью программы).

1. Текст, ограниченный фигурными скобками { и } в строках (1 - 8), в языке Pascal служит комментарием для пояснения программы. Комментарий не влияет на выполнение программы, но значительно повышает ее наглядность.  Комментарий может занимать несколько строк.

2. Программа может начинаться с заголовка - строка (2). Он начинается  словом program, за которым следует название программы. Заголовок не  обязателен и в последующих примерах обычно отсутствует.

3. В любом языке программирования используются зарезервированные служебные слова, имеющие определенный смысл (обычно на основе английских слов, как в языке Pascal). В пособии для наглядности они выделены полужирным шрифтом. В этой программе служебными словами являются: program - программа, var – переменные (от слова variable - переменная), real – вещественный, begin – начало, read – читать, write – писать, end - конец.

4. После заголовка располагаются описания используемых в программе величин и других объектов. За словом  var следуют описания переменных. Слово real в строке (3) указывает, что переменные величины x, y, s  могут принимать вещественные значения (целые и нецелые числа). В этой программе, как и в других в данном пособии,  величины X и Y обозначены строчными буквами  x  и  y (так удобнее набирать на клавиатуре).

5. Строки (5 – 7) между словами begin  и end содержат операторы программы – команды для выполнения компьютерных операций. В  конце программы после слова end ставится точка.

2.2. Правила записи программы

Алфавит (используемые символы) языка  Pascal включает латинские буквы, цифры, знаки операций, скобки и другие специальные символы.

Программа подобно обычному книжному тексту состоит из «слов». Роль «слов» играют служебные слова, имена, числа и другие константы, знаки операций и отдельные символы: скобки, запятая, точка с запятой и др.

Из слов составляются предложения: описания переменных, констант и других объектов программы, а также операторы – команды для выполнения операций. Предложения разделяются точкой с запятой.

Для обозначения переменных и других объектов в программе используют придуманные программистом имена. Имя может состоять из любого количества букв и цифр, но начинаться  должно с буквы. Имена могут содержать знак подчеркивания, который здесь считается буквой. Имена не должны совпадать со служебными словами языка. Примеры имен:  X, Kod, a1D5, DlinaPuti, Add, poisk_chisla.  В отличие от некоторых языков (например, C, C++), в именах и служебных словах языка Pascal прописные и строчные буквы не различаются. Например, имена X и x, Add и add, а также служебные слова Var и vaR считаются одинаковыми.

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

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

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

Для наглядности программы важен хороший стиль программирования – оформления программы, который значительно облегчает составление, понимание и отладку программ. Желательно, чтобы имена объектов выражали их смысл. Если предложения не очень короткие, то каждое из них лучше начинать с новой строки. Строки, вложенные в  предложение, начинают правее охватывающего предложения на ступеньку из двух-трех символов, как, например, строки (5-7) в программе 2.1. Смысл используемых величин, назначение частей программы и другие основные идеи ее построения желательно описать в комментариях.  Важно отделять комментарий от основного текста, чтобы он не мешал читать программу.

2.3. Переменная и постоянная величина

Информация в программах представляется в виде величин. Величина имеет обозначение в программе, значение, которое хранится в некоторой области памяти компьютера, и адрес – номер первого байта этой области.

Значение постоянной  величины – константы  - не изменяется при выполнении программы.  Обычно константы записываются в виде чисел и других обозначений, явно показывающих их значения, но могут обозначаться и именами.

Примеры констант языка Pascal:

- целочисленные константы:         48        -123;

- вещественные константы, т. е. действительные (целые и нецелые) числа:

57.6   -2.0        (дробная часть отделяется точкой),

3.8E-6        (число 3.8, умноженное на 10 в степени -6);

- символьные константы (одиночные символы) заключаются в апострофы - одиночные кавычки:        'A' ,  '5' ,   '*' ,   '-';

- строковые константы  также пишутся в апострофах:

                        ‘КАИ’,  ‘Введите число’.

Переменная величина  (или просто - переменная) обозначается именем и при  выполнении  программы  может изменять свое значение.

Константа тоже может иметь имя. Примеры определения именованных констант:

const  epsilon = 0.000001;

       pi = 3.14159265358;

       NMAX = 100;

Использование именованных констант облегчает понимание и изменения программы.

2.4. Присваивание

Переменную можно сравнить с классной доской, на которой записано некоторое значение. Это значение можно многократно читать и переписывать (копировать) в другое место. Его можно стереть и на том же месте написать новое значение. Прежнее значение при этом теряется.

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

Задание нового значения переменной называется присваиванием. Присваивание является важнейшей операцией большинства  языков программирования.

В языке Pascal оператор присваивания имеет вид

переменная  :=  выражение

Примеры операторов присваивания:

X := 5;        читается "X присвоить 5"

A := X - 2;        читается "A присвоить X-2"

X := X + 1;        читается "X присвоить X+1"

При выполнении оператора присваивания сначала вычисляется значение выражения, записанного справа от знака присваивания, а затем это значение заменяет собой прежнее значение переменной, указанной в левой части оператора. Таким образом, присваивание можно понимать как операцию "заменить на". Последний из приведенных операторов, например, увеличивает на единицу значение переменной X.

Выражение языков программирования пишется подобно  алгебраическим выражениям, но, в отличие от них, не допускает многоэтажной записи дробей, индексов и степеней,  поскольку  вводится с клавиатуры.  Поэтому дробная черта заменяется знаком деления '/', индексы пишутся в квадратных скобках после имени переменной. Знаком умножения служит звездочка '*'. Подробнее выражения рассмотрены в разделе 3.

Пример 2.2. Обмен значений переменных. Требуется написать операторы, при выполнении которых переменные  X и Y обменяются значениями.

Для решения задачи скопируем значение X во вспомогательную переменную, например, R.  После этого можно присвоить переменной X новое значение, а затем  скопировать старое значение X из R в  Y:                        

R := X;   X := Y;   Y := R           { Обмен X <--> Y  }

Вопрос. А нельзя ли решить эту задачу проще: X:=Y; Y:=X ?

Задачи

2.1. Какими будут значения переменных после выполнения следующих операторов присваивания?

а)   x:=1;  a:=x+4;   x:=x+1;   a:=a*2;   x:=x+a;  a:=a+1;

б) X:=5;  Y:=2*X;  X:=X*X+Y-5;  Y:=X-Y;

в) A:=5;  B:=8;  B:=B+A;  A:=B-A;  B:=B-A;

2.2. Каким было значение переменной x, если после выполнения следующих операторов оно стало равно 21?

     /* x:=? */        x:=x+1;  x:=x*2;  x:=x-1;  x:=x+10;        /* x=21 */

2.3. Написать оператор присваивания, который изменяет знак на противоположный у вещественной переменной t.

2.4. Написать последовательность операторов присваивания, в результате выполнения которых целочисленные переменные А и В обменяются значениями. Не использовать дополнительные переменные.

2.5. Написать последовательность операторов присваивания, обменивающих значения переменных, как показано стрелками:

а) A ® B ® C ® D ® E                б) A ® B ® C

                                                    ________                         

в) A ¬ B ® C ® D                г) A ¬® B ® C ® D

                  ________

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

а) x := a + b * c;

б) x := a * b – c / e;

в) x := a + b * (c - e) / (a - b);

г) x := a / (b - a) + x * (a + c / b);

2.7. Написать минимальное количество простых присваиваний, содержащих по одному умножению (без использования других арифметических операций), для вычисления следующих значений (где x - вещественное число, ^ - возведение в степень). Использовать минимум вспомогательных переменных.

а) x^4                б) x^6                в) x^7                г) x^8

д) x^9                е) x^10                ж) x^13        з) x^15

и) x^21        к) x^28                л) x^64        м) x^59.

3. ВВОД  И ВЫВОД. ФАЙЛЫ

3.1. Ввод и вывод

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

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

В языке Pascal  оператор ввода имеет вид:

read(список переменных)       или        readln(список переменных),

где список переменных – это последовательность имен, разделенных запятыми.

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

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

В отличие от оператора read, оператор readln  после ввода указанных в нем значений пропускает  последующие данные до конца строки (нажатия клавиши Enter). Последующий ввод начнется со следующей строки.  Например, при вводе текста из двух строк:

3. 4   5   6

7. 8   9

операторами      readln(X, Y);  read(A, B)

первый оператор введет значения  X = 3,  Y = 4 и пропустит числа 5 и 6 до начала следующей строки, второй оператор введет A = 7 и B = 8, а последующий ввод начнется с числа 9.

Оператор вывода в языке Pascal имеет вид:

write(список выражений)       или        writeln (список выражений) .

Выражения в списке разделяются запятыми. Значения выражений выводятся  на экран.

За выражением через двоеточие можно указать ширину поля – минимальное количество символов для  выводимого значения. Значение будет расположено в правой части поля, а слева перед ним выводится необходимое количество пробелов. Когда заданная ширина недостаточна для значения, оно все равно выводится полностью. Например, оператор

write(‘X=’,12: 4, ‘ ‘,345: 2,  57: 6)

выведет следующий текст (пробелы обозначены буквами b):

X=bb12b345bbbb57.

Пробел перед цифрой 3 является значением константы ‘ ’.

При выводе вещественного числа после ширины поля через двоеточие можно указать еще число выводимых дробных разрядов. Например, при A=12.34, PI=3.1415926, V=36.8 оператор

write(A:5:3, PI:5:2, ‘ Объем:’, V:6:2, ’ л.’)

выведет текст:

12.340 3.14 Объем: 36.80 л.

Оператор writeln отличается от оператора write только тем, что после вывода значений дополнительно выводятся символы конца строки – переход в начало следующей строки. Оператор writeln без аргументов вставляет в выходной файл символы перехода в начало следующей строки.

3.2. Файлы

Операторы read и  readln вводят данные из стандартного входного потока, обозначаемого  файловой переменной  input. Операторы write и  writeln  выводят данных в стандартный выходной поток, обозначаемый  файловой переменной output. Переменные input и output не требуется описывать.

По умолчанию (при запуске программы) входной поток input соответствует клавиатуре, а  выходной поток output - экрану.

В олимпиадных задачах обычно требуется использовать файлы. Если необходим ввод из файла, то можно назначить потоку  input входной  файл с помощью оператора:                  

assign (input, ‘имя_файла ’),

а затем подготовить его – открыть для ввода  оператором  

reset(input).

Последующие операторы read и readln  будут вводить данные не с клавиатуры, а из файла (начиная с первого символа). Входной файл необходимо создать до его открытия. Это делается с помощью любого текстового редактора, в том числе в системе Turbo Pascal.

Потоку output можно назначить выходной  файл оператором

assign(output, ‘имя_файла ’),

а затем его  открыть для вывода  оператором  

rewrite(output).

Если выходной файл существует, то при открытии он очищается – становится пустым; в противном случае создается новый пустой файл.

Последующие операторы write и writeln вместо экрана будут выводить данные в файл.

По окончании работы с файлом требуется  закрыть файл оператором

close(файловая переменная).

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

По завершении программы операционная система обычно сама закрывает потоки input и  output.

Если, например, в программе 2.1 требуется вводить перемножаемые  числа из файла in.txt, а результат умножения выводить в файл out.txt,  то решением задачи будет  программа 3.1. Закрывать потоки input и output в конце программы не обязательно.        

{ Программа 3.1. Площадь прямоугольника (с файлами)      }         

program P2_2;                                        

var   x, y, s: real;          { Размеры и площадь прямоугольника }

begin                                             

       assign(input, ‘in.txt’);  reset(input);

       assign(output, ‘out.txt’); rewrite(output);

   read(x, y);                       {  Ввод значений X и  Y           }        

   s = x * y;                             {  Вычисление площади          }        

   write (s);                          {  Вывод результата                  }

   close(input); close(output);        { Закрытие файлов }

end.                

Задачи

3.1. Какие значения выведет следующий фрагмент программы, если для ввода заданы числа: 1 2 3 ?

               var a, b: integer;

                  . . .

               read (a, b, a);

               write (a, b, a);

3.2. По аналогии с программами 2.1 и 3.1, используя ввод с клавиатуры и вывод на экран, а также файлы, напишите программы (или фрагменты программ)  для   вычисления следующих величин.

а) длины окружности,  площади круга и объема шара одного и того же заданного радиуса;

б) площади и периметра прямоугольного треугольника по длинам двух катетов.

4. АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ

4.1. Типы данных

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

Людям также требуется  знать тип объекта, чтобы правильно обращаться  с ним. Так, операция “построить дом” будет выполняться по-разному в зависимости от типа дома: возводится ли этот дом, например,  для жилья, или собирается из детского конструктора или создается в какой-нибудь компьютерной игре.

 Описания (или объявления) переменных в программе записываются после служебного слова var с помощью предложений вида

имя, … , имя: тип;

В таком предложении перечисляются имена переменных, относящихся к одному типу,  задаваемому служебным словом.

Например, описания переменных

var   x, y:     real;

        m, Nomer, i:  integer;  

обозначают, что x и  y являются переменными  вещественного типа real,  m, Nomer, i – целочисленные переменные - целого типа integer.

4.2. Целые числа

В языке Pascal есть несколько типов  целых и вещественных чисел. Целочисленные типы данных языка Turbo Pascal приведены в табл. 4.1.

Таблица 4.1. Целые типы данных

Константы целого типа записываются в виде последовательности цифр со знаком или без знака, например: 0,  611, -172.  

Для целых чисел допустимы арифметические операции: + (сложение), - (вычитание), * (умножение), div (деление нацело, с отбрасыванием дробной части частного), mod (остаток от деления).

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

Для целочисленного деления соблюдается равенство

Делимое = Делитель * Частное + Остаток

Пример:  14 div 4 = 3,      14 mod 4  = 2,     14 = 4 * 3 + 2.

Обычное деление целых чисел «/» вырабатывает частное вещественного типа (с сохранением дробной части).

Пусть дана, например, целочисленная величина X = 329. Младшая цифра  X  равна  X mod 10 = 9.  Операция X div 10 = 32 удаляет из X младшую цифру, получая значение всех остальных старших разрядов.  Вторая   справа цифра    X равна (X div 10) mod 10 = 2.

В общем случае, в системе счисления с основанием B:

операция X div BK  удаляет K младших цифр из числа X,                   (4.1)

X mod BK = (K младших цифр  числа X),                                              (4.2)

(K-я справа цифра  X)  = (X div BK-1) mod B = (X mod BK) div BK-1      (4.3)

Пример 4.1.   Квартира. Даны разделенные пробелами числа: номер квартиры N, количество этажей в доме H и  количество квартир K на лестничной площадке каждого этажа. Требуется составить выражения, вычисляющие: номер подъезда P, этаж E, и номер M данной квартиры на лестничной площадке, считая от 1 (1 ≤ N ≤ 10000, 1≤ H≤500, 1≤ K≤100).

Пример входных данных:                 Ожидаемый результат:

92  9  4                                        3  5  4

Решение. При изменении этажа E на 1  номер квартиры изменяется на величину K. При изменении номера подъезда P на 1 номер квартиры изменяется на число квартир в подъезде K*H.  Поэтому можно рассматривать искомые величины: P, E и M как «цифры» заданного номера квартиры N в смешанной системе счисления, имеющие вес, соответственно K*H,  K и 1.

В отличие от обычных цифр, изменяющихся от 0,  квартиры, подъезды и этажи обычно нумеруют от 1. Поэтому удобно при вычислениях считать, что нумерация начинается от 0 (т. е. уменьшена на 1), а результаты увеличить на 1. Тогда можно использовать  формулы (4.1 – 4.3).   Получим:

P  =  (N-1) div (K*H) + 1,                  

E  = ((N-1) mod  (K*H)) div K + 1,  

M =  (N-1) mod  K + 1.

4.3. Вещественные числа

Вещественные типы данных  языка  Pascal показаны в табл. 4.2. Хотя тип comp считается вещественным, он предназначен для представления больших целых значений.

Для вещественных чисел допустимы арифметические операции: + (сложение), - (вычитание), * (умножение), / (деление).

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

Таблица 4.2. Вещественные типы данных          

4.4. Выражения

Выражение состоит из операндов, знаков операций и круглых скобок и записывается, как принято в математике.

Сначала выполняются операции в скобках,  затем вне скобок. При этом сначала выполняются более старшие операции: *, /, div, mod, а затем  - более младшие: + и -.  Внутри каждой из этих групп операции имеют одинаковый приоритет и выполняются слева направо.

Кроме константы и имени переменной, операндом выражения может быть также вызов функции, который заменяется значением функции, например, abs(A-1).

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

Стандартные функции вещественного аргумента языка Pascal приведены в табл. 4.3. 

Вещественное значение можно преобразовать в целое с помощью стандартных функций trunс(X) и round(X) (см. табл. 4.3). Обратное преобразование целого значения в вещественное происходит автоматически, если вещественной переменной присвоить целочисленное выражение, например:   X :=  25 + 8.

Таблица 4.3. Стандартные числовые функции языка Pascal

Вопрос. Каковы значения арифметических выражений:

а) 3 + 15 mod 10,

б) 5 * 12 / 3 / 4 * 5,

в) 3.4 / 2 + 7 mod 20,

г)  trunc(3.7 + 0.5) – round(3.7) ?

Задачи

Напишите программы или фрагменты программ для  следующих задач.

4.1. Промежуток времени составляет D суток,   H  часов,  M  минут и  S секунд (0 ≤ D ≤ 10000, 0 ≤ H ≤ 23,  0 ≤ M ≤ 59, 0 ≤ S ≤ 59). Получить его значение T в секундах.

4.2. Задан промежуток времени T в секундах (T<1000000). Получить его в смешанных единицах: сколько он составляет суток D, часов H, минут M и секунд S (0 ≤ H ≤ 23,  0 ≤ M ≤ 59, 0 ≤ S ≤ 59).

4.3.  Подсчитать число белых клеток на шахматной доске, если верхняя левая клетка  белая.

а) Размер доски N*N  (N ≤ 100).

б) Размер доски M*N (M, N ≤ 100).

4.4.  Подсчитать число черных клеток на шахматной доске, если верхняя левая клетка  белая.

а) Размер доски N*N  (N ≤ 100).

б) Размер доски M*N (M, N ≤ 100).

4.5. Составить программу для задачи «Квартира».

4.6.  Вычислить координаты Xs, Ys  середины отрезка, соединяющего точки с координатами  X1, Y1 и X2, Y2.

4.7. Для точки с координатами X, Y вычислить ее координаты Xn, Yn в другой системе координат с началом в точке X0, Y0 (оси координат параллельны старым осям).

4.8.  Прямоугольник. Для  прямоугольника ABCD на плоскости даны в порядке обхода координаты трех вершин Xa, Ya, Xb, Yb, Xc, Yc. Вычислить координаты  вершины D.

4.9.  Параллелограмм. Для  параллелограмма ABCD на плоскости даны в порядке обхода координаты трех вершин Xa, Ya, Xb, Yb, Xc, Yc. Вычислить координаты вершины D.

4.10.  Квадрат. Для  квадрата ABCD на плоскости даны координаты Xa, Ya, Xc, Yc диагонально расположенных вершин A и C. Вычислить координаты вершин B и D. Вершины A, B, C, D расположены по часовой стрелке.

4.11. Вычислить расстояние D между точками на плоскости с вещественными координатами X1, Y1, X2, Y2, используя теорему Пифагора.

4.12. Треугольник. Вычислить площадь S треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc. Использовать формулу Герона:  S  = sqrt((p-a)*(p-b)*(p-c)),  где a, b, c длины сторон треугольника, p – полупериметр: p = (a + b + c)/2.

5. ПРОСТЫЕ ФУНКЦИИ

5.1. Описание функции

Программист может создавать и использовать свои собственные функции. Для этого описание новой  функции помещается перед программой после описания переменных.

В простейшем случае, когда значение функции можно записать в виде одного выражения, описание функции имеет вид:

function имя функции (описание параметров): тип значения;

begin

     имя функции := выражение

end;

Описание начинается с заголовка функции. В нем указывается придуманное программистом имя функции и тип ее значения. После имени функции в скобках приводятся описания типов  аргументов или, как чаще говорят программисты, параметров функции – переменных, от которых зависит ее значение. Описание аргументов вместе со скобками может отсутствовать.

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

В теле функции должен присутствовать оператор присваивания, в левой части которого записано имя функции, а справа – выражение, вычисляющее  ее значение. В простейшем случае это – единственный оператор.

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

Пример 5.1.   Расстояние между двумя точками плоскости. Вычислить расстояние D между точками на плоскости с вещественными координатами X1, Y1, X2, Y2.

Решение. По теореме Пифагора получим:

D = sqrt(sqr(X1 - X2)  +  sqr(Y1 - Y2)).                             (5.1)

Вычисление площади можно записать как оператор присваивания в программе, а можно оформить как описание функции (назовем ее dist – расстояние, дистанция), аргументами которой являются координаты двух точек:

{   Расстояние между точками (X1, Y1) и (X2, Y2) }

function  dist (X1, Y1, X2, Y2: real): real;

begin

     dist := sqrt(sqr(X1 - X2)  +  sqr(Y1 - Y2))

end;

5.2. Площадь многоугольника

Пример 5.2. Площадь треугольника с вершиной в начале координат. Вычислить площадь S треугольника с вершинами в начале координат О и  точках  плоскости с вещественными координатами X1, Y1, X2, Y2.

Решение. Известная формула Герона для вычисления площади треугольника по длинам его сторон a, b, c:  

S  = sqrt((p-a)*(p-b)*(p-c)),         где полупериметр  p = (a + b + c)/2,

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

Значительно удобнее простая формула:

S = 0.5 * (X1*Y2 – X2*Y1).                                      (5.2)

Эта формула дает ориентированную площадь – со знаком: S > 0 при обходе треугольника от точки 1 к точке 2 против часовой стрелки (когда начало координат остается слева), и S < 0 при обходе по часовой стрелке (когда начало координат остается справа).

По знаку S можно узнать относительное расположение вершин треугольника. Например, если площадь некоторого треугольника при обходе ABC больше нуля, то обход был против часовой стрелки и, следовательно, поворот от AB к BC и от BC к CA происходит налево.  Если учитывать знак не требуется, то площадь вычисляется по абсолютной величине.

Эту формулу можно оформить как описание функции S2, зависящей от координат двух заданных точек:

{   Площадь треугольника по 2 точкам:  (X1, Y1), (X2, Y2), (0, 0) }

function S2 (X1, Y1, X2, Y2: real): real;

begin

     S2 := 0.5 * (X1*Y2 – X2*Y1)

end;

Вопрос. Попробуйте вывести  формулу (5.2), нарисовав чертеж, хотя бы для одного варианта расположения точек (это нетрудно).

Пример 5.3.   Площадь многоугольника. Дано количество вершин N  и вещественные координаты вершин в порядке обхода произвольного многоугольника: X1, Y2, … XN, YN. Найти его площадь S.

Решение. Ориентированная площадь S многоугольника произвольной формы (в том числе звездообразного и т. п.) равна сумме ориентированных площадей треугольников, полученных соединением всех  вершин многоугольника с началом координат и образованных каждой стороной и началом координат (рис. 5.1).

По формуле (5.2) получим

                              n

S = 0.5 * Σ (Xi * Yi+1 – Xi+1 * Yi),                                          (5.3)

                             i =1

где:    Xn+1 = X1,  Yn+1 = Y1,  S > 0 при обходе многоугольника против часовой стрелки (когда многоугольник остается слева), S < 0 при обходе многоугольника по часовой стрелке (когда многоугольник остается справа).

Если, например, начало координат O вне многоугольника (как на рис. 5.1)  то при соединении вершин с началом координат образуется фигура OCDEA, напоминающая «парашют», «куполом» которого служит многоугольник ABCDE, а «стропами» – отрезки между его вершинами и началом координат. Площадь области «строп» OABC слагается из треугольников, образованных ближними к началу координат сторонами многоугольника. Треугольники, образованные дальними от начала координат сторонами, составляют площадь всего «парашюта» OCDEA.  При обходе многоугольника ABCDE для вычисления его площади по формуле (5.3) направление обхода  треугольников области «строп» ABO и BCO (показано стрелками) противоположно обходу треугольников «парашюта»: CDO,  DEO и EAO, и их площади имеют разные знаки. В итоге из площади «парашюта» вычитается площадь «строп» и получается площадь «купола» (многоугольника). Ее знак совпадает со знаком площади «парашюта» - положителен при обходе многоугольника против часовой стрелки.  

Используя функцию S2, формулу (5.3) можно записать в виде

            n

S = Σ  S2 (Xi , Yi+1, Xi+1, Yi),                                                        (5.4)

           i =1

В частном случае, ориентированная площадь S треугольника с координатами вершин X1, Y1,  X2, Y2,  X3, Y3, по формуле (5.3) равна  

S = 0.5 * (X1*Y2 – X2*Y1 + X2*Y3 – X3*Y2 + X3*Y1 – X1*Y3)      (5.5)

Пользуясь формулой (5.4), ее можно записать иначе

S = S2(X1, Y1, X2, Y2) + S2(X2, Y2, X3, Y3) + S2(X3, Y3, X1, Y1)     (5.6)

Следствие. Из формул (5.2, 5.3) видно, что удвоенная площадь любого многоугольника с целочисленными координатами вершин выражается целым числом. Иначе говоря, площадь «целочисленного» многоугольника кратна 0.5.

Пример 5.4. Площадь треугольника. Составить программу получения в файле output.txt площади S треугольника с заданными в файле input.txt  вещественными координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

Решение. Можно оформить расчет по формуле (5.6) в виде функции S3, для вычисления которой используем ранее созданную функцию S2. Получим программу 5.1, содержащую две функции.

{ Программа 5.1  Площадь треугольника ABC                         }

var Xa, Ya, Xb, Yb, Xc, Yc: real;

{   Площадь треугольника по 2 точкам:  (X1, Y1), (X2, Y2), (0, 0) }

function S2 (X1, Y1, X2, Y2: real): real;

begin

     S2 := 0.5 * (X1*Y2 – X2*Y1)

end;

{   Площадь треугольника по 3 точкам: (X1, Y1), (X2, Y2) и (X3, Y3) }

function S3 (X1, Y1, X2, Y2, X3, Y3: real): real;

begin

     S3 := S2(X1, Y1, X2, Y2) + S2(X2, Y2, X3, Y3) + S2(X3, Y3, X1, Y1)

end;

begin                                             

           assign(input, ‘input.txt’);  reset(input);

           assign(output, ‘output.txt’); rewrite(output);

   read(Xa, Ya, Xb, Yb, Xc, Yc);                      

   write (abs(S3(Xa, Ya, Xb, Yb, Xc, Yc)));                          

   close (input); close (output);      

end.                

Задачи

5.1. Промежуток времени составляет D суток,   H  часов,  M  минут и  S секунд (0 ≤ D ≤ 10000, 0 ≤ H ≤ 23,  0 ≤ M ≤ 59, 0 ≤ S ≤ 59). Составить на языке Pascal функцию time(D, H, M, S), вычисляющую это время  в секундах.

5.2. Составить на языке Pascal функции:

a) hip (A, B) – длина гипотенузы прямоугольного треугольника с катетами A  и  B,

б) высота Ha, опущенная из вершины A треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

в) периметр треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

г) длина медианы Ma из вершины A треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

5.3. Площадь треугольника. Составить программу вычисления площади S треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

а) Использовать формулу (5.5) непосредственно в программе.

б) Составить и использовать функцию S3, вычисляющую площадь треугольника по  формуле (5.5) без функции S2.

в) Использовать формулу Герона:  S  = sqrt((p-a)*(p-b)*(p-c)),  где a, b, c длины сторон треугольника, p – полупериметр: p = (a + b + c)/2. Для вычисления длин сторон использовать функцию dist из раздела 5.1.

5.4. Площадь четырехугольника. Составить программу вычисления площади S четырехугольника с заданными  координатами  вершин на  плоскости:  X1, Y1, X2, Y2, X3, Y3, X4, Y4. Использовать функцию S2 или S3.

5.5. Составить программу вычисления высот Ha, Hb, Hc треугольника с заданными  координатами  вершин на  плоскости:  Xa, Ya, Xb, Yb, Xc, Yc.

6. ВЕТВЛЕНИЕ

6.1. Управляющие операторы

Рассмотренные ранее программы ведут себя примитивно – одинаково во всех случаях. Действия людей более разнообразны и зависят от обстоятельств, например: «если идет дождь, то взять зонт»; «если блюдо недосолено, то добавить соли»; «повторять движения щетки, пока обувь не будет чистой»; «выполнять упражнение заданное число раз» и т. д. Управляющие операторы позволяют  реализовать подобное поведение в программе. К ним  относятся условный оператор и оператор выбора, а также рассмотренные в следующем разделе операторы цикла.

  6.2. Условный оператор

Условный оператор предусматривает выполнение одной из двух ветвей программы - двух вариантов действий, и имеет вид

if  условие  then оператор_1  else  оператор_2

Если условие истинно, то выполняется оператор_1, иначе выполняется оператор_2 (if – если, then – то, else - иначе).

Примечание. Перед словом else точка запятой недопустима, т. к. она ставится между операторами, а else не является началом оператора.

Когда во втором  варианте не требуется ничего делать, после else ничего не пишут – пустой оператор, или используют  сокращенный) условный оператор без конструкции «else оператор_2»:

if условие then оператор

Примечание. Если операторы if вложены друг в друга, то слова if и else соотносятся подобно скобкам: каждое слово else соответствует ближайшему предшествующему «не закрытому» if.

Простейшее условие записывается с помощью операций сравнения: = (равно),   <> (не равно), < (меньше), > (больше), <= (меньше или равно), >= (больше или равно). Например, оператор

 if A > B then X := A else X := B

присвоит переменной X максимальное значение из  двух величин: A  или B.

Вопрос. Как без использования функции abs записать присваивание

X := abs(X)  ?

По правилам языка, каждая ветвь условного оператора должна содержать один оператор. Еcли ветвь содержит несколько операторов, то их объединяют в один составной оператор с помощью операторных скобок - служебных слов begin  и end. Составной оператор записывается в виде:

begin оператор ; оператор ; … ; оператор end

Например, после выполнения условного оператора

if  X > Y then begin

    R := X;  X := Y;  Y := R        {  Обмен значений X и Y  }

end

переменная X будет иметь меньшее, а переменная Y – большее из  их исходных значений.

0. 6.3. Логический тип данных

Условие в операторе if является логическим выражением. Логический  тип данных boolean  (булев, булевский - по имени английского математика Дж. Буля)  состоит из двух значений - логических констант, обозначаемых служебными словами  true (истина) и  false  (ложь).

Логические значения могут быть результатом операций сравнения, например, выражение 7 + 2 <= 9 имеет значение true, а сравнение 2 > 5 выдает значение false. Их можно присваивать логическим переменным, например:

var X, Y:  boolean;

       A, B: integer;

        …

X := A <= (B + 9);  

Над значениями типа boolean можно выполнять логические операции:  not  (НЕ – отрицание), and (И - логическое умножение, конъюнкция) и  or (ИЛИ - логическое сложение, дизъюнкция). С  помощью логических операций из простых условий  составляют сложные, которые могут стать частями еще более сложных условий и т. д.

Значение логического выражения вычисляется по таблицам истинности логических операций (табл. 6.1).

Таблица 6.1. Логические операции

Логические операции имеют следующие свойства (доказываются перебором вариантов  значений по таблице истинности).

1. Закон отрицания          not (not x) = x

2. Коммутативность      x and y = y and x

x or y = y or x

3. Ассоциативность         (x and y) and z = x and (y and z)

(x or y) or z = x or (y or z)

4. Дистрибутивность      x and (y or z) = (x and y) or (x and z)

x or (y and z) = (x or y) and (x or z)

5. Законы  де Моргана      not (x or y) = not x and not y

not (x and y) = not x or not y

Из законов де Моргана следует полезное правило: отрицание любого логического выражения получается заменой в нем всех операций И и ИЛИ друг на друга, а каждого их операнда - на его отрицание.

Зачастую легче  сформулировать условие, противоположное требуемому, а затем  получить его отрицание по правилам де Моргана.

Операции логического выражения выполняются по старшинству в следующем порядке:  not, and, or, сравнения, арифметические операции.

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

Пример.  Год g  является  високосным (содержит не 365, а 366 дней), если он без остатка делится на 400 или делится на 4, но не делится на 100:

if ((g mod 400) = 0) or ((g mod 4) = 0) and ((g mod 100) <> 0)

       then               . . .                                                 { год g   високосный }

Пример 6.1. Монеты 3 и 5. Определить, можно ли выплатить заданную целочисленную сумму  S  монетами достоинством  3 и 5, имеющимися в достаточном количестве (S ≤ 2000 000 000). Программа должна вывести слово YES, если сумму можно выплатить, и слово NO в противном случае.

Примеры входных данных             Выходные данные для этих примеров:

6. YES

4                                                  NO

Решение. Если  сумма S кратна 3, то  ее  можно выплатить монетами по 3. В противном случае остаток S mod 3 равен  1 или 2. Если остаток равен  1 и    S ≥ 10, то  сумму можно выплатить, заменив три монеты по 3 на 2 монеты по 5. Если остаток равен  2, то достаточно заменить монету 3 на монету 5. Поэтому можно выплатить любую сумму S ≥ 10 (даже имея всего две монеты по 5). При S < 10 невозможно выплатить суммы:  1, 2, 4, 7. Отсюда –  программа 6.1:

{ Программа 6.1  Задача «Монеты 3 и 5»    }

var s: longint;

begin                                             

      assign(input, ‘input.txt’);  reset(input);

      assign(output, ‘output.txt’); rewrite(output);

             read(s);                      

      if (s=1) or (s=2) or (s=4) or(s=7) then write(‘NO’)

      else write(‘YES’);    

   close(input); close(output);        

end.

Примечание. Условие (s=1) or (s=2) or (s=4) or (s=7) можно заменить таким

(s-1)*(s-2)*(s-4)*(s-7) = 0.

6.4. Символьный тип

Компьютеры чаще обрабатывают не  числовую, а  символьную  информацию  – тексты, состоящие из символов.

Значениями символьного типа данных  char (character – символ) являются буквы, цифры  и другие символы. Символьная константа пишется в апострофах – одиночных кавычках, например: ‘A’, ‘a’, ‘Ю’, ‘5’, ‘+’,  ‘ ‘ (пробел) или в виде числового кода символа с символом #, например,  #13.

В памяти компьютера символ хранится в виде целого числа – кода символа. Символьные значения можно вводить и выводить в виде символов, присваивать символьным переменным, а также сравнивать по величине их кодов операциями:  =, <>, <,  >, <=, >=.

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

Таблица 6.2. Стандартные символьные функции языка Pascal

Обычно в персональных компьютерах для символов используется американский стандартный код ASCII  (читается «аски»),  занимающий один байт. Коды от 0 до 127 являются международным стандартом. Коды от 128 до 255 используются по-разному, в том числе для кириллицы.

Конкретный набор символов и их кодировка зависят от транслятора, но во всех кодировках (и для всех языков) соблюдаются следующие условия.

1. Цифры закодированы отрезком натурального ряда:

ord('1') = ord('0') + 1

ord('2') = ord('0') + 2

. . .

ord('9') = ord('0') + 9

Отсюда - важные соотношения:

Код цифры  =  ord('0') + Значение цифры                                    (6.1)

Значение цифры  =  Код цифры – ord( '0')                                   (6.2)

2. Коды заглавных латинских букв возрастают по алфавиту, но не обязательно подряд.

3. Коды строчных латинских букв также возрастают по алфавиту, но не обязательно подряд.

Русские буквы (они имеются не во всех кодировках) кодируются не всегда по алфавиту и могут не обладать этими свойствами.

Пример описания символьных переменных:    var  sim, с : char;

Поскольку цифры кодируются последовательными целыми числами, условие "значение переменой sim является цифрой"  запишется так:

(sim >= '0') and (sim <= '9')

Его отрицание (противоположное условие) "значение sim не является цифрой" можно получить заменой and на or, а каждого неравенства - на противоположное:

(sim < '0') or (sim > '9')

Если заглавные и строчные латинские буквы кодируются отдельными отрезками натурального ряда (как, например, в коде ASCII), то условие "значение символьной переменой sim является латинской буквой" можно записать так:

(sim >='A') and (sim <='Z') or (sim >='a') and (sim <='z')

Пример 6.2. Символьный ввод числа. Входной текст из 5 символов содержит время t в формате чч:мм, где чч – час, мм – минута  (по 2 цифры, через двоеточие). Требуется ввести и присвоить час и минуту целочисленным переменным h и m, а затем получить время t в минутах. Например, при вводе текста 10:02 должны получиться значения  h = 10,  m = 2,  t = 602.

Решение. Если бы числа разделялись не двоеточием, а пробелами и/или символами новой строки,  то их можно вводить оператором  read (h, m). В данном случае придется  читать текст по одному символу и вычислять значения часа и минуты  по двум цифрам, например, так:

var sim1, sim2: char;   h, m, t: integer;

…

read(sim1, sim2);                                                        { две цифры часа        }

h := 10*(ord(sim1) - ord(‘0’)) + ord(sim2) - ord(‘0’);

read(sim1);                                              { Пропуск двоеточия  после часа }

read(sim1, sim2);                                                        { две цифры минуты  }

m := 10*(ord(sim1) - ord(‘0’)) + ord(sim2) - ord(‘0’);

t := 60 * h + m;

Задачи

6.1. Даны координаты  X1, Y1, X2, Y2 двух полей шахматной доски  - номера вертикали и горизонтали, целые числа от 1 до 8. Вывести слово ‘YES’ или  ‘NO’ в зависимости от того, соблюдается или нет следующее условие.

а) Эти поля имеют одинаковый цвет.

б) Эти поля имеют разный цвет.

в) С одного поля на другое можно перейти ходом шахматной ладьи.

г) С одного поля на другое можно перейти ходом шахматного слона.

д) С одного поля на другое можно перейти ходом шахматного ферзя.

е) С одного поля на другое можно перейти ходом шахматного коня.

ж) С одного поля на другое можно перейти ходом шахматного короля.

Примечание. Шахматная доска имеет  размер 8 * 8 полей, раскрашенных попеременно в белый и черный цвет. Ладья может ходить по горизонтали или по вертикали на любое расстояние. Слон ходит по диагонали на любое расстояние. Ферзь ходит по горизонтали,  вертикали или диагонали на любое расстояние. Король ходит на соседнее поле по горизонтали,  вертикали или диагонали. Конь ходит «буквой Г» - делает шаг на два поля по горизонтали или вертикали, а затем - шаг на одно поле в любом перпендикулярном направлении.

6.2. Омлет. На приготовление порции омлета требуется E1 яиц, M1 граммов молока и B1 граммов масла. Составить программу подсчета, сколько порций омлета можно приготовить из E яиц, M граммов молока и B граммов масла.

6.3. Составить логическую функцию (возвращающую значение типа boolean).

а) digit (sim) - cимвольная переменная sim содержит цифру

б) letter (sim) - cимвольная переменная sim содержит заглавную латинскую букву.

в)  (sim) - cимвольная переменная sim содержит цифру или  латинскую букву.

г) Имеющихся продуктов: E яиц, M граммов молока и B граммов масла, достаточно для  приготовления порции омлета, для которой требуются E1 яиц, M1 граммов молока и B1 граммов масла, где E1, M1 и B1 – имена констант.

6.4. Составить символьную функцию, обладающую значением типа char.

а) chartype (sim),  возвращающую значение ‘1’, если символьный параметр sim содержит цифру, значение  ‘a’, если   sim содержит латинскую букву, и значение sim в остальных случаях.

б) small (sim), которая при значении sim, являющимся заглавной латинской буквой, возвращает соответствующую строчную букву, а в остальных случаях возвращает значение sim (считать, что коды заглавных букв образуют отрезок натурального ряда, и коды строчных букв обладают этим же свойством).

7. ПРОГРАММЫ С  ВЕТВЛЕНИЕМ

Разберем несколько задач, которых содержат разные варианты действий.

7.1. Приближенное сравнение чисел

При  сравнении вещественных чисел, особенно с операциями = «равно» и <> «не равно», необходима  осторожность, поскольку их значения хранятся с ограниченным числом цифр, и операции с ними являются приближенными.

Например, если переменные X и Y относятся к разным вещественным типам   var X: real; Y: extended; и им присвоены одинаковые значения  X:=5.3;  Y:=5.3, то результатом сравнения  X = Y будет false, т. к. они хранятся в двоичной системе приближенно с разным числом разрядов. Подобным образом в десятичной системе, например, значения  дроби 1/3 с разным числом разрядов 0.3333 и 0.33333 не равны друг другу.

Аналогичным образом нельзя рассчитывать, что будет соблюдаться, например, точное равенство  10 * 0.1 = 1. Эти величины в компьютере будут очень близки, но точного совпадения не может быть, т. к. число 0.1 в двоичной системе образует периодическую дробь (как 1/3 в десятичной системе).

Поэтому точное сравнение вещественных величин X = A необходимо заменить приближенным равенством X ≈ A, которое можно записать в виде   abs (X-A) < eps, где eps – зависящая от задачи допустимая погрешность, например 0.000001 (рис. 7.1).

Это условие равносильно двойному неравенству A – eps ≤  X ≤ A + eps. Тогда надо вместо X < A писать   X < A - eps,  X > A  заменить на   X > A + eps,   X ≤ A  записывать как X <= A+eps,  а X ≥ A представлять в виде X >= A - eps.

7.2. Задача «Открытка и конверт»

Пусть для заданных вещественных чисел a, b, g, h требуется определить, войдет ли прямоугольная открытка размером a*b  в прямоугольный конверт размером g*h. Считать, что открытка войдет, если ее размеры не больше, чем у конверта. Сравнение необходимо производить с погрешностью не более 10-6.

Пример входных данных                    Выходные данные  для этого примера:

15  10  9.5  16                                      NO

Решение. Удобно считать, что a  и g – размеры коротких сторон открытки и конверта, b и h  - размеры длинных: a ≤ b, g ≤ h (если это не так, обменяем стороны местами).

Из симметрии   прямоугольника следует, что если открытку можно вложить в конверт, то можно сделать и так, чтобы их центры совпадали. Тогда, чтобы вложить открытку, ее останется только вращать вокруг  общего центра. При этом вершины открытки  движутся по окружности диаметром d, равным диагонали открытки (рис 7.2). Возможность вложения зависит от диаметра. По теореме Пифагора: d2 = a2 + b2.

Если окружность и конверт не пересекаются, то либо d < g - вся окружность внутри конверта, тогда открытка войдет в любом положении; либо   диаметр больше диагонали конверта: d > g2 + h2, тогда весь конверт внутри окружности, и открытка не входит.

Окружность может пересекать либо две, либо четыре стороны конверта. Если d ≤ h, то пересекаются две стороны,  открытку надо располагать параллельно сторонам конверта, и она войдет, когда   a ≤ g  и  b ≤ h.  

Если d > h, но d < g2 + h2 (как на рис. 7.2), то пересекаются четыре стороны. Тогда открытку надо располагать так, чтобы ее длинная сторона была почти параллельна диагонали конверта, и вложение возможно только при условии, что короткая сторона открытки не больше расстояния (обозначенного на рис. 7.2 вопросительным знаком) между двумя точками пересечения окружности со сторонами конверта около этой диагонали.

Чтобы не извлекать корни, удобнее сравнить квадраты этих величин. По теореме Пифагора, квадрат этого расстояния равен e2 + f2, и условием вхождения в конверт  будет a2 ≤ e2 + f2. Дважды используя  теорему Пифагора, получим:     e = (g – sqrt(d2 - h2))/2,    f = (h – sqrt(d2  -  g2))/2.

После подстановки этих значений в условие вхождения и его преобразования оно примет вид, приведенный в программе 7.1 с учетом погрешности:  a2 ≤ b2  - g * sqrt(d2 - h2)  - h *  sqrt(d2 - g2) + eps.

{     Программа 7.1.       Задача  OK. Открытка и конверт

   Войдет ли открытка a * b в конверт g * h.

   Метод: Теорема Пифагора  - войдет "по диагонали", если сторона  открытки  <=  отрезка между точками пересечения описанной  окружности открытки со сторонами конверта.

P71_ok.pas                                                       }

const eps=1e-6;                          { Погрешность сравнения }

var a, b, g, h, d2, w: real;

begin

  assign(input, 'input.txt');  reset  (input);

  assign(output,'output.txt'); rewrite(output);

  while not SeekEof {(input)} do begin

    read(a, b, g, h);

    if a > b then begin w:=a; a:=b; b:=w; end;          { a <= b }

    if g > h then begin w:=g; g:=h; h:=w; end;          { g <= h }

    if (a<=g) and (b<=h) then  writeln('YES')       { стороны || }

    else begin                          { Попробуем по диагонали }

      d2 := a*a+b*b;                    { Квадрат диаметра       }

      if (d2 > g*g+h*h) then writeln('NO')

      else if (d2 >= h*h) then       { Пересечение с 4 сторонами }

        if a*a <= b*b-g*sqrt(d2-h*h)-h*sqrt(d2-g*g)+ eps

        then writeln('YES')  

        else writeln('NO')

      else writeln('NO'); {Пересечение 2 сторон, || уже проверено}

    end

  end;

  close(input); close(output);

end.

{  Тесты к задаче OK. Открытка и конверт (30 баллов)

     Открытка   Конверт    Пройдет?  Баллы

 #    a   b     g     h    (ответ)   (30)    

 1    1  1.1    1     1      NO        1    

 2    2   2     2     2      YES       2

 3    3   4     3     4.1    YES       2

 4    4   5     5.1   4      YES       2

 5    5   4     4.1   5      YES       2

 6    6   3     6     3.1    YES       2

 7    2  11.9  11.6   7      YES       2    

 8    2  12    11.6   7.1    NO        2    

 9    2  12    11.6   7.3    YES       3    

10   20   5    16.1  19      YES       3    

11    5  20    16    19.1    YES       3    

12    5  20    16    19      YES       3    

13    3.4 3.4 2.4 5.1        NO        3  }

7.3. Задача «Треугольник и точка»

Даны вещественные  координаты четырех точек плоскости: X, Y,  X1, Y1,  X2, Y2,  X3, Y3. Требуется определить, лежит ли точка X, Y внутри треугольника с вершинами в  точках X1, Y1,  X2, Y2,  X3, Y3. Допустима погрешность  не более 10-6. Составить функцию, возвращающую значение true или false соответственно (или программу, выводящую слово ‘YES’, если внутри, и слово  ‘NO’ в противном случае).

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

const eps = 1E-6;                                           { Допустимая погрешность  }

. . .

{   Точка (X, Y) внутри треугольника: (X1, Y1), (X2, Y2) и (X3, Y3) }

function Vnutri (X, Y, X1, Y1, X2, Y2, X3, Y3: real): boolean;

   var st, st1, st2, st3: real;                          { Площади  треугольников }

begin

     st := abs(S3(X1, Y1, X2, Y2, X3, Y3));

     st1 := abs(S3(X, Y, X2, Y2, X3, Y3));

     st2 := abs(S3(X1, Y1, X, Y, X3, Y3));

     st3 := abs(S3(X1, Y1, X2, Y2, X, Y));

     Vnutri := abs(st1 + st2 + st3 - st) < eps;

end;

Решение 2. Эту задачу можно решить для любого выпуклого многоугольника, проверив знаки площадей всех треугольников, образованных  соединением  данной точки со сторонами многоугольника. Если точка внутри многоугольника, то при его обходе она будет расположена по одну сторону от всех сторон многоугольника, и площади всех треугольников будут одного знака: все либо положительны, либо отрицательны. Если точка находится  на стороне многоугольника, то соответствующая площадь равна нулю. Если же точка расположена снаружи многоугольника, то треугольники будут иметь площади разных знаков.

Задачи

7.1. Составить функции приближенного сравнения вещественных чисел X и Y с погрешностью,  задаваемой константой EPS.

а) Eq (X, Y)         -  X  (приблизительно) равен Y.

б) NotEq (X, Y)         -  X  (приблизительно) не равен Y.

в) GrEq (X, Y)         -  X  (приблизительно) не меньше Y.

7.2. Используя функцию Vnutri, напишите программу решения задачи «Треугольник и точка».

7.3. Котлеты. На сковороде, вмещающей M котлет, необходимо поджарить с двух сторон  каждую из N  имеющихся котлет (0 < M ≤1000, 0 ≤N < 32768). На поджаривание котлет с одной стороны тратится 1 минута. Составить программу вычисления, за какое минимальное число минут T можно поджарить все котлеты с двух сторон.

Пример входных данных            Выходные данные для этого примера:

2 3             (М=2, N=3)                3        (не считайте это ошибкой!)

7.4. День учителя. День учителя отмечается в первое воскресенье октября. Определить на какое число D приходится день учителя  в  заданном году G (1950 ≤ G ≤ 3000),  учитывая, что   1 января 1 года н. э. был понедельник по новому стилю.  

Указание. Год считается високосным (366, а не 365 дней), если он нацело делится на 400 или делится на 4, но не делится на 100.

Пример входных данных            Выходные данные для этого примера:

2007                                        6

7.5. Оптовая покупка. Диск стоит CD руб, коробка (KD дисков) стоит CK руб, а ящик (KK коробок) стоит CB руб.  Составить программу,  которая по числу N необходимых дисков вычисляет числа B,  K,  D - ящиков,  коробок и дисков,  которые следует купить, чтобы покупка обошлась дешевле  (разрешается  приобрести  больше  дисков чем требуется). Числа N,  KD, KK не превышают 10000; цены CD, CK и CB не превышают 1000000.00 руб.

Входные данные:                        Выходные данные:

CD  KD  CK  KK  N                        B  K  D

Пример входных данных            Выходные данные для этого примера:

9  10  100  10.5  90  8500                0 1 0    

8. ЦИКЛЫ

Цикл  (круг по-гречески)  –  это повторяющееся выполнение некоторого участка программы (и сам повторяемый участок). Только благодаря циклам мы можем заставить  компьютер проделать большую работу, повторяя небольшое число написанных нами операторов. В языке Pascal - три оператора цикла: цикл с предусловием, цикл с постусловием и цикл с параметром.

8.1. Цикл с предусловием

Наиболее универсальным является  цикл с предусловием - оператор while, имеющий вид (while – пока, do – делать):

while условие do оператор

Условие – это логическое выражение. Пока это выражение истинно, повторяется выполнение оператора: если условие соблюдается, то выполняется оператор и снова проверяется условие и т. д. Перед каждым повторением цикла логическое выражение вычисляется заново. Для повторения нескольких операторов их объединяют в составной оператор.

Если условие окажется ложным при первой же проверке, то число повторений цикла будет нулевым. С помощью цикла while можно запрограммировать любые повторяющиеся действия.

Пример 8.1. Фальшивая монета.  Среди N  монет одна  фальшивая, легче настоящей. Имеются чашечные весы  без  делений  и гирь, с  помощью  которых можно только узнать,  равен ли  вес на двух чашках, или на какой чашке вес меньше.  Весы могут вместить все монеты.

     Составить программу (фрагмент программы) для вычисления минимального количества взвешиваний V, достаточного для определения,  какая из N монет фальшивая (1≤ N≤ 2000 000 000).

Пример входных данных:        Выходные данные для этого примера:

4                                        2

Решение. Составим тесты, постепенно увеличивая N. При N=1 ответ 0: взвешивания не нужны. При N=2 ответ 1: фальшивой является более легкая монета. При N=4 первое взвешивание даст более легкую пару монет, и задача сводится к случаю N=2. Вообще, для четного N=2*M одно взвешивание сводит задачу к N=M. Возникает предположение, казалось бы, подтверждаемое примером из задачи, что ответом будет минимальное V, для которого 2V ≥ N.

Однако, для N=3 ответ 1. Достаточно одного взвешивания, чтобы из трех монет (или куч) найти более легкую (если известно, что она есть), благодаря тому, что взвешивание имеет не два, а три возможных исхода: «меньше», «больше» или «равно» (когда легкая монета не на весах,  а в третьей куче)!

Если делить монеты на три кучи: две равные взвешивать, а третью откладывать (она может содержать меньше монет, если их число не кратно 3), то каждое взвешивание уменьшает число подозрительных монет, как минимум, втрое.  Поэтому ответом будет минимальное V, для которого 3V ≥ N.  

В программе 8.1 возведение числа 3 в степень V выполняется c помощью цикла повторного умножения степени тройки s3 на 3, пока s3 меньше заданного числа монет N. Необходимое количество взвешиваний V подсчитывается как число повторений этого цикла. Для N ≤ 2000 000 000 потребуется не более 20 повторений цикла. В программе  величины N и V обозначены строчными буквами  n  и  v (так удобнее набирать на клавиатуре).

{ Программа 8.1.      Задача M. Фальшивая монета

Найти минимальное число взвешиваний, достаточное         для поиска одной легкой монеты из N данных.      

Метод: возведение 3 в степень v до 3^v >= n     }                                  

var n, v, s3: comp;      {longint не достаточен }

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   read (n);

   v := 0; s3 := 1;

   while s3 < n do begin   { s3 = 3 в степени v }

      s3 := 3*s3;          

      v := v + 1;

   end;

   write(v);

   close(output); close(input);

end.

Примечание. Для знакомых с понятием алгоритма: при n > 1 решением является  v =  1 + trunc (log 3 (n - 0.5)) = 1 + trunc (ln (n - 0.5)/ ln (3)).

8.2. Цикл с постусловием

В отличие от цикла с предусловием, в цикле с постусловием (пост – после по-латински) условие пишется и проверяется не до, а после повторяемых действий - тела цикла:  

repeat оператор; оператор; … оператор  until условие

Здесь тело цикла может включать несколько операторов, т. к. оно с обеих сторон ограничено ключевыми словами: repeat  (повторять) и   until (пока не).  Кроме того, здесь указывается условие выхода из цикла, когда происходит  прекращение повторений, а не условие продолжения, как в операторе while.

Цикл с постусловием повторяется, как минимум, один раз, поскольку  тело цикла сначала выполняется, и только потом проверяется, следует ли его повторять. Этот цикл пригоден, когда не бывает нулевого числа повторений, и в таких случаях он может быть удобнее цикла while, но эти случаи нелегко распознать. Во избежание ошибок, начинающим программистам лучше избегать использования этого цикла.

8.3. Цикл с параметром

Цикл с параметром - это цикл, при повторении которого изменяется с постоянным шагом некоторая переменная - параметр цикла. Такой цикл в языке Pascal организуется с помощью оператора for (для):

for переменная := выражение_1  to  выражение_2  do   оператор

Выполнение оператора повторяется для каждого значения целочисленной переменной при ее увеличении с шагом 1 от выражение_1 до выражение_2, включительно  (причем выражение_2 вычисляется один раз перед началом цикла). Параметр цикла может быть и символьного типа.  Его значением будут символы, коды которых изменяются на 1.

Например, цикл (где n – целая переменная)

for n := 2 to 10 do  write(‘ ‘, n-1)

выведет числа: 1 2 3 4 5 6 7 8 9.

Если вместо to (до) написано downto (вниз до), то параметр цикла убывает на 1. Например, фрагмент программы

var  sim: char;

        …

for sim := ‘D’ downto ‘A’ do  write(‘ ‘, sim)

выведет через пробел символы от ‘D’  до ‘A”   в порядке уменьшения их кодов:  D C B A.

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

Пример 8.2. Среднее значение и дисперсия. Задано количество чисел N, за которым следуют N вещественных чисел X1, X2, …, XN. Требуется составить программу, вычисляющую среднее арифметическое значение Xsr заданных чисел и их дисперсию (разброс) D - среднее арифметическое значение квадратов  отклонений чисел от Xsr:               n

                                              Xsr = (  Xi ) / n                                            (8.1)

                                                                 i =1

                                                             n

                                            D = (  (Xi  - Xsr)2 ) / n                               (8.2)

                                                             i =1

Решение. Для вычисления суммы заданных чисел и Xsr  достаточно иметь переменную X, содержащую очередное (текущее)  входное число. После ввода числа в переменную X и прибавления его к сумме значение этого числа больше не потребуется, и его можно стереть. Так можно по одному вводить  в переменную X и обрабатывать все входные числа.

Для вычисления таким способом D по формуле (8.2) необходимо уже знать Xsr, и поэтому потребовалось бы второй раз просматривать (вводить) последовательность чисел или сохранять их все в памяти.  

Этого можно избежать, если преобразовать формулу (8.2), выполнив возведение в квадрат и разложив ее на три суммы:

          n                               n

D = (  (Xi  - Xsr)2 ) / n = (  (Xi 2 - 2 Xi Xsr + Xsr2 ) / n =

         i =1                             i =1

      n                                   n                                                   n                                            n

= ( Xi 2 - 2 Xsr  Xi  + n Xsr2 ) / n  =  ( Xi 2) / n - 2 Xsr ( Xi) / n + Xsr2  =

     i =1                                 i =1                                 i =1                                  i =1

      n                                                               n

=  ( Xi 2) / n - 2 Xsr 2 + Xsr2   =   ( Xi 2) / n - Xsr 2                                      (8.3)

     i =1                                                             i =1

Для вычисления Xsr и D по формуле (8.3) достаточно   просмотреть    

входные числа один раз, прибавляя каждое число к сумме чисел                                                                                                            

        n                                                                                                          n 

s1 =  Xi,  а квадрат этого числа  –  к сумме квадратов чисел  s2 =  Xi 2.

       i =1                                                                                         i =1        

Тогда  Xsr = s1 / n,     D = s2 / n - Xsr 2.  Эти формулы реализованы в программе 8.2. Поскольку количество повторений цикла обработки чисел известно до начала его выполнения, здесь удобен оператор for.

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

{ Программа 8.2. Среднее значение и дисперсия (разброс).      

Подсчет среднего арифметического значения Xsr заданных чисел и их  дисперсии D - среднего арифметического значения квадратов  отклонений чисел от Xsr.

Метод: подсчет суммы чисел s1  и суммы их квадратов s2.                                        

   srdisp_sd.pas                                      }

var n,i: longint;         { количество чисел и номер числа }

        Xsr, d,                        { среднее значение и дисперсия   }

x,                                 { текущее число                                     }

s1, s2: real;        { суммы чисел и их квадратов     }

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   read(n);

   s1:=0; s2:=0;

   for i:=1 to n do begin

     read (x);

     s1 := s1 + x;

     s2 := s2 + x * x;

   end;

       Xsr = s1 / n;    D = s2 / n – Xsr * Xsr;

   write(’Среднее = ’, Xsr , ‘ Дисперсия = ‘,   D);

   close(output); close(input);

end.

Пример 8.3. Коридор 2*N.  Прямоугольный коридор размером 2 на N  решили застелить прямоугольными плитками размером 1 на 2.  Дана длина коридора N. Составить программу подсчета, каким количеством способов это можно сделать,  если не должно оставаться не застеленной поверхности?  Например, коридор 2 на 3 можно застелить тремя способами, а 2 на 4 - пятью.

Пример входных данных:        Соответствующие выходные данные:

4                                                5

Решение. Обозначим k = F(N) -  искомое количество способов застелить коридор длины N.  Очевидно, что F(1) = 1, и есть один способ застелить коридор нулевой длины –  не   класть    плитки, т. е. F(0) = 1.

Способы застелить коридор длины N можно разделить на две группы, когда крайняя плитка лежит либо поперек коридора, либо вдоль. Если ее положить поперек, то число способов застелить оставшийся коридор длины N-1 равно F(N-1). Если крайнюю плитку положить вдоль, то рядом параллельно придется положить еще плитку, и есть F(N-2) способов застелить остальную часть коридора длины N-2. Таким образом, получаем рекуррентную формулу:

F(0) = 1,   F(1) = 1,  а для N > 1   F(N)  =  F(N-1) + F(N-2)              (8.4)

Рекуррентной называется формула, выражающая значение какой-либо величины через ее предыдущие значения.

Получились так называемые числа Фибоначчи – числовая последовательность:  1, 1, 2, 3, 5, 8, …, в которой каждое число, начиная с третьего, равно сумме двух предыдущих чисел. Числа Фибоначчи встречаются в очень многих задачах.

Для вычисления очередного числа k = F(N) достаточно знать два предыдущих значения k1 = F(N - 2) и  k2 = F(N-1). Решение задачи дано в следующем фрагменте программы.

var n, k, k1, k2: longint;

       i: integer;                  

 . . .

read (n);

if n < 2 then k := 1

else begin

     k1 := 1;   k2 := 1;

     for i:=2 to n do begin

         k := k1 + k2;

         k1:=k2;   k2:= k;

     end;

end;

write (k)

Недостаток этого решения в том, что «крайние» значения F(N) при N=0  и N=1 вычисляются не так, как все остальные: у них  нет предшественников, и для них пришлось писать отдельную ветку программы.

Здесь проявляется один из общих законов природы – «краевой эффект» - возникновение аномальных (и чаще неприятных) явлений на границах разных областей: вулканы и землетрясения на границах плит земной коры, искривление поверхности жидкости у стенок сосуда, ухудшение дорог на границах административных районов и т. п. Краевой эффект может появляться в самых разных ситуациях.  Как поется в песне: «На границе тучи ходят хмуро…».

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

В данном случае от краевого эффекта можно избавиться следующим приемом, назовем его «кайма». Создадим около начальных  значений N полосу - «кайму»,  отодвинув границу N от начального значения  N=0 так, чтобы оно не было крайним, а имело два предыдущих значения. Для этого продолжим последовательность  F(N): F(0)=1, F(1)=1, F(2)=2, …  на два числа в сторону меньших  N по формуле  F(N)  =  F(N -1) + F(N-2):     F(-2) = 1,   F(-1) = 0.

 Теперь для всех допустимых N, начиная с N=0,  можно вычислять F(N)  по общей формуле F(N)  =  F(N -1) + F(N-2),  и программа 8.3 станет проще:

{        Программа 8.3.  Коридор 2*N.            

  Число F(N) способов застелить коридор 2*N плитками 1*2.

Метод: рекуррентная формула F(N)=F(N-1)+F(N-2), F(-2)=1, F(-1)=0.  }

var n, k, k1, k2: longint;

       i: integer;                  

begin        …

read (n);

k1 := 1;   k2 := 0;

for i:=0 to n do begin

   k := k1 + k2;

   k1:=k2;   k2:= k;

end;

write (k)

end.

Вопрос. Для какого максимального N  пригодна программа 8.3?

8.4. Ввод данных до конца файла

В некоторых случаях требуется вводить и обрабатывать исходные данные до конца входного файла. Чтобы узнать, можно ли еще читать символы из файла, используют стандартную логическую функцию eof (сокращение от End Of File – конец файла):      eof (файловая переменная)

Она возвращает значение true, если достигнут конец соответствующего файла - прочитан последний символ, и false в противном случае. Файловую переменную (вместе со скобками) можно не указывать, тогда подразумевается стандартный входной поток input. Эта функция удобна при вводе символов.

Другая стандартная  функция seekeof (seek eof  – искать конец файла):

seekeof (файловая переменная)

отличается от eof тем, что в поиске конца файла пропускает пробелы и табуляции. Она удобна при вводе чисел.

Чтение и обработку символов до конца файла (потока  input) можно организовать так:

var sim: char;                {  Текущий символ файла }

        …

while not eof do begin

     read (sim);

     Обработка sim;

end

Ввод и обработка чисел отличается только функцией проверки:

var X: integer;                {  Текущее число (любого типа) }

        …

while not seekeof do begin

     read (X);

     Обработка X;

end

Во многих случаях для отладки программы удобно устроить цикл до конца файла для обработки за один запуск  нескольких тестовых наборов входных данных. Шаблон подобной программы может выглядеть так:

begin

    assign (input,'input.txt');     reset(input);

    assign (output,'output.txt'); rewrite(output);

    while not seekeof  do begin             {  или  not eof  для символов   }

       {   Однократное решение задачи    }

        read ( … );

            …

        write ( … );

    end;

    close(output); close(input);

end.

Пример 8.4. Программа с обработкой нескольких тестов.  В программе 8.4 приведена другая версия программы 8.1 для задачи «Фальшивая монета». Эта версия за один запуск обрабатывает несколько тестов – вариантов исходных данных (до конца файла). Результат каждого теста выводится с новой строки оператором  writeln.

В комментариях после программы приведены тесты для ее проверки на олимпиаде с указанием баллов за каждый тест.

Эта программа содержит вложенный цикл: фрагмент однократного решения задачи находится внутри цикла обработки  нескольких вариантов исходных данных до конца файла. Одно выполнение внешнего цикла - однократное решение задачи,  включает несколько повторений вложенного цикла – возведение числа 3 в степень v повторением умножений.

{  Программа 8.4.   Задача M. Фальшивая монета

  Найти минимальное число взвешиваний, достаточное         для поиска одной легкой монеты из N данных  

(1≤ N≤ 2000 000 000).      

 Метод: возведение 3 в степень v до >= n.         }                                        

var n, v, s3: comp;          {longint не достаточен }

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   while not seekeof do begin { Тесты до конца файла}

 {   Однократное решение задачи    }

     read (n);

     v := 0; s3 := 1;

     while s3 < n do begin     { s3 = 3 в степени v }

        s3 := 3*s3;                

        v := v + 1;

     end;

     writeln(v);

   end;

       close(output); close(input);

end.

{  Тесты для задачи М. Монета (1 фальшивая, легче)

   input.txt    output.txt    Баллы

  Кол.монет  Кол.взвешиваний (15 + 5)

         N         V

1)          1   0             2

2)          3   1             2

3)         81   4             2

4)         82   5             2

5)      19683   9             2

6)      19684  10             2

7) 1000000000  19             3      

8) 2000000000  20 (3^20>3E9)! 5 longint не пройдет! }

Пример 8.5. Число слов в тексте. Входной текст продолжается до конца файла и состоит из слов, разделенных любым количеством пробелов. Требуется составить программу подсчета количества слов в тексте.

Пример входных данных:        Выходные данные для этого примера:

15   декабря  2007 г.                        4

Решение. Начало слова отличается от других мест текста тем, что первый символ слова не является пробелом, а перед ним расположен пробел. Количество таких ситуаций равно числу слов. Для их подсчета необходимо проверять два соседних символа: текущий символ, назовем его sim, и предыдущий символ simpr. Перед вводом символа запоминается предыдущий символ.

Первое слово не будет подсчитано, если перед ним не окажется пробела. Чтобы избавиться от этого краевого эффекта, в программе 8.5 переменной simpr в качестве начального значения присвоен пробел, и таким образом он как бы  «вставляется»  в начало текста.

  Аналогичным образом можно было бы увеличивать счетчик слов в конце слова, но тогда может возникнуть краевой эффект, если за последним словом не будет пробела.

{  Программа 8.5. Задача «Число слов в тексте»

Метод: запоминание и проверка двух соседних символов.}                                        

var sim, simpr: char;    { Текущий и предыдущий символ }

    k: integer;                    { количество слов             }

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   k:=0; simpr:= ' ';

   while not eof do begin { Чтение до конца файла}

     read (sim);

     if (simpr = ' ') and (sim <> ' ') then k := k + 1

     simpr := sim;

   end;

   write(k);

       close(output); close(input);

end.

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

Примеры входных данных:        Выходные данные для этих примеров:

(()(()))                                YES

)()(                                        NO

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

Обозначим результат работы значением логической переменной verno (true – «расстановка правильная»,  false – «расстановка неправильная»).  Для вывода слова NO достаточно одного нарушения правила. Поэтому начальным значением этой переменной сделаем true, а если найдем нарушение, то присвоим ей значение false, и это значение больше изменяться не должно. Программа 8.6 читает входной текст по одному символу, пока не кончится файл.

Эта программа решает более общую задачу, чем задана в условии. Она может проверить  правильность расстановки скобок даже тогда, когда текст,  представляет собой выражение и содержит другие символы кроме  скобок.  Программа интересуется только скобками, а  другие символы  пропускает.

{  Программа 8.6. Задача «Правильность скобок»

Проверка правильности расстановки скобок входного текста.      

 Метод: глубина вложения скобок >= 0, в конце 0. }                                        

var sim: char;          { Текущий символ         }

    g: integer;                   { Глубина скобок         }

    verno: boolean;     { Расстановка правильная }

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   g:=0; verno:=true;

   while not eof do begin { Чтение до конца файла}

     read (sim);

     if sim = '(' then g := g + 1

     else if sim = ')' then g := g - 1;

     if g < 0 then verno:=false;

   end;

   if verno and (g = 0) then write('YES')

   else write('NO');

       close(output); close(input);

end.

Задачи

Во всех задачах требуется составить программу, которая вводит данные из файла input.txt, а результат выводит в файл output.txt.

8.1. Сумма цифр. Найти сумму цифр заданного целого числа, не превышающего 2000 000 000.

Пример входных данных            Выходные данные для этого примера:

1946                                        20

8.2. Наибольшее число. Задано количество чисел N, за которым следуют N вещественных чисел X1, X2, …, XN. Найти наибольшее число.

Пример входных данных            Выходные данные для этого примера:

6  3.5  5  -2  1  -3  0                5

8.3. Количество максимальных чисел. Задано количество чисел N, за которым следует последовательность из  N целых чисел X1, X2, …, XN. Определить, сколько раз в последовательности встречается максимальное  число.

Пример входных данных            Выходные данные для этого примера:

7   3  1  5  -2  4  5  0                2

8.4. Два наибольших числа. Задано количество чисел N, за которым следует последовательность из  N целых чисел X1, X2, …, XN. Найти два наибольших  числа в последовательности: максимальное и наибольшее из остальных.

Пример входных данных            Выходные данные для этого примера:

7   3  1  5  -2  4  5  0                5 5

8.5.  Даны три целых числа A, B и C (A ≤ B  ≤ 2000 000 000).  Подсчитать количество чисел от A  до B, включая границы, сумма цифр которых равна C.

Пример входных данных            Выходные данные для этого примера:

25  70   7                                6

8.6.  Наибольший общий делитель. Даны два натуральных числа. Найти их наибольший общий делитель.

Пример входных данных            Выходные данные для этого примера:

24  60                                        12

а) Числа не превышают 30000.

б) Числа не превышают 1000 000 000.

8.7.  Слова. Входной текст продолжается до конца файла и состоит из слов, разделенных произвольным числом пробелов.

а)  Подсчитать количество слов, заканчивающихся буквой ‘а ‘.

Пример входных данных            Выходные данные для этого примера:

Папа мама и я                        2

б)  Подсчитать количество слов, начинающихся и заканчивающихся одинаковым символом.

Пример входных данных            Выходные данные для этого примера:

2002 год боб                        2

в)  Подсчитать максимальную длину слова.

Пример входных данных            Выходные данные для этого примера:

To be or not to be                        3

г)  Подсчитать количество слов, имеющих длину больше трех, но меньше семи символов.

Пример входных данных            Выходные данные для этого примера:

Что имеем не ценим                2

9. МАССИВЫ

9.1. Описание массива

Массив -  это конечная последовательность пронумерованных элементов одинакового типа  - базового типа. Например, массив X из четырех целых чисел может иметь значение: (9, 6, 1, 7). Номер элемента называется его индексом (индекс – указательный палец по-латински).

Элемент массива может иметь несколько индексов. Количество индексов (одинаковое для всех элементов массива) называется  размерностью массива.

Размерность массива – число его измерений – не следует путать с размером массива, который определяется количеством его элементов или объемом занимаемой памяти.

Одномерный массив (массив с одним индексом) часто называют вектором. Двумерный массив (с двумя индексами) можно рассматривать как матрицу – прямоугольную таблицу элементов, в которой первый индексом является номер строки, а вторым - номер столбца.

Элементы массива обозначаются одинаковым именем и отличаются индексами. Элемент массива записывается как  имя массива, за которым в квадратных скобках указываются индексы элемента. Можно каждый индекс записывать в отдельных скобках, но обычно все индексы заключаются в общие скобки и разделяются запятыми. Индекс может задаваться в виде выражения.

Элемент массива является переменной или константой, тип которой указан в описании массива. C ним можно обращаться, как с любой переменной или константой: присваивать значение, вводить, выводить, использовать в качестве операнда в выражении и т. д. Массив удобен для выполнения одинаковых действий над несколькими величинами.

Тип массива описывается следующим образом (array – массив, of - из):

array [тип индекса] of базовый тип

Тип индекса чаще всего задают, указывая  интервал - начальное и конечное целое или символьное значение через две точки «..». Например,  описания:

const  kv:  array [0 .. 5] of integer = (0, 1, 4, 9, 16, 25);

var v: array [-10 .. 10] of real;

          t: array [0 .. 5] of char;

 m: array [1 ..10, 1 .. 20] of integer;

 k:  array [‘A’ ..’D’] of integer;

создают в программе следующие массивы.

- постоянный массив (массив констант) kv с индексами от 0 до 5 через 1 и заданными значениями элементов типа integer:  kv[0] = 0, kv[1] = 1, kv[2] = 4, kv[3] = 9, kv[4] = 16, kv[5] = 25.  

- вещественный массив - вектор v: v[-10], v[-9], ... v[10] – 21 вещественная переменная типа real;

- символьный вектор t:      t[0], t[1], ... t[5]     -     6  символьных переменных типа char;   t   можно также рассматривать как текст из 6 символов.

- целочисленную матрицу m из 10 строк и 20 столбцов, всего 10*20 = 400 элементов. Элементы матрицы - целочисленные переменные типа integer, записываются с двумя индексами: номер строки и номер столбца, и размещаются в памяти по строкам (строка за строкой) в следующем порядке:

m[1, 1],    m[1, 2],  ... , m[1, 20],

m[2, 1],    m[2, 2],  ... , m[2, 20],

. . .

m[10, 1], m[10, 2], ... , m[10, 20];

- целочисленный вектор k, состоящий  из переменных типа integer с символьными индексами – кодами символов от ‘A’ до ’D’ через 1: k[‘A’],  k[‘B’],  k[‘C’],  k[‘D’].

Основное свойство массива состоит в том, что все его элементы одновременно присутствуют в оперативной памяти, одинаково доступны и могут обрабатываться в любом порядке.

9.2. Строки символов

Строка символов (или просто строка) – данные типа string (строка, цепочка) - это конечная последовательность от 0 до 255 символов, разновидность символьного массива в языке Pascal.

Строковая константа записывается как последовательность символов, заключенная в апострофы – одинарные кавычки, например: ‘КАИ’, ‘В здоровом теле здоровый дух!‘, ‘’ – пустая строка (0 символов), ‘Об’’явление’ – слово Об’явление – внутренняя кавычка удваивается, чтобы отличить ее от закрывающей кавычки.  

Переменная строка описывается в виде

var имя: string;          или         var имя: string(максимальная длина);

Строка может содержать  от 0 до заданного максимального числа символов. Если максимальная длина не указана, она считается равной 255.

Например, описания:

const   D:   array [1 .. 4] of string = (‘север’, ‘юг’, ‘запад’, ‘восток’);

var   T: string;  

         name: string(10);

создают в программе следующие величины:

- массив констант D с индексами от 1 до 4 через 1 из элементов типа string – строка символов, значения которых заданы строковыми константами:  D[1] = ‘север’, D[2] = ‘юг’, D[3] = ‘запад’, D[4] = ‘восток’. Эти значения можно выводить, присваивать переменным типа  string, сравнивать и т. п.

- строковую переменную T, содержащую до 255 символов;

- строковую переменную name длиной до 10 символов.

Со строковой переменной можно обращаться как с символьным массивом типа  array [0 .. максимальная длина] of char.  Нулевой байт этого массива содержит фактическую длину строки, которая может изменяться.

Например, после присваивания T := ‘КАИ’   значение  T[1] равно  ‘К’, T[2] = ‘А’, T[3] = ‘И’. Значение T[4] не определено. Байт T[0] содержит число 3 – длину строки, но относится к типу char. Поэтому  эту длину необходимо записывать как ord(T[0]), чтобы преобразовать в целое число.

Пример 9.1. День недели. Даны три числа D,  M, G, разделенные  пробелами и обозначающие дату: день, месяц и год (1D31,  1M12, 1G3000). Составить программу, которая определяет день недели этой даты (по новому стилю),  учитывая, что   1 января 1 года н. э. был понедельник.

Указание. Високосными считаются те годы,  которые делятся на 400, и те, которые делятся на 4, но не делятся на 100.

Пример входных данных:        Выходные данные для этого примера:

1  1  2001                                понедельник

Решение. Названия дней недели удобно хранить в массиве строковых констант типа string: dn[nd] – название дня недели с номером nd (от 0 до 6). Номер nd является остатком от деления на 7 количества  дней от некоторого понедельника до даты «d m g». Началом отсчета удобно считать дату «1 1 1».

Число дней между датами «1  1  1» и «d  m  g» слагается из трех частей.

а) Между датами «1 1 1» и «1 1 g» прошло g -1 лет по 365 дней. Каждый високосный год добавляет по 1 дню. Таких лет, включая g, было: g div 400 кратных 400, плюс g div 4  кратных 4, за минусом g div 100 кратных 100, итого:

365*(g-1) + g div 4  - g div 100 +  g div 400.

Поскольку год содержит 365 = 52*7 + 1 дней, т. е. 52 недели и 1 день,  за год день недели сдвигается на 1, и умножение на 365 можно убрать.

б) Количество дней между датами «1 1 g» и «1 m g», зависящее от m,  обозначим d1m[m]. Таблицу значений этой функции для обычного года и m от 1 до 12 удобно хранить в виде постоянного массива d1m.

в) Между датами «1 m g» и «d m g» прошло d – 1 дней.

Итак, количество дней между датами «1 1 1» и «d m g» равно:

   nd = 365*(g -1) + g div 4  - g div 100 +  g div 400 + d1m[m] + d – 1

В этой формуле уже учтен сдвиг на 1 день, когда год g – високосный, но этот сдвиг начинается только с 1 марта. Поэтому значение nd необходимо уменьшить на 1, когда   g  –  високосный год и m < 3. Отсюда – программа 9.1.

{   Программа  9.1. День недели   Д. Г. Хохлов                   }

const  dn: array [0..6] of string=('понедельник', 'вторник',

      'среда', 'четверг', 'пятница', 'суббота', 'воскресенье');

    d1m: array [1..12] of longint=(0,31,59,90,120,151,181,212,

          243,273,304,334);      { dm[m]=кол. дней от 1.1 до 1.m }

var d,m,g,nd: longint;

begin

   assign (input, 'input.txt');  reset(input);

   assign (output,'output.txt'); rewrite(output);

   while not seekeof do begin       { Однократное решение задачи }

      read(d,m,g);

      nd:={365*}(g-1)+ g div 400+ g div 4- g div 100 + d1m[m]+d-1;

      if (m<3) and ((g mod 400=0) or (g mod 4=0)and(g mod 100 >0))

      then nd:=nd-1;

      writeln (dn[nd mod 7]);

   end;

   close(output); close(input);

end.

{     Тесты задачи «День недели» (15 баллов)

   День Месяц  Год       Ответ        Баллы

    6     3   2000     понедельник      2

   29     2   2000     вторник          2

    3     1   2001     среда            2

   29     2   2024     четверг          2

    2     6   2800     пятница          2

    6     3   2900     суббота          2

   28    12   3000     воскресенье      3

}

Пример 9.2. Программа 9.2. Перестановка символов текста t в обратном порядке:

var  i, j; integer;

t: array [1 .. 100] of char;

s: char;

. . .

for i:=1 to  50 do begin 

     s:=t[i];  t[i]:=t[101-i];  t[101-i] := s      { Обмен t[i]  <-->  t[101-i]   }

end   

Цикл повторяется 50 раз с изменением i от 1 до 50, а 101-i  от 100 до 51.

Если в условии задачи фигурируют переменные с индексами, для них не всегда требуется использовать массив. Массив нужен для входных или выходных данных, если их элементы обрабатываются неоднократно или не в том порядке, в котором вводятся или выводятся. В этих случаях приходится одновременно хранить в памяти все элементы в виде массива.

Если же элементы обрабатываются по одному разу в порядке их ввода или вывода, возможна их последовательная обработка и массив не требуется: достаточно хранить в оперативной памяти один текущий элемент (см. пример 8.2).

Использование массива в таком случае не только усложняет программу и замедляет ее работу, но и без необходимости ограничивает ее возможности,  т. к. объем данных в этом случае не сможет превосходить размер массива.

В последующих разделах приведены примеры решения задач с одномерными массивами.

9.3. Одномерные   массивы

Пример 9.3. Частота символов. Входной текст продолжается до конца файла. Подсчитать число повторений (частоту) каждого символа текста с кодом более 32 (имеющего изображение).

Пример входных данных:            Выходные данные для этого примера:

9/10/2007                                 Символ  Частота

                                        /                2

0                3

                                1                1

2                1

                                7                1

                                9                1

Решение. Организуем массив счетчиков, содержащий 256 – 33 = 223 счетчика символов по числу их возможных кодов 256, кроме 33 символов с кодами от 0 до 32. Удобно чтобы номер счетчика совпадал с кодом подсчитываемого  символа: от 33 до 255. Получается простая программа 9.3.

{   Программа  9.3. Частота символов                     }

var sim: char;                    { Текущий символ    }

   k: array [33..255] of integer; { счетчики символов }

   i: integer;

begin

   assign(input, 'input.txt');   reset(input);

   assign(output, 'output.txt'); rewrite(output);

   for i := 33 to 255 do k[i]:=0;

   while not eof do begin { Чтение до конца файла}

     read (sim);

     if ord(sim)>32 then k[ord(sim)]:=k[ord(sim)]+1

   end;

   writeln(’Символ  Частота’);

   for i := 33 to 255 do

      if k[i] > 0 then

         writeln(chr(i), ’      ’, k[i]);

       close(output); close(input);

end.

9.4. Разработка сверху вниз

Пример 9.4. Сортировка массива. Дано количество чисел n и вещественные числа X1, X2, ..., Xn (n ≤ 1000). Составить программу вывода заданных вещественных чисел в порядке возрастания.  

Пример входных данных:        Выходные данные для этого примера:

5     9   6   7   2   3                      Упорядоченные числа: 2.0   3.0   6.0   7.0   9.0

Решение. При разработке сложного алгоритма (программы) рекомендуется  поступать как при написании сочинения: сначала составляют план – разбивают его на части, а потом уже уточняют детали – пишут планы и тексты этих частей. Такой метод называется «разработка сверху вниз» – от целого к частям. Разработаем данную программу методом сверху вниз.

Программа состоит из обрабатываемых данных и алгоритма:

Программа = Данные + Алгоритм

На каждом шаге разработки сначала детализируются данные, а потом уже уточняется алгоритм –  операции над ними. Для записи программы при этом удобно использовать псевдокод – неформальный вариант языка программирования в сочетании с любыми удобными обозначениями, которые затем по мере детализации постепенно переводят на язык программирования. Там, где нетрудно, соблюдаем правила языка Pascal, а где затруднительно, пишем, как нам удобнее.

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

Запишем на псевдокоде этот «план» программы из трех шагов вместе с описанием данных. Операции пока напишем  на естественном (русском) языке:

const NMAX = 1000;                      { Максимальное количество чисел }

var n: integer;                                       {  Количество входных чисел   }

  x:  array [1 .. NMAX] of real;       {  Обрабатываемый массив      }

1. Ввод массива x;

2. Сортировка массива x по возрастанию;

3. Вывод массива x;

Применение символической константы NMAX облегчает при необходимости изменение размера массива.

Детализируем  шаги алгоритма, разделяя их, если потребуется, горизонтальной чертой и добавляя описание необходимых переменных. Это можно делать в любом удобном порядке. Неформальную запись  операции используем как заголовок – комментарий перед более детальным вариантом.  

Начнем, например, с ввода. Сначала вводится количество чисел n, а затем n раз повторяется  ввод элемента массива x[j]  с изменением j от 1 до n.

{ 1. Ввод массива x    }

j: integer;

   . . .

Ввод n;

for j := 1 to  n do

Ввод x[j];

Аналогично выглядит вывод массива, перед которым добавим вывод заголовка.

{ 3. Вывод массива x     }

Вывод заголовка "Упорядоченные числа:";

for j := 1 to  n do

Вывод x[j];

Теперь детализируем шаг сортировки. Существуют десятки  методов  сортировки. Одним из простейших  методов сортировки является  метод  выбора наименьшего элемента.

Определяется индекс (номер) наименьшего числа – минимального элемента массива. Затем  этот элемент меняется местами с первым элементом массива и оказывается на своем месте, где он должен быть после сортировки.

Этот шаг повторяется с остальной частью массива, начиная  со второго элемента, пока  остаток массива не уменьшится до одного элемента.

Для приведенного в задаче примера расположение чисел в массиве после каждого шага показано на рис. 9.1.  

9   6   7   2   3

2   6   7   9   3

2   3   7   9   6

2   3   6   9   7

2   3   6   7   9

Рис. 9.1. Трассировочная таблица сортировки выбором

(подчеркнута область поиска минимального элемента)

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

n + (n-1) + (n-2) + (n-3) + … + 2 =  (n+2)*(n-1)/2  n2 /2.

Таким образом, сортировка выбором имеет, как говорят,  квадратичную временную сложность: время сортировки приблизительно пропорционально n2 - квадрату длины сортируемого массива. При удлинении массива, например,  в 10 раз время сортировки увеличится приблизительно в 100 раз.

Другие простые методы также имеют квадратичное время сортировки. Более быстрые (и более сложные!) методы выполняют сортировку за время, пропорциональное n * log n. Величина log n пропорциональна количеству цифр в числе. Например,  при n = 1000 отношение log n  /  n будет порядка  3 / 1000.

Иногда возможна сортировка подсчетом количества значений за время порядка n (задача 9.2).

Описанный метод представлен в алгоритме шага 2. Сортировка состоит из повторяющихся шагов – просмотров массива. Начальный индекс просмотра, назовем его k, изменяется от 1 до n-1:

{  2. Сортировка массива x по возрастанию методом выбора  }

var  k: integer;                        { Начальный индекс просмотра   }

   . . .

for k :=1 to  n-1 do

Просмотр элементов x[k], ... , x[n];

Просмотр включает определение индекса jmin минимального элемента и обмен этого элемента с начальным элементом просмотра. Начальным значением jmin будет индекс начала просмотра.

{        Просмотр элементов x[k], ... , x[n]        }

var  j, jmin: integer;         { Индекс текущего и минимального элемента }

       w: real;                       { для обмена                                                         }

          . . .

    jmin := k;

for j := k+1 to n do 

   if x[j] < x[jmin] then jmin := j;

w:=x[k];   x[k]:=x[jmin];  x[jmin] :=w;           {  Обмен  x[k]  x[jmin];  }

Разработанный алгоритм реализован в программе 9.4.

{  Программа 9.4. Сортировка чисел по возрастанию выбором }

const NMAX = 1000;              { Максимальное количество чисел }

var n: integer;              {  Количество входных чисел     }

   x: array [1 .. NMAX] of real; { Обрабатываемый массив}

k: integer;           { Начальный индекс просмотра     }

   j, jmin: integer;    { Индекс текущего и миним-го эл-та}

   w: real;              { для обмена                     }

begin

   assign (input, 'input.txt');  reset(input);

   assign (output,'output.txt'); rewrite(output);

   { 1. Ввод массива x    }

   read (n);

   for j := 1 to  n do

read (x[j]);

{  2. Сортировка массива x по возрастанию методом выбора      }

for k :=1 to  n-1 do begin

 { Просмотр элементов x[k], ... , x[n]                      }

   jmin := k;

 for j := k+1 to n do 

    if x[j] < x[jmin] then jmin := j;

 w:=x[k]; x[k]:=x[jmin]; x[jmin]:=w; { Обмен x[k] и x[jmin];}

  end;

  { 3. Вывод массива x                 }

  write (‘Упорядоченные числа’);

  for j := 1 to  n do

     write (‘ ‘, x[j]);

  close (input);  close (output);

end.

Задачи

9.1. Сортировка 0, 1, 2. Дано количество чисел N (0 < N ≤ 10000) и последовательность из N чисел,  каждый элемент которой равен 0, 1 или 2. Переставить элементы последовательности так,  чтобы сначала располагались все нули, затем все единицы и,  наконец,  все двойки.

Пример входных данных:            Выходные данные для этого примера:

6 1 0 1 1 2 0                                0 0 1 1 1 2

9.2. Сортировка подсчетом значений. Дано количество чисел  N (0 < N ≤ 10000) и N целых чисел из  диапазона от 1 до 30000. Вывести эти числа в порядке неубывания.

Пример входных данных:            Выходные данные для этого примера:

6  7 8 172 611 172 54                7 8 54  172  172  611

Указание. По аналогии с программой 9.3, в сортируемом массиве подсчитывается количество экземпляров каждого возможного значения (а можно обойтись и без массива – читать из файла!). Необходим массив счетчиков, количество которых равно количеству возможных значений. Для входного числа x[i] увеличивается на 1 счетчик с индексом x[i].  В сортируемый массив (или выходной файл) записываются в требуемом порядке нужные значения в подсчитанных количествах. Время сортировки порядка N.

9.3. Палиндром. Входной текст - это слово длиной до 255 символов. Проверить, является ли это слово палиндромом (перевертышем), т. е симметричным и поэтому не изменяемым при перестановке  символов в обратном порядке.

Примеры входных данных            Выходные данные для этих примеров:

наган                                          YES

ванна                                 NO

9.4. Равенство слов. Входной текст содержит два слова, разделенные пробелом. Проверить, одинаковы ли эти слова.

Примеры входных данных:            Выходные данные для этих примеров:

нет нет                                        YES

нет да                                        NO

9.5. Алфавитный порядок. Входной текст содержит два слова из строчных латинских букв, разделенные пробелом. Вывести символ <, когда в алфавитном порядке (в словаре) первое слово расположено раньше второго, символ  >, когда первое слово позже второго, и символ =, когда слова равны.

Примеры входных данных:            Выходные данные для этих примеров:

no yes                                        <

program problem                                >                                

can can                                        =

9.6. Анаграммы. Входной текст содержит два слова, разделенные пробелом. Проверить, являются ли они анаграммами, т. е. можно ли, переставив каким-либо образом символы  первого слова, получить второе слово.

Пример входных данных            Выходные данные для этого примера:

лунка кулан                        YES

ванна аванс                                NO

Подсказка. Можно, если они содержат одинаковые символы в равных количествах, и после сортировки символов, например, по алфавиту (возрастанию кодов), эти слова совпадут.

9.7. Входной текст содержит два слова, разделенные пробелом. Проверить, можно ли из символов  первого слова составить второе слово.

Пример входных данных            Выходные данные для этого примера:

каламбур румба                        YES

1946  611                                   NO            (требуются два символа «1»)

9.8. Самое длинное слово. Входной текст состоит из слов, разделенных любым числом пробелов, и заканчивается точкой. Найти в тексте самое длинное слово (или одно из них).

Пример входных данных            Выходные данные для этого примера:

Скоро новый год.                        Скоро

10. ПОДПРОГРАММЫ

10.1. Описание подпрограмм

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

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

Основная программа управляет работой подчиненных  программ, каждая из которых специализируется на своей части общей задачи и при необходимости вызывает  подчиненные ей программы.

Подпрограмма (подчиненная программа) - это программа, которую можно вызывать для выполнения в разных местах одной или нескольких  программ.

Программа, внутри которой выполняется подпрограмма, по отношению к подпрограмме называется главной, основной или вызывающей программой. В то же время, она сама может быть подпрограммой  по отношению к вызывающей ее программе.

Например, в программе 5.1  (для нахождения площади треугольника) функция  S3(X1, Y1, X2, Y2, X3, Y3), для вычисления которой используется функция S2(X1, Y1, X2, Y2), является главной по отношению  к S2 и подчиненной по отношению к основной программе, в составе которой вычисляется S3.

Для подпрограмм  применяются обозначения, аналогичные   функциям    в математике. Перед использованием функции  необходимо  дать ее определение  (описание), например:    

F(x) = x * x + 2                                       (10.1)

Теперь можно использовать эту функцию, например, для вычисления ее значения  при  x=5:

F(5) = 5 * 5 + 2 = 27                                  (10.2)

Вызов подпрограммы или обращение к подпрограмме (команда «выполнить подпрограмму») записывается аналогично использованию функции (10.2):

P (a1, a2, ... , an)                                      (10.3)

где P - имя подпрограммы (аналогично имени функции F), a1, a2, ... , an - аргументы (параметры) вызова, конкретные величины, подставляемые на место параметров при выполнении подпрограммы, как аргумент 5 вместо  x  в вызове  (10.2). Тип аргумента должен совпадать с типом соответствующего по порядку параметра.

Существуют два вида подпрограмм: функция и процедура.

Функция – это подпрограмма, обладающая значением (как в математике). Вызов функции заменяется ее значением и может служить операндом выражения, но не является самостоятельным оператором.

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

Вызов процедуры выглядит так же, как и вызов функции, но не может использоваться внутри выражения, а записывается как самостоятельный оператор.

 Мы уже познакомились с некоторыми стандартными подпрограммами: функциями, например, abs, sin, trunс и т. п., а также процедурами: read, write, assign и др. Описания стандартных подпрограмм находятся в библиотеке транслятора, и их можно использовать в любых программах.

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

Как уже говорилось в разделе 5, описание функции начинается с заголовка

function имя функции (описание параметров): тип значения;

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

Описание параметров мало отличается от описания обычных переменных. Главное отличие в том, что тип данных в заголовке функции или процедуры должен обозначаться одним словом  - именем типа.

Поэтому, если параметр является массивом, то его тип  требуется предварительно обозначить некоторым именем.

Программист может давать придуманные им имена  любому определению типа, описав эти имена после служебного слова type – тип, следующим образом

type имя типа = определение типа;

Пример описания типов с именами  vector и int:

type vektor = array[1..100] of real;

          int = integer;

После этого описания  переменных     var  v1, v2: vector;   N, a: int;

эквивалентны следующим

var v1, v2: array[1..100] of real;

       N, a: integer;

В программе все описания должны предшествовать их использованию. Описания типа обычно размещаются в программе перед описаниями переменных.

Значение функции должно быть простого типа – одна величина, и не может иметь составной тип – из нескольких величин, как, например, массив.

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

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

Пример. Описание вещественной функции max(X, Y), значением которой является больший из двух вещественных аргументов:

function max (X, Y: real): real;

  var Z:  real;

begin

     if X > Y then Z := X else Z := Y;

     max := Z

end;

Можно написать короче:

function max (X, Y: real): real;

begin

     if X > Y then max := X else max := Y

end;

В вызывающей программе эту функцию можно использовать в любом выражении, например, так:

var A, B, C: real;   …  A := 5 + max (B+C, 3.5)                        (10.4)

Процедура отличается от функции только тем, что не обладает значением. Поэтому в теле процедуры ее имени  не  присваивается значение, а в заголовке процедуры отсутствует тип значения:

procedure имя процедуры (описание параметров);

В том месте программы, где нужно выполнить заданные в процедуре действия, пишут ее  вызов в виде оператора процедуры:

имя (аргументы)

Параметры подпрограммы играют роль «почтового ящика» для обмена данными с вызывающей программой.  Параметр-переменная, перед которым в заголовке подпрограммы ставят слово var, является выходным параметром – результатом работы  подпрограммы, и его значение передается в вызывающую программу – присваивается  соответствующему аргументу, которым должна быть переменная  вызывающей программы.  

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

 Можно описать процедуру pmax, которая присваивает Z большее из двух значений X, Y:

procedure pmax (X, Y: real; var Z: real);  

begin

     if X > Y then Z := X else Z := Y

end;

Тогда вместо (10.4) придется писать сложнее, например, так:

 var A, B, C: real;   …  pmax (B+C, 3.5, A);   A := 5 + A

10.2. Примеры подпрограмм

Пример 10.1.  Составить подпрограмму ввода целого числа, перед которым возможны пробелы, символы "новой строки" (с кодом 13) и знак (подобным образом вводит число стандартная процедура read).

{ Программа 10.1         Ввод целого числа  znach            }

procedure vvod_chisla (var  znach: integer);

    var sim: char;  

         znak: integer;

begin

znach := 0;  znak := 1;

{        Пропуск пробелов и "новых строк" до числа        }

repeat read(sim) until (sim <> ' ') and (sim <> #13);

{        Чтение знака        }

if (sim = '-' ) or (sim = '+') then begin

     if sim = '-'  then znak := -1;

     read (sim);

end;

{        Чтение цифр        }

while (sim>='0') and (sim<='9') do begin

      znach := 10 *znach + ord(sim) – ord('0');

 read (sim);

end;

znach := znach * znak;

end;

Пример 10.2. Контрольная работа (задача Саратовской олимпиады). Ученик выполнил контрольную работу из 5 задач  по переводу чисел из двоичной системы счисления в восьмеричную. Двоичные числа содержат не более 31 значащей цифры, восьмеричные - не более 11 значащих цифр.

Требуется составить программу, формирующую слово без пробелов из пяти символов “+” (верно) или “-“ (неверно) в зависимости от  того,  верно  или нет  переведено  соответствующее  число,  и  выставляющую оценку 5, если верно решены 5 задач,  оценку 4  за 4 задачи,  3 за 3 задачи и 2 в остальных случаях.

     Входной файл содержит результаты контрольной, записанные без пробелов в виде пяти строк. Каждая строка имеет вид:

двоичное число=восьмеричное число

     Выходной файл содержит две строки:

слово

оценка

Пример файла input.txt:             Файл output.txt для этого примера:

1101=15                                     +-+++

10=3                                           4

10=2

1100=14

1000=10

{  Программа 10.2. Контрольная работа             

  Проверка контрольной работы по переводу чисел

  из двоичной системы в восьмеричную.

    Метод: ввод числа                        }

var c: char;

    ocenka, x2, x8, i: longint;

function chislo (b: integer): longint;

  var z: longint;

begin

  repeat read(c) until (c>='0') and (c<='9');

  z:=0;

  while (c>='0') and (c<='9') do begin

    z := b * z + ord(c) - ord('0');

    read(c);

  end;

  chislo := z;

end;

begin

  assign(input, 'input.txt');   reset  (input);

  assign(output,'output.txt'); rewrite(output);

  while not SeekEof  do begin

    ocenka:=0;

    for i := 1 to 5 do begin

      {  Ввод       }

      x2 := chislo(2);  x8 := chislo(8);

      {  Обработка  }

      if x2=x8 then begin

         inc(ocenka); write('Y');

      end else        write('N');

    end;

    if ocenka < 2 then  ocenka:=2;

    {  Вывод      }

    writeln; writeln(ocenka);

  end;

  close(input); close(output);

end.

{         Тесты задачи K. Контрольная (20 баллов)

                         Баллы                          Баллы

   Вход:           Выход:(20)       Вход:        Выход: (20)

1) 1101=15         YYNYY  4      2) 0=0          YYYNN   4

   10=2            4                101=5        3

   10=3                             110=6

   1100=14                          1001=10

   1000=10                          10=1                   }

Применение подпрограмм позволяет:

а) избегать дублирования одинаковых частей программы, оформляя их в виде подпрограмм;

б)  сделать структуру программы более четкой и понятной, разбивая ее таким образом на части (модули) – идея  модульного программирования;

в) расширять язык программирования, добавляя в него новые операции в виде функций и операторы в виде процедур;

г) Повторно использовать имеющиеся программы при разработке новых программ.

Разработку многомодульной программы из нескольких подпрограмм удобно вести сверху вниз: от вызывающих программ к вызываемым. При этом сначала составляется основная программа с использованием вызовов пока еще не разработанных подпрограмм, затем - вызываемые из нее подпрограммы, которые могут обращаться к отсутствующим пока подпрограммам более низкого уровня и т. д.

Такой нисходящий подход надо умело сочетать с разработкой снизу вверх: от программ нижнего уровня (не вызывающих другие программы) к использующим их программам более  высокого уровня и т. д. до главной программы.

Задачи

10.1. Составить определения следующих функций.

а) min (x, y).

б) max (a, b, c).

в) min (a, b, c).

г) 1, если заданный символ является латинской буквой, и 0 в противном случае.

д) 0, если нельзя построить треугольник из трех отрезков заданной длины (каждая сторона треугольника должна быть меньше суммы двух других сторон); 1 - треугольник равносторонний, 2 - равнобедренный, 3 - любой другой.

е) Число Фибоначчи f(n), где f(0) = 0,        f(1) = 1, f(j) = f(j-1) + f(j-2) для целого j>1.

ж) Наибольший общий делитель натуральных чисел А и В.

з) Количество десятичных цифр заданного целого числа.

и) Значение числа, полученного выписыванием в обратном порядке десятичных цифр заданного натурального числа.

к) Количество единичных битов в двоичной записи заданного числа типа       word.

л) Ввод и вычисление значения двоичного целого числа.

10.2. Составить подпрограммы для решения следующих задач.

а) Поменять местами значения переменных x, y.

б) Значения переменных x, y, z поменять местами так, чтобы оказалось x   і  y  і  z.

в) Вычислить длину окружности, площадь круга и объем  шара одного и того же заданного радиуса.

г) Вычислить площадь и периметр прямоугольного треугольника по длинам двух катетов.

д) Для  квадрата ABCD на плоскости даны координаты XA, YA, XC, YC диагонально расположенных вершин A и C. Вычислить координаты вершин B и D.

е) Вывод заданного целого числа в двоичной системе счисления.

ж) Вывод заданного целого числа в шестнадцатеричной системе счисления.

з) Определить, сколько раз в строке встречается сочетание символов ":=".

и) Строка содержит выражение со скобками. Определить максимальное число уровней вложенности скобок.

к) Выяснить, имеется ли в заданном строке пара соседних одинаковых символов.

л) Удалить из строки пробелы, сдвинув остальные символы.

10.3. Данная строка символов представляет собой последовательность слов, разделенных произвольным числом пробелов. Составить подпрограммы определения следующих величин:

а) количества слов в строке;

б) количества слов, начинающихся с буквы ‘А’;

в) количества слов, оканчивающихся буквой ‘W’;

г) количества слов, начинающихся и оканчивающихся одной и той же буквой;

д) количества слов, содержащих заданную букву;

е) количества слов, имеющих длину больше трех, но меньше семи символов.

ж) максимальной длины слова.

10.4. Составить подпрограмму ввода действительного числа с возможным знаком

а) с фиксированной точкой, например: -3.14 или 345.782;

б) с плавающей точкой, например: -31.4E-1 или 1e6.

10.5. Составить подпрограмму вывода действительного числа  с воз-можным знаком;

а) с фиксированной точкой, например: -3.14 или 345.782;

б) с плавающей точкой, например: -31.4E-1 или 1e6.

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

Пример входных данных            Выходные данные для этого примера:

лунка кулан                        YES

ванна аванс                                NO

а) Сортировку слова - строки символов, оформить как процедуру. Проще всего использовать сортировку подсчетом частоты символов (см. программу 9.3 и задачу 9.2).

б) Как и в варианте а), подсчитывать частоты символов в процедуре, но не обнулять, а сохранить значения счетчиков частоты для первого слова. При обработке  второго слова  вместо увеличения счетчиков на 1 уменьшать их на 1. Для этого нужно сделать шаг счетчика (1 или -1) параметром процедуры подсчета частоты символов. Тогда все счетчики будут равны нулю после обработки двух слов только в том случае, когда слова являются анаграммами (насколько каждый счетчик увеличится в первом слове, настолько же он уменьшится во втором).  В этом методе можно не переставлять символы в словах и даже не хранить слова в памяти, а  читать их из файла по одному символу.

10.7. Входной текст содержит два слова, разделенные пробелом. Проверить, можно ли из символов  первого слова составить второе слово. Использовать метод из задачи  10.6 б. Ответ будет утвердительным, если в итоге все счетчики будут неотрицательными.

Пример входных данных            Выходные данные для этого примера:

каламбур румба                        YES

1946  611                                   NO            (требуются два символа «1»)

Литература

1. Бондарев  В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. - Харьков: Фолио; Ростов р/Д: Феникс, 1998. - 368 с.

2. Брудно А.Л., Каплан Л.И. Московские олимпиады по программированию. - М.: Наука, 1990. - 208 с.  

Много разнообразных олимпиадных задач «первого поколения» с решениями на языках Pascal, C, BASIC.

3. Вирт Н.  Алгоритмы + структуры данных =  программы.  - М.: Мир, 1985.

4. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.

Классический учебник автора языка Pascal по основным структурам данных и их использованию в алгоритмах.

5. Дагене В.А.,  Григас Г.К.,  Аугутис К.Ф.  100 задач по программированию. - М.: Просвещение, 1993. - 255 с.

Хорошо написанный разбор большого числа простых олимпиадных задач.

6. Долинский М.С. Решение сложных и олимпиадных задач по программированию. Учебное пособие. – СПб.: Питер, 2006. – 366 с.

Методы решения сложных олимпиадных задач на примерах  задач студенческого командного чемпионата мира по программированию и других соревнований.

7. Епанешников А.М., Епанешников В.А. Программирование на языке Turbo Pascal 7.0 .  - М.:  «ДИАЛОГ-МИФИ», 2001. - 367 с.  

8. Кирюхин В.М.,  Лапунов А.В., Окулов С.М. Задачи по информатике.  Международные олимпиады 1989-1996 гг.  - М.:  ABF, 1996. - 272 с.  

Разбор задач с решениями.

9. Кормен Т., Лейзерстон Ч., Ривест Р. Алгоритмы: построение и анализ, Пер. с англ. – М.: МЦНМО, 2000. – 960 с.

Хорошо изданный учебник энциклопедического объема с подробным разбором большого числа разнообразных методов и алгоритмов решения задач.

10. Липский  В.  Комбинаторика  для программистов.  - М.: Мир, 1988. - 213 с.

Один из лучших учебников по дискретной математике – хорошее сочетание краткого изложения большого числа математических методов с их удачным описанием в виде алгоритмов на псевдокоде на базе языка Pascal.

11. Московские олимпиады по информатике / Под ред. Е.В. Андреевой,  В.М. Гуровица и В.А. Матюхина. – М.: МЦНМО, 2006. – 256 с.

Задачи последних лет с разбором методов решения.

12. Окулов С.М. Основы программирования. – М.: ЮНИМЕДИАСТАЙЛ, 2002. – 424 с.

13. Окулов С.М. Программирование в алгоритмах. – М.: БИНОМ. Лаборатория знаний, 2002. – 341 с.

Методы решения олимпиадных задач на языке Pascal. Много оригинальных задач с решениями. Автор - один из наиболее авторитетных в России специалистов в подготовке школьников к олимпиадам по информатике.

14. Скиена С.С.,  Ревилла М.А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям.  Пер. с англ. – М.: КУДИЦ-ОБРАЗ, 2005. – 416 с.  

Типовые методы решения олимпиадных задач с примерами задач студенческого командного чемпионата мира по программированию.

16. Фаронов В.В. Программирование на языке Pascal. Учебное пособие. – СПб.: Питер, 2001.

15. Хохлов Д.Г. Программирование на языке высокого уровня. Часть 1. Основы программирования: Учебник - Казань: КГТУ-КАИ, Кафедра АСОИУ, 2005. - 247 с. Часть 2. Методы программирования: Учебник - Казань: Мастер Лайн, 2006. - 266 с.

Учебник для студентов первого курса по основам техники и технологии программирования (на базе языка C) с описанием основных структур данных и методов алгоритмизации, алгоритмами на псевдокоде и примерами решения разнообразных задач от простых до олимпиадных на языках С и Pascal.

17. Шень  А.  Программирование:  теоремы и задачи. – 2-е изд.,  испр. и доп.- М.: МЦНМО, 2004. – 296 с.

Очень хорошо написанный лаконичный и четкий разбор широкого круга задач, в том числе олимпиадного характера.

18. http://www.olympiads.ru  Сайт всероссийской олимпиады школьников по информатике

19. http://www.acm.ifmo.ru  Сайт полуфинала студенческого командного чемпионата мира по программированию среди студентов и Всероссийской командной олимпиады школьников по информатике

20. http://www.acm.sgu.ru Сайт с автоматической тестирующей системой Саратовского государственного университета.

21. http://online-judge.uva.es Автоматическая тестирующая система университета г. Валадолид (Испания) – наиболее известная в мире, более 1000 задач (на английском языке).

22. http://www.programming-challenges.com  Проверка задач и программы из книги «Скиена С.С.,  Ревилла М.А. Олимпиадные задачи по программированию».

УКАЗАТЕЛЬ АЛГОРИТМОВ И ПРОГРАММ

стр.    

2.1. Площадь прямоугольника – программа                                          17

3.1. Площадь прямоугольника – программа (с файлами)                        27

Квартира (подъезд, этаж, номер на этаже) - алгоритм                                31

Расстояние между двумя точками плоскости- функция                        36

Площадь треугольника  с вершиной в начале координат- функция        37

Площадь треугольника - функция                                                     39

6.1. Монеты 3 и 5 – выплата суммы монетами 3 и 5                                44

Символьный ввод числа                                                                47

7.1. Открытка и конверт  (Войдет ли открытка A*B в конверт C*D)        52

Треугольник и точка (проверка вхождения)                                        53

8.1 Фальшивая монета (минимальное число взвешиваний)                        57

8.2. Среднее значение и дисперсия                                                        60

8.3. Коридор 2*N (число способов укладки)                                        63

8.4 Обработка  нескольких тестов (до конца файла)                                65

8.5. Число слов в тексте                                                                67

8.6. Правильность скобочной структуры                                                68

9.1. День недели                                                                                75

9.2. Переворот текста                                                                        75

9.3. Частота символов                                                                        76

9.4. Сортировка чисел выбором                                                        80

10.1 Ввод целого числа – подпрограмма                                                88

10.2. Контрольная работа (системы счисления)                                        89

О Г Л А В Л Е Н И Е

E

Рис. 5.1. Площадь многоугольника

A

B

C

O

D

A

A - eps

A + eps

eps

eps

X ≈ A

X < A

X > A

Рис. 7.1. Приближенное сравнение чисел

X

f

g

h

e

e

  f

?

 e

Рис. 7.2. Открытка и конверт

d

?

g

h