ББК 73 С 34

Рецензент д-р физ.-мат. наук проф. С.В.Русаков

УДК 519.6

Семакин И.Г., Шестаков А.П.

С 34 Лекции по программированию: Учебное пособие. Изд. 2-е, доп. - Пермь: Изд-во Перм. ун-та, 1998.- 279 с.

ISBN 5-8241-0159-0

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

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

идополнения в прилагаемый задачник.

Вразработке сборника задач принимала участие Н.А.Ситникова.

ББК 73

ПРЕДИСЛОВИЕ

Программирование все в большей степени становится заня­ тием лишь для профессионалов. Объявленный 10 лет назад лозунг “Программирование — вторая грамотность” остался в прошлом. В понятие “компьютерная грамотность” сегодня входит, прежде всего, навык использования многообразных средств информационных техно­ логий. Решая ту или иную информационную задачу, необходимо вы­ брать адекватное программное средство. Это могут быть электронные таблицы, системы управления базами данных, математические пакеты и пр. И только в том случае, если подобные средства не дают воз­ можности решить задачу, следует прибегать к универсальным языкам программирования.

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

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

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

программирования, а в последнее время — объектно-ориентированное и визуальное программирование.

Цель, которую преследуют авторы данной книги, — обучить чи­ тателя основам структурной методики программирования. Для этой цели язык Паскаль — наиболее подходящее средство. Автор Паскаля — швейцарский профессор Никлаус Вирт создавал его именно для этого. Структурная методика остается основой программистской культуры. Не освоив ее, взявшийся изучать программирование не имеет никаких шансов стать профессионалом.

Реализации Паскаля в версиях фирмы Borland для IBM, известных под названием ТУрбо-Паскаль, значительно расширили язык по сра­ внению с виртовским вариантом. Начиная с версии 5.5, Турбо-Паскаль становится также и языком объектного программирования (в данной книге эта тема не затрагивается).

Предлагаемый к}фс ориентирван на “структурное воспитание” про­ граммиста, глубокое (не поверхностное) освоение базовых средств Паскаля. Такая подготовка позволит при необходимости легко перейти к изучению других языков программирования, поскольку в Паскале заложена и четко реализована практически вся идеология языков про­ граммирования высокого уровня.

Необходимой подготовкой к данному курсу является предваритель­ ное изучение алгоритмизации на учебных исполнителях, усвоение основ структурной методики:

—построение алгоритмов из базовых структур;

—освоение метода последовательной детализации.

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

Еще одно качество профессионала — способность воспринимать красоту программы, получать эстетическое удовольствие от хорошо написанной программы. Нередко это чувство помогает интуитивно

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

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

В заключение хочется еще раз подчеркнуть, что это учебник по программированию, а не учебник по Паскалю. Более подробное и формальное изложение Паскаля можно найти в книгах, приведенных в списке литературы. В аналогичной методической последовательно­ сти можно построить курс программирования на базе других струк­ турных языков, например Си, Турбо-Бэйсик. Однако, как уже отме­ чалось, с методической точки зрения Паскаль — наиболее подходящее для этого средство.

1.1. История и классификация языков программирования высокого уровня

Язык программирования — это способ записи программ решения различных задач на ЭВМ в “понятной” для компьютера форме. Про­ цессор компьютера непосредственно понимает язык машинных, команд (ЯМК). Из базового курса информатики на примере учебного ком­ пьютера “Нейман” Вы узнали, что программирование на ЯМК — дело непростое. Программист должен знать числовые коды всех машинных команд, должен сам распределять память под команды программы и данные. На языках машинных команд трудно поддерживать структур­ ную методику программирования.

Появление языков типа Автокод-Ассемблер облегчило участь про­ граммистов. Переменные величины стали изображаться символиче­ скими именами. Числовые коды операций заменились на мнемониче­ ские (словесные) обозначения, которые легче запомнить. Язык про­ граммирования стал понятнее для человека, но при этом удалился от языка машинных команд. Чтобы компьютер мог исполнять про­ граммы на Автокоде, потребовался специальный переводчик — транс­ лятор. Транслятор — это системная программа, переводящая текст программы на Автокоде в текст эквивалентной программы на ЯМК.

Компьютер, оснащенный транслятором с Автокода, понимает Ав­ токод. В этом случае можно говорить о псевдо-ЭВМ (аппаратура + транслятор с Автокода), языком которой является Автокод. Языки типа Автокод-Ассемблер являются машинно-ориентированными, т.е. они настроены на структуру машинных команд конкретного ком­ пьютера. Разные компьютеры с разными типами процессоров имеют разный Ассемблер. Языки программирования высокого уров­ ня (ЯПВУ) являются машиннонезависимыми языками. Одна и та же программа на таком языке может быть выполнена на ЭВМ разных типов, оснащенных соответствующим транслятором. Форма записи программ на ЯПВУ, по сравнению с Автокодом, еще ближе к традици­ онной математической форме, к разговорному языку. Очень скоро Вы увидите, что, например, на языке Паскаль она почти такая же, как на Алгоритмическом языке, введенном А.П. Ершовым в школьную инфор­ матику. ЯПВУ легко изучаются, хорошо поддерживают структурную

методику программирования.

Первыми популярными языками высокого уровня, появившимися в 50-х годах, были Фортран, Кобол (в США) и Алгол (в Европе). Языки Фортран и Алгол были ориентированы на научно-технические рас­ четы математического характера. Кобол — язык для программирова­ ния экономических задач. В Коболе, по сравнению с двумя другими названными языками, слабее развиты математические средства, но зато хорошо развиты средства обработки текстов, организация вы­ вода данных в форме требуемого документа. Для первых ЯПВУ пред­ метная ориентация языков была характерной чертой.

