Алгоритмические структуры
Линейный алгоритм
Линейный алгоритм– это алгоритм, в котором все операции выполняются только последовательно (рис.1).
Разветвляющийся (ветвящийся) алгоритм
Разветвляющийся или ветвящийся алгоритм – это алгоритм, в котором последовательность выполнения операций зависит от определенных условий.
Если в алгоритме присутствует «действие 1» и «действие 2» (то есть ветвь 1 и ветвь 2), то это разветвляющийся алгоритм с полной альтернативой (рис.2). Если же вместо «действия 2» предусмотрен переход к выполнению операции «n», которая находится в общей (основной) ветви, то такая форма записи называется неполной альтернативой (рис.3). Во втором случае (то есть в случае неполной альтернативы) в одной из ветвей алгоритма предусмотрены некоторые действия (операции), а во второй ветви нет никаких действий.
Циклический алгоритм
Циклический алгоритм – это алгоритм, в котором многократно выполняются одни и те же действия, например с целью многократного выполнения вычислений по одним и тем же зависимостям при различных значениях входящих в них переменных. Использование циклов существенно сокращает объем алгоритма. Можно выделить три основных типа циклических алгоритмов:
По способу определения числа повторений различают циклы с заранее неизвестным количеством повторений и заранее известным количеством повторений (циклы с параметром).
В цикле с параметром определенная последовательность операций выполняется несколько раз в зависимости от заданной величины, которая называется параметром цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг.
Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием.
В циклах с предусловием условие проверяется на входе (до операций, выполняемых в цикле). В циклах с постусловием условие проверяется после выполнения всех операций внутри цикла. В этом случае операторы тела цикла будут реализованы хотя бы один раз или до тех пор, пока не станет возможным условие выхода из цикла.
В циклах с постусловием сначала выполняются все операции, включенные в цикл, и только после этого проверяется заданное условие. В зависимости от результата проверки осуществляется выход из цикла или его повторение.
Цикл с условием называют также итерационным циклом.
Для изображения циклов с предусловием и постусловием можно использовать символ «Граница цикла» (рис. 4):
Начало цикла 1
Начало цикла 2
Начало цикла 3
Тело цикла 3
Конец цикла 3
Конец цикла 2
Конец цикла 1
Рисунок 5 – Структура алгоритма, содержащего несколько вложенных циклов
Для организации и внутреннего, и внешнего циклов могут использоваться разные типы алгоритмических структур (цикл с параметром, цикл с предусловием, цикл с постусловием).
На рис. 6 представлена блок-схема алгоритма с внутренним циклом. В данном случае и внешний и внутренний циклы организованы на базе алгоритмической структуры «цикл с параметром».
На каждом шаге по внешнему циклу внутренний цикл выполняется несколько раз. Количество внутренних циклов на каждом внешнем цикле зависит от параметра внутреннего цикла.
Пусть, например, задано, что параметр внешнего цикла меняется от 1 до 5 с шагом 1, а параметр внутреннего цикла – от 1 до 10 с шагом 1.
Это означает, что на каждом шаге по внешнему циклу внутренний цикл будет выполняться 10 раз. Так как внешний цикл должен выполниться 5 раз, то внутренний цикл выполнится при этом 50 раз.
Примеры алгоритмов различных типовых структур: линейных, ветвящихся, циклических, с комбинацией типовых структур.
Что такое ветвящийся алгоритм
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений (ветвей). Каждое отдельное направление процесса обработки данных является отдельной ветвью вычислений. Ветвление в программе — это выбор одной из нескольких последовательностей команд при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным или конечным результатам. Признак характеризует свойство данных и имеет два или более значений.
Ветвящийся процесс, включающий в себя две ветви, называется простым, более двух ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых ветвящихся процессов.
Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» — условие выполнено и «нет» — условие не выполнено.
Алгоритмы (turtle) ч. 6
В информатике имеются такие элементарные виды алгоритмов (как виды кирпичиков в конструкторе Лего):
1) линейный (другое название — следование) алгоритм, когда команды (действия, шаги программы), выполняются последовательно друг за другом;
2) ветвящийся (другие названия разветвляющийся, условный) – алгоритм, который содержащий хотя бы одну проверку условия «Если(УСЛОВИЕ)», в результате которой осуществляется переход на один из возможных вариантов решения «ТО» или «ИНАЧЕ» (в «тяжёлых» случаях возможны несколько условий, которые могут содержаться внутри других веток);
3) циклический – алгоритм, который может многократно выполнять одно и то же действие (в «тяжёлых» случаях возможны несколько циклических алгоритмов, вложенных друг в друга). Число повторов в цикле задаётся либо заранее программистом, либо при помощи других способов получения данных (например, кнопки, датчики, взаимодействие с другими компьютерами в сети).
Отметим, что это были элементарные конструкции-кирпичики. Но могут быть конструкции посложнее (можно говорить о сложных, составных кирпичиках). Так, любой элементарный вид алгоритма может содержать в себе другую конструкцию (кирпичик, или несколько кирпичиков) того же вида, или другого, то есть алгоритмические конструкции могут быть вложенными друг в друга, а, значит, могут усложняться просто до безобразия )))
Рассмотрим простые (элементарные) виды алгоритмов на примере трёх Черепашек по именам line, tree, cycle (линия, дерево и цикл).
Линейный алгоритм
Посмотрите, команды для черепашки line следуют одна за другой, и, что очень важно: отступ от левого края у всех команд нулевой.
Ветвящийся алгоритм
Очень важно! При ветвлении после команды if (условие): отступ первой ветки меняется на 4 пробела! Потом идёт команда else: и опять она имеет нулевой отступ. А затем снова 4 пробела для отступа!
Отметим, что черепашка cicle пошла прямо 4 раза и столько же раз повернула налево. В Scratch такое тоже было. Давайте вспомним.
ВАЖНО-ПРЕВАЖНО! Фраза range(8) создаёт ряд чисел от 0 до 7, а фраза for i in позволяет переменной i «пробежаться» по ряду.
Линейный, ветвящийся и циклический алгоритмы в Scratch
Сложный алгоритм в Scratch
Как видим, даже в сложном алгоритме пока что ничего сложного ))) Если всё понятно, то теперь можно переходить к изучению более сложных вещей! Например, рисование красивых геометрических фигур, или ввод чисел с клавиатуры, или разговоры с черепашкой.
Виртуальная лаборатория МЭШ — Подготовка к КЕГЭ, олимпиадам, изучение языков Python, C++, C#, Java (ID приложения:
263764)
Сайт Silvertests.ru — подготовка к КЕГЭ, олимпиадам
(там же C, C++, Java, Pascal, PHP, …)
ReplIT — черепашка онлайн и не только
Алгоритмы ветвящейся структуры
Алгоритмом ветвящейся структурыбудем называть такой алгоритм, котором выбирается один из нескольких возможных путей (вариантов) вычислительного процесса.
Каждый подобный путь называется ветвью алгоритма.
Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения (проверяемое условие) и в зависимости от истинности или ложности проверяемого условия для выполнения выбирается та или иная ветвь алгоритма. Алгоритм предполагает выполнение Действия 1,если записанное условие истинно (выполняется), и выполнение Действия 2,если условие ложно (не выполняется).
В частном случае может отсутствовать один из блоков «Действие 1» или «Действие 2».
Пусть, например, В — проверяемое условие, a SI, S2 — некоторые выполняемые инструкции (действия). Тогда: Если условие В выполняется (истинно), то
выбрать для исполнения S1, иначе
выбрать для исполнения S2 Запишем ветвящийся алгоритм на псевдокоде и графически:
Существуют задачи, связанные с вычислением функций, заданных несколькими арифметическими выражениями (формулами). Приведем пример такой задачи.
Пример.
Вычислить значение Y по одной из формул:
Алгоритм Bemel;
Переменные х, у вещественные; Начало
Ввод (х);
Если х Р [80, если 5
Циклический Алгоритм
Реализует повторение некоторых действий. Иными словами, циклические алгоритмы включают в себя циклы.
Циклом называется последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров.
Примером циклических алгоритмов может служить алгоритм покраски забора. Действительно, рассмотрим этот алгоритм в словесно-формульном виде:
ШагI. Подготовить исходные данные (забор, краску, кисть).
Шаг II.Подойти к забору.
Шаг III.Обмакнуть кисть в краску.
ШагIV. Нанести краску кистью на поверхность забора.
ШагV. Если забор еще не весь окрашен, то повторить алгоритм, начиная с пункта (Шаг III).
Существует несколько видов циклических инструкций, с помощью которых можно организовать циклы.
1. Инструкция «цикл с параметром»(цикл с заданным количеством повторений).
х — параметр цикла (является счетчиком количества повторений);
a, b — соответственно начальные и конечные значения параметра цикла;
h — шаг, с которым изменяется параметр цикла; S — оператор (инструкция), повторяемый в цикле. Общий вид структуры цикла с параметром будет:
Для х := а до b с шагом h повторять S
2. Инструкция «циклс предусловием»(цикл-«пока»):
В — некоторое проверяемое логическое условие;
S — оператор (инструкция), повторяемый в цикле.
Тогда инструкция в псевдокоде примет вид:
 |
| Выход из цикла |
Блок-схема такого цикла имеет вид:
3. Инструкция «циклс постусловием» (цикл-«до>>):
Пока В повторять S
 |
| Выход из цикла |
Блок-схема такого цикла имеет вид:
 | |
 |  |
 | |
 | |
 | |
 |
 |
Контрольные вопросы
1. В зависимости от особенностей своего построения
алгоритмы делятся на несколько основных групп:
Некоторые из этих понятий не относятся к основным группам алгоритмов. Укажите, какие именно.
2. «Линейным называется алгоритм, в котором все эта
пы решения задачи выполняются строго последовательно».
Верно ли данное высказывание?
3. «Алгоритмом ветвящейся структуры называется та
кой алгоритм, в котором выбирается один из нескольких
возможных путей (вариантов) вычислительного процесса».
Верно ли данное высказывание?
4. Циклом называется:
а) этап решения задачи, выполняемый строго последо
вательно;"
б) последовательность действий, выполняемых много
кратно, каждый раз при новых значениях параметров;
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
| Выход из цикла |
| а) блок-схема № 1 |
Укажите, какая из вышеприведенных блок-схем является блок-схемой алгоритма циклической структуры? 7. Ниже приведены блок-схемы циклических алгоритмов:
Выход из цикла 6) блок-схема № 2
Укажите, какая из вышеприведенных блок-схем является блок-схемой цикла с постусловием?
Ответы
1. Правильный ответ — в.
2. Правильный ответ — ДА.
3. Правильный ответ — ДА.
4. Правильный ответ — б.
5. Правильный ответ — б.
6. Правильный ответ — а.
7. Правильный ответ — б.
Язык программирования Pascal Понятие о языках программирования
Итак, мы с вами уже познакомились с одним из основных понятий всего нашего курса — понятием алгоритма. Рассмотрели так же его свойства и способы записи.
Вспомним, так же, что составленный алгоритм решения задачи следует перевести на язык, понятный ЭВМ, аналогично тому, как алгоритм, записанный на русском языке, нужно перевести на французский, если исполнителем является француз. Мы говорили, что такие (понятные ЭВМ) языки называются языками программирования, запись алгоритма на таком языке называется программой, а процесс перевода алгоритма на указанный язык — программированием.
Теперь, наконец, настало время перейти к изучению одного из таких языков. Как и в большинстве стран мира в качестве обучающего мы с вами будем использовать язык программирования Pascal.
Дадим вначале более строгие общие понятия и определения.
Под программойпонимают описание, воспринимаемое ЭВМ и достаточное для решения определенной задачи. Иначе говоря, программа — это упорядоченный список команд, необходимых для решения некоторой задачи.
Для создания программ используют те или иные системы программирования.
Под системой программирования понимают совокупность языка программирования и виртуальной машины, обеспечивающей выполнение на реальной машине программ, составленных на этом языке.
Языком программирования называют систему обозначений, служащую в целях точного описания алгоритмов для ЭВМ или, по крайней мере, достаточную для автоматического нахождения такого алгоритма. Эти языки являются искусственными языками со строго определенным синтаксисом.
Виртуальная машина — это программный комплекс, эмулирующий работу реальной машины с определенным входным языком на ЭВМ с другим, машинным языком, а
 |
 |
 |
 |
 |
 |
 |
 |
 |
иными словами, реализующий входной язык программирования.
Такая техника реализации языка программирования позволяет сделать последний удобным для использования человеком. Виртуальная машина содержит транслятор и/или интерпретатор и может включать библиотеки стандартных подпрограмм, отладчик, компоновщик и другие сервисные средства.
Что такое ветвящийся алгоритм
Рассмотрим несколько задач, решение которых на компьютере получается с помощью ветвящихся алгоритмов.
Первая задача: даны два числа; выбрать большее из них.
Пусть исходными данными являются переменные А и В. Их значения будут задаваться вводом. Значение большего из них должно быть присвоено переменной С и выведено на экран компьютера. Например, если А = 5, В = 8, то должно получиться: С = 8.
Блок-схема алгоритма решения этой задачи изображена на рис. 3.6.
 |
| Рис. 3.6. Алгоритм выбора большего из двух чисел (с полным ветвлением) |
Нетрудно понять смысл этого алгоритма. Если значение переменной А больше, чем В, то переменной С присвоится значение А. В противном случае, когда А В. Изучая базы данных и электронные таблицы, вы узнали, что такое отношение является логическим выражением. Если оно справедливо, то результатом будет логическая величина "истина" и выполнение алгоритма продолжится по ветви "да"; в противном случае логическое выражение примет значение "ложь" и выполнение алгоритма пойдет по ветви "нет".
До выполнения на компьютере правильность алгоритма можно проверить путем заполнения трассировочной таблицы. Вот как будет выглядеть трассировка нашего алгоритма для исходных значений А = 5, В = 8.
| Шаг | Операция | А | В | С | Проверка условия |
| 1 | ввод А, В | 5 | 8 | ||
| 2 | А>В | 5 | 8 | 5 > 8, нет (ложь) | |
| 3 | С:=В | 5 | 8 | 8 | |
| 4 | вывод С | 5 | 8 | 8 |
Ветвление является структурной командой. Его исполнение происходит в несколько шагов: проверка условия (выполнение логического выражения) и выполнение команд на одной из ветвей "да" или "нет". Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге.
В алгоритме на рис. 3.6 используется полное ветвление. Эту же самую задачу можно решить, применяя структурную команду неполного ветвления. Блок-схема такого алгоритма изображена на рис. 3.7.
 |
| Рис. 3.7. Алгоритм выбора большего из двух значений (с неполным ветвлением) |
Выполните самостоятельно трассировку этого алгоритма для вариантов 1) А = 0,2, В = 0,3; 2) А = 7, В = 4; 3) А = 5, В = 5. Если вы все проделаете правильно, то убедитесь, что алгоритм верный.
А теперь запишем рассмотренные алгоритмы на Алгоритмическом языке (АЯ). Во-первых, нужно решить вопрос о том, как описать переменные в этом алгоритме. Вспомним, что для всех переменных в алгоритме на Алгоритмическом языке необходимо указать их тип.
Как выглядит команда ветвления, вы уже знаете. Вот два алгоритма на АЯ, соответствующие блок-схемам на рис. 3.6 и 3.7:
| алг БИД1 вещ А, В, С нач ввод А, В если А>В то С:=А иначе С:=В кв вывод С кон | алг БИД2 вещ А, В, С нач ввод А, В С:=А если В>А то С:=В кв вывод С кон |
Под сокращенным названием алгоритмов ВИД подразумевается "Большее из двух".
Для программирования характерно то, что одна и та же задача может быть решена с помощью разных алгоритмов. И чем сложнее задача, тем больше можно придумать различных алгоритмов ее решения. Для больших задач (производственных, научных) практически невозможно точное совпадение алгоритмов, составленных разными программистами.
Следующая задача: упорядочить значения двух переменных X и Y по возрастанию. Смысл этой задачи следующий: если для исходных значений переменных справедливо отношение X Y (например, X = 2, Y = 1), то выполнить обмен значениями.
Алгоритм обмена значениями двух переменных был рассмотрен в предыдущем параграфе. Вспомним, что для обмена нужна третья вспомогательная переменная.
В алгоритме решения данной задачи используется неполное ветвление. Приведем блок-схему (рис. 3.8) и алгоритм на АЯ.
алг СОРТИРОВКА
вещ X, Y, С
нач ввод X, Y
если X>Y
то С:=Х
Х:=Y
Y:=С
кв
вывод X, Y
кон
Здесь роль вспомогательной переменной для обмена выполняет С.
Сложные ветвящиеся алгоритмы
Получим алгоритм решения еще одной задачи: найти наибольшее значение среди трех величин: А, В, С.
Естественно, возникает следующая идея этого алгоритма: сначала нужно найти большее из значений АИВИ присвоить его какой-то дополнительной переменной, например D; затем найти большее среди D и С. Это значение можно присвоить той же переменной D.
алг БИТ1
вещ А, В, С, D
нач ввод А, B, С
если А>В
то D:=A
иначе D:=B
кв
если C>D
то D:=C
кв
вывод D
кон
Эту же задачу можно решить с помощью алгоритма, имеющего структуру вложенных ветвлений. Его блок-схема приведенная на рис. 3.10.
А вот как выглядят описание этого алгоритма на АЯ и трассировочная таблица при А = 5,В = 7,С = 2.
| Шаг | Операция | А | В | С | D | Проверка условия |
| 1 | ввод А, В, С | 5 | 7 | 2 | - | |
| 2 | А>В | 5 | 7 | 2 | - | 5 > 7, нет |
| 3 | В>С | 5 | 7 | 2 | - | 7 > 2, да |
| 4 | D:=B | 5 | 7 | 2 | 7 | |
| 5 | вывод D | 5 | 7 | 2 | 7 |
1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в апострофах. Например, по команде
Определите, какая задача решается по следующему алгоритму:
