Самостоятельная работа на понимание линейной алгоритмической структуры

Содержание
  1. Основные алгоритмические конструкции
  2. 2.4.1. Следование
  3. Вопросы и задания
  4. Электронное приложение к уроку
  5. Алгоритмы и структуры данных для начинающих: сложность алгоритмов
  6. Асимптотический анализ
  7. Порядок роста
  8. Константный — O(1)
  9. Линейный — O(n)
  10. Логарифмический — O( logn)
  11. Линеарифметический — O(n·logn)
  12. Квадратичный — O(n 2)
  13. Наилучший, средний и наихудший случаи
  14. Что мы измеряем?
  15. Продолжение следует
  16. Алгоритмы. Разработка алгоритма решения задачи
  17. Базовые алгоритмические конструкции
  18. Линейные алгоритмы
  19. Пример
  20. Разветвляющиеся алгоритмы
  21. Циклические алгоритмы
  22.  Пример
  23. Тест по информатике Основные алгоритмические конструкции 8 класс
  24. Вариант 1
  25. Вариант 2
  26. Алгоритм ветвления. Отличие от алгоритмов линейной структуры | OTUS
  27. Ещё раз о линейности
  28. Ветвление в алгоритмических последовательностях
  29. Логика разветвляющих алгоритмов
  30. Программный способ записи

Основные алгоритмические конструкции

Самостоятельная работа на понимание линейной алгоритмической структуры

Урок 17. Практическая работа № 5. Основные алгоритмические конструкции. Следование

Ключевые слова:  • следование • ветвление • повторение • линейные алгоритмы • разветвляющиеся алгоритмы 

• циклические алгоритмы 

Человеку в жизни приходится решать множество различных задач. Решение каждой из них описывается своим алгоритмом, и разнообразие этих алгоритмов очень велико. Вместе с тем для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения. Это положение выдвинул и доказал Э. Дейкстра в 70-х гг. прошлого века.

Эдсгер Вибе Дейкстра (1930-2002) — выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

2.4.1. Следование

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

Графическое представление алгоритмической конструкции «следование» приведено на рис. 2.8.

Рис. 2.8. Алгоритмическая конструкция «следование»

Пример 1. Линейный алгоритм приготовления отвара шиповника.

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

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

По команде закрасить Робот закрашивает клетку, в которой он находится.

Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение, обозначенное звёздочкой:

Пример 3. Дан фрагмент линейного алгоритма: х:=2 у:=х*х У:=У*У х:=у*х 

s:=x+y

Выясним, какое значение получит переменная s после выполнения этого фрагмента алгоритма. Для этого составим таблицу значений переменных, задействованных в алгоритме:

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

Пример 4. Некоторый исполнитель может выполнять над целыми числами кроме операций сложения, вычитания, умножения и деления ещё две операции: с помощью операции div вычисляется целое частное, с помощью операции mod — остаток.

Например: 5 div 2 = 2; 5 mod 2 = 1; 2 div 5 = 0; 2 mod 5 = 2.

Покажем, как с помощью этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 500 (k500), 100 (k100), 50 (k50) и 10 (k10) рублей.

Исполните алгоритм для s = 745 и s = 1864. Составьте соответствующие таблицы значений переменных.

Ознакомьтесь с имеющимся в Единой коллекции цифровых образовательных ресурсов модулем для коллективной работы «Линейные алгоритмы» (217039). Совместно с друзьями постарайтесь составить алгоритмы для имеющихся в модуле задач. Пройдите тестирование.

Вопросы и задания

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

2. Какие алгоритмы называются линейными?

3. Приведите пример линейного алгоритма: а) из повседневной жизни; б) из литературного произведения; 

в) из любой предметной области, изучаемой в школе. 

4. Запишите линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение:

5. По алгоритму восстановите формулу. а1:=1/х а2:=а1/х аЗ:=а2/х а4:=аЗ/х у:=а1+а2 у:=у+аЗ 

у:=у+а4

6. Какое значение получит переменная у после выполнения алгоритма? х:=1 у:=2*х у:=у+3 у:=у*х у:=у+4 у:=у*х 

у:=у+5

Восстановите формулу вычисления у для произвольного значения X.

7. Для заданного количества суток (tƒh) требуется определить количество часов (h), минут (m) и секунд (с).

8. Известно, что 1 миля = 7 вёрст, 1 верста = 500 саженей, 1 сажень = 3 аршина, 1 аршин = 28 дюймов, 1 дюйм = 25,4 мм. Пользуясь этой информацией, составьте линейный алгоритм перевода расстояния X миль в километры.

9. Исходное данное — целое трёхзначное число х. Выполните для х = 125 следующий алгоритм. а:=х div 100 b:=x mod 100 div 10 с: =х mod 10 

s:=a+b+c

Какой смысл имеет результат s этого алгоритма?

10. Определите значение целочисленных переменных x и y после выполнения алгоритма. х:=336 y: =8 х:=х div у у:=х mod у

Электронное приложение к уроку

Презентации, плакаты, текстовые файлыВернуться к материалам урокаРесурсы ЭОР

Cкачать материалы урока

 Презентация «Основные алгоритмические конструкции. Следование»

 Презентация «Основные алгоритмические конструкции. Следование» (Open Document Format)

Ссылки на ресурсы ЕК ЦОР

Свободное программное обеспечение:

Источник: http://infoplaneta.ucoz.net/index/urok_18_prakticheskaja_rabota_5_osnovnye_algoritmicheskie_konstrukcii_sledovanie/0-207

Алгоритмы и структуры данных для начинающих: сложность алгоритмов

Самостоятельная работа на понимание линейной алгоритмической структуры

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

Конечно, вы наверняка пользовались списком или стеком, но знаете ли вы, как они работают? Если нет, то вы не можете быть уверены, что принимаете правильные решения относительно того, какой алгоритм использовать.

Понимание алгоритмов и структур данных начинается с умения определять и сравнивать их сложность.

Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, связный список, сортировка и множества.

Если не хочется копаться и разбираться, но есть потребность быстро понять основы оценки сложности, идите сюда.

Асимптотический анализ

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

Сколько времени потребуется на обработку массива из десяти элементов? Тысячи? Десяти миллионов? Если алгоритм обрабатывает тысячу элементов за пять миллисекунд, что случится, если мы передадим в него миллион? Будет ли он выполняться пять минут или пять лет? Не стоит ли выяснить это раньше заказчика?

Все решают мелочи!

Порядок роста

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

«Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных.

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

Константный — O(1)

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

public int GetCount(int[] items){ return items.Length;}

Линейный — O(n)

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

Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.

public long GetSum(int[] items){ long sum = 0; foreach (int i in items) { sum += i; } return sum;}

Логарифмический — O( log n)

Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (Прим. пер.

: в анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность.

Метод Contains бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

Линеарифметический — O(n·log n)

Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. В следующих частях мы увидим два таких примера — сортировка слиянием и быстрая сортировка.

Квадратичный — O(n 2)

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

Например, если массив из тысячи элементов потребует
1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года.

Даже если он будет в сто раз быстрее, работа займет 84 дня.

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

Наилучший, средний и наихудший случаи

Что мы имеем в виду, когда говорим, что порядок роста сложности алгоритма — O(n)? Это усредненный случай? Или наихудший? А может быть, наилучший?

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

К примеру, мы увидим примеры алгоритмов, которые в среднем имеют порядок роста O(1), но периодически могут становиться O(n) (например, ArrayList.add).

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

Самое важное здесь то, что O(n) означает, что алгоритм потребует не болееn шагов.

Что мы измеряем?

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

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

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

Операции, количество которых мы будем измерять, включают в себя:

  • сравнения («больше», «меньше», «равно»);
  • присваивания;
  • выделение памяти.

То, какие операции мы учитываем, обычно ясно из контекста.

К примеру, при описании алгоритма поиска элемента в структуре данных мы почти наверняка имеем в виду операции сравнения. Поиск — это преимущественно процесс чтения, так что нет смысла делать присваивания или выделение памяти.

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

Продолжение следует

На этом мы заканчиваем знакомство с анализом сложности алгоритмов. В следующий раз мы рассмотрим первую структуру данных — связный список.

Перевод статьи «Algorithms and Data Structures»

Источник: https://tproger.ru/translations/algorithms-and-data-structures/

Алгоритмы. Разработка алгоритма решения задачи

Самостоятельная работа на понимание линейной алгоритмической структуры

Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи.

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

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

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

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

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

  • Этап 1 . Математическое описание решения задачи.
  • Этап 2 . Определение входных и выходных данных.
  • Этап 3 . Разработка алгоритма решения задачи.

Базовые алгоритмические конструкции

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

  • следование (линейный алгоритм);
  • ветвление (разветвляющийся алгоритм);
  • цикл-пока (циклический алгоритм).

Линейные алгоритмы

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.

На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:

Этап 1. Математическое описание решения задачи.

Математическим решением задачи является известная формула:

,

где с-длина гипотенузы, a, b – длины катетов.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.

Этап 3. Разработка алгоритма решения задачи.

Словесное описание алгоритмаЗапись алгоритма на языке блок-схем
  1. Начало алгоритма.
  2. Ввод значений длин катетов a и b.
  3. Вычисление длины гипотенузы с по формуле
  4. Вывод значения длины гипотенузы.
  5. Конец алгоритма
На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.

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

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

Циклические алгоритмы

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

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

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

  • параметр цикла – величина, с изменением значения которой связано многократное выполнение цикла;
  • начальное и конечное значения параметров цикла;
  • шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении.

Цикл организован по определенным правилам. Циклический алгоритм состоит из подготовки цикла, тела цикла и условия продолжения цикла.

В подготовку цикла входят действия, связанные с заданием исходных значений для параметров цикла:

  • начальные значения цикла;
  • конечные значения цикла;
  • шаг цикла.

В тело цикла входят:

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

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

 Пример

ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 1 до 100.

Этап 1. Математическое описание решения задачи.

Обозначим сумму натуральных чисел через S. Тогда формула вычисления суммы натуральных чисел от 1 до 100 может быть записана так:

где Xi – натуральное число X c номером i, который изменяется от 1 до n, n=100 – количество натуральных чисел.

Этап 2. Определение входных и выходных данных.

Входными данными являются натуральные числа: 1, 2, 3, 4, 5, …, 98, 99, 100.

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

Параметр циклавеличина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.

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

  • начальное значение параметра цикла равно 1,
  • конечное значение параметра цикла равно n,
  • шаг цикла равен 1.

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

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

S=S+i;              I=I+1;

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

Этап 3. Разработка алгоритма решения задачи.

Введем обозначения: S – сумма последовательности, i – значение натурального числа.

Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.

Словесное описание алгоритмаЗапись алгоритма на языке блок-схем
  1. Начало алгоритма.
  2. Подготовка цикла: S:=0; i=1; n= 100;
  3. Проверка условия. Если i

Источник: https://www.turbopro.ru/index.php/osnovy-programmirovaniya/6836-algoritmy-razrabotka-algoritma-resheniya-zadachi

Тест по информатике Основные алгоритмические конструкции 8 класс

Самостоятельная работа на понимание линейной алгоритмической структуры

15.11.2018Тесты по предметамИнформатика8 класс

Тест по информатике Основные алгоритмические конструкции 8 класс с ответами. Тест включает в себя 2 варианта. В каждом варианте по 7 заданий.

Вариант 1

1. В результате выполнения алгоритма:

а:=10b:=20а:=а-b/2

если а>b

то с:=а+b
иначе с:=b-а
все

переменная с примет значение:

1) 302) 203) 0

