Информатика группа 505.Законспектировать прислать на почту,фото отчетом. 08.11.2022 г.

 Примеры составления алгоритмов

Определение 1.4. Под алгоритмизацией понимают процесс разработки алгоритма решения какой-либо задачи.

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

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

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

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

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

Задача 1.1. Даны два действительных числа а и Ь. Необходимо найти их сумму 5, разность Я, произведение Р и частное Н от деления а на Ь.

Алгоритм кажется очевидным: ввести в память ЭВМ числа а и Ь, выполнить вычисления 5 = а + Ь, Я = а - Ь, Р= а : Ь, Н = а/Ь и вывести на экран (принтер) полученные результаты. Однако такой алгоритм ошибочен для случая, когда Ь = 0. В этом случае чисто математически мы могли бы записать, что Н- а/Ь = со. Однако в компьютере операция деления на нуль не определена, вследствие чего на экране дисплея будет выведено сообщение «деление на нуль» и вычисление программы прервано. Поэтому проверка, равно ли Ь нулю, в алгоритме должна быть предусмотрена. Правильный алгоритм приведен на рис. 1.3. Ниже дана текстовая его форма.

Шаг 1. Ввести а, Ь.

Шаг 2. Вычислить Б = а + Ь, Я = а - Ь, Р= аЬ.

Шаг 3. Вывести Я, Р.

Шаг 4. Если Ь = 0, перейти к шагу 7.

Шаг 5. Вычислить Н = а/Ь .

Шаг 6. Вывести Н и перейти к шагу 8.

Шаг 7. Вывести Ь = 0, Н — СО.

Шаг 8. Остановиться.

Задача 1.2. Даны два действительных положительных числа а и Ь. Найти среднее арифметическое и среднее геометрическое этих чисел.

