Razdel_13_Osn_alg_i_i_progr_ya_11_05_10
.pdfМОСКОВСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ
Кафедра ИНФОРМАТИКИ И МАТЕМАТИКИ
Сборник
учебно-методических материалов
по дисциплине
ИНФОРМАТИКА
и
МАТЕМАТИКА
ЕН.Ф.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