4) -20

2. Исполнителю Чертежник был задан алгоритм:

нц 2 разсместиться на вектор (1, -2)сместиться на вектор (-1, 3)

кон

Этот алгоритм можно заменить командой:

1) сместиться на вектор (0, 2)2) сместиться на вектор (-1 , 2)3) сместиться на вектор ( 1, -2)

4) сместиться на вектор (1, 2)

3. Был задан алгоритм:

В результате выполнения этого алгоритма переменная у примет значение:

1) 152) 303) 20

4) 45

4. В результате выполнения алгоритма для х = 150

а:=10b:=x div a

а:=а-b/3

переменная а примет значение:

1) 52) -53) 25

4) 15

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

Для проверки истинности условия отсутствия стены у клетки, в которой находится Робот, используются команды: свер­ху свободно, снизу свободно, слева свободно, справа свободно.

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

нач
пока влево
пока вверх
пока вправо
пока вниз
кон

Количество клеток, соответствующих требованию, что, выполнив предложенную программу, Робот уцелеет и остановится в той же клетке, с которой он начал движение, равно:

1) 22) 103) 4

4) 6

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

7. Запишите название алгоритма, содержащего конструк­цию повторения.

Вариант 2

1. В результате выполнения алгоритма:

а:=50b:=20а:=а-b/2

если а>b

то с:=а+b
иначе с:=b-а
все

переменная с примет значение:

1) -302) 1703) 60

4) 20

2. Исполнителю Чертежник был задан алгоритм:

нц 2 разсместиться на вектор (1 , 3)сместиться на вектор (-2, -5)

кон

Этот алгоритм можно заменить командой:

1) сместиться на (-1, -2)2) сместиться на (2, 4)3) сместиться на (1, -2)

4) сместиться на (3, -6)

3. Был задан алгоритм:

В результате выполнения этого алгоритма переменная а примет значение:

1) 82) 93) 10

4) 7

4. В результате выполнения алгоритма для х = 250:

а:=10b:=x mod a

а:=а-b/2

переменная а примет значение:

1) 102) -53) 25

4) 5

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

Для проверки истинности условия отсутствия стены у клетки, в которой находится Робот, используются команды свер­ху свободно, снизу свободно, слева свободно, справа свободно.

Если Робот начнет движение в сторону нахо­дящейся рядом с ним стены, то он разрушится, и выполнение програм­мы прервется.

нач
пока вниз
пока вправо
пока вверх
пока влево
кон

Количество клеток, соответствующих требованию, что, выполнив предложенную программу, Робот уцелеет и остановится в той же клетке, с которой он начал движение, равно:

1) 12) 103) 4

4) 6

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

