[Gl]лекция 10. Основы алгоритмизации[:]

Этапы решения задачи на компьютере

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

В этом случае процесс решения задачи на компьютере включает в себя следующие основные этапы:

1. Постановка задачи.

2. Выбор метода решения (построение математической модели).

3. Разработка алгоритма.

4. Составление программы.

5. Реализация программы на компьютере.

6. Анализ полученных результатов.

Постановка задачи.Чтобы выбрать метод решения, разработать математическую модель, необходимо четко представлять, чем мы располагаем – какие есть исходные данные, каковы ограничения на них. И, конечно же, никакую задачу нельзя решить, если не понимать, что будет являться решением задачи, что должно стать результатом всего процесса решения. На эти вопросы может помочь ответить правильная постановка задачи. Так, если задача конкретная (например, надо решить уравнение 2х²+3х+5=0, где коэффициенты уравнения - константы), то под постановкой задачи понимаем ответ на вопросы:

какие исходные данные известны;

что требуется определить.

Если задача обобщенная (например, надо решить квадратное уравнение ax²+bx+c= 0), то отвечать при постановке задачи понадобится еще на третий вопрос: какие данные допустимы. Итак, постановка задачи "решить квадратное уравнениеax²+bx+c= 0" выглядит следующим образом:

Дано: a,b,c- коэффициенты уравнения.

Требуется: x1,x2 - корни у равнения.

Ограничения: a<>0 иD=b²–4ac>=0

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

Выбор метода решения (построение математической модели).Разрабатывать алгоритм как последовательность действий будущего исполнителя, направленных на решение задачи, можно лишь тогда, когда ясно, как решать задачу, в чем ее смысл, сложность, к какому классу задач она принадлежит, какой способ, метод решения наиболее адекватно будет соответствовать реальным явлениям и процессам. Таким образом, речь идет о выборе метода решения в простейшем случае и о построении математической модели реальной задачи в более сложной ситуации. Действительно, компьютер решает задачу, выполняя команды нашего алгоритма, выраженные на языке программирования. Но мы знаем, какой вид приняли эти команды, попав в память компьютера: они имеют вид электрических сигналов, соответствующих двоичному способу кодирования. Обработка этих сигналов, выполнение требуемых операций происходит в компьютере по законам алгебры логики и двоичной системы счисления. Это возможно, если все действия, необходимые для решения задачи, формализованы, то есть, представлены как математические операции и соотношения между входящими в них переменными. В случае большого числа параметров, ограничений, возможных вариантов исходных данных модель явления может иметь очень сложное математическое описание (правда, реальное явление еще более сложно), но если такого описания не будет, то переложить решение задачи на компьютер вряд ли удастся. Поэтому часто построение математической модели требует упрощения требований задачи, отказа от некоторых ограничений. А для решения квадратного уравнения, когда необходимо получить значения его корней (если они есть), мы можем воспользоваться известными из курса алгебры формулами. На уроках математики доказывалась правильность метода решения квадратного уравнения путем вычисления по формулам x₁=,x₂=

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

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

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

Реализация программы на компьютере.Это значит, что текст программы вводят с клавиатуры в оперативную память и проводят ее отладку. Отладка компьютерной программы означает не только устранение синтаксических ошибок, в поиске которых помогает транслятор. Также должна обязательно производиться проверка работы программы на конкретных вариантах исходных данных, подобранных так, чтобы охватить все возможные для данной задачи случаи. Например, если это программа решения квадратного уравнения, то нужно проверить ее работоспособность как для варианта значений коэффициентовa,b,c, при которых дискриминантD>0, так и при таком вариантеa,b,c, когдаD < 0. Отметим, что здесь речь идет о проверке именно работоспособности программы. Это означает проверку возможности работы всех ее альтернативных ветвей от начальной команды программы до предусмотренного условием задачи выхода из программы (остановки), в том числе проверку отсутствия неправильной организации циклов (в частности, зацикливания).

