«Универсальная» блок-схема и 3 типовых алгоритма 
Дважды за день заходила речь об одном и том же, да и жаль выкидывать пару картинок, могут ещё понадобиться. Речь шла об изображении базовых типовых алгоритмов, связанных с расчётом какой-либо элементарной характеристики последовательности (массива) — суммы, количества, произведения, максимума, минимума и т.п.
В картинках не показаны «начало» и «конец», только содержательная часть.
ГОСТовские «перевёртыши» на практике крайне неудобны, классическое изображение с помощью «ромбика» часто сбивает начинающих с толку похожестью на обычное ветвление (плюс они забывают делать шаг в конце тела цикла),
а вот значок «цикла с параметром», если отказаться от паскалевского шага, непременно равного единице, удобен и нормально воспринимается.
I Алгоритм табулирования (составление списка или таблицы)
Алгоритм табулирования (составление списка или таблицы)
Что писать в фигурках вместо цифр?
1. Примем, что управляющая переменная цикла называется x, а здесь зададим её начальное (x1) и конечное (x2) значения, а также шаг изменения dx. Это можно записать присваиванием x1=0,x2=1,dx=0.1 или поставить вместо прямоугольника параллелограмм (оператор ввода) с подписью «ввод x1,x2,dx«;
2. Обычно внутри значка «цикл с параметром» (цикл, пределы изменения и шаг управляющей переменной которого известны) пишут что-то вроде псевдокода: «для x от x1 до x2 шаг dx» или то же самое в форме x=x1,x1+dx..x2 или просто x=x1,x2,dx ;
3. Для очередного x вычислить y=f(x). Этот шаг может включать несколько действий и предполагать вставку дополнительных блоков «расчёт» или условных операторов;
4. Вывести строку таблицы: вывод x, f(x)
II. Алгоритм вычисления суммы, количества или произведения нужных элементов последовательности
Алгоритм вычисления суммы, количества или произведения нужных элементов последовательности
Вместо цифр в элементах блок-схему указываем:
1. Для каждой искомой величины задать по переменной и присвоить ей начальные значения: сумме s=0, количеству k=0, произведению p=1 (на самом деле, это не совсем корректно, но для обсуждаемого уровня сойдёт);
2. Выполняется как в задаче I;
3. Считаем очередной элемент последовательности y=f(x), с тем же замечанием, что к задаче I;
4-5. Если y отвечает условию задачи (проверка на шаге 4), сумма на шаге 5 ищется в виде s=s+f(x), количество в виде k=k+1, произведение в виде p=p*f(x). При нескольких искомых величинах блок вида 4-5 может повторяться несколько раз;
6. По выходе из цикла выводим найденную величину или величины.
III. Алгоритм поиска максимума или минимума
Блок схема задачи II годится и для этого случая.
1. Для каждого максимума или минимума задать по переменной (примем, что минимум обозначен min, а максимум — max) и присвоить каждой переменной начальные значения: максимуму – заведомо малое значение (например, -1030, оператор будет иметь вид Max=-1030) или первый элемент последовательности (массива); минимуму присвоить заведомо большое значение (например, 1030) или первый элемент последовательности;
2-3. Выполняются как в задачах I-II, с теми же замечаниями.
4-5. Для поиска максимума проверяется условие 4 f(x)>max, выполняется действие 5 вида max=f(x), дли минимума проверяется условие 4 f(x)<min и выполняется действие 5 вида min=f(x). С чем сравнивали max или min, то им и присваиваем.Могут понадобиться дополнительные условия, связанные логической операцией «И» либо «ИЛИ» с основным, например, поиск максимального из отрицательных элементов предполагает проверку y<0 and y>max;
6. По выходе из цикла выводим найденную величину или величины.
Несмотря на обилие средств для рисования блок-схем, удобнее простого Paint из Win7 и выше для этой цели ничего пока не придумали 
IV. Схема ввода и обработки элементов одномерного массива
Как правило, ввод, обработка или вывод одномерного массива (вектора, списка) выполняется поэлементно с помощью цикла с параметром (цикла «for»). Счётчиком цикла служит номер элемента в массиве (обычно применяется нумерация с единицы). Ниже показаны ввод и обработка массива x из 6 элементов.
Схема ввода и обработки элементов одномерного массива
V. Реализация алгоритма в кратных (вложенных) циклах
Основное отличие – все действия над матрицей (таблицей) выполняются поэлементно в двойном цикле следующего вида:
Блок-схема двойного цикла с параметром
Здесь показан ввод матрицы A из 6 строк и 4 столбцов, а счётчиками внешнего и внутреннего цикла с параметром служат номера строки (i) и столбца (j) в матрице. Обработка и вывод элементов матрицы могут быть реализованы аналогичными конструкциями, часто, если элементы обрабатываются последовательно и независимо друг от друга, ввод и обработку или обработку и вывод можно объединить.
31.10.2016, 21:46 [10915 просмотров]
Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи. Решение одной и той же задачи может быть реализовано с помощью различных алгоритмов, отличающихся друг от друга как по времени счета и объему вычислений, так и по своей сложности. Запись этих алгоритмов с помощью блок-схем позволяет сравнивать их, выбирать наилучший алгоритм, упрощать, находить и устранять ошибки.
Отказ от языка блок-схем при разработке алгоритма и разработка алгоритма сразу на языке программирования приводит к значительным потерям времени, к выбору неоптимального алгоритма. Поэтому необходимо изначально разработать алгоритм решения задачи на языке блок-схем, после чего алгоритм перевести на язык программирования.
При разработке алгоритма сложной задачи используется метод пошаговой детализации. На первом шаге продумывается общая структура алгоритма без детальной проработки отдельных его частей. Блоки, требующие детализации, обводятся пунктирной линией и на последующих шагах разработки алгоритма продумываются и детализируются.
В процессе разработки алгоритма решения задачи можно выделить следующие этапы:
- Этап 1 . Математическое описание решения задачи.
- Этап 2 . Определение входных и выходных данных.
- Этап 3 . Разработка алгоритма решения задачи.
Базовые алгоритмические конструкции
В теории программирования доказано, что для записи любого, сколь угодно сложного алгоритма достаточно трех базовых структур:
- следование (линейный алгоритм);
- ветвление (разветвляющийся алгоритм);
- цикл-пока (циклический алгоритм).
Линейные алгоритмы
Линейный алгоритм образуется из последовательности действий, следующих одно за другим. Например, для определения площади прямоугольника необходимо сначала задать длину первой стороны, затем задать длину второй стороны, а уже затем по формуле вычислить его площадь.
Пример
ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.
На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:
Этап 1. Математическое описание решения задачи.
Математическим решением задачи является известная формула:
,
где с-длина гипотенузы, a, b – длины катетов.
Этап 2. Определение входных и выходных данных.
Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.
Этап 3. Разработка алгоритма решения задачи.
| Словесное описание алгоритма | Запись алгоритма на языке блок-схем |
|
На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.
|
Разветвляющиеся алгоритмы
Алгоритм ветвления содержит условие, в зависимости от которого выполняется та или иная последовательность действий.
Пример
ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.
Этап 1. Математическое описание решения задачи.
Из курса математики известно, если x > y, то наибольшее число x, если x < y, то наибольшее число y, если x = y, то число x равно числу y.
Этап 2. Определение входных и выходных данных.
Входными данными являются значения чисел x и y. Выходным данными являются:
- наибольшее число
- любое из чисел, если числа равны
Для решения задачи нам необходимо знать значения x и y.
Этап 3. Разработка алгоритма решения задачи.
| Словесное описание алгоритма | Запись алгоритма на языке блок-схем |
|
|
В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма, которые соответствуют номерам шагов словесного описания алгоритма
В рассматриваемом алгоритме (рис.3) имеются три ветви решения задачи:
- первая: это элементы 1, 2, 3, 4, 8.
- вторая: это элементы 1, 2, 3, 5, 6, 8
- третья: это элементы 1, 2, 3, 5, 7, 8.
Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.
Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.
Циклические алгоритмы
Циклический алгоритм – определяет повторение некоторой части действий (операций), пока не будет нарушено условие, выполнение которого проверяется в начале цикла. Совокупность операций, выполняемых многократно, называется телом цикла.
Алгоритмы, отдельные действия в которых многократно повторяются, называются циклическими алгоритмами, Совокупность действий, связанную с повторениями, называют циклом.
При разработке алгоритма циклической структуры выделяют следующие понятия:
- параметр цикла – величина, с изменением значения которой связано многократное выполнение цикла;
- начальное и конечное значения параметров цикла;
- шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении.
Цикл организован по определенным правилам. Циклический алгоритм состоит из подготовки цикла, тела цикла и условия продолжения цикла.
В подготовку цикла входят действия, связанные с заданием исходных значений для параметров цикла:
- начальные значения цикла;
- конечные значения цикла;
- шаг цикла.
В тело цикла входят:
- многократно повторяющиеся действия для вычисления искомых величин;
- подготовка следующего значения параметра цикла;
- подготовка других значений, необходимых для повторного выполнения действий в теле цикла.
В условии продолжения цикла определяется допустимость выполнения повторяющихся действий. Если параметр цикла равен или превысил конечное значение цикла, то выполнение цикла должно быть прекращено.
Пример
ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 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 Алгоритм с условием (алгоритм ветвления). Зашел в магазин, подошел к прилавку, «МОЛОКО ЕСТЬ», если выполняется «ДА», то купить молоко, выйти из магазина. Если «МОЛОКО ЕСТЬ» выполняется «НЕТ», то выйти из магазина.
№ 3 Циклический алгоритм. Взять тарелку, вымыть ее, проверить условие «ЕСТЬ ЕЩЕ ТАРЕЛКИ?» — если выполняется условие «ДА», то повторить алгоритм сначала. Выполнять алгоритм до тех пор, пока ответом на условие «ЕСТЬ ЕЩЕ ТАРЕЛКИ?» будет «НЕТ». В этом случае закончить алгоритм.
-
Комментариев (0)