Razdel_13_Osn_alg_i_i_progr_ya_11_05_10

МОСКОВСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ

Кафедра ИНФОРМАТИКИ И МАТЕМАТИКИ

Сборник

учебно-методических материалов

по дисциплине

ИНФОРМАТИКА

и

МАТЕМАТИКА

ЕН.Ф.01

Для студентов дневной формы обучения

Часть 13

Основы алгоритмизации и программирования

Москва

2010

Часть 13. Основы алгоритмизации и программирования

Сборник учебно-методических материалов подготовлен в рамках программы дисциплины «Информатика и математика», составленной в соответствии с требованиями Государственного образовательного стандарта и образовательного стандарта Московского гуманитарного университета и содержит:

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

учебно-методические рекомендации к организации самостоятельной работы студентов;

учебный материал для самостоятельной работы студентов.

Составители сборника:

Выжигин А. Ю. – к. т. н., доцент, заведующий кафедрой информатики и математики МосГУ

Сборник учебно-методических материалов рекомендован к изданию на заседании кафедры 19.05.2010 г., протокол № 7.

2

Часть 13. Основы алгоритмизации и программирования

Оглавление

ЭЛЕМЕНТЫ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ «ИНФОРМАТИКА И МАТЕМАТИКА. РАЗДЕЛ

13. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ» .....................................................				5
ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ..............................................................................				6
1	ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ...........................................................			7
	1.1	ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ .............................................................................		7
	1.1.1		Алгоритм и программа ..........................................................................................................	7
	1.1.2 Что такое язык программирования .....................................................................................			7
	1.1.3		Компиляторы и интерпретаторы .......................................................................................	8
	1.1.4		Уровни языков программирования .......................................................................................	10
	1.1.5		Поколения языков программирования .................................................................................	11
	1.1.6 Обзор языков программирования высокого уровня .............................................................			13
	1.1.7 Языки программирования баз данных .................................................................................			15
	1.1.8 Языки программирования для Интернета .........................................................................			16
	1.1.9		Языки моделирования ...........................................................................................................	18
	1.1.10		Прочие языки программирования ........................................................................................	19
	1.1.11		Системы программирования ................................................................................................	20
	1.1.12		Архитектура программных систем ....................................................................................	24
2	СЛОВЕСНЫЕ АЛГОРИТМЫ ...........................................................................................................			28
	2.1	ОПРЕДЕЛЕНИЕ АЛГОРИТМА ..............................................................................................................		28
	2.2	"ИСПОЛНИТЕЛЬ АЛГОРИТМА" ..........................................................................................................		28
	2.3	СВОЙСТВА АЛГОРИТМОВ..................................................................................................................		29
	2.4	ФОРМА ЗАПИСИ АЛГОРИТМОВ ..........................................................................................................		29
	2.5	СЛОВЕСНЫЙ СПОСОБ ЗАПИСИ АЛГОРИТМОВ .....................................................................................		30
	2.6	ГРАФИЧЕСКИЙ СПОСОБ ЗАПИСИ АЛГОРИТМОВ..................................................................................		31
	2.7	ПОНЯТИЕ ПСЕВДОКОДА....................................................................................................................		33
	2.8	ЗАПИСЬ АЛГОРИТМОВ НА ШКОЛЬНОМ АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ ...................................................		34
	2.8.1		Основные служебные слова ....................................................................................................	34
	2.8.1.1		Команды школьного АЯ ....................................................................................................................	36
	2.8.1.2 Пример записи алгоритма на школьном АЯ .....................................................................................			36
3	БАЗОВЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ .........................................................................			37
	3.1	ИТЕРАЦИОННЫЕ ЦИКЛЫ...................................................................................................................		42
	3.2	ВЛОЖЕННЫЕ ЦИКЛЫ ........................................................................................................................		44
	3.2.1.1 Пример вложенных циклов для.........................................................................................................			44
	3.2.1.2 Пример вложенных циклов пока.......................................................................................................			45
	3.3	. ОТЛИЧИЕ ПРОГРАММНОГО СПОСОБА ЗАПИСИ АЛГОРИТМОВ ОТ ДРУГИХ ..........................................		45
	3.4	КОМПОНЕНТЫ АЛГОРИТМИЧЕСКОГО ЯЗЫКА .....................................................................................		46
	3.5	ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМИЧЕСКИХ ЯЗЫКОВ ..........................................................................		46
	3.6	ПРАВИЛО ЗАПИСИ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ..........................................................................		49
	3.6.1.1 Примеры записи арифметических выражений..................................................................................			50
	3.7	ЗАПИСЬ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ ..................................................................................................		50
	3.7.1.1 Примеры записи логических выражений, истинных при выполнении указанных условий. ............			51
	3.8	ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ........................................................................................................		53
	Ответы		..................................................................................................................................................	67
