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

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

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

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

1. Поменять местами содержимое двух переменных (три ведра).

Назовем эти переменные a и b (пусть их значения равны 15 и -3) и изобразим их на схеме. Чтобы поменять их содержимое местами, добавим еще одну (буферную) переменную c, в которой временно запомним значение переменной a (1-е действие). Затем занесем в a значение переменной b (2-е действие), а затем в b - c (3-е действие). После того, как продумали таким образом алгоритм, изобразим его в виде блок-схемы.

Определить, имеют ли две переменные один знак.

Чтобы узнать одного ли знака две переменные, достаточно их перемножить. Если результат положительный, то переменные одного знака. Поскольку в алгоритме должна быть предусмотрена реакция на все допустимые варианты исходных данных, то должна быть и проверка a и b на нулевые значения.

Проверить делимость числа на 3

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

Алгоритм обработки массива.

При решении задач с массивами чисел или символов чаще всего используется один и тот же алгоритм единообразной поочередной обработки каждого элемента массива в отдель­ности. Для этого обычно применяется цикли­ческий алгоритм с параметром, рассмотренный справа. Массив a из n элементов будем обозначать {a}n, а элемент массива с номером i - ai. Сначала вводится количество n элементов массива a  и сам массив (блок 1). Затем проводятся подготовительные операции (блок 2), содержание которых зависит от решаемой задачи. Обычно здесь задаются начальные значения вспомогательным переменным. Блоки 3, 4 и 6 являются обязательными, именно они реа­лизуют цикл и позволяют поочередно обработать каждый элемент массива. Блок 3 задает номер начального элемента обрабатываемого мас­сива, блок 4 позволяет закончить обработку и выйти из цикла после превышения номером текущего элемента значения n, а блок 6 позволяет после обработки текущего элемента перей­ти к следующему, увеличив номер элемента на 1.

При обработке i-го элемента массива в некоторых случаях возможен досрочный выход из цикла, тогда в блок-схеме появляется блок 9, на который передается управление прямо от блока 5. После окончания обработки производят вывод исходного массива для контроля правильности его ввода (блок 7), а затем анализируют и печатают результаты обработки (блок 8).

---

Найти сумму элементов массива

В качестве примера рассмотрим нахождение суммы элементов массива. В блоке 2 введем переменную s, в которой будем копить искомую сумму. Чтобы найти действие, которое	s=0 s=0+a1 s=0+a1 +a2 s=0+a1 +a 2+ a3	s=0 s=s+a1 s=s+a2 s=s+a3
надо повторить для каждого элемента массива (блок 5), рассмотрим, что находится в s при прибавлении к сумме каждого следующего элемента. Из таблицы справа видно, что в s каждый раз заносится то, что там было после предыдущего шага (под­черкнуто), плюс текущий элемент, т.е. s=s+ai . В блоке анализа результатов (блок 8) просто напечатаем значение s.

Найти максимальный элемент массива.

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

мального из уже рассмотренных элементов. Вначале занесем туда первый элемент, как наибольший из рассмотренных (блок 2). На каждой итерации (блок 5) будем заносить туда текущий элемент ai, если он больше предыдущего максимального (при этом старое значение стирается), если же нет, то оставлять там то, что было. После окончания обработки массива в amax останется самый большой элемент. В блоке 8 анализа результатов  просто напечатаем значение amax .

Использование флага наступления события

В некоторых задачах требуется обработать не все элементы массива, а только соответствующие некоторому условию. В этом случае после обработки массива иногда неизвестно, были найдены такие элементы или нет. Чтобы узнать это, используют прием алгоритмизации, называемый флагом. Перед обработкой массива (в блоке 2) в некоторую переменную (назовем ее flag) заносят число 0. В процессе обработки элементов (блок 5) в эту переменную заносят число 1, если обрабатываемый элемент удовлетворяет заданному условию. Тогда после окончания обработки до­статочно проверить значение этой переменной - если там остался ноль, то подходящих

элементов не нашлось. В качестве примера рассмотрим поиск первого четного элемента массива. Перед циклом в блоке 2 занесем в переменную flag число 0. При обработке i-го элемента массива (блок 5) в случае его четности занесем в flag число 1 и сделаем досрочный выход из цикла, передав управление на блок 9, в противном случае продолжим цикл, перейдя на блок 6. После окончания обработки (блок 8) проверим значение переменной flag. Если оно не 0, значит четные элементы были, поэтому выводим ai.

Системы программирования

Состав.

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

---

В состав системы программирования обычно входят:

0. описание применяемого языка программирования;

1. тестовый редактор, позволяющий ввести текст программы и записать его в файл на диске;

2. программы-трансляторы, переводящие исходный текст программы в машинный код;

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

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

Язык программирования, алфавит, синтаксис, семантика.

Программа – набор команд на понятном ЭВМ языке, реализующих заданный алгоритм.

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

Синтаксис – это набор правил написания языковых конструкций.

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

Реализация языка

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

Имеются два основных вида средств реализации языка: компиляторы и интерпретаторы.

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

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

В принципе любой язык программирования может быть как интерпретируемым, так и компилируемым, но в большинстве случаев у каждого языка есть свой предпочтительный способ реализации. Языки Фортран, Си, Паскаль в основном компилируют, языки Бейсик и Лисп широко используют оба способа.

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

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

---

Этапы обработки программы машиной

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

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

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

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

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

5. Загрузка. С помощью программы загрузчик (или интерпретатор команд операционной системы, обычно это файл command.com), программа загружается в оперативную память и управление передается на ее первую команду (принцип Фон-Неймана). Обычно в начале работы программы вводятся исходные данные либо из файла, либо пользователем с клавиатуры. В процессе выполнения программа выводит результаты на экран, принтер или в файл на диске.

---

---

Смотрите также файлы

• Лекция 05.docx

• Лекция 03.docx

• Лекция 02.docx

• Лекция 09.docx

• Лекция 08.docx