Как правильно составить алгоритм для уравнения

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

,

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

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

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

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

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

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

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

Пример

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

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

Из курса математики известно, если x > y, то наибольшее число x, если x y, то переход к шагу 6, иначе к шагу 7.

Вывод информации: число x больше y. Переход к шагу 8.

Вывод информации: число y больше x. Переход к шагу 8.

Конец алгоритма.

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

В рассматриваемом алгоритме (рис.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.

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

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

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

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

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

Один из методов решения квадратных уравнений

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

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

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

procedure SqRoot(Editi,Edit2,Edit3:tEdit;Label2:tLabel);
var
a,b,c:real;
d:real;
xl,x2:real;
begin
<Ввод исходных данных>a:=StrToFloat(Editl.text);
b:=StrToFloat(Edit2.text);
с:=StrToFloat(Edj.t3.text);
< Вычисление дискриминанта >d:=Sqr(b)-4*a*c;
if d=0 then begin
Label2.color:=clRed;
Label2.font.color:=clRed;
Label2.caption:=’Дискриминант меньше нуля.’+#13+
‘Уравнение не имеет корней.’ end else
begin

х1:=(-b+Sqrt(d))/(2*a);
x2:=(-b-Sqrt(d))/(2*а);

Label2.font.color:=clBlack;
Label 2.caption=’Корни уравнения:’ +#13+’xl=1+FloatToStr(xl)
+#13+’x2=’+FloatToStr(x2);
end;
end.

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

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

Решение квадратных уравнений средствами Visual Basic

Задача: Дано квадратное уравнение общего вида: ax 2 +bx+c=0. Ввести в память компьютера числовые коэффициенты: a, b, c, выполнить необходимый анализ введенной информации согласно известному из курса средней школы алгоритму решения квадратного уравнения: найти дискриминант d=b 2 -4ac и, проанализировав его знак, найти все действительные корни, если знак дискриминанта положительный, или сообщить о том, что действительных корней нет, если знак дискриминанта отрицательный.

Начать составление проекта решения данной задачи необходимо с ответа на вопрос: что нужно поместить на форму Form1?

Поместим на форму две кнопки: CommandButton1 и CommandButton2.

Для этого нужно воспользоваться Панелью элементов (объектов) управления General, которая расположена в левой части основного окна компилятора Visual Basic.

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

1. ввод коэффициентов исходного уравнения a, b, c;
2. расчет дискриминанта d=b 2 — 4ac;
3. анализ знака дискриминанта, вычисление корней уравнения и вывод их на форму, если знак дискриминанта d>0 (положительный);
4. вывод сообщения: «Решений нет», если знак дискриминанта d 2 -5x+6=0.

Далее рассмотрим процесс решения второго квадратного уравнения: 10x 2 +5x+200=0.

В окне InputBox вводим значение первого коэффициента уравнения a=10.

Ввод первого коэффициента a завершается нажатием кнопки Ok.

Аналогично в окне InputBox вводим значение второго коэффициента уравнения b=5.

Ввод второго коэффициента b так же завершается нажатием соответствующей кнопки Ok.

Наконец, в окне InputBox вводим значение третьего коэффициента нового уравнения c=200.

Ввод третьего коэффициента c так же завершается нажатием соответствующей кнопки Ok.

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

И, наконец, рассмотрим процесс решения третьего квадратного уравнения: x 2 -8x+16=0.

Это уравнение имеет двукратный корень, так как его дискриминант d=0. Как и в двух предыдущих случаях, вводим коэффициенты квадратного уравнения. Первым вводим коэффициент a=1.

Далее вводим второй коэффициент уравнения b= –8.

Третий коэффициент уравнения c=16 вводим в последнюю очередь.

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

Как правильно составить алгоритм для уравнения

Данный материал представляет собой справочное руководство по составлении алгоритмов, которые являются необходимой составной частью контрольной и курсовой работы по дисциплине «Информатика».

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

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

В любом случае рекомендуется обратить внимание на следующее. Разбирая или составляя алгоритм, нужно мысленно представить некоторый автомат по обработке данных (компьютер), который будет выполнять действия, предписанные этим алгоритмом. Без такого представления невозможно понять сам алгоритм. Ниже, при разборе примеров, станет понятно, что такой мысленный автомат совсем несложен. Во всяком случае он несравнимо проще реального компьютера, хотя общие принципы их функционирования в основном одинаковы. Допустимо (например, при составлении описания) отождествлять работу такого автомата с работой самого алгоритма.

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

1. Алгоритм и алгоритмизация

Алгоритм – это инструкция о том, в какой последовательности нужно выполнить действия при переработке исходного материала в требуемый результат. [ последователь­ность точных предписаний, понятных исполните­ лю (компьютеру, роботу и пр.), совершить последо­ вательность действий, направленных на достиже­ ние конкретного результата. ]

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

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

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

На практике получили известность два способа изображения алгоритмов:

в виде пошагового словесного описания;

в виде блок-схем.

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

2. Блок-схема и ее элементы

Блок-схема – это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19002-80 и ГОСТ 19003-80 «Схемы алгоритмов и программ».

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

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

При соединении блоков следует использовать только вертикальные и горизонтальные линии потоков.

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

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

Линии потоков должны быть параллельны линиям внешней рамки или границам листа

Название

Элемент

Комментарий

Вычислительное действие или последовательность вычислительных действий

Обращение к процедуре

Вывод данных, печать данных

Разрыв линии потока

Начало, конец, пуск, останов, вход и выход во вспомогательных алгоритмах

Используется для размещения надписей

Горизонтальные и вертикальные потоки

Линии связей между блоками, направление потоков

Слияние линий потоков

Расстояние между параллельными линиями потоков должно быть не менее 3 мм , между остальными элементами схемы – не менее 5 мм .

Горизонтальный и вертикальный размеры блока должны быть кратны 5 мм (делиться на 5 нацело). Отношение горизонтального и вертикального размеров блока b/а = 1.5 является основным. При ручном выполнении блока допустимо отношение b/а = 2.

Блоки «Начало», «Конец» и «Соединитель» имеют высоту а/2, т. е. вдвое меньше основной высоты блоков.

Для размещения блоков рекомендуется поле листа разбивать на горизонтальные и вертикальные (для разветвлявшихся схем) зоны.

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

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

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

3. Константы, переменные и ячейки памяти

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

В состав такого автомата входят:

память, состоящая из отдельных ячеек;

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

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

В простейшем случае константой является любое арифметическое число. Например, 12, 0.78, 0, –45.33 и т. д. ( Константами могут быть такие строки символов, структуры данных и др.).

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

Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b , H2 – переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной . Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “переменная” и “адрес ячейки” памяти являются идентичными.

Запись вида Y = 5.5 следует понимать так: записать константу 5.5 в ячейку с адресом Y (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее место будет помещена константа 5.5). Произносить эту запись следует так: “переменной Y присвоить значение 5.5” .

Запись вида L = M следует понимать так: прочитать константу, расположенную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: «переменной L присвоить значение переменной M (или просто: L присвоить M)».

4. Массивы

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

Одномерный массив – это последовательность ячеек, расположенных в одну линию. На рис. 1 приведен пример такого массива.

Массив имеет имя q. Для того чтобы можно было отличить одну ячейку массива от другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1. Номер ячейки массива называется его индексом , а константа в ячейке – элементом массива. Теперь становится возможной работа с отдельной ячейкой такого массива. Например, команда q 7 = 8.2 означает, что в 7-ю ячейку массива q надлежит записать константу 8.2. Команда r 41 = q 2 + q 5 означает, что нужно сложить константы, записанные во 2-ю и 5-ю ячейки массива q, и результат записать в 41-ю ячейку одномерного массива r. Эту же операцию можно описать другими словами: 41-му элементу массива r присвоить значение суммы 2-го и 5-го элементов массива q.

Двумерный массив по расположению ячеек напоминает математическую матрицу ( рис. 2 ). Элемент такого массива характеризуется двумя индексами: первый показывает строку, в которой расположена ячейка, второй – ее столбец. Например, команда d 2, 5 = 43 означает, что в ячейку, размещенную на пересечении 2-й строки и 5-го столбца двумерного массива d, нужно записать константу 43.

Аналогично устроена структура массивов трех- и большей размерности.

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

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

На рис. 3 приведен пример блок-схемы алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.

Рис. 3. Линейный алгоритм

Блок-схема алгоритма состоит из шести блоков. Выполнение алгоритма начинается с блока 1 «Начало». Этот блок символизирует включение автомата, настройку его на выполнение алгоритма и выделение памяти под все переменные, которые задействованы в алгоритме. В алгоритме рис. 3 таких переменных три: A, Р, S. Следовательно, под каждую из них алгоритмом будет выделено по одной ячейке памяти. На этом блок 1 будет отработан.

Как видно из рис.3, блок 1 связан вертикальной линией потока с блоком 2. Эта линия не имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2. Блок 2 «Перфокарта» ( см. табл. 1) показывает, что переменной A следует присвоить значение. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент. Можно, например, потребовать ввод константы с клавиатура или получить его из заранее подготовленного файла. Возможно эта константа будет получена через внешние источники данных, например, от физической установки, подключенной к компьютеру.

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

Далее управление по линии потока передается к блоку 3 «Процесс». В этом блоке при выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А (т. е. 5), и результат (т. е. 20) присваивается переменной Р (т. е. константа 20 записывается в ячейку по адресу Р). После выполнения этих операций управление передается к блоку 4.

В блоке 4 аналогичным образом производится умножение значений переменной А и результат (константа 25) присваивается переменной S (в ячейку по адресу S будет занесена константа 25). После этого выполняется переход к блоку 5.

При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы 5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление передается последнему блоку 6.

В блоке б “Конец” производится освобождение ячеек памяти, которые были зарезервированы под переменные А, P, S, и алгоритм заканчивает работу.

Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400.

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

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

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

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

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

Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x.

На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную структуру. Однако, если учесть, что делить на нуль нельзя из-за переполнения ячейки, то, во-первых, нужно из вычислений исключить вариант х = 0 и, во-вторых, проинформировать пользователя алгоритма о возникшей ошибке. Если этого не сделать, то при вычислениях может возникнуть аварийный выход до получения результата. В профессиональной практике аварийные завершения крайне нежелательны. т. к. к этому моменту уже может быть накоплено определенное количество результатов, которые окажутся необработанными и попросту пропадут. Можно привести другие примеры, когда аварийный останов компьютера может повлечь куда более серьезные последствия.

Решение задачи представлено блок-схемой рис. 4.

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

Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода аргументов X и Y. Затем в блоке 3 производится проверка условия X = 0. Здесь автомат проверяет равна ли нули константа, введенная в ячейку с адресом X. Результатом такой проверки является ответ «Да» или «Нет». В зависимости от этого ответа выполнение алгоритма пойдет по одной или другой ветви. Если результат проверки окажется отрицательным, то на х можно делить и управление передается блоку 4.

В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4, автомат выведет сообщение «Ошибка» и затем закончит работу в том же блоке 7.

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

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

Различают циклы с наперед известным и наперед неизвестным количеством проходов.

Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3, . сумма которых больше числа К.

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

Блок-схема алгоритма решения этой задачи приведена на рис. 5. Она состоит из восьми блоков.

После начала работы в блоке 2 вводится значение числа К. Далее в блоке 3 переменная i получает значение 1, т. е. значение, с которого начнется отсчет натуральных чисел. Переменная S, предназначенная для накопления сумма этих чисел, перед началом суммирования получает значение 0. После этого управление передается блоку 5.

В нем при выполнении команды S = S + i производится сложение содержимого ячеек S и i, а результат записывается в ячейку S. Поскольку до операции сложения было S = 0, i = 1, то после операции будет S = 1. При записи нового значения старое содержимое ячейки S (нуль) стирается, а на его место записывается число 1.

Нужно обратить внимание на то, что если бы до этой операции в блоке 3 не была выполнена команда S = 0 (записать нуль в ячейку S ), то при нахождении суммы S + 1 возникла бы ошибка, поскольку из ячейки S была бы извлечена константа, которая оказалась там после распределения памяти.

После суммирования первого члена последовательности в блоке 6 выполняется проверка условия о превышении суммы S заданного числа К.

Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении операции значение переменной увеличивается на 1 и становится равным 2. Теперь алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2. После этого сумма станет равной 3. В блоке б вновь проверяется условие получения требуемой суммы и т. д. Цепочка блоков 5-4 будет обрабатываться вновь и вновь до того момента, когда однажды при определенном значении переменной i, наконец, выполнится условие S > К, т. е. когда накапливаемая в таком цикле сумма впервые превысит заданное значение К. Переменная i, значение которой при очередном проходе цепочки этих блоков увеличивается на 1, играет роль счетчика этого цикла.

Далее производится переход к блоку 7, где отпечатается значение количества членов ряда (извлечено и отпечатано число из ячейки i, которое там хранится в момент выполнения условия), суммы S и в блоке 8 алгоритм закончит работу.

Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным количеством проходов (повторений). Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N ( под длиной массива понимается количество его элементов ). Блок-схема алгоритма дана на рис. 6.

Рис. 6. Циклический алгоритм

Вначале в блоке 2 производится ввод двух переменных N и Z. Первая из них представляет одну ячейку. В нее записывается одна константа – число, равное количеству элементов массива Z. Именно такое количество ячеек объединяет другая переменная – Z.

Следует подчеркнуть, что если бы ввод этих переменных в блоке 2 производился в противоположном порядке, то это привело бы к ошибке. Действительно, невозможно заполнить N ячеек массива Z, когда самое N еще не известно (оно будет введено позже Z). Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того, чтобы приготовить ячейку к дальнейшему накоплению необходимой суммы.

Блоки 4-6 представляет собой сам цикл, в котором накапливается сумма.

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

Как видно из рис. 7, цикл состоит из заголовка и тела. Всякий цикл обязательно имеет свой счетчик.

На рис. 8, где показана структура и параметры заголовка цикла, роль такого счетчика выполняет переменная i. Внутри заголовка после счетчика и символа «=» через запятую указывает начальное и конечное значения счетчика и шаг его изменения (на рис. 8 их роль выполняют переменные j, k, l соответственно). Если значение шага l = l, то его можно не указывать.

Сначала производится вход в цикл. После этого начинается его выполнение.

Рис. 7. Структура цикла Рис. 8. Структура заголовка цикла

Внутри заголовка счетчику первоначально присваивается значение i = j. Затем выполняется блоки, образующие тело цикла. Обработка блоков внутри цикла производится по часовой стрелке. В результате после первого выполнения тела цикла управление вновь передается заголовку. Здесь к текущему значению счетчика добавится шаг. Теперь, если новое значение счетчика не вышло за свои пределы (т. е. не стало больше своего конечного значения при положительном шаге или меньше конечного значения – при отрицательном шаге), то снова выполняется тело цикла, вновь после возврата к заголовку к счетчику добавляется шаг. Так цикл будет выполняться до тех пор, пока значение счетчика однажды не выйдет за предписанный предел. Как только такой предел будет преодолен, произойдет выход из цикла и управление будет передано блоку, который следует сразу за циклом.

Вернемся к блок-схеме рис. 6. Заголовок ее цикла представлен блоком 4. Роль счетчика цикла играет переменная i, которая должна в цикле изменяться от 1 до N. Поскольку шаг явно не указан, то по умолчанию он подразумевается равным 1. Тело цикла образуют блоки 5 и 6.

Сразу после входа в цикл переменная i примет начальное значение i = 1. Далее в блоке 5 выполняется проверка положительности первого элемента массива Z (т. к. i = 1). Если этот элемент действительно положителен, то в блоке б он будет добавлен к переменной S, после чего выполняется возврат к заголовку цикла. Если этот элемент не положителен (т. е. нуль или отрицательный), то будет выполнен переход сразу к заголовку цикла, минуя блок суммирования 6.

На втором круге цикла счетчик i в заголовке увеличится на 1 и станет равным 2. Теперь, при новом выполнении тела цикла, в блоке 5 проверяется на положительность второй элемент массива Z и, если он положителен, то добавляется в сумму и т. д. Последний раз тело цикла выполнится при i = N. При этом значении счетчика проверяется последний элемент массива. Наконец, в заголовке цикла i примет значение N+1. Это значение выходит за предписанный предел, следовательно, произойдет выход из цикла и управление перейдет блоку 7. В этом блоке выводится накопленная сумма и алгоритм закончит работу.

8. Алгоритмы со структурами вложенных циклов

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

Рис. 9. Алгоритм сортировки массива

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

Пример 1. Рассмотрим задачу сортировки одномерного массива Z длины N. Отсортировать массив – значит расположить его элементы в порядке роста или убывания.

Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.

Блок-схема этого алгоритма сортировки показана на рис. 9. Она включает 12 блоков. После начала работы в блоке 2 переменная N и массив Z заполняются константами. Затем в блоке 3 проверяется условие о том, нужно ли сортировать массив.

Это сводится к установлению факта наличия в массиве нескольких элементов, т. к. массив из одного элемента всегда отсортирован. Если этот факт установлен, то алгоритм приступает к сортировке. Процедура сортировки выполняется в цикле, объединяющем блоки 4-10. В теле этого цикла содержится другой цикл, который образован блоками 6-8. Его назначение станет ясно из дальнейшего разбора алгоритма.

После входа в наружный цикл его счетчик i примет значение 1, что в рамках нашего метода подразумевает первый проход по массиву.

Далее будут выполнены блоки 5-10, составляющие тело наружного цикла. В блоке 5 размещены две вспомогательные переменные V и L. Первая из них предназначена для фиксирования наименьшего элемента, а вторая – для запоминания его индекса. Так как i = 1, то при первом проходе в блоке 5 V примет значение первого элемента, а L значение 1. Затем во внутреннем цикле, образованном блоками 6-8, где его счетчик j будет изменяться от 2 до N, последовательно проводится сравнение соответствующих элементов массива Z со значением переменной V. При этом всякий раз, как будет найден меньший чем v элемент, значение V будет заменено на значение этого элемента, а в переменной L будет зафиксирован его индекс. Понятно, что после выполнения внутреннего цикла в переменной V будет содержаться значение, равное наименьшему элементу, а в L – индекс этого элемента. В блоке 9 далее проверяется, не является ли наименьший элемент первым элементом массива. Если это не так, то в блоке 10 на место наименьшего элемента (его номер L) запишется первый (т. к. при первом проходе L =1 ), а на место первого элемента – наименьший (он равен V). После этого произойдет возврат управления к заголовку наружного цикла блоку 4. В нем значение счетчика станет равным i = 2.

Затем вновь выполняется его тело, но уже для нового значения счетчика i. Теперь с помощью блоков 5-10 отыскивается наименьший элемент массива начиная с номера 2. Затем в блоках 9-10 он займет второе место в массиве и т. д. Когда тело наружного цикла выполнится (N-1), раз массив будет отсортирован.

В блоке 12 отсортированный массив будет выведен и в блоке 13 алгоритм окончит работу.

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

Пример 2. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов. Необходимо найти среднее арифметическое S его отрицательных элементов и заменить положительные элементы побочной диагонали массива средним арифметическим S.

Рис. 10. Блок-схема алгоритма

Блок-схема алгоритма показана на рис. 10. Она состоит из 13 блоков. В блоке 2 переменная N и весь массив Z заполняются константами. В блоке 3 рабочие переменные S и К получает значение нуль. Переменная S сначала будет играть роль сумматора отрицательных элементов массива, затем после накопления суммы она примет значение среднего арифметического. Переменная К нужна для подсчета количества отрицательных элементов массива.

В блоках 4-7 выполняется накопление суммы отрицательных элементов массива.

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

После входа в наружный цикл в блоке 4 переменная i примет значение i = 1. Далее будет выполнено его тело ( блоки 5-7 ), которое, в свою очередь, также является циклом. После входа во внутренний цикл в блоке 5 переменная j примет значение j = 1. Затем в блоке 6 проверяется на отрицательность элемент массива Z, расположенный в первой строке и первом столбце, т. к. i = 1 и j = 1.

Если он окажется отрицательным, то в блоке 7 переменная К увеличится на 1, а к S добавляется значение этого элемента. После этого выполняется возврат к блоку 5, т. е. к заголовку внутреннего цикла. Здесь j увеличится на 1, станет равной j = 2 и управление перейдет к блоку 6. В нем проверяется элемент, стоящий все в той же первой строке, но во втором столбце (i = 1, j = 2). Если он окажется отрицательным, то К снова увеличится на 1, а к накопленному к этому времени S добавляется значение этого элемента и т.д. Когда полностью выполнится внутренний цикл, т. е. переменная j «пробежит» от 1 до N, в переменную S накопится сумма всех отрицательных элементов первой строки массива, а в К – их количество. Теперь управление передается к блоку 4 заголовка наружного цикла, где i станет равной i = 2. Снова будет отработано его тело, т. е. цикл 5-7. При этом будет найдена уже сумма отрицательных элементов первых двух строк массива, а в К сохранится количество этих элементов. Когда выполнится весь наружный цикл, в S будет константа, равная сумме отрицательных элементов всего массива, а в К – их количество. Теперь управление перейдет к блоку 8. Если окажется, что в массиве есть отрицательные элементы (К>0), то в блоке 9 вычисляется среднее арифметическое как отношение суммы элементов к их количеству. Результат помещается а ту же переменную S. Отметим, что если бы блок 8 проверки отсутствовал, то при К = 0 (в массиве нет ни одного отрицательного элемента) в блоке 9 из-за деления на нуль возникла бы ошибка. Эта ошибка повлекла бы аварийное завершение вычислений до окончания работы алгоритма.

Далее выполняется блоки 10-11, которые также образует цикл. В нем производится замена элементов побочной диагонали на среднее арифметическое S (побочной диагональю является прямолинейная цепочка ячеек в диапазоне от нижнего левого угла до верхнего правого угла массива). Обратите внимание, на то что переменная i, которая использовалась ранее, в целях экономии памяти применяется вновь.

Проследим работу этого цикла. После входа в блок 10 счетчик примет значение i = 1. Затем в блоке 11 при этом значении будет вычислен индекс столбца элемента N – 1 + i = N. Таким образом, элемент с индексами (1, N) станет равным S. На втором круге цикла i увеличится на 1 и станет i = 2. Нетрудно видеть, что теперь элемент (2, N-1) станет равным S и т. д. На последнем круге цикла элемент (N, 1) получит значение S, что завершит изменение значений всех элементов побочной диагонали на среднее арифметическое S.

Наконец, в блоке 12 измененный массив будет выведен и в блоке 13 алгоритм закончит работу.

9. Вспомогательные алгоритмы

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

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

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

Рис. 11. Процедура Warn

Первый блок схемы рис. 11 в отличие от ранее рассмотренных примеров, где этот блок имел наименование “Начало”, включает имя процедуры Warn и один формальный параметр i. С помощью этого имени в алгоритме рис. 12 выполняется обращение именно к этой процедуре.

Из схемы видно, что если на вход процедуры Warn подать i = 0, то она в блоке 3 выдаст сообщение «Введите данные». При любом другом i будет выведено сообщение «Конец расчетов». Этим исчерпываются возможности процедура Warn.

На рис. 12 дана схема головного алгоритма ( первый блок имеет наименование «Начало» ). Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn.

Опишем последовательность и механизм обработки данных, которые предписаны алгоритмами рис. 11 и 12.

Рис. 12. Головной алгоритм

Выполнение алгоритмических действий всегда начинаются с головного алгоритма. Поэтому сначала будет выполнен блок 1 схемы рис. 12. Далее в блоке 2 головной алгоритм выполняет обращение к процедуре Warn при конкретном значении ее аргумента (0). Это конкретное значение называется фактическим параметром процедуры.

Теперь управление временно переходит в алгоритм рис. 11 процедуры Warn. Здесь и далее по всей процедуре Warn формальный параметр i заменяется на фактический параметр 0 (нуль) всюду, где он встречается.

Далее обрабатывается блок 2 процедуры, где с учетом сказанного проверяется условие 0 = 0. Результатом проверки станет перевод управления к блоку 3, в котором выводится сообщение «Введите данные». На этом процедура заканчивается и управление вновь передается в головной алгоритм к блоку 3.

Далее в блоках 3-5 алгоритма рис. 12 выполняются уже понятные действия по вводу, суммированию и выводу переменных. Затем управление передается в блок б, который содержит новое обращение к процедуре Warn с фактическим параметром 1.

Снова управление переключается на схему рис. 11, где вместо формального параметра i всюду записывается фактический параметр – константа 1. Поскольку в блоке 2 условие 1 = 0 не выполнится, то будет выполнен блок 4 и алгоритм выведет сообщение «Конец расчетов». После этого управление возвращается в головной алгоритм к блоку 7, где и будет окончательно завершен алгоритмический процесс.

Внешне такой процесс может выглядеть примерно так. На экран выводится сообщение «Введите данные» и компьютер переходит в режим ожидания ввода двух констант с клавиатуры. Затем после их ввода на экране появляется три константы и надпись «Конец работы». На первый взгляд может показаться, что процедуры лишь усложняют решение задачи. Действительно, рассмотренную здесь задачу проще решить одним алгоритмом, не прибегая к составление процедуры. Однако при составлении алгоритма решения сложной задачи очень быстро становится ясно, что без использования процедур обойтись просто невозможно. На практике при решением серьезных алгоритмических задач часто одному программисту не под силу выполнить весь объем работ. Поэтому над ее решением работает обычно коллектив программистов под руководством координатора. Образно говоря, координатор здесь работает как головной алгоритм, а его программисты как процедуры. При этом каждый программист (часто независимо от других) получает от координатора задание по составление процедур определенного назначения. В результате такой организации работы задача получает разрешение.

10. Декомпозиция алгоритма

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

Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост. Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы оформляет в процедуры или функции верхнего уровня. Затем, если необходимо, такие этапы делят на этапы более низкого уровня. Наиболее сложные из них также оформляют процедурами или функциями и т. д. Следуя методу «от сложного к простому», в конечном итоге достигают решения поставленной задачи. Приведем пример декомпозиции для решения задачи сортировки массива. Эта задача была решена ранее в разд. 8 (рис. 9) без использования вспомогательных алгоритмов. Решение задачи декомпозиции состоит из трех основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в дальнейшей декомпозиции, поэтому выполняются в головном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент вычислений, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort.

Этап сортировки, в свои очередь, состоит из двух этапов: 1) установления необходимости сортировки и (N–1) – кратного прохода по массиву и 2) нахождения наименьшего элемента во фрагменте массива и перестановки этого элемента с начальным элементом фрагмента. Поскольку последний этап многократно повторяется при выполнении первого этапа, то его можно оформить в отдельную процедуру. Этой процедуре можно дать имя Tra (от английского transposition – перестановка). Блок-схемы головного алгоритма, процедуры Sort и процедуры Тrа показаны на рис. 13-15 соответственно.

Рис. 13. Головной алгоритм Рис. 14. Процедура Sort

Дадим краткое, описание взаимодействия этих алгоритмов в ходе решения задачи сортировки.

Рис. 15. Процедура Tra

Выполнение начинается с головного алгоритма (рис. 13). В блоке 2 вводятся исходные данные, затем в блоке 3 выполняется сортировка массива. В блоке 4 отсортированный массив выводится и алгоритм заканчивает работу. Сортировка массива в блоке 3 головного алгоритма выполняется обращением к процедуре Sort, показанной на рис. 14. Переменные A и N являются фактическими параметрами, Переменные А и N, которые использованы в блок-схеме алгоритма Sort, является формальными параметрами.

При обращении к процедуре Sort на вход подаются параметры A и N. В результате в теле процедуры производится замена формального параметра R на фактический параметр A, аналогично формальный K заменяется на фактический N.

Далее в блоке 2 проверяется необходимость сортировки массива R. Затем, если такая необходимость будет установлена, в цикле 3-4 будет выполняется сортировка массива. При всяком значении счетчика цикла в его теле производится нахождение наименьшего элемента фрагмента и его перестановка с начальным элементом этого фрагмента. Эти операции выполняются отдельно с помощью процедуры Tra. Как видно из рис. 15, на вход процедуры Tra нужно подать имя массива (A), количество элементов (N) и номер элемента (i), которым начинается фрагмент. В теле процедуры в блоках 2-5 отыскивается наименьший элемент фрагмента (v) и его номер (k). Затем в блоке 6 выполняется вышеназванная перестановка элементов.

Таким образом, весь процесс управляется головным алгоритмом, который выполняет сортировку посредством обращения к вспомогательному алгоритму – процедуре Sort.

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

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

Рассмотрим задачу вычисления факториала числа N! = 1 . 2 . 3 . . . N. Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции.

Рис. 16. Функция Fact

Ее блок-схема показана на рис. 16. Переменная К используется для накопления произведения и, поскольку 0! = 1 и1! = 1, то в блоке 2 ей сразу присваивается значение 1. Далее, если N>1, то в цикле, образованном блоками 4-5, накапливается искомое произведение и помещается в переменную К. В блоке 6 имя Fact функции получает значение вычисленного произведения из ячейки К. Для процедур действия, размещенного в блоке 6, не может быть, а для функций оно должно быть обязательно, поскольку иначе значение функции на выходе окажется неопределенным.

Обращение к функции в других алгоритмах (головных, процедурах, функциях) производится по ее имени.

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

Пример использования функции Fact показан на рис. 17. В операторе присваивания используется обращение к функции для N = 6. После передачи этого значения в алгоритм рис. 16 и вычислений внутри него результат будет сначала присвоен имени функции, т. е. переменной Fact, а затем в операторе присваивания — переменной L.

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

Квадратное алгебраическое уравнение имеет вид:

ах^2 + bx + c = 0. (1)

Здесь а, b и с – коэффициенты. Сначала надо вычислить дискриминант квадратного уравнения

D = (b^2 – 4ac) (2)

Если D > 0, то квадратное уравнение имеет два корня х1 и х2. Обозначим С = корень(D). То есть надо вычислить квадратный корень из D. Имеем такие решения

х1 = (–b + C)/(2a) и x2 = (–b – C)/(2a). (3)

Если дискриминант D = 0, то C = 0 и оба корня одинаковы Х1 = Х2 (хотя в школе обычно говорят, что имеется только одно решение) и вычисляются по формуле

Х1 = Х2 = –b/(2a). (4). Эта формула следует из формулы (3) при С = D = 0.

Если дискриминант D меньше нуля, то корень из D вычислить нельзя, С будет мнимым числом. Вообще говоря, корни есть (2 штуки), но они будут мнимыми числами. Хотя в школе учат, что в этом случае корней НЕТ. Так и будем считать, что корней нет.

Алгоритм решения будет следующий

Но только здесь дискриминант D обозначен малой буквой d

Исследовательская работа

«Алгоритм решения уравнений»

СОДЕРЖАНИЕ

1.     Введение. Актуальность,
проблема, цель, гипотеза, задачи и методика исследования……………………………………………………………….3

2.     Анализ учебной литературы с
целью поиска правила или алгоритма решения уравнений с одним неизвестным в
несколько действий ……………………………………………………………………………….5

3.     Поиск алгоритма ………………………………………………………………….6

4.     Как пользоваться алгоритмом …………………………………………….7

5.     Применение алгоритма при
решении уравнений ………………………..8

6.     Вывод ………………………………………………………………………10

7.     Список литературы ………………………………………………………11

Введение

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

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

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

30 + х : 2 = 100

В таком уравнении
ученики часто в первую очередь находят компонент деления – делитель:

(30 + х) = 100 *
2, что приводит к ошибке.

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

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

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

Задачи исследования:

— изучение темы
«Уравнения» в учебниках разных авторов;

— поиск алгоритма
решения уравнений в несколько действий с одним неизвестным;

— демонстрация
использования алгоритма на практике;

— доказательство
практической пользы алгоритма решения уравнений;

— рекомендации по
включению алгоритма в учебники.

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

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

Было изучено три
учебных издания «Математика», по одному из которых ранее обучались учащиеся 5
класса:

— комплект Моро
М.И.,  Бантова М.А.,  Бельтюкова Г.В. Математика. 1, 2, 3, 4 классы;

— комплект Аргинская
И.И. Математика. 1,2, 3 классы;

— комплект Петерсон
Л. Г. Математика. 1, 2, 3, 4 классы.

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

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

Поиск алгоритма.

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

Соотнесем два
правила:

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

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

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

Это и есть
алгоритм решения уравнения с одним неизвестным.

Как пользоваться алгоритмом

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

Возьмем
уравнение:

4000 – (3х + 6) :
6 * 2 – 28 = 1000

(При решении
данного уравнения заведомо не применяются правила упрощения выражения).

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

Будем
подчеркивать неизвестный компонент (при решении этого делать необязательно):

4000 – (3х +
6) : 6 * 2 –
28 = 1000

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

4000 – (3х + 6) :
6 * 2 = 1000 + 28

4000 – (3х + 6) :
6 * 2 = 1028  

4000 – (3х + 6) : 6 * 2 =1028

Находим
вычитаемое. Чтобы найти вычитаемое, надо из уменьшаемого вычесть разность:

(3х + 6) : 6 * 2
= 4000 – 1028

(3х + 6) : 6 * 2
= 2972

Следуя алгоритму,
находим компоненты умножения и деления в обратном порядке.

(3х + 6) : 6 * 2 = 2972

Находим
множитель. Чтобы найти множитель, надо произведение разделить на другой
множитель:

(3х + 6) : 6 =
2972 :2

(3х + 6) : 6 =
1486

(3х + 6) : 6 = 1486

Находим делимое. Чтобы
найти делимое, надо частное умножить на делитель:

(3х + 6) = 1486 *
6

(3х + 6) = 8916

Следуя алгоритму,
находим компоненты действий, находящихся в скобках, в обратном
порядке.

3х + 6 = 8916

Находим
слагаемое. Чтобы найти слагаемое, надо из суммы вычесть другое слагаемое:

3х = 8916 – 6

3х = 8910

3 * х = 8916

Находим
множитель. Чтобы найти множитель, надо произведение разделить на другой
множитель:

х = 8910 : 3

х = 2970

Корень данного
уравнения – число 2970.

Выполним
проверку:

4000 – (3 * 2970
+ 6) : 6 * 2 = 1000

Применение алгоритма при
решении уравнений

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

1. № 64 стр. 93
(Петерсон Л. Г. Математика. 4 класс. Часть 3.):

А) (24 – х) * 5 –
32 = 48

По правилу
решения уравнения, находим компонент вычитания – уменьшаемое:

(24 – х) * 5 = 48
+ 32

(24 – х) * 5 = 80

Находим компонент
умножения – множитель:

(24 – х) = 80 : 5

(24 – х) = 16

Находим компонент
вычитания – вычитаемое:

х = 24 – 16

х = 8

2. № 144 стр. 157 (Аргинская И.И.
Математика. 3 класс.):

(6у – 72) : 2 –
84 = 201

Находим компонент
вычитания – уменьшаемое:

(6у – 72) : 2 =
201 + 84

(6у – 72) : 2 =
285

Находим компонент
деления – делимое:

(6у – 72) = 285 *
2

(6у – 72) = 570

Находим компонент
вычитания – уменьшаемое:

6у = 570 + 72

6у = 642

Находим компонент
умножения – множитель:

у = 642 : 6

у = 107

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

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

30 + х : 2 = 100

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

х : 2 = 100 – 30

х : 2 = 70

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

х = 70 * 2

х = 140

Вывод

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

Список использованной
литературы:

1. Петерсон Л. Г. Математика. 1
класс. Части 1, 2, 3. М., «Ювента». 2004.

2. Петерсон Л. Г. Математика. 2
класс. Части 1, 2, 3. М., «Ювента». 2004.

3. Петерсон Л. Г. Математика. 3
класс. Части 1, 2, 3. М., «Ювента». 2007.

4. Петерсон Л. Г. Математика. 4
класс. Части 1, 2, 3. М., «Ювента». 2004.

5. Моро М.И.,  Бантова М.А.,  Бельтюкова
Г.В. Математика. 1 класс. Части 1,2. М., «Просвещение». 2007.

6. Моро М.И.,  Бантова М.А., 
Бельтюкова Г.В. Математика. 2 класс. Части 1,2. М., «Просвещение». 2006.

7. Моро М.И.,  Бантова М.А., 
Бельтюкова Г.В. Математика. 3 класс. Части 1,2. М., «Просвещение». 2007.

8. Моро М.И.,  Бантова М.А., 
Бельтюкова Г.В. Математика. 4 класс. Части 1,2. М., «Просвещение». 2003.

9. Аргинская И.И. Математика. 1
класс. М., «Просвещение». 1995.

10. Аргинская И.И. Математика. 2
класс. М., «Просвещение». 1997.

11. Аргинская И.И. Математика. 3
класс. М., «Просвещение». 1995.

Пусть
задана непрерывная функция • Требуется
опре-

делить
такое значение > , чтобы f[X)
=
О
•
Мы будем считать, что корни уже
отделены,т.е. известны-числа а
и
в
такие,
что в промежутке [а,
6]
существует
единственный ко­рень, либо известно
значение Х_с
,
достаточно
близко располо­женное к корню. Наиболее
часто используются методы половинного
деления, метод Ньютона, метод простой
итерации.

В
методе половинного деления промежуток
[
й-_}
о]
делится
точкой с
— (ti
i-Ь)/
¿
на
две равные части. Образуется два
промежутка [а>С]
и
1С,
Si
в
одном из которых находится корень (если
f(C)
р-0
).
Для следующего шага промежуток уже
будет вдвое меньше длины. Выбирается
тот промежуток,в котором произ­ведение
на концах будет ¿
О
.

Таким
образом,в алгоритме будут использованы
две перемен­ные, которые можно
рассматривать как левый и правый конец
про­межутка. Для левого конца на
разных шагах знак функции будет один
и тот же. Таким образом,вычисляется
точка с
,
вычисля­ется fíe)
и
определяется оС■
ju.)-f(C)
.
Если ОС
?
О
,
то
ко­рень находится в промежутке ¿c_}
6J
,
т.е. правый конец оста­ется тот же
самый (6)
,
а левый конец изменится,т.е. теперь
ле­вым концом станет С . Если OL
<.
О
,
то корень находится на промежутке
£■’£■. í
J
,
и следовательно, не изменяется левый
ко­нец {&), а изменяется правый (#).
После анализа сС
мы
пришди к той же задаче, но с половинной
длиной промежутка. Продолжается цикл
до тех пор, пока длина промежутка не
станет Ъ
.
Алгоритм можно записать в виде ;

_fx
=
f(CL))
F¿ jit);
„,.í
-:c¿<£l
tJ/¿;
f*f(^c>i
*uf-fi’C),h¿
;
c’-j;
f:-*;
*á-&h¿)#4;
ó’iу
Mf_t
.m¿: *
с;
Fx
•■
f_t—
éiij
ми;
**Ц-
^x~^c»

■
oiidmí,’ x
—
(U
* mf:
…

Метод
простой итерации предполагает, что
уравнение записа-но
в виде^ v
—
и известно начальное значение Хс
—
ПодставляяК_в
а правую
часть, получим некоторое значение k_i
,
под’ставицХ_А
в правую часть, получим Ж_г
и
т.д. Если известно Х_л
,
товычисляется
по формуле x„rí •
Следует
сразу от-

метить,
что Mi,Ji_2>
.■■
,Х*. не
рекомендуется рассматривать как
элементы массива, хотя бы потому, что
мы не знаем сколько элемек­tob
в
этом массиве и,
как правило, нам нужны не все^л.’_г,
..
,
а
то значение, к которому стремится(если
стремится) последова­тельность {Х_л}
при
>г—»-<■«. анализ формулы показывает,
что по прежнему, старому значению
приближения вычисляется новое, более
точное, лучшее приближение у
.

так
как х,*₂— i.)
•
^т0
ПР^И
продолжении
процесса «но-

вое»
значение на предыдущем шаге станет»старым»
для следующего шага.

условие
выхода должно предусматривать два
случая — схо­димость процесса и его
расходимость. если процесс сходится,
то для достаточно большого п
iX_nrL-x_n_
—
<£ , т.е. разница между X
и
У
для
сходящегося процесса » О
й
можно остановить­ся, если модуль этой
разности будет меньше заданной величины
d
.
для
того, чтобы расходящийся процесс
обрабатывался данным алго­ритмом
(часто до решения трудно определить
сходимость), необхо­димо задать
условие расходимости. оно обычно
задается по
количест­ву итераций — если оно больше
У₀
(например
100), то считается, что процесс расходится.

алгоритм
можно записать в виде:j.
—
х₀;
i+ij
М
•’
Учу
(-Я
) •Mi
i У~
<f(*)’,d
;
У
-к,
д
—
У,
yiiy(iüi
‘ •■
■

часто
для решения уравнения используется
метод ньютона. как и в методе простой
итерации в этом методе требуется знание
начального, достаточно близкого к
искомому корню,приближения Х₀
.
X_L
вычисляется
по формуле х_х
io
—
jM/j«‘(-ко),
где f*(X_e)
—производная
от функции /,‘
ji
)
.

если
известно х_л>
то
Х„.
_t
вычисляется
по формуле

алгоритм
метода ньютона получается из алгоритма
простой итерациипри
1уХ)~!l- f
(х)
.
рассмотрим пример. пусть исполнитель

не
умеет извлекать квадратный корень,
как самостоятельную опе­рацию.
требуется выразить эту операцию через
4
арифметические
операции. X
*
Си
эквивалентно
решению уоавнения Х^г-й.
‘О. применим
метод ньютона

—^lcn.’i⁼
Хщ
*
ч£
*в
—
■*■
(Хп~*
а-/.!*.).

в
качестве Х₀
выберем
iL
прц^&*0
.
алгоритм запишем в виде;

X
-Щ
*и:-у;
(X*
1/£ )/.
;

у-х;
х-
у; Упу^оСЛ? і

можно
показать,что этот процесс сходится при
любом 0->о
, поэтому
блок расходимости из алгоритма простей
итерации изъят. важно подчеркнуть,что
если имеется койкретное уравнение,
корни которого определены,то мы можем
найти эти корни, независимо от вида
функции /(х) ,т.е.можно
сказать,что построенные алгоритмы
применимы к достаточно широкому классу
уравнений.

5.4.
пример
решения задачи
10 спортсменов принимают участие в
забеге на 5000 м.
из­вестно,что скорость і-
-го
спортсмена в момент Ь
зависит
от его начальной скорости V?*и
степени его физической подготовки

и
Определяется
по
йоэмуле …
¿0) -А-У-^УТ

требуется
составить прогноз распределения мест
не финише.

обозначим
через 1£
время преодоления
дистанции і-ым
спорт­сменом. 7порядочим числе (г
в
порядке возростания.З
этом
случае с какдым ^связывается определенный
номер К
, который
является ис­комой величиной. таким
образом, определиз уиелвь£,мы сведем
нашу задачу к упорядочению чисел.

пусть
і)-расстояние,
пройденное і
-)Ш
спортсменом
за время І
,
тогда
числа ііявляются
корнймй уравнений 5^
(^)
‘5000-О
следовательно,определение
^ при известной функции сведено к
решению трансцендентного урамнения.для
его решения мы можем при­менить один
из описанных выше методов.т.к. мн находим
значение ¿¿ приближенно,будем
считать,что погрешность не должна
превышать’ о.оісек.
при
использовании метода.половинного
деления необходимо Зі
-ние
интервала,содержащего корень. нижней
границей такого интер­вала можно
взять число С,
а
верхней- число ЗбОС,
т.к.
за это время дистанция будет преодолена
любим спортсменом, дл- определения
5^(0
вспомним,что

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

106
чаете»!
и интеграл рассматривать как сумму 100
слагаемых.

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

Алгоритм
решения задачи состоит из четырех
блоков. В первом осуществляется ввод
информации, организация циклов перебора
эле­ментов массива, подготовке
информации для второго блока, обраще­ние
к четвёртому блоку, видача
результатов
счета. Зо
втором
блоке осуществляется решение уравнения
для определения t;
.
Для
каждого L
уравнение
имеет свои параметры, поэтому эту часть
алгоритма желательно оформить как
самостоятельный елок., с изме­няющейся
входной информацией.

Второй
блок обращается к блоку определения
функций Sitt)
для
различных значений і
,
определяемых алгоритмом второго блока.
Следовательно, блек вычисления интеграла
должен допускать не толь­ко
изменение параметров подынтегральной
функции, но и изменение верхнего предела
интегрирования, четвёртый блок
предназначен для упорядочения (одним
из возможных методов) массива чисел.

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

СПИСОК
РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Гурова
Л.И. Основы программирования,-М.
:Статистика,1976.-

318с.

1. К
   р и н и ц к и й H.A., Миронов
   Г.А., Фролов
   Г.Д. Программирование и алгоритмические
   языки.-М. :Наука,1975..-ч90с.

2. Ж
   оголев
   Е.А., Трифонов
   Н.П. Курс программирования.-М.:Наука,1971,-ЗВОс.

СОДЕРЖАНИЕ

1. АНАЛИЗ
ЗАДАЧИ 3

1. Моделирование
   процесса решения 3

2. Формализация
   процесса решения задачи 4

3. Примеры 7

2. ПОНЯТИЕ
АЛГОРИТМА 9

1. Интуитивное
   понятие алгоритме 9

2. Некоторые
   свойства алгоритмов 10

3. Пример 13

2.4. Связь
интуитивного понятия алгоритма и
строгогоопределения
алгоритма 15

3. СПОСОБЫ
ИЗОБРАЖЕНИЯ АЛГОРИТМОВ 16

3.1. Связь
алгоритма и метода решения задачи 16

1. 3.2. Общая
   структура оператора и набор
   основныхоператоров Формульнс—словесный
   способ записи алгоритмов 21

2. Операторные
   схемы записи алгоритмов 22

3. Блок-схема
   — рабочий инструмент программиста 24

4. ОСНОВНЫЕ
СТРУКТУРНЫЕ ЭЛЕМЕНТЫ АЛГОРИТМОВ 29

1. Линейные
   и ветвящиеся участки алгоритма 29

2. Общая
   структура циклического процесса 31

3. Вида
   циклов ¹⁷

³⁴

5. ОСНОВНЫЕ
ВЫЧИСЛИТЕЛЬЯНЕ АЛГОРИТМЫ 36

1. Алгоритмы
   обработки массивов 36

2. Вычисление
   функций 39

3. Алгоритмы
   решения уравнений 43

4. Пример
   реяения задачи ⁴⁵
   Список
   рекомендуемой литературы ⁴⁶

ОСНОВЫ
АЛГОРИТМИЗАЦИИ

Методические
указания по курсу

»
ПРАКТИКУМ НА Э В М «

Состз
жители: доц. И.Г.ГУБАРЬ, вссист В.Н.2ШЮВ

Редактор
З.В.Иванова Техрг актор Н.Р.Алексеева

Формат
60×34 1/16. Бумага типографская # 2. Печать
плеская. Усл.печ.л. 2,01. Уч.-изд.л. 2,01, Заказ
* 45 Тираж 500 экз. Цена 45 к.

^редакЦионно-издательский
отдел ЛГУ, г. Глепропетровск, пр. Гагарина,
72.

Ротапринт
ЛГУ, г. Днепропетровск, ул. Генерале
Пушкин?, 4

Соседние файлы в папке Библиотека

• #
• #