Анализ полученных результатов.Анализируя получаемые результаты такого контрольного расчета, в случае их правильности можно сделать вывод о правильности всех предшествующих программированию этапов. Как же определить, что результаты получены правильные? Для этого в зависимости от класса решаемой задачи применяют разные подходы:

сравнивают полученные результаты с результатом, рассчитанным в соответствии с тем же методом, но вручную или с помощью калькулятора. Для приведенного выше примера это означает сравнение значений корней квадратного уравнения, полученных при компьютерном расчете, со значениями тех же корней, предварительно рассчитанных вручную. Условием правомерности такого сравнения является расчет этих значений в обоих случаях одним и тем же методом и при одинаковых наборах значений коэффициентов уравнения. Для предварительных расчетов вручную обычно подбирают исходные значения, облегчающие их проведение. Так, для коэффициентов a,bиcв случае различных действительных корней удобными являются соответственно значения 1; 3; -4, для случая двух действительных совпадающих корней - значения 1; 2; 1, а при отсутствии действительных корней - значения 1; 3; -4;

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

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

Понятие алгоритма. Исполнители алгоритмов. Свойства алгоритмов. Типы алгоритмов и формы их представления

Понятие алгоритма используется давно. Сам термин "алгоритм" произошел при переводе на европейские языки имени арабского математика IX в. Аль-Хорезми, которым были описаны правила (алгоритмы) выполнения основных арифметических действий в десятичной системе счисления.

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

Алгоритм– это организованная последовательность конечного числа точных и понятных действий (команд, директив), необходимых для решения задачи опредленного типа.

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

Исполнители алгоритмов.Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя, ведь выполнимость алгоритма зависит от того, какие действия может совершить исполнитель (или как говорят, входят в его репертуар). Например, прочесть алгоритм решения системы линейных уравнений графическим методом сможет и первоклассник, а выполнить его, конечно же, нет. С другой стороны, малыш четырех-пяти лет не сможет прочесть правила (алгоритм) поведения за столом во время еды, но выполнить их сможет, если ему о них рассказать и показать, что они означают.

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

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

От компьютера, как от любого другого исполнителя, требуется четкое выполнение команд алгоритма. А от нас, как от разработчиков алгоритмов работы компьютера, требуется знание и соблюдение правил их составления. Эти правила заключаются в том, что алгоритм, предназначенный для исполнения автоматом, должен обладать пятью свойствами (удовлетворять пяти требованиям). Эти требования нашли отражение и в приведенном выше определении алгоритма. Требования к алгоритму объясняются тем, что такой исполнитель не имеет своего интеллекта, его возможности всегда ограничены.

Свойства алгоритмов (требования к алгоритмам).

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

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

Детерминированность. Будучи понятным, алгоритм не должен содержать команды, смысл которых может восприниматься неоднозначно. (Например, робот будет поставлен в тупик командой "Взять две-три ложки песка": что значит "две-три"?, какого песка?). Кроме того, недопустимы ситуации, когда после выполнения очередной команды исполнителю не ясно, какую команду выполнять на следующем шаге.

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

Массовость. Разработка алгоритмов – процесс интересный, творческий, но непростой, требующий многих, часто коллективных, умственных усилий и затрат времени. Поэтому предпочтительно разрабатывать алгоритмы, обеспечивающие решение всего класса задач данного типа. Например, если составляется алгоритм решения квадратного уравненияax²+bx+c=0, он должен быть вариативен, то есть обеспечивать возможность решения для любых допустимых исходных значений коэффициентовa,b,c. Про такой алгоритм говорят, что он удовлетворяет требованию массовости.

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

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

Задача. Вычислить площадь круга.

Дано: R, радиус круга.

Требуется: S, площадь руга.

Связь: S=3.14R².

Запишем алгоритм словесно (на русском языке). То есть запишем последовательность команд, выполнение которых позволит при заданном значении радиуса круга найти его площадь:

Прочесть (получить) значение R. (ВВОД ДАННЫХ)

Присвоить переменной S значение выражения 3,14*R*R. (КОМАНДА ПРИСВАИВАНИЯ)

Записать (вывести) полученное значение S. (ВЫВОД РЕЗУЛЬТАТА)

Короче можно записать так:

Прочесть значение R

S := 3,14*R*R

Записать значение S

Знак ":=" означает "присвоить". Запись А:=А+2 в программировании она означает команду присваивания. Сначала исполнитель вычисляет значение выражения, стоящего в правой части, а затем полученное значение присваивает переменной, стоящей в левой части. Например, после выполнения команд х:=3; х:=х*5 переменная х примет значение 15.

Графическая форма представления основана на замене типичных алгоритмических команд определенными геометрическими фигурами.

Блок ввода

Блок вычисления

Блок вывода

Разветвляющиеся алгоритмы. Команда ветвления.

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

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

Задача: вычислить y=|x|.

Дано: х – значение аргумента.

Требуется: у – значение функции. Связь: y =

Словесное представление:

Прочесть значение x.

Если х>=0 то

y:= х

иначе

у:=– х

Конец ветвления

Записать значение у

Упражнение. Какое значение примет Z в результате выполнения алгоритма

X:=3; Y:=4

ЕСЛИ X>Y, ТО Z:=X*X+Y

ИНАЧЕ Z:= Y*Y+X

Конец ветвления

Z:=2*Z

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

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

Здесь Q - проверяемое условие; P₁, P₂, …, P_n- действия, которые должны быть выполнены в случае истинности условия Q (положительная ветвь ветвления); T₁, T₂, …, T_m- действия, выполняемые, если условие Q ложно (отрицательная ветвь ветвления).

При словесном представлении алгоритма полная условная конструкция реализуется командой ветвления вида:

Если Q то

P₁

P₁

…

P_n

иначе

T₁

T₂

…

T_m

Конец ветвления

Циклические алгоритмы. Команда повторения

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

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

Рассмотрим графическое представление циклического блока алгоритма. В него входят в качестве базовых следующие структуры: логический элемент с проверкой условияРи блокS, называемый телом цикла. Здесь тело циклаSрасположено после проверки условияР(цикл с предусловием), поэтому может случиться, что при определенных условиях блокSне выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называетсяцикл-пока. При словесном представлении алгоритма команда, организующая повторение вцикле-покаимеет вид:

Пока Р повторять

S

Конец цикла

Таким образом, если Р не выполняется, то предусмотрен выход из цикла на команду, записанную после строки "Конец цикла". Здесь условие Р - это условие на продолжение цикла.

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

Повторять

S

пока не Р

Конец цикла

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

Для примера напишем блок-схему алгоритма вычисления суммы всех натуральных чисел от 1 до введенного пользователем N. Надо отметить, что можно было бы обойтись линейным алгоритмом, используя формулу суммыnчленов арифметической прогрессии. Однако нам интересно именно на этом простом примере проиллюстрировать работу циклического алгоритма.

Дано n=10.

Найти S=1+2+…+10.

Учитывая то, что S_i+1= S_i+i+1, где S_i=1+2+…+i.

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

Шаг
0	S:=0;	Усовершенствуем, программу, введя новую переменную i, которая пробегала бы все числа от 1 до 100.	S:=0;		S:=0; i:=0;
1	S:=S+1;		i:=1; S:=S+i;		i:=i+1; S:=S+i;
2	S:=S+2;		i:=2; S:=S+i;		i:=i+1; S:=S+i;
3	S:=S+3;		i:=3; S:=S+i;		i:=i+1; S:=S+i;
	…		…		…
100	S:=S+100;		i:=100; S:=S+i;		i:=i+1; S:=S+i;

i:=i+1;

S:=S+i;

Итак, тело нашего цикла:

Найдем условие продолжения цикла. Так как перед входом в цикл значение переменной i равно 0. Поставим условие продолжения <100, т.е. i =0,1,2,…,99.

[kgl]