Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

.pdf
Скачиваний:
837
Добавлен:
13.08.2013
Размер:
9.55 Mб
Скачать

В.Г. Давыдов

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

и основы

алгоритмизации

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

Москва «Высшая школа» 2003 '

УДК 004.4 ББК 32.965

Д 13

Рецензенты:

кафедра «Систем управления и информатики» Санкт-Петербургского государст­ венного института точной механики и оптики (технического университета) (зав. ка­ федрой, д-р техн. наук, проф. В.В. Григорьев);

канд. техн. наук, доц. Санкт-Петербургского электротехнического университета «ЛЭТИ» СВ. Власенко

Давыдов, В.Г.

Д 13 Программирование и основы алгоритмизации: Учеб. пособие/В.Г. Давыдов. — М.: Высш. шк., 2003. — 447 е.: ил.

ISBN 5-06-004432-7

Учебное пособие написано в соответствии с разработанной с участием автора примерной программой курса «Программирование и основы алгоритмизации», утвер­ жденной Министерством образования Российской Федерации для подготовки бакалав­ ров и специалистов по направлениям 5502 и 6519 «Автоматизация и управление».

Его цель состоит в поэтапном формировании у студентов следующих слоев зна­ ний и умений — знание основных понятий программирования (слой 1), знание базо­ вого языка программирования C++ (слой 2) и умение решать задачи на ЭВМ (слой 3).

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

Для студентов высших учебных заведений, обучающихся по специальности 210100 «Управление и информатика в технических системах».

УДК 004.4 ББК 32.965

Учебное издание

Давыдов Владимир Григорьевич ПРОГРАММИРОВАНИЕ И ОСНОВЫ АЛГОРИТМИЗАЦИИ

Редактор ТВ. Рысева, Художник ТС. Лошаков

Лицензия ид № 06236 от 09.П.01

Изд. № РЕНТ-183. Подп в печать 14.08.03. Формат 60x88Vi6. Бум. газетная. Гарнитура «Тайме». Печать офсетная. Объем 27,44 усл. печ. л., 27,94 усл. кр.-отг.. Тираж 3000 экз. Заказ № 3184.

ФГУП «Издательство «Высшая школа», 127994, Москва, ГСП-4, Неглинная ул., 29/14. Тел.: (095) 200-04-56. E-mail: mfo@v-shkola.ru http://www.v-shkola.ru

Отдел реализации: (095) 200-07-69, 200-59-39, факс: (095) 200-03-01. E-mail: sales@v-shkola.ru Отдел «книга-почтой»: (095) 200-33-36. E-mail: bookpost@v-shkola.ru

Отпечатано в ФГУП ордена «Знак Почета» Смоленской областной типографии им. В.И. Смирнова. 214000, г. Смоленск, пр-т им. Ю. Гагарина, 2.

I S B N 5 - 06 - 004432 - 7 © Ф Г У П «Издательство «Высшая школа», 2003

Оригинал-макет данного издания является собственностью издательства «Высшая школа», и его репродуцирование (воспроизведение) любым способом без согласия издатель­ ства запрещается.

ПРЕДИСЛОВИЕ

Учебное пособие обеспечивает курс "Программирование и ос­ новы алгоритмизации" и соответствует разработанной с участием автора примерной программе этого курса, рекомендованной Мини­ стерством образования для подготовки бакалавров и специалистов по направлениям 5502 и 6519 "Автоматизация и управление". Посо­ бие ориентировано на студентов, начинающих изучение курса про­ граммирования "с нуля", но может быть полезным и преподавателям высших учебных заведений.

Учебное пособие состоит из введения, двух частей и приложе­ ний. Во введении приводятся сведения о системах счисления, дается классификация языков программирования и их краткая характери­ стика. В первой части пособия в качестве базового языка програм­ мирования изучается язык C++ (за исключением его средств объект­ но-ориентированного программирования и стандартных библиотек)

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

ит.п. В прилоэюениях приведены следующие полезные сведения:

варианты тестов и программных проектов;

сведения о создании программного проекта в различных интег­ рированных средах программирования;

рекомендации по структуре программы и пример оформления ее исходного текста;

методика отладки программы;

примерная программа дисциплины "Программирование и основы

алгоритмизации",

рекомендованная Министерством образования

и др.

 

Для удобства

преподавателей и студентов пособие содержит

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

и др.

в соответствии с возможностями учебного плана предусмат­ риваются следующие три траектории изучения материала:

1. Траектория, рассчитанная на 130 академических часов заня­ тий в рамках подготовки бакалавров (направление 5502 "Автомати­ зация и управление") и специалистов (направление 6519). Это мак­ симальная траектория, охватывающая весь изложенный в учебном пособии материал.

2.Минимальная траектория, рассчитанная на 65 академиче­ ских часов занятий. В рамках такого варианта:

не изучается материал, изложенный в подразд. 1.2, 6.6, 6.8, в разд. 7, 8 (кроме подразд. 8.1), 10, 11, 12 (кроме подразд. 12.1- 12.6), 15 (кроме подразд. 15.8 и 15.9), 16 и 17 (кроме подразд. 17.4);

не выполняются программные проекты, описанные в приложени­ ях П.1.2.1 и П.1.2.3.

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

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

davydov@aivt.ftk.spbstu.ru.

Автор

1. ВВЕДЕНИЕ

Электронная

вычислительная

машина (ЭВМ)

представляет со­

бой устройство,

способное хранить

и выполнять

программы. Про­

граммы - это алгоритмы и структуры данных. Известна следующая формула Никлауса Вирта - разработчика языка Паскаль:

Алгоритмы + структуры данных = программы

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

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

1.1.Системы счисления

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

Основным элементом ЭВМ является электронный ключ, имею­ щий два состояния - "включено" или "выключено". Это хорошо соответствует двоичной системе счисления, в которой используются две цифры: "О" и " 1 " , обозначающие один двоичный разряд - бит.

Рассмотрим системы счисления более подробно и, в частности, системы счисления, применяемые в ЭВМ.

Система счисления - совокупность приемов и правил для запи­ си чисел цифровыми знаками. Различают непозиционные и позици­

онные системы счисления.

 

 

В непозиционной системе

счисления значение знака (символа)

не зависит от его положения

в числе. Пример - римская

система

счисления.

 

 

Позиционная система счисления - система, в которой

значение

цифры числа определяется ее положением (позицией) в числе. Лю­ бая позиционная система счисления характеризуется основанием. Основание "^" позиционной системы счисления - количество цифр, используемых при изображении числа в данной системе.

Для позиционной системы счисления справедливо равенство,

\idi3b\bdiQMOQ развернутой формой записи числа:

где A^^j^ - произвольное число, записанное в системе счисления с ос­ нованием 'V"; ^/ - коэффициенты ряда или значения разрядов числа (цифры системы счисления); п + 1 т - количество целых и дробных

разрядов числа.

 

На практике, для краткости, используют сокращенную

запись

чисел:

 

Ая) = ^п<^п-х • ••а,а^,а_,а_2...а_,„

(2)

Пример. Для десятичного числа 349,17 развернутая форма за­

писи

3-10'+4-10'+9-10VM0-'+7 10-',

а сокращенная

349.17

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

Вдвоичной системе счисления для записи числа в сокращен­

ной форме используются цифры О и 1, в восьмеричной - О, 1,2, ..., 7, в десятичной - О, 1,2, ..., 9 и в шестнадцатеричной - О, 1,2, ..., 9, А,

В, С, D, Е, F.

 

 

Перевод

чисел из двоичной, восьмеричной или

илестнадцате-

ричной систем

счисления в десятичную систему легко

выполняется

с помощью развернутой формы записи числа (1). Например, двоич­ ное число

42) =1101,001(2)

соответствует десятичному числу ^ = Ь2'+1-2'ч-1-2'+1-2-' =13,125

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

Перевод чисел из десятичной системы в двоичную систему счисления поясним примером.

Пусть требуется перевести десятичное число 13,125 в двоич­ ную систему счисления. Целая и дробная части десятичного числа переводятся по разному: целая - делением на основание q — 2^ г.

дробная - умножением на q = 2. Vi деление, и умножение выполня­ ются в десятичной системе счисления.

При делении 13 на 2 получаем частное 6 и остаток 1. При де­ лении 6 на 2 получаем частное 3 и остаток 0. При делении 3 на 2 получаем остаток 1 и частное 1. Поскольку частное меньше двух, то на этом деление заканчивается.

При умножении 0,125 на два получаем 0,250 {целая

часть

произведения 0). При умножении 0,250 на 2 получаем 0,500