7. Запишите название алгоритма, содержащего конструк­цию ветвления.

Ответы на тест по информатике Основные алгоритмические конструкции 8 класс
Вариант 11-22-13-14-15-36. ветвление7. циклический алгоритм (цикл)

Вариант 2

Источник: https://testytut.ru/2018/11/15/test-po-informatike-osnovnyie-algoritmicheskie-konstruktsii-8-klass/

Алгоритм ветвления. Отличие от алгоритмов линейной структуры | OTUS

Самостоятельная работа на понимание линейной алгоритмической структуры

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

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

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

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

И каждое действие исполняется лишь после окончания исполнения предыдущего. Также предполагается наличие определённых исходных данных и результата выполнения.

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

Ещё раз о линейности

Линейная последовательность — самая простая из возможных структур. При наличии линейности команды выполняются в чёткой последовательности и в порядке их записи, то есть друг за другом. Вот линейная алгоритмическая последовательность посадки дерева:1) выкапывание ямки в земле;2) размещение в ямке саженца;3) закапывание ямки;4) поливание места посадки водой.

Такой линейный алгоритм имеет следующую блок-схему:

А вот и общая схема линейного алгоритма:

Ветвление в алгоритмических последовательностях

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

Если на минуту покинуть мир алгоритмизации и программирования, можно спроецировать ветвление на многие жизненные ситуации. Если на улице дождь, человек берёт зонт, если очень жарко, будет выбрана одежда полегче и т. д.

Всё зависит от условия выбора. Как тут не вспомнить рыцаря на распутье из русских народных сказок?

«Направо пойдёшь — жену найдёшь, налево пойдешь — богатым будешь, прямо пойдёшь — смерть найдёшь».

Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».

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

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

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

Компьютерные программы и игры тоже построены на выборе действий. А блок-схема при наличии ветвления приобретает иной вид:

Логика разветвляющих алгоритмов

Логику можно описать следующим образом:

ЕСЛИ ТО ИНАЧЕ

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

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

Для закрепления можно решить задачу.

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

Решение легко описывается посредством схематических блоков:

Следующий пример легко экстраполируется в жизнь. Речь идёт об алгоритме для перехода дороги при наличии светофора. Он имеет следующий вид:1. Подходим к светофору.2. Смотрим, какой горит свет.3. Если зелёный, переходим дорогу.4. Если красный, ждём, пока загорится зелёный, а потом переходим дорогу.

Соответствующая блок-схема:

Программный способ записи

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

То есть надо написать программу, используя для этого команды из СКИ. СКИ — это список команд исполнителя — перечень команд, ему понятных.

А любой исполнитель способен исполнить лишь те команды, которые включены в его СКИ, а если говорить человеческим языком — входят в набор его компетенций.

Для примера можно реализовать алгоритм на языке программирования Pascal. Исходя из вышесказанного, следует использовать команды, входящие в терминологию Pascal.

Простейший пример описания алгоритма с разветвляющейся структурой — условный оператор IF. Полная конструкция этого условного оператора имеет следующий вид:

ifthenelse

Здесь if — это «если», then — это «то», else — «иначе».

Условный оператор работает просто:— вычисляется значение логического выражения, которое расположено после служебного слова IF;— если результат — истина, выполняется оператор 1, который размещён после THEN, причём действие после ELSE пропускается;— если результат — ложь, пропускается уже действие после THEN, а действие после ELSE выполняется с помощью оператора 2.

Теперь можно вспомнить пресловутого витязя на распутье и написать простую программу, реализующую этот алгоритм с помощью соответствующих условных операторов.

program Algoritm_vetvlenia;Var x :string;BeginWriteLn ('Витязь, куда путь держишь?');ReadLn (x);If x='Направо' then writeLn ('Направо пойдёшь — жену найдёшь');If x='Налево' then writeLn ('Налево пойдешь — богатым будешь');If x='Прямо' then writeLn ('Прямо пойдёшь — смерть найдёшь');ReadLn;End.

Попробовать этот алгоритм в работе можно на любом онлайн-компиляторе, поддерживающим Pascal. Но не стоит на этом останавливаться — лучше всего написать собственную программу, что позволит получить максимальную пользу от урока.

Источники:• http://informatic.hop.ru/p33.htm;• https://interneturok.ru/lesson/informatika/6-klass/algoritm-i-ispolniteli/prakticheskaya-rabota-2-sostavlenie-algoritmov;• https://www.turbopro.ru/index.

php/algoritmizatsiya-i-ispolniteli/5210-algoritmy-ponyatie-i-vidy-algoritma-blok-skhemy;• https://www.yaklass.

ru/p/informatika/6-klass/algoritmy-14002/tipy-algoritmov-13610/re-61ead1ff-bc77-453f-ac99-e46da267f3f3.

Источник: https://otus.ru/nest/post/1731/

Ваш педагог
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: