8.1. Основные понятия программирования
Введем основные понятия программирования. Их рассмотрение позволит сосредоточить внимание на специфике вычислительной машины как средства выполнения разрабатываемых программ и подготовит Вас для восприятия дальнейшего материала.
Исполнитель — это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный конечный набор действий. Приказ на выполнение действия из указанного набора, выраженный каким-либо заранее оговоренным способом, называется предписанием, а вся совокупность допустимых приказов — системой предписаний исполнителя.
Давая задание исполнителю на выполнение некоторой работы, мы обычно выдаем ему не одно предписание, а некоторую конечную последовательность предписаний, задавая также порядок, в котором эти предписания должны быть выполнены. Такая последовательность предписаний с указанием порядка их выполнения называется программой.
Всякое действие производится над некоторыми объектами, и о его результатах можно полностью судить по изменению состояния этих объектов. Один из видов объектов — переменная. Понятие переменной является одним из центральных понятий программирования. (Понятие переменной имеет в программировании другой смысл, чем в математике.) Поясним это понятие на примере.
Пример. Требуется найти произведение любых двух натуральных чисел n, m. Результат обозначить через k.
Составим задание для исполнителя, который не умеет выполнять умножение, а умеет лишь складывать. В этом случае решение задачи не может быть выполнено в одно действие, а требует разложения на ряд последовательных действий, т. е. составления программы.
Так как программа должна «работать» для любой пары натуральных чисел, то сами конкретные числа в программе не фигурируют. Вместо чисел употребляются имена, обозначающие изменяемые объекты, которые называются переменными. Перед началом вычислений этим переменным должны быть присвоены значения. Присвоение — одно из важнейших действий, выполняемых вычислительной машиной (на использование которой в качестве исполнителя мы и ориентируемся в конечном счете).
Переменную можно представить себе как ящик, обозначенный именем, идентифицирующим эту переменную. Присвоение переменной с именем n значения 5 можно представить себе так; положить в ящик, обозначенный n, 5 шаров. (Ящик является аналогом ячейки памяти ЭВМ.)
Значение одной переменной можно переслать в другую переменную. При этой операции значение пересылаемой переменной не изменяется. Например переслать значение n в переменную i, или присвоить переменной i значение n, означает задать i такое же значение, которое имеет переменная n, т.е, скопировать значение n. Если было, допустим, n=5, то присвоение i значения n (записывается i = n — i присвоить значение n) означает, что нужно как бы посмотреть, какое число находится в ячейке памяти n, и такое же число «положить» в ячейку памяти i. Теперь будет i=5, но при этом n сохранило значение (n=5). Следует отметить также, что в выражении i = n знак «=» обозначает не равенство, а операцию присвоения.
Часто в программировании используется такая операция присваивания, когда слева и справа используется одна и та же переменная, например, i = i + 1. Такая запись означает, что сначала должна быть выполнена операция сложения (i+1), а затем полученная сумма присвоена переменной i в качестве ее нового значения. При этом старое значение i пропадает, «стирается». После выполнения этой операции i будет иметь значение на 1 больше, чем перед ее выполнением.
Вернемся к нашей задаче. Чтобы получить произведение n на m, используя операцию сложения, нужно просуммировать m слагаемых, равных n, т. е. вычислить
Но эта формула — не программа, хотя бы потому, что здесь есть неопределенность (например, многоточие),
Решение этой задачи можно представить как последовательность выполнения следующих простых шагов;
Положить k = 0.
Далее выполнить операцию
k = k + n
m раз. При этом после каждого выполнения указанной операции значение k увеличивается наn. В итоге в k будет получен результат решения задачи.
Чтобы выполнить операцию требуемое число раз, нужно считать, сколько раз эта операция уже выполнена. Используем для этого вспомогательную переменную i. Назовем ее счетчиком. Перед первым прибавлением к k значения n положим i = 1 и после очередного изменения k. значение счетчика i будем менять на 1.
Тогда программа может быть записана так:
1 задать конкретные значения n, m
2 k = 0
3 i =1
4 k = k + n
5.i = i +1
6 если i 
m идти к 4. (Повторить выполнение операций, начиная с п. 4)
7 закончить вычисления
Пояснения к программе.
1. Программа написана на обычном языке человеческого общения с использованием общепринятой математической символики (это так называемый «естественный» язык).
2. Операторы 2, 3 задают начальные значения переменных k и i. В языках программирования предписание о выполнении некоторой операции (например, операции присваивания) называется оператором.
3. Оператор 4 при каждом своем выполнении увеличивает значение k на n. Оператор 5 увеличивает значение счетчика на 1 после того, как выполнено очередное сложение.
4. Оператор 6 проверяет условие i m, и если оно выполняется, т. е. не все m сложений еще выполнены, то происходит возврат к оператору 4 и повторное выполнение программы, начиная с оператора 4. Как только в процессе выполнения программы условие i m не будет выполнено, процесс вычислений заканчивается. Это произойдет, когда будет i > m, т. е. все нужные сложения выполнены.
Приведенная программа задает порядок действий, которые могут быть выполнены, когда n и m получат конкретные значения.
Совокупность значений переменных, которые должны быть заданы перед выполнением программы, называется исходными данными.
Упражнение 1. Выполнить программу при n=5, m=3. Проследить за изменением переменных.
Указание. Для каждой переменной, используемой в программе (n, m, k., i), предусмотреть ячейку памяти. При задании значения переменной записать это значение в ячейке памяти с соответствующим именем. После выполнения программы сравнить содержимое ячейки k с правильным ответом (результатом умножения 3 на 5).
Решение. Содержимое ячеек памяти (значения переменных) после выполнения оператора 1.
Отсутствие записи означает, что значение переменной не определено.
Содержимое ячеек памяти после выполнения операторов 2, 3.
Содержимое ячеек n, m далее не изменяется.
После первого выполнения операторов 4, 5.
Выполнение оператора 6 не изменяет значений переменных, а связано с проверкой условия. Условие здесь задано в виде отношения и вычисляется каждый раз при текущих значениях входящих в него переменных. Результатом вычисления условия является да, если условие удовлетворяется для входящих в него переменных, или нет, если условие не удовлетворяется. При значении да в данной программе будет осуществляться переход к оператору 4, при значении нет — переход к следующему по порядку оператору (в данном случае — окончание выполнения программы).
При первом выполнении оператора 6 проверяется условие 2 3. Оно имеет значение да, поэтому следующим выполняется оператор с номером 4.
После второго выполнения операторов 4, 5.
При втором выполнении оператора 6 условие 3 3 имеет значение да, и снова выполняется оператор 4.
После третьего выполнения операторов 4, 5.
При третьем выполнении оператора 6 условие 4 3 не удовлетворяется (имеет значение нет}, и выполнение программы прекращается.
Результатом является последнее значение переменной k, равное 15.
Изменение значений переменных при выполнении программы можно представить в более компактном виде — в виде трассировочной таблицы, в которой записываются все значения, последовательно принимаемые изменяемыми переменными программы. Для рассмотренной выше программы изменяются только переменные k и i, и трассировочная таблица имеет вид
|
k |
0 |
5 |
10 |
15 |
|
i |
1 |
2 |
3 |
4 |
Отметим, что в рассмотренной программе после выполнения оператора 6 (если условие выполняется) осуществляется возврат к оператору 4 и повторное выполнение операторов 4—6. Многократно повторяющаяся при выполнении часть программы носит название цикл. Цикл является типичной структурой, реализуемой в программах для ЭВМ. Его использование позволяет записать последовательность действий один раз, а выполнять их многократно, после каждого выполнения возвращаясь к началу этой последовательности (цикла).
Упражнение 2. Составить программу на естественном языке для возведения числа х в степень k (k — натуральное число), используя операцию умножения. Результат обозначить через z.
Выполнить программу для х=4, k=3, фиксируя изменение переменных с использованием: а) ячеек памяти; б) трассировочной таблицы.
Решение. Необходимо составить программу для вычисления
Положим вначале z = 1, а далее выполним операциюz = z * x
k раз. Для подсчета выполненных умножений используем счетчик i (см. также предыдущий пример).
Программа на естественном языке будет иметь вид
1 задать конкретные значения x, k
2 z = 1
3 i = 1
4 z = z * x
5 i = i +1
6 если i k идти к 4
7 закончить вычисления
Предусмотрим четыре ячейки памяти для переменных. При изменении значения переменной старое значение теперь будем зачеркивать и рядом записывать новое:
Последнее значение z = 64 и является результатом выполнения программы.
8.2. Понятие алгоритма
Алгоритмом называется четкое описание последовательности действий, которые необходимо выполнить для решения задачи. Практически решение любой задачи требует получения результата по заданным исходным данным. Следовательно, можно сказать, что алгоритм описывает последовательный процесс преобразования исходных данных в результат.
Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги (этапы), причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап (шаг) алгоритма представляет собой либо другую, более простую задачу, алгоритм решения которой разработан ранее, либо должен быть достаточно простым и понятным без пояснений.
Четко сформулированная последовательность правил, описывающих этот процесс, и является алгоритмом.
Если алгоритм разработан, то его можно вручить для выполнения человеку (и вообще любому исполнителю, в том числе и ЭВМ), не знакомому с решаемой задачей, и, точно следуя правилам алгоритма, этот человек (или другой исполнитель) получит ее решение.
Например, вам предложено выполнить следующую последовательность действий при заданных значениях а = 1, b = 3, c = 2:
1. Вычислить D = b2 – 4ac
2. Сравнить D с нулем. Если D < 0, перейти к 3. Впротивном случае вычислить
3. Прекратить вычисления.
Оказывается, выполнив приведенную последовательность для указанных значений а, b и c, вы решили квадратное уравнение х2 + 3х + 2 = 0.
Свойства алгоритма
Алгоритм обладает следующими основными свойствами, раскрывающими его определение:
1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов). При этом для выполнения каждого шага (этапа) алгоритма требуется некоторый конечный отрезок времени. То есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Определенность (или детерминированность). Это свойство состоит в том, что каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость. Это свойство состоит в том, что алгоритм решения задачи разрабатывается в общем виде, т. е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. В отдельных случаях исходные данные могут отсутствовать.
Например, приведенный выше алгоритм решения квадратичного уравнения применим для различных наборов коэффициентов а, b, c (а ¹ 0).
Чтобы разработать алгоритм, нужно хорошо представить себе ход решения задачи. При этом полезно решить задачу самому (на бумаге) для каких-либо наборов данных, не требующих громоздких вычислений, запоминая выполняемые действия, так, чтобы далее эти действия формализовать, т. е. записать в виде последовательности четких правил.
Понятия алгоритма и программы разграничены не очень четко. Обычно программой называют окончательный вариант алгоритма решения задачи, ориентированный на конкретного исполнителя.
Этап, результатом которого является разработка алгоритма решения задачи, часто называют алгоритмизацией, понимая под этим сведение задачи к последовательности этапов, выполняемых последовательно друг за другом. В широком смысле алгоритмизация включает и выбор метода решения задачи, а также формы представления исходной информации с учетом специфики ЭВМ.
Разработанный алгоритм можно зафиксировать несколькими способами, например:
- на естественном языке, как это было сделано в предыдущем примере;
- в виде схемы;
- на специальном языке для записи алгоритмов (алгоритмическом языке).
Запись алгоритма на естественном языке
Хотя естественный язык не требует детальных разъяснений и полной формализации, сформулируем некоторые правила, которые облегчат в дальнейшем переход к .алгоритмическому языку.
Введем следующие обозначения типичных этапов алгоритма:
1. Этап обработки (вычисления)
v — выражение
(v — переменная, выражение задает правило вычисления значения, которое далее будет присвоено переменной v. Это может быть, например, знакомое нам алгебраическое (арифметическое) выражение).
2. Проверка условия
если условие идти к N.
Если условие удовлетворяется, выполняется переход к этапу N. Если условие не удовлетворяется, то условимся, что осуществляется переход к следующему по порядку этапу.
3. Конец вычислений;
закончить вычисления.
4. Переход к этапу с номером N
идти к N
Изображение алгоритма в виде схемы
Схемой называется наглядное графическое изображение алгоритма, когда отдельные действия (этапы) алгоритма изображаются при помощи различных геометрических фигур (блоков), а связи между этапами (последовательность выполнения этапов) указываются при помощи линий, соединяющих эти фигуры. Направления линий сверху вниз и слева направо принимаются за основные и могут (если не имеют изломов) не иметь стрелок
Существует Государственный стандарт (ГОСТ), определяющий правила выполнения схем и обозначения для отдельных операций процесса обработки данных. Далее приводятся обозначения некоторых, наиболее часто употребляемых операций.
Типичные действия алгоритма изображаются следующими геометрическими фигурами.
Этап обработки (вычисления) изображается прямоугольником (рис. 8.1а). Внутри прямоугольника записывается содержание этого этапа.
Проверка условия изображается ромбом. Условие записывается внутри ромба. В результате проверки условия осуществляется выбор одного из двух возможных путей вычислительного процесса (рис. 8.1б).
Если условие выполняется, т. е. имеет значение да — то следующим выполняется этап по стрелке да. Если условие не выполняется, то осуществляется переход по стрелке нет.
Рис. 8.1. Блоки, используемые в схемах алгоритма
Начало и конец вычислительного процесса изображаются фигурой, показанной на рис. 8.1в. Внутри нее записывается слово начало или конец.
Ранее созданные и отдельно описанные алгоритмы и программы (подпрограммы) изображаются фигурой на рис. 8.1г. Внутри нее указывается имя подпрограммы и параметры, при которых подпрограмма должна быть выполнена.
Ввод исходных данных и вывод результатов изображаются параллелограммом (рис. 8.1д). Внутри него пишется слово ввод или печать и перечисляются переменные, подлежащие вводу или выводу. Параллелограммом обозначается ввод/вывод вообще. Если ввод или вывод осуществляется с использованием конкретных устройств, то блоки ввода/вывода изображаются при помощи специальных фигур. Так, ввод/вывод с использованием дисплея, вывод на печатающее устройство изображаются соответственно фигурами, представленными на рис. 1.1е, 1.1ж.
Комментарий используется в тех случаях, когда пояснение не помещается внутри блока (рис. 8.1з).
В качестве примера изобразим в виде схемы алгоритм вычисления произведения двух натуральных чисел n и m с использованием операции сложения, записанный ранее на естественном языке, добавив этапы ввода/вывода (рис. 8.2). Схема позволяет наглядно представить структуру алгоритма. В частности, на схеме хорошо видны циклы: это последовательности блоков, после последнего из которых осуществляется возврат к началу последовательности (на схеме это — замкнутые участки). Схемы обычно используются для изображения промежуточных вариантов алгоритма. Окончательный вариант, предназначенный для исполнителя–ЭВМ (программа), должен быть записан на алгоритмическом языке.
Рис. 8.2.
В настоящее время существует технология разработки программ без использования схем. Однако независимо от этого на начальном этапе изучения программирования использование схем при разработке алгоритмов целесообразно. Использование схем обеспечивает приобретение прочных навыков разработки алгоритмов, являющихся основой так называемого структурного подхода, особенно плодотворного при постановке и решении на ЭВМ сложны задач.
ГОСТом, помимо типов фигур, предписываются также определенные размеры их сторон, одинаковые размеры блоков. Этих требований необходимо придерживаться при оформлении окончательной документации. На промежуточных этапах разработки алгоритма придерживаться этих требований ГОСТа не обязательно.
Понятие об алгоритмических языках
Алгоритмические языки близки к естественному языку. Именно такая цель ставилась при их разработке. Однако правила построения конструкций в алгоритмической языке более «жесткие». Это означает, что алгоритмически языки допускают меньшее разнообразие для описаний действий алгоритма, чем естественный язык и привычная математическая символика, и машина однозначно понимает любую конструкцию языка. Например, для умножение двух переменных a и b общепринятая математическая символика допускает несколько возможных форм записи: 1) ab 2) а x b 3) а ×b и т. п. А на алгоритмическом языке во например на языке Basic, эту операцию можно записать только единственным образом как a*b. Небольшие, ошибки или описки, допускаемые в предложениях естественного языка и не искажающие, на наш взгляд, смысла, совершенно недопустимы в алгоритмическим языке, где каждый символ и его место в конструкции имеют строго фиксированное значение.
Так как программа на алгоритмическом языке предназначена для выполнения на ЭВМ, то в алгоритмическом языке, помимо средств, описывающих действия алгоритма, обязательно должны быть также определены средства, позволяющие вводить исходные данные в ЭВМ и выводить результаты выполнения программы.
Программа, составленная на алгоритмическом языке, не может быть непосредственно выполнена ЭВМ, так как ЭВМ умеет выполнять только последовательность элементарных операций, а в программе на алгоритмическом языке в одном выражении может, например, содержаться несколько операций, и форма записи такой программы понятна человеку, но недоступна ЭВМ. Поэтому необходимо какое-то промежуточное звено, которое выполняло бы работу по расчленению отдельных действий программы и записи их на машинном языке. Работа эта несложная, но требует скрупулезного внимания и педантичности. К такой работе больше всего и приспособлена ЭВМ. Перевод программы с алгоритмического языка на машинный осуществляется ЭВМ с помощью специальной программы, которая носит название транслятор. В программе-трансляторе «заложены» все правила алгоритмического языка и способы преобразования различных его конструкций на машинный язык. Именно поэтому при составлении программы на алгоритмическом языке нужно скрупулезно придерживаться правил этого языка, иначе ЭВМ вас не поймет или поймет неправильно. Наиболее распространенными алгоритмическими языками в настоящее время являются Basic, Pascal, C.
8.3. Основные структуры алгоритмов
Основные структуры алгоритмов — это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий. Приводимые ниже структуры рекомендуются при использовании так называемого структурного подхода к разработке алгоритмов и программ. Структурный подход предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ.
К основным структурам относятся:
1. Следование. Последовательное размещение блоков и групп блоков. В программе реализуется последовательным размещением операторов.
2. Цикл До (рис. 8.3). Применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия. Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено. Тело цикла — а последовательность действий, которая выполняется многократно (в цикле). Начальные присвоения — задание начальных значений тем переменным, которые используются в теле цикла.
  | |
| Рис. 8.3 | Рис. 8.4 |