{целая

часть произведения 0). При умножении 0,500 на 2 получаем

1,000

{целая часть произведения 7). Поскольку дробная часть теперь ну­ левая, то умножение на этом заканчивается.

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

1101,001(2)

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

Особенно просто выполняется перевод чисел из двоичной сис­ темы счисления в системы счисления с основанием, равным степе­ ням 2, и наоборот. При указанном переводе удобно пользоваться табл. 1.

Табл. 1. Перевод чисел из двоичной системы в восьмеричную или шестнадцатеричную системы счисления и наоборот

Восьмеричная

Двоичная

Шестнадцатеричная

Двоичная

цифра

триада

цифра

тетрада

0

000

0

0000

1

001

1

0001

2

010

2

0010

3

011

3

ООН

4

100

4

0100

5

101

5

0101

6

по

6

оно

7

111

7

0111

 

 

8

1000

 

 

9

1001

 

 

А

1010

 

 

В

1011

 

 

С

1100

 

 

D

1101

 

 

Е

1110

 

 

F

1111

Примеры перевода

чисел из одной системы счисления

в дру­

гую:

 

 

1. 42)=1 101,1 1001(,)

^8)=?

 

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

 

001 101 , 1 1 0 0 1 0

 

В соответствии с табл.

1 заменяем полученные триады

восьме­

ричными цифрами и получаем

 

 

2. 42)=И01Д 1001(2)

 

4.6)=?

 

 

Перевод числа выполняется аналогично предыдущему, но вме­

сто триад выделяются двоичные тетрады:

 

 

 

1101 , 1100 1000

 

В соответствии с табл.

1 заменяем

полученные тетрады шест-

надцатеричными цифрами и получаем

 

 

 

 

^ 1 6 ) = - ^ ' ^ ^ ( 1 6 )

 

 

3. 4,6)-^^1,^^06)

 

42)=?

 

 

в соответствии с табл.

1 заменяем

шестнадцатеричные

цифры

тетрадами

 

 

 

 

1010

1111 0001 , 1 1 1 1 1110

 

и получаем

 

 

 

 

^2)

=101011110001,1111111(2)

 

4. 48)=710,526(,,)

 

42)=?

 

 

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

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

1.2.Классификация языков программирования

иих краткая характеристика

Языки программирования делятся на две группы:

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

2. Машинно-независимые языки - их можно использовать на любой ЭВМ. Языки этой группы называют универсальными языка­

ми.

 

Машинно-зависимые

языки^ в зависимости от их близости к

машинным языкам, делятся на три группы:

машинные языки (языки нулевого уровня);

ассемблерные языки (языки первого уровня или языки типа 1:1, последнее означает, что одна ассемблерная команда после транс­ ляции порождает ровно одну машинную команду);

макроассемблеры (языки второго уровня или языки типа \\п).

Аналогично, маилинно-независимые

языки включают сле­

дующие группы языков:

 

Процедурные языки (третий уровень): Си, C+-I-, Паскаль, ФОРТРАН, БЭЙСИК и др. Процедурные языки требуют детальной разработки алгоритма решения и, по существу, являются языками для записи алгоритмов решения задач.

Проблемные языки (четвертый уровень) или языки типа "заполни бланк". Это языки описания задач, специализированные языки. Используя подобный язык программирования, пользователь со­ общает только, какую задачу надо решить и с какими данными. Как решить задачу - "знает" язык. В качестве примера проблемно­ го языка можно назвать язык ПРОСПО, разработанный фирмой IBM для программирования систем управления производствен­ ными процессами.

Универсальные языки (пятый уровень): ПЛ/1, АЛГОЛ-68, Ада и др. При создании универсальных языков в их состав включили все лучшее, что имелось на момент создания в процедурных языках.

1.2.1. Машинные языки

Рассмотрим машинные языки на примере простого машинного языка (ПМ), разработанного для студентов кафедры "Автоматика и вычислительная техника" Санкт-Петербургского государственного политехнического университета проф. Лекаревым М.Ф. Язык ПМ подробно рассмотрен в [1] и его описание имеется на прилагаемом компакт-диске. Здесь, если вместе с учебным пособием Вы приоб­ рели еще и компакт-диск, рекомендуем рассмотреть имеющийся в [1] материал, включая структурную организацию и функционирова­ ние простой ЭВМ.