Лекция 6. Алгоритмы

План

1.      Понятие алгоритма.

2.      Свойства алгоритмов.

3.      Описание алгоритмов в виде блок-схем.

4.      Средства ввода-вывода информации.

5.      Выбор действий в алгоритмах,

6.      Повторение действий в алгоритмах.

1. Понятие алгоритмов

Алгоритм – это четкое и понятное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели. Алгоритм - последовательность действий со строго определёнными правилами выполнения.

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

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

Для описания алгоритмов мы будем использовать определённую форму записи. Запись алгоритма должна оформляться по следующим правилам.

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

Рассмотрим общую форму записи алгоритма. Справа записан ещё один пример алгоритма – алгоритм приветствия, исполнителем которого может быть ЭВМ:

Алг   «название»                                   алг  « приветствие»

Нач                                                         нач

         <действие 1>                                         вывод Добрый день

         <действие 2>                                         запрос Ваше имя, имя

         <действие 3>                                         вывод Рад встрече, имя

Кон                                                          кон  

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

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

Алг  «написание сочинения»

Нач

         Выбрать тему сочинения

         Продумать и написать план

         Написать черновик сочинения

         Тщательно проверить черновик

         Переписать сочинение начисто

Кон

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

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

В записи вычислительных алгоритмов мы видим новое обозначение – знак   :=.   Этот знак читается «присваивается». Например, запись первой операции    D:= a*b – b*c в этом алгоритме читается: переменной D присваивается значение выражения a*d – b*c. Смысл этой операции состоит в следующем. Исполнитель – ЭВМ или человек – должен вычислить значение переменных     a, b, c и d и присвоить это значение переменной D. Процесс выполнения этой операции можно описать цепочкой соотношений:  D = a * d – b * c = 3 * 2 - 1 * 1        

А конечный результат – равенством: D=5. Полученный результат указан справа от описания алгоритма. Здесь же приведено соотношение D = a*d – b*c, которое поясняет, какой результат будет получен после выполнения присваивания D: = a*d – b*c при произвольных значениях величин a, b, c, d. Соотношение справа – равенство, а в алгоритме записано присваивание. Введение новых обозначений для записи  вычислительных операций связано с особенностью их выполнения в ЭВМ. Эта особенность состоит в том, что результаты всех вычислений, все исходные данные записываются и хранятся в памяти машины. Так, в рассматриваемом  алгоритме решения системы уравнений в памяти должны находиться  величины a, b, c, d, e, f, D, Dx, Dy, x и y. При этом каждая из них должна размещаться в отдельной ячейке памяти.

Выполнение ЭВМ присваивания  D: = a*d – b*c состоит в следующем. ЭВМ извлекает из памяти значения переменных a, b, c, d, вычисляет по ним  значение формулы a*d – b*c и записывает полученное по ним значение формулы.

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

2. Свойства алгоритмов

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

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

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

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

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

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

3. Описание алгоритмов в виде блок-схем

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

Обозначение блока                                Пояснения

                                                   Начало,

                                                   Конец

                                 Вычислительное действие (операция присваивания)                                    

                                              Проверка условия (условный переход)

                                         Ввод исходных данных, вывод результатов               

                                                     Узел

                                                     Линии связи

Например, блок-схема алгоритма вычисления значения функции y = x2 + 2x при х=2, имеет вид:

Вопросы для закрепления:

1.      Что такое алгоритм?

2.      Как выполняются присваивания?

3.      Что такое переменные в алгоритмах?

4.      Каковы основные свойства алгоритмов?

5.      В чем проявляются ошибки в алгоритмах?

Задания:

1. Опишите алгоритм движения от дома до техникума.

2. Составьте алгоритм решения линейного уравнения и приведите примеры его выполнения.

3. Составьте алгоритм решения квадратного уравнения и приведите примеры его выполнения.

4. Составьте блок-схему алгоритма решения следующих задач:

а) решение квадратного уравнения: A * x2 + B * x + C = 0, A = 2, B = 4,  C = 3.

б) определение площади треугольника по основанию и высоте.

в) определение площади треугольника по трем сторонам.

г) вычисление значения функции Y = 3 * X3 + 4 * X2 – 6 * X + 5 при Х = 3.

1.      Средства ввода-вывода информации

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

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

В процессе запроса информации ЭВМ выводит на экран стандартные фразы-запросы (подсказки) и ждет от человека ввода числовых или символьных данных. Вводимые человеком ответы записываются в переменные, имена которых указаны после «подсказки».

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

Вопросы, упражнения и задания для самопроверки:

1.         Составьте сценарий и диалоговый алгоритм решения линейного уравнения.

2.         Составьте алгоритм для рисования фигур: треугольника, кольца, полумесяца.

3.         Каковы размеры экрана ваших ЭВМ в техникуме?

4.         Какими операциями в ЭВМ организуются ввод-вывод сообщений?

5. Выбор действий в алгоритмах

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

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

Условные действия:

если  < условие > то

          < действие >

кесли

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

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

Выбираемые действия:

если  <условие>  то 

           <действия 1> 

иначе

           <действия 2>

 кесли

Правила выполнения: действия 2 выполняются тогда и только тогда, когда соблюдается условие. Действия 2 выполняются, только если условие не соблюдается.

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

Вопросы, упражнения и задания для самопроверки:

1.      Каковы правила выполнения условных действий в алгоритмах?

2.      Каковы правила выполнения выбираемых действий в алгоритмах?

3.      Опишите алгоритм перехода через дорогу (с соблюдением правил дорожного движения).

4.      Составьте алгоритм вычисления значений функции и нарисуйте ее график:

                                                 1 при  x ≥ 1,

                                    y =        0  при  -1 < x < 1,

                                                -1  при  x ≤ -1.

6. Повторение действий в алгоритмах

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

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

Цикл со счетчиком

от  k = l  до  n

цикл

           <действие>

кцикл

Правила выполнения циклов со счетчиком иллюстрируется схемой алгоритма, приведенной справа. До начала цикла счетчик получает начальное значение k = l. Далее выполняются <действия>, а затем проверяется, достиг ли счетчик конечного значения. Если счетчик еще не достиг конечного значения, то он увеличивается на единицу и <действия> выполняются еще раз. Если же счетчик уже достиг конечного значения, то выполнение цикла завершается.

Выполнение пока-цикла можно наглядно представить такой схемой:

Пока-цикл

пока   <условие>    цикл

           <действие>

кцикл

Правила выполнения: если условие выполняется с самого начала, то выполняются и действия; если после этого условия вновь выполнены, то вновь выполняются и действия. Повторение действий продолжается до тех пор, пока выполняются условия. Завершение выполнения цикла происходит тогда и только тогда, когда перестанут выполняться условия повторения.

Вопросы и задания для самопроверки:

1.      Каковы правила выполнения циклов с заданным числом повторений?

2.      Каковы правила выполнения циклов типа пока-цикл?

3.      Как вы думаете, что такое зацикливание алгоритмов?

4.      Как проверяются на примерах алгоритмы с циклами?

5.      Составьте алгоритм подсчета суммы арифметической прогрессии.

6.      Составьте алгоритм вычисления суммы последовательных натуральных чисел от 1 до 10000. Можете ли вы предложить алгоритм, не использующий циклов?

Тест к лекции 6

Алгоритмы.

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

1)      последовательность формул;

2)      блок – схема;

3)      таблица;

4)      словесное описание.

2.      На рисунке часть блок – схемы. Как называется такая вершина:

1)      предикатная;

2)      объединяющая;

3)      функциональная;

4)      сквозная?

3.      На рисунке представлена часть блок-схемы.

Как называется такая вершина:

1)      предикатная;

2)      объединяющая;

3)      функциональная;

4)      сквозная?

4.      На рисунке представлена часть блок – схемы.

Как она называется?

1)      альтернатива;

2)      итерация;

3)      вывод данных;

4)      следование?

5.      На рисунке представлена часть блок – схемы

Как она называется?

1)      альтернатива;

2)      композиция;

3)      цикл с предусловием;

4)      итерация?

6.      На рисунке представлена часть блок – схемы.

Как она называется:

1)      альтернатива;

2)      композиция;

3)      цикл с предусловием;

4)      цикл с постусловием?

7.      На рисунке представлена часть блок – схемы. Как она называется?

1)      альтернатива;

2)      композиция;

3)      цикл с постусловием;

4)      цикл с предусловием?

8.      Как называется конструкция блок – схемы, изображенная на рисунке:

1)      выполнение операции;

2)      начало-конец алгоритма;

3)      вызов вспомогательного алгоритма;

4)      ввод/вывод данных?

9.      Как называется конструкция блок – схемы, изображенная на рисунке:

1)      выполнение операции;

2)      начало-конец алгоритма;

3)      вызов вспомогательного алгоритма;

4)      ввод/вывод данных?

10.  Как называется конструкция блок-схемы, изображенная на рисунке:

1)      выполнение операции;

2)      начало-конец алгоритма;

3)      вызов вспомогательного алгоритма;

4)      ввод-вывод данных?

11.  Как называется конструкция блок-схемы, изображенная на рисунке:

5)      выполнение операции;

2) начало-конец алгоритма;

3) вызов вспомогательного алгоритма;

4) ввод-вывод данных?