Большое количество языков программирования появилось в 60-70-х годах. А за всю историю ЭВМ их было создано более тысячи. Но распространились, выдержали испытания временем немногие. В 1965 году в Дартмутском университете был разработан язык Бейсик. По замыслу авторов, — это простой язык, легко изучаемый, предназна­ ченный для программирования несложных расчетных задач. Наиболь­ шее распространение Бейсик получил на микроЭВМ и персональных компьютерах. На некоторых моделях бытовых и школьных компьюте­ ров программировать можно только на Бейсике. Однако Бейсик — неструктурный язык, и потому он плохо подходит для обучения ка­ чественному программированию. Справедливости ради следует заме­ тить, что последние версии Бейсика для ПК (например QBasic) стали более структурными и по своим изобразительным возможностям при­ ближаются к таким языкам, как Паскаль.

В эпоху ЭВМ 3-го поколения получил большое распространение язык PL/1 (Programm Language One), разработанный фирмой IBM. Это был первый язык, претендовавший на универсальность, т.е. на возможность решать любые задачи: вычислительные, обработки тек­ стов, накопления и поиска информации. Однако PL/1 оказался сли­ шком сложным языком. Для машин типа IBM 360/370 транслятор с него оказался недостаточно оптимальным, содержал ряд невыявленных ошибок. На ЭВМ класса мини и микро он вообще не получил распространения. Однако линия на универсализацию языков была под­ держана. Старые языки были модернизированы в универсальные ва­ рианты: Алгол-68, Фортран-77.

Значительным событием в истории языков программирования стало создание в 1971 году языка Паскаль. Его автор — швейцарский профессор Н. Вирт разрабатывал Паскаль как учебный язык струк-

турного программирования.

Наибольший успех в распространении языка Паскаль обеспечили персональные компьютеры. Фирма Borland International, Inc (США) разработала систему программирования Turbo-Pascal для ПК. ТурбоПаскаль — это не только язык и транслятор с него, но еще и операцион­ ная оболочка, позволяющая пользователю удобно работать на Паскале. ТУрбо-Паскаль вышел за рамки учебного предназначения и стал язы­ ком профессионального программирования с универсальными возмож­ ностями. Транслятор с Турбо-Паскаля по оптимальности создаваемых ИМ программ не уступает лидеру в этом качестве — транслятору Фор­ трана. В силу названных достоинств Паскаль стал источником многих основных современных языков программирования, например, таких, как Ада, Модула-2 и др.

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

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

ЭВМ будущего, пятого, поколения называют машинами “искус­ ственного интеллекта” Но прототипы языков для этих машин были созданы МИого раньше их физического появления. Это языки ЛИСП и Пролог-

ЛИСП Появился в 1965 году. Основным в языке ЛИСП служит по­ нятие рекурсивно определенных функций. А поскольку доказано, что любой алгоритм может быть описан с помощью некоторого набора ре­ курсивных функций, то ЛИСП по сути является универсальным язы­ ком. С его Помощью на ЭВМ можно моделировать достаточно сложные Процессы, в частности — интеллектуальную деятельность людей.

Язык Пролог разработан во Франции в 1972 году также для реше­ ния пр°бДем “искусственного интеллекта” Пролог позволяет в фор­ мальном Н&де описывать различные утверждения, логику рассуждений

Пзаставляет ЭВМ давать ответы на заданные вопросы. Реализовать тот или иной язык программирования на ЭВМ — это

значит создать транслятор с этого языка для данной ЭВМ. Суще­ ствует два принципиально различных метода трансляции. Они соот­ ветственно называются: “компиляция” и “интерпретация” . Для объ­ яснения их различия можно предложить следующую аналогию: лектор должен выступить перед аудиторией на незнакомом ей языке. Перевод можно организовать двумя путями:

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

2.Синхронный перевод: лектор читает доклад, переводчик одно­ временно с ним слово за слово переводит выступление.

Компиляция является аналогом полного предварительного пере­ вода; интерпретация — аналогом синхронного перевода. Трансля­ тор, работающий по принципу компиляции, называется компилято­ ром. Транслятор, работающий методом интерпретации, — интерпре­ татором.

При компиляции в память ЭВМ загружается программа-компиля­ тор. Она воспринимает текст программы на ЯПВУ как исходную ин­ формацию. После завершения компиляции получается программа на языке машинных команд. Затем в памяти остается только программа на ЯМК, которая выполняется и получаются искомые результаты.

Интерпретатор в течение всего времени работы программы на­ ходится во внутренней памяти. В ОЗУ помещается и программа на ЯПВУ Интерпретатор в последовательности выполнения алгоритма “читает” очередной оператор программы, переводит его в команды и тут же выполняет эти команды. Затем переходит к переводу и выпол­ нению следующего оператора. При этом результаты предыдущих пе­ реводов в памяти не сохраняются. При повторном выполнении одной

итой же команды она снова будет транслироваться. При компиля­ ции исполнение программы разбивается на два этапа: трансляция и выполнение. При интерпретации, поскольку трансляция и выполне­ ние совмещены, программа на ЭВМ проходит в один этап. Однако откомпилированная программа выполняется быстрее, чем интерпре­ тируемая. Поэтому использование компиляторов удобнее для больших программ, требующих быстрого счета. Программы на Паскале, Си, Фортране всегда компилируются. Бейсик чаще всего реализован че­ рез интерпретатор.