Понятия алгоритма и блок-схемы
Алгоритм - конечная последовательность точно определенных действий, которые должны быть выполнены для решения поставленной задачи. Наиболее распространенные типы алгоритма - словесный и графический. В первом случае алгоритм составлен на естественном или математическом языке. Во втором - в видекомпактной формы из графических знаков с указанием связеймежду ними. Алгоритм, реализованный в виде программы - конечный продукт, готовый для ввода в ЭВМ. Можно в принципе сразу писать программу в среде, но если она сложна, то целесообразно сначала составить графическую иллюстрацию. Эта иллюстрация называется блок-схемой.
Алгоритмы можно классифицировать как линейные, разветвляющиеся и циклические. Линейные алгоритмы представляются программой, в которой каждая операция выполняется последовательно одна за другой.
Линейные программы
Приведем пример реализации вычислительной формулы
F=((A+B)2- tg2x/ÖA + B+ln(1+ex).
В символах среды Excel это выражение имеет вид
F=((A+B)^2 - TAN(X)^2)/(A + В)^(1/2) + LN(1+EXP(X))
В этом примере алгоритм линейный и его приведенная реализация весьма проста. Однако для примера словесного алгоритма и применения блок-схемы разобьем выражение на части и рассмотрим весь ход решения задачи от составления алгоритма до реализации его в виде программы.
Словесный алгоритм:
1. Ввести значения А, В, X.
2. Вычислить числитель функции F.
3. Вычислить знаменатель функции F.
4. Вычислить функцию F.
5. Напечатать значение функции F.
Графический алгоритм (блок-схему) приведем на рис. 1.
| Ввод данных |
| Ч=числитель |
| З=знаменатель |
| F=Ч/З |
| Печать результата |
Рис.1. Блок-схема линейного алгоритма
Замечание. В основном линейные программы реализуют арифметические выражения. Поэтому желательно их перед составлением программ оптимизировать с целью уменьшения команд и операторов.
Разветвляющиеся программы
Эти программы реализуются на основе операторов если. Кроме того, возможны варианты с использованием логических операций типа И для сравнения двух и более соотношений в этих операторах. Перечисленные операторы относятся к группе операторов, реализующих средства автоматизации. Они позволяют компьютеру перевести логику решения задачи на язык программы, с помощью которой ЭВМ может "сама" принимать решения, т.е. нарушать естественный порядок действий на основе управления передачей управления.
Оператор если
Простейший формат записи оператора:
если условие оператор1;оператор2
Здесь условие – выражение (в простейшем случае сравнение двух чисел), которое можно трактовать как истинное или ложное.
В условии используется знак соотношения, принимающий одно из следующих значений:
<, >, =, <=, >=
Правило: Если условие выполняется, т.е. результат сравнения является истинным, то управление передается на оператор1, а если не выполняется - то на оператор2, следующий сразу за оператором ЕСЛИ, который в свою очередь может содержать условие.
Приведем примеры.
Пример 2. Вычислить функцию F=sin(x) для х > 1. Вычисление провести для нескольких значений Х.
Словесный алгоритм:
6. Ввести значение X.
7. Проверка значения Х. Если Х>1, то перейти к п.3, в противном случае перейти к п.1
8. Вычислить функцию F.
9. Напечатать значение функции F. Перейти к п.1
| Ввод Х |
| да |
| нет |
| F=SIN(X) |
| Вывод результата |
| X>1 |
| X >1 |
| X <=1 |
Рис. 2. Блок-схема разветвляющегося алгоритма
Пример 3. Вычислить функцию F, если ввод параметров А, В, С, X организован с клавиатуры и на экран монитора выдается сообщение о прохождении решения по конкретной ветви - печать результатов в программе должна быть одна. Функция F имеет вид:
| sin2(X+A)+e2-AX2+BX + C, если А/В>1 F= cos(X2-B)+tg3(X)-ln(AX2-B), еслиА/B<=1 |
Словесный алгоритм:
1. Ввести значения А, В, С,X.
2. Вычислить значение Z=A/B.
3. Проверить значение Z. Если Z>1, перейти к п.4, иначе перейти к п.6
4. Вывести текст “Z>1”.
5. Вычислить F=Sin(X+A)…..Перейти к п.8
6. Вывести текст “Z<1”.
7. Вычислить F=Cos(X2-B)…….
8. Напечатать значение функции F.
| Ввод A,B,C,X |
| да |
| нет |
| F=SIN(X+A)^2……… |
| Вывод результата F |
| Z>1 |
| Z >1 |
| Z <=1 |
| Z=A/B |
| F=COS(X^2-B)…….. |
| Вывод текста “Z>1…” |
| Вывод текста “Z<=1….” |
Рис. 3. Блок-схема алгоритма для примера 3
Логический оператор И.
Логическая операция И часто используется для комбинации двух и более соотношений.
Например:
если одновременно А>2.5 и В<3.65.
В символах среды Excel это выражение имеет вид:
ЕСЛИ(И(А>2,5;B<3,65))
ПРИМЕР 4. Вычислить значение функции Z по одной из трех формул в зависимости от того, какое значение аргумента X будет задано. Используем логические операторы ЕСЛИ и И.
| 3x+Ö1+x2, если x<0 Z=2xcos(x)e -2x, если 0<= x<=1 2sin(3x), если x>1 |
Словесный алгоритм:
1. Ввести значение X.
2. Проверить значение Х. Если Х<0, перейти к п.3, иначе перейти к п.4
3. Вычислить Z=3X+Ö…..Перейти к п.7
4. Проверить нахождение Х в интервале [0,1]. Eсли “да”, то переход к п.5,иначе к п.6
5. Вычислить Z=2XCos(X)…….Перейти к п.7
6. Вычислить Z=2Sin(3X)…….
7. Напечатать значение функции Z.
| Ввод ,X |
| Z=3X+ Ö ……… |
| Вывод результата Z |
| да |
| нет |
| X<0 |
| X <0 |
| Z=2SIN(3X) |
| X>=0 и X<=1 |
| да |
| нет |
| Z=2XCOS(X) ……. ……… |
Рис. 4. Блок-схема алгоритма для примера 4 (сложное условие)
Циклические процессы
Если вычисления по одним и тем же формулам нужно повторить несколько раз при различных значениях переменных, входящих в эти формулы, то необходимо организовать ЦИКЛИЧЕСКИЙ вычислительный процесс.
Применение алгоритмов циклической структуры позволяет существенно сократить объем программы.
Для организации цикла необходимо выбрать ПАРАМЕТР ЦИКЛА - простую переменную, которая будет изменять свое значение при каждом повторении цикла и управлять работой цикла, а также предусмотреть 4 основных действия:
1. Задание начального значения параметра цикла.
2. Рабочий участок (или " тело цикла ") - повторяемые в цикле действия, необходимость
которых вытекает непосредственно из математической постановки задачи.
3. Изменение параметра цикла.
4. Проверка условия окончания повторений цикла и переход к его началу, если повторения не закончены.
Пример 5. Вычислить все квадраты чисел от 1 до 100. Формализация этой задачи в математическом смысле означает вычисление значении Y = N2 для (N=l,...,100).
Словесный алгоритм:
1. Ввести значение N=0.
2. Вычислить значение N=N+1
3. Вычислить значение функции Y
4. Напечатать значение функции Y.
5. Проверить значение N. Если N<100, перейти к п.2, иначе окончание счета
| да |
| нет |
| Ввод N=0 |
| Y=N2 |
| Вывод результата Y |
| N=N+1 |
| N<100 |
| Конец счета |
Рис. 5. Блок-схема циклического алгоритма для примера 5
Пример 6. В этом примере надо вычислить значения функции F для значений Х, изменяющимся с постоянным шагом D. Значения А, В, С – постоянны.
Fi =Сos2(Хi + А/В)-A-Sin(Xi +C), где Xi+1=Xi+D,
D- const, (i=0,1, 2,...,10), X0 =e-a/b
Здесь параметр I будет управлять количеством повторов при вычислении (11 раз)
Начальное значение переменной цикла I равно нулю, конечное равно 10.
Словесный алгоритм:
1. Ввести значения A, B, C, D.
2. Присвоить начальное значение I=0
3. Вычислить значение X=e-a/b
4. Вычислить значение функции F=Cos2(X+A/B)…
5. Напечатать значение функции F.
6. Увеличить значение Х на значение шага, т.е. Х=Х+D
7. Увеличить значение параметра цикла I=I+1
8. Проверить значение I. Если I<=10, перейти к п.4, иначе окончание счета
Блок-схема циклического алгоритма для примера 6
| Ввод A,B,C,D |
| X=X+D |
| Вывод результата F |
| I=0 |
| F=Cos(X+A/B)^2 …. |
| X=Exp(-A/B) |
| I=I+1 |
| I<=10 |
| Конец счета |
Рассмотрим еще один вариант организации циклического процесса.
Ниже приведена блок-схема вычисления функции
Y = X*LN(X) при X = 0.1; 0.4; 0.7 с указанием основных действий:
Словесный алгоритм:
1. Присвоить значение X=0,1 (задание начального значения параметра цикла)
2. Вычислить значение Y=XLn(X) (рабочий участок цикла – тело цикла)
3. Напечатать значение функции Y(рабочий участок цикла – тело цикла)
4. Х=Х+0,3 (изменение параметра цикла)
5. Проверить на окончание цикла. Если X<=0,7, перейти к п.2, иначе окончание счета
Блоки 2,3 - тело цикла образуют линейный участок вычислительного процесса. Параметр X - простая переменная вещественного типа.
Для Х известно начальное (0.1), конечное (0.7)значения и шаг изменения (0.3).
Выход из цикла произойдет при X>0.7 (1)
Эту задачу называют еще задачей табулирования функции на заданном диапазоне изменения аргумента. В инженерных расчетах такая задача встречается, когда необходимо получить таблицу значений некоторой величины, определяемой формулой, если известно, что один из параметров, входящих в эту формулу, может принимать любые значения в диапазоне [a;b].
Шаг h изменения параметра выбирается в зависимости от того, сколько значений табулируемой величины нужно получить.
Графическая блок-схема алгоритма будет такой:
| X=0,1 |
| Ввод Х=0,1 |
| X=X+0,3 |
| Вывод результата Y |
| X<=0,7 |
| Конец счета |
| Y=XLn(x) |
| да |
| нет |
Действия над массивами
Как правило, в задачах необходимо обрабатывать массивы - последовательности чисел разных размеров и типов. В этом случае используется доступ к каждому элементу описанного массива по его номеру (индексу), определяющему местоположение конкретного элемента в массиве. Это можно сделать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках.
< Пример >:
Массив А[1..15] вещественный (это значит, что массив А-последовательность вещественных
чисел)
...
А[1]:=1,3; А[2]:=2,1; А[3]:= -1,5... – элементы массива А
< Пример >:
Массив А [1..10] целый; (это значит, что массив А - последовательность из 10 целых чисел)
...
А[1]:=1; А[2]:=2; А[3]:=А[1]+А[2];...(элементы массива А)
Понятно, что при работе с двумерным массивом указываются два индекса.
< Пример >:
массив А [1..10,1..5] целый; (матрица из 10 строк и 5 столбцов)
...
А[1,1]:=1; (Элемент равен 1, стоит в 1 строке, 1 столбце матрицы)
А[2,1]:=4; (Элемент равен 4, стоит во 2 строке, 1 столбце матрицы)
А[1,2]:=А[1,1]+А[2,1]; (Элемент равен 1+4=5, стоит в 1 строке, 2 столбце матрицы)
Индексированные элементы массивов могут использоваться, как простые переменные соответствующего типа: использоваться в условных и циклических конструкциях, входить в качестве параметров операторов ввода/вывода, им можно присваивать любые значения, соответствующие их типу.
ПОИСК ЭЛЕМЕНТОВ - реализуется сочетанием операторов цикла и условных, задающих условие поиска. Иногда вводятся дополнительные переменные для подсчета или суммирования нужных элементов или их значений. В некоторых задачах такие дополнительные переменные могут понадобиться для запоминания местоположения нужных элементов, т.е. значений их индексов.
Рассмотрим пример 7.
Найти сумму отрицательных элементов массива А =A1;A2;A3…AN и их местоположение.. (здесь 1,2,3,… - индексы, указывающие местоположение элемента в массиве А. N – количество элементов в массиве)
Нам нужна дополнительная переменная, в которой будем накапливать сумму отрицательных элементов массива – назовем ее S. Еще нужна переменная – назовем ее В - это будет массив, состоящий из порядковых номеров отрицательных элементов массива А. Количество элементов в массиве В считаем с помощью переменной J. Просмотром элементов массива А управляет переменная I.
Рассмотрим пример на произвольном массиве А=2; -3,4; 1; 2; -2; 1,5; 4,4; -3; 10,8; 6, т.е. 10 произвольных чисел (N =10). Если массив будет состоять из 100 или 1000 чисел, алгоритм решения будет такой же, как и для 10 чисел, поэтому для простоты и визуального просмотра исходного массива мы ограничимся 10 элементами массива.
Для ввода и вывода произвольной последовательности чисел необходимо организовывать цикл.