Как известно, среднее арифметическое чисел а, Ь определяется как ?= {а + Ь)/2, а среднее геометрическое как С =у[аЬ. Поэтому блок-схема алгоритма представлена на рис. 1.4. Текстовая его форма будет такой.

Шаг 1. Ввести а, Ь.

Шаг 2. Вычислить ?= (а + Ь)/2, С = 4аЬ.

Рис. 1.3. Алгоритм выполнения арифметических действий над действительными

числами а, Ь

5 = (а+6)/ 2

Рис. 1.4. Алгоритм вычисления среднего арифметического и среднего геометрического двух чисел

Шаг 3. Вывести (7. Шаг 4. Остановиться.

В приведенном алгоритме записана операция среднего геометрического (7 = 4аЬ. Казалось бы, следовало вначале вычислить значение с=аЬ, а затем, используя, например, алгоритм Ньютона (см. рис. 1.1), вычислить (7. Однако в наборе стандартных программ компьютера имеется программа, вычисляющая квадратный корень из положительного числа. Поэтому при соответствующем обращении к этой программе она и вычислит (7.

Задача 1.3. Даны два действительных числа а и Ь. Определить, какое из чисел большее или они равны. Алгоритм решения задачи изображен на рис. 1.5.

Текстовая его форма такая.

Шаг 1. Ввести а, Ъ.

Шаг 2. Если а = Ь, перейти к шагу 6.

Шаг 3. Если а > Ь, перейти к шагу 5.

Шаг 4. Вывести Ъ> а и перейти к шагу 7. Шаг 5. Вывести а> Ь и перейти к шагу 7. Шаг 6. Вывести а = Ь.

Шаг 7. Остановиться.

Задача 1.4.

Вычислить значение функции 1 -х, если* < 1;

+ х³. если 2 < х <

• ? =
• 1/х², если 1 < х <

л/Г

1 + х + х², еслих > 3.

Алгоритм вычисления ? представлен на рис. 1.6. Текстовая его форма следующая.

Шаг 1. Ввести х

Шаг 2. Если х< 1, перейти к шагу 8.

Шаг 3. Если х< 2, перейти к шагу 7.

Шаг 4. Если л:< 3, перейти к шагу 6.

Шаг 5. Вычислить ?= 1 +Х + *² и перейти к шагу 9.

Шаг 6. Вычислить ? = V1 + х³ и перейти к шагу 9.

Шаг 7. Вычислить ?= 1/х² и перейти к шагу 9.

Шаг 8. Вычислить ?- 1 - х.

Шаг 9. Вывести х, ?.

Шаг 10. Остановиться.

Задача 1.5. Составить алгоритм вычисления корней квадратного уравнения ах² + Ьх + с = Ос действительными коэффициентами а, Ь, с ф 0, когда а ф 0, Ь ф0, с ф0.

Как известно, в зависимости от знака дискриминанта с1 = Ь² - 4 ас квадратное уравнение ах² + Ьх + с = Ос действительными коэффициентами а, Ь, сф 0 может иметь три типа корней: разные действительные корни, если с1> 0, равные действительные корни, если с!= 0, и комплексные сопряженные корни, если с! < 0. Разные действительные корни вычисляются по формулам

Начало

Вывести х, У

I

Конец

~ь + 4<4 ~ь -4(1 г,

х, =-, х₂ =-. Равные корни определяются так: х, =

2 а " 2 а

= х₂ = —. Комплексные сопряженные корни вычисляются так 2 а

м

• 2а
• — мнимая часть

же, как и действительные, только представляются двойкой чисел -Ь . л!4

— ± /-—, где знак / указывает на то, что 2а 2а

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

Шаг 1. Ввести а, Ь, с.

Шаг 2. Вычислить с1 = Ь² - 4ас, к = а + а, к = -Ь/к.

Шаг 3. Если <4< 0, перейти к шагу 7.

Шаг 4. Если <4> 0, перейти к шагу 6.

Шаг 5. Положить х, = к и перейти к шагу 10.

Шаг 6. Вычислить g = 4(4, г = g/h, х_х = к + г, х₂ = к - г и перейти к шагу 9.

Шаг 7. Вычислить g = у{4, г = g/h.

Шаг 8. Вывести: «Корни комплексные х, = /:+/>, х₂ = /:-/>» и перейти к шагу 11.

Шаг 9. Вывести: «Корни действительные» х,, х₂ и перейти к шагу 11.

Шаг 10. Вывести: «Корни, равные х, = х₂» х,.

Шаг 11. Остановиться.

Большинство приведенных алгоритмов содержат так называемые разветвления, т. е. места в блок-схемах, где вычисления направляются по разным путям. Эти места определяются блоками сравнения величин. Из каждого блока имеется два выхода, один из которых соответствует тому случаю, когда условие сравнения выполняется («да»), другой — случаю, когда оно не выполняется («нет»). Такие алгоритмы называются алгоритмами с разветвляющейся структурой.

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

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

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

Задача 1.6. Дан ряд чисел х₁₅ х₂,..., х,-, ..., х_п. Найти их сумму 5.

Так как сумма 5 = х, + х₂ + ... + х,- + ... + х_п и суммирование чисел выполняется последовательно, т. е. к найденной сумме 5_М добавляется х,- число, то вычисление 5, = 5_М + х,- повторяется п - 1 раз, если положить 5_М =х_х. Поэтому алгоритм вычисления суммы будет таким, как изображен на рис. 1.8. Текстовая его форма включает следующие действия.

Шаг 1. Ввести х,, ..., х_п, п.

Шаг 2. Положить 5=х,.

Шаг 3. Положить / = 2.

Шаг 4. Если /> п, перейти к шагу 7.

Шаг 5. Положить 5=5+ х,-.

Шаг 6. Положить / = / + 1 и вернуться к шагу 4.

Шаг 7. Вывести 5.

Шаг 8. Остановиться.

Рис. 1.8. Алгоритм вычисления суммы п чисел

В этом алгоритме роль счетчика циклов отводится переменной /, которая изменяется с шагом 1. Если бы требовалось вычисление суммы чисел х_}, ..., х_п через одно число, то очевидно, что шаг изменения переменной / должен быть взят равным 2, а начальное ее значение 3. Таким образом, в четвертом блоке схемы алгоритма следовало бы указать /= 3, а в седьмом / = /' + 2.

Задача 1.7. Составить алгоритм вычисления функции п («л-факториал»). Как известно, п — это произведение п натуральных чисел 1 • 2 • 3 •... • п. При этом принимают, что 1! = 1. Поэтому вычисление значения п можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала Т⁷ на очередное натуральное число. Алгоритм вычисления п приведен на рис. 1.9.

Начало

т~

Его текстовая форма такая.

Шаг 1. Ввести п.

Шаг 2. Положить Р= 1.

Шаг 3. Вычислить /= 2.

Шаг 4. Если / > п, перейти к шагу 7.

Шаг 5. Положить Г- Я.

Шаг 6. Положить /= /+ 1 и вернуться к шагу 4.

Шаг 7. Вывести Т⁷.

Шаг 8. Остановиться.

Аналогичным образом можно построить алгоритмы вычисления значений 2", а^п, где а — вещественное, а п — целые числа.

Задача 1.8. Составить алгоритм вычисления выражения к = = ^2 + ^2~+ ^2 + ... + л/2 . Нетрудно видеть, что если в качестве

-v-

пкорней

начального значения взять к = а/2 , то повторяющимся действием будет вычисление выражения V2 + к. Поэтому алгоритм решения этой задачи имеет вид, изображенный на рис. 1.10. Его текстовая форма такая.

Шаг 1. Ввести п.

Шаг 2. Вычислить к = а/2.

Шаг 3. Положить /= 2.

Шаг 4. Если /> п, перейти к шагу 7.

Шаг 5. Вычислить к = л/2 + к.

Шаг 6. Положить /'=/'+ 1 и вернуться к шагу 4. Шаг 7. Вывести к.

Шаг 8. Остановиться.

Задача 1.9. Составить алгоритм вычисления выражения S = = sin л: + sin²* ... + sin"*.

Если взять начальное значение суммы S = s'mx, то повторяющимся действием будет 5 + 5sin*. Алгоритм, вычисляющий указанную сумму, представен на рис. 1.11. Его текстовая форма такая.

Шаг 1. Ввести п, х.

Шаг 2. Вычислить 5 = sin*.

Шаг 3. Положить / = 2.

Шаг 4. Если /> п, перейти к шагу 7.

 

Шаг 5. Вычислить S =S + ^sinx.

Шаг 6. Положить / = / + 1 и вернуться к шагу 4. Шаг 7. Вывести S.

Шаг 8. Остановиться