4 АЛГОРИТМЫ ......................................ЛИНЕЙНОЙ И РАЗВЕТВЛЯЮЩЕЙСЯ СТРУКТУРЫ				78
5 АЛГОРИТМЫ .................................., РЕАЛИЗУЕМЫЕ С ПОМОЩЬЮ ЦИКЛОВ ТИПА ДЛЯ				95
6 АЛГОРИТМЫ ......, РЕАЛИЗУЕМЫЕ С ПОМОЩЬЮ ВЛОЖЕННЫХ ЦИКЛОВ ТИПА ДЛЯ				108
7 АЛГОРИТМЫ ................................, РЕАЛИЗУЕМЫЕ С ПОМОЩЬЮ ЦИКЛОВ ТИПА ПОКА				131
	7.1.1 ............................................................................................Цикл типа пока с прерыванием			131
	7.1.2 ...........................................................................................Цикл типа пока без прерывания			132

8 АЛГОРИТМЫ, РЕАЛИЗУЕМЫЕ С ПОМОЩЬЮ ВЛОЖЕННЫХ ЦИКЛОВ ТИПА ПОКА .155

3

Часть 13. Основы алгоритмизации и программирования

9 АЛГОРИТМЫ, РЕАЛИЗУЕМЫЕ С ПОМОЩЬЮ КОМБИНАЦИИ ЦИКЛОВ ТИПА ДЛЯ И

ПОКА ............................................................................................................................................................		179
10	АЛГОРИТМ ЕВКЛИДА................................................................................................................	205
11	ТЕСТОВЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ ПОДГОТОВКИ «ОСНОВЫ
АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ. ЧАСТЬ 1.»........................................................		209
12	ТЕСТОВЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ ПОДГОТОВКИ «ОСНОВЫ
АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ. ЧАСТЬ 2.»........................................................		214
13	ТЕСТОВЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ ПОДГОТОВКИ «ОСНОВЫ
АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ. ЧАСТЬ 3.»........................................................		217
14	ТЕСТОВЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ ПОДГОТОВКИ «ОСНОВЫ
АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ. ЧАСТЬ 4.»........................................................		221
15	РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА ..........................................................................................	224
	ЛИТЕРАТУРА ОСНОВНАЯ............................................................................................................................	224
	ЛИТЕРАТУРА ДОПОЛНИТЕЛЬНАЯ................................................................................................................	225

4

Часть 13. Основы алгоритмизации и программирования

Элементы содержания дисциплины

«Информатика и математика. Раздел 13. Основы алгоритмизации

и программирования»

Наименование элемента со-	Студент должен:
держания (темы)
Алгоритмизация и языки программирования
Языки программирования вы-	знать: характерные черты языков программирования
сокого уровня	высокого уровня
Словесные алгоритмы	знать: понятие алгоритма
	уметь: выполнять заданный алгоритм в словесной
	форме
Блок-схемы. Ветвление.	знать: форму записи алгоритма ветвления на языке
	блок-схем
	уметь: находить результат работы алгоритма ветвле-
	ния
Блок-схемы. Задачи на ветв-	знать: условный оператор
ление. Принадлежность от-	уметь: находить результат работы алгоритма с услов-
резку	ным оператором
Блок-схемы. Цикл со счетчи-	знать: форму записи циклического алгоритма на языке
ком	блок-схем
	уметь: находить результат работы циклического алго-
	ритма
Блок-схемы. Циклы	знать: форму записи алгоритма на языке блок-схем
	уметь: находить результат работы циклического алго-
	ритма

5

Часть 13. Основы алгоритмизации и программирования

Организация самостоятельной работы

Составители рекомендаций:

Выжигин А. Ю. – к. т. н., доцент,

заведующий кафедрой информатики и математики МосГУ

Телепин А. М. – доцент кафедры информатики и математики МосГУ

Самостоятельная работа — важная составляющая часть высшего об-

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

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

Самостоятельная работа включает подготовку студентов к практиче-

ским занятиям, тестированию и зачету. Эта подготовка состоит в знаком-

стве с содержанием разделов данного учебного пособия и выполнении за-

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

6

Часть 13. Основы алгоритмизации и программирования

1 Языки программирования высокого уровня

1.1 Языки программирования высокого уровня

1.1.1Алгоритм и программа

Управлять компьютером нужно по определенному алгоритму. Алго-

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

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

ков. В итоге получается текст программы — полное, законченное и де-

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

ются трансляторами, либо переводится в машинный код, либо исполняет-

ся.

1.1.2Что такое язык программирования

Самому написать программу в машинном коде весьма сложно, при-

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

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

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

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

ется на этапе составления алгоритма), но автоматически перевести такую программу в машинный код пока невозможно из-за высокой неоднознач-

ности естественного языка. Языки программирования — искусственные

7

Часть 13. Основы алгоритмизации и программирования

языки. От естественных они отличаются ограниченным числом «слов»,

значение которых понятно транслятору, и очень строгими правилами запи-

си команд {операторов). Совокупность подобных требований образует

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

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

ра и выдает сообщение о синтаксической ошибке, а правильно написанное,

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

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

1.1.3Компиляторы и интерпретаторы

С помощью языка программирования создается не готовая програм-

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

ревести в машинный код (для этого служат программы-компиляторы) и

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

граммы-интерпретаторы). Интерпретатор берет очередной оператор язы-

ка из текста программы, анализирует его структуру и затем сразу исполня-

ет (обычно после анализа оператор транслируется в некоторое промежу-

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

ли один и тот же оператор должен выполняться в программе многократно,

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

Кроме того, для выполнения такой программы на другом компьютере там также должен быть установлен интерпретатор — ведь без него текст про-

8

Часть 13. Основы алгоритмизации и программирования

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

что интерпретатор моделирует некую виртуальную вычислительную ма-

шину, для которой базовыми инструкциями служат не элементарные ко-

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

ходный код). Они просматривают его в поисках синтаксических ошибок

(иногда несколько раз), выполняют определенный смысловой анализ и за-

тем автоматически переводят (транслируют) на машинный язык — гене-

рируют машинный код. Нередко при этом выполняется оптимизация с по-

мощью набора методов, позволяющих повысить быстродействие програм-

мы (например, с помощью инструкций, ориентированных на конкретный процессор, путем исключения ненужных команд, промежуточных вычис-

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

ры с процессором, поддерживающим соответствующий машинный код.

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

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

татора, наоборот, допустимо в любой момент остановить работу програм-

мы, исследовать содержимое памяти, организовать диалог с пользовате-

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

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

9

Часть 13. Основы алгоритмизации и программирования

ты. Интерпретатор при выполнении каждого оператора проверяет множе-

ство характеристик операционной системы и при необходимости макси-

мально подробно информирует разработчика о возникающих проблемах.

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

струмента изучения программирования, так как позволяет понять принци-

пы работы любого отдельного оператора языка. В реальных системах про-

граммирования перемешаны технологии и компиляции, и интерпретации.

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

рующий код не обязательно будет машинным — он даже может быть ис-

ходным кодом, написанным на другом языке программирования (это су-

щественно упрощает процесс трансляции, но требует компилятора для ко-

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

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

1.1.4Уровни языков программирования

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

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

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

го кода, но не в виде чисел, а с помощью символьных условных обозначе-

ний, называемых мнемониками. Однозначное преобразование одной ма-

шинной инструкции в одну команду ассемблера называется транслитера-

цией. Так как наборы инструкций для каждого модели процессора отлича-

ются, конкретной компьютерной архитектуре соответствует свой язык ас-

семблера, и написанная на нем программа может быть использована толь-

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

10