Алгоритмы с повторением действий и групп операций. Алгоритм с повторением
В алгоритмические структуры цикл входит серия команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
Циклические алгоритмические структуры бывают двух типов:
Циклы со счетчиком, в которых тело цикла выполняется определенное количество раз;
Циклы с условием, в которых тело цикла выполняется до тех пор, пока выполняется условие.
Алгоритмическая структура цикл может быть зафиксирована различными способами:
Графически, с помощью блок-схемы;
На языке программирования, например на языках Visual Basic и VBA, с использованием специальных инструкций, реализующих циклы различного типа.
Цикл со счетчиком. Когда заранее известно, какое число повторений тела цикла необходимо выполнить, можно воспользоваться циклической инструкцией (оператором цикла со счетчиком) For. . . Next (рис. 19).
Синтаксис оператора For. . . Next следующий: строка, начинающаяся с ключевого слова For, является заголовком цикла, а строка с ключевым словом
Next - концом цикла; между ними располагаются операторы, представляющие собой тело цикла.
В начале выполнения цикла значение переменной Счетчик устанавливается равным НачЗнач. При каждом «проходе» цикла переменная Счетчик увеличивается на величину шага. Если она достигает величины КонЗнач, то цикл завершается и выполняются следующие за ним операторы.
Циклы с условием. Часто бывает так, что необходимо повторить тело цикла, но заранее неизвестно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Этот цикл реализуется с помощью инструкции Do... Loop.
Условие выхода из цикла можно поставить в начале, перед телом цикла (рис. 20) или в конце, после тела цикла (рис. 21).
Проверка условия выхода из цикла проводится с помощью ключевых слов While или Until. Эти слова
Придают одному и тому же условию противоположный смысл. Ключевое слово While обеспечивает выполнение цикла до тех пор, пока выполняется условие, т. е. пока условие имеет значение истина. В этом случае условие является условием продолжения цикла. Как только условие примет значение ложь, выполнение цикла закончится.
Ключевое слово Until обеспечивает выполнение цикла до тех пор, пока не выполняется условие, т. е. пока условие имеет значение ложь. В этом случае условие становится условием завершения цикла. Как только условие примет значение истина, выполнение цикла закончится.
11Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов; блок-схемы.
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.2. Вставить ключ в замочную скважину.3. Повернуть ключ два раза против часовой стрелки.4. Вынуть ключ.
Виды алгоритмов:
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);
3. Разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов :
· В устной форме.
· В письменной форме на естественном языке.
· В письменной форме на формальном языке.
· Для более наглядного представления алгоритма широко используется графическая форма – блок-схема , которая составляется из стандартных графических объектов.
Определение 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.
числами а, Ь
Рис. 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 -х, если*
+ х 3 . если 2
- 1/х 2 , если 1
1 + х + х 2 , еслих > 3.
Алгоритм вычисления ? представлен на рис. 1.6. Текстовая его форма следующая.
Шаг 1. Ввести х
Шаг 2. Если х 1, перейти к шагу 8.
Шаг 3. Если х перейти к шагу 7.
Шаг 4. Если л:
Шаг 5. Вычислить ?= 1 +Х + * 2 и перейти к шагу 9.
Шаг 6. Вычислить ? = V1 + х 3 и перейти к шагу 9.
Шаг 7. Вычислить ?= 1/х 2 и перейти к шагу 9.
Шаг 8. Вычислить ?- 1 - х.
Шаг 9. Вывести х, ?.
Шаг 10. Остановиться.
Задача 1.5. Составить алгоритм вычисления корней квадратного уравнения ах 2 + Ьх + с = а, Ь, с ф 0, когда а ф 0, Ь ф0, с ф0.
Как известно, в зависимости от знака дискриминанта с1 = Ь 2 - 4 ас квадратное уравнение ах 2 + Ьх + с = Ос действительными коэффициентами а, Ь, сф 0 может иметь три типа корней: разные действительные корни, если с1> 0, равные действительные корни, если с!= 0, и комплексные сопряженные корни, если с! 0. Разные действительные корни вычисляются по формулам
Вывести х, У
~ь + 4 г,
х, =-, х 2 = -. Равные корни определяются так: х, =
2 а " 2 а
= х 2 = -. Комплексные сопряженные корни вычисляются так 2 а
- - мнимая часть
же, как и действительные, только представляются двойкой чисел -Ь . л!4
- ± /--, где знак / указывает на то, что 2а 2а
значения корня. В связи с изложенным в алгоритме вычисления корней на первом этапе должно быть предусмотрено вычисление значения дискриминанта и дальнейшая проверка его знака. Алгоритм с максимальной экономией вычислительных операций приведен на рис. 1.7. Ниже дана его текстовая форма.
Шаг 1. Ввести а , Ь , с.
Шаг 2. Вычислить с1 = Ь 2 - 4ас, к = а + а, к = -Ь/к.
Шаг 3. Если 0, перейти к шагу 7.
Шаг 4. Если 0, перейти к шагу 6.
Шаг 5. Положить х, = к и перейти к шагу 10.
Шаг 6. Вычислить g = 4(4, г = g/h, х х = к + г, х 2 = к - г и перейти к шагу 9.
Шаг 7. Вычислить g = у{4, г = g/h.
Шаг 8. Вывести: «Корни комплексные х, = /:+/>, х 2 = /:-/>» и перейти к шагу 11.
Шаг 9. Вывести: «Корни действительные» х, х 2 и перейти к шагу 11.
Шаг 10. Вывести: «Корни, равные х, = х 2 » х,.
Шаг 11. Остановиться.
Большинство приведенных алгоритмов содержат так называемые разветвления, т. е. места в блок-схемах, где вычисления направляются по разным путям. Эти места определяются блоками сравнения величин. Из каждого блока имеется два выхода, один из которых соответствует тому случаю, когда условие сравнения выполняется («да»), другой - случаю, когда оно не выполняется («нет»). Такие алгоритмы называются алгоритмами с разветвляющейся структурой.
Теперь рассмотрим алгоритмы, которые содержат фрагменты повторения вычислений - циклы. В зависимости от того, известно ли наперед число повторений некоторого участка алгоритма или нет, различают циклы арифметические и итерационные.
В арифметических циклах число повторений вычислений контролируется с помощью управляющей переменной, играющей роль счетчика циклов. При каждом очередном вычислении значение счетчика изменяется на заданную величину и сравнивается с установленным количеством повторений. Если эти величины совпадают, повторения прекращаются, т. е. осуществляется выход из цикла по счетчику. В противном случае повторения вычислений продолжаются. Если перед началом цикла значение счетчика превышает заданное число повторений, он не выполняется вообще. Возможен также принудительный выход из цикла по некоторому наперед заданному условию.
В циклах итерационного типа, в которых число повторений наперед неизвестно, их прекращение (выход из цикла) осуществляется при выполнении некоторого условия. Обычно это условие формулируется, например, так: выполнять повторения до тех пор, пока х где с - постоянная величина (константа), ах-увеличивается с каждым повторением (итерацией). В том случае, когда условие проверяется до начала повторений, циклы относят к группе циклов с предусловием, когда же эта проверка осуществляется после каждой очередной итерации, они классифицируются как циклы с постусловием. Для первой группы циклов, если х >с, повторения вычислений не будет вообще, для второй всегда выполнится хотя бы один цикл. Все арифметические циклы - это циклы с предусловием.
Задача 1.6. Дан ряд чисел х 15 х 2 ,..., х,-, ..., х п. Найти их сумму 5.
Так как сумма 5 = х, + х 2 + ... + х,- + ... + х п и суммирование чисел выполняется последовательно, т. е. к найденной сумме 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. Поэтому вычисление значения п можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала Т 7 на очередное натуральное число. Алгоритм вычисления п приведен на рис. 1.9.
Его текстовая форма такая.
Шаг 1. Ввести п.
Шаг 2. Положить Р= 1.
Шаг 3. Вычислить /= 2.
Шаг 4. Если / > п, перейти к шагу 7.
Шаг 5. Положить Г- Я.
Шаг 6. Положить /= /+ 1 и вернуться к шагу 4.
Шаг 7. Вывести Т 7 .
Шаг 8. Остановиться.
Аналогичным образом можно построить алгоритмы вычисления значений 2", а п, где а - вещественное, а п - целые числа.
Задача 1.8. Составить алгоритм вычисления выражения к = = ^2 + ^2~+ ^2 + ... + л/2 . Нетрудно видеть, что если в качестве
п корней
начального значения взять к = а/2 , то повторяющимся действием будет вычисление выражения V2 + к. Поэтому алгоритм решения этой задачи имеет вид, изображенный на рис. 1.10. Его текстовая форма такая.
Шаг 1. Ввести п.
Шаг 2. Вычислить к = а/2.
Шаг 3. Положить /= 2.
Шаг 4. Если /> п, перейти к шагу 7.
Шаг 5. Вычислить к = л/2 + к.
Шаг 6. Положить /"=/"+ 1 и вернуться к шагу 4. Шаг 7. Вывести к.
Шаг 8. Остановиться.
Задача 1.9. Составить алгоритм вычисления выражения S = = sin л: + sin 2 * ... + 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. Остановиться.
Задача 1.10. Составить алгоритм вычисления среднего квадратического п действительных чисел х у, х 2 , ..., х п.
Известно, что средним квадратическим п действительных
чисел является величина 5* = Л -(х? + х + ... + х 2 п. Поэтому ал-
горитм будет таким (рис. 1.12). Его текстовая форма включает следующие действия.
Шаг 1. Ввести Ху, ..., х„, п.
Шаг 2. Положить / = 1.
Шаг 3. Если /> п, перейти к шагу 7.
Шаг 4. Положить ^ = 0.
Шаг 5. Вычислить +х,-х г
Шаг 6. Положить /=/-+- 1 и вернуться к шагу 3.
Шаг 7. Вычислить =8 к /п.
Шаг 8. Вычислить =д/^7.
Шаг 9. Вывести Шаг 10. Остановиться.
Задача 1.11. Составить алгоритм вычисления числа сочетаний п чисел по т для п > т > 0.
Число сочетаний из п по т, обозначаемое С" ! , вычисляется
по известной формуле С"" =
. Казалось бы построение
(п - т)т
алгоритма не вызывает проблем: вычислить значения п,
- (п - т) , т, используя для этого алгоритм (см. рис. 1.9), а затем реализовать формулу для определения С”". Такой подход в общем требует выполнения п - 1 + (п - т - 1) + т - 1 = 2/7-3 циклов. Имеется возможность сконструировать алгоритм вычисления значения С;, который будет выполнять всего т циклов. Тогда, в худшем случае, когда т всего лишь на единицу меньше п, число циклов будет примерно в 2 раза меньше 2/7. Этот алгоритм основан на использовании рекуррентного сотношения для вычисления С"".
/ X 1 , . . . , X/; , И
Рис. 1.12.
п действительных чисел
С, и т. д.
Для построения алгоритма запишем общее выражение для вычисления С" ! , которое будем вычислять в цикле. Согласно рекуррентному соотношению при т = 0 число сочетаний С^ 1 = С 1 =
При т = і число со-
= п. При т = 1 число сочетаний С 2 п
и І +1 ^ I
четании С, =-
пи -1 У1 - 171 ^ щ і
Оно записывается так: С =
С"”, С п = п и позволяет вычислять сочетания последовательно С =п, С 2 = ---С" п,
С" п. Так как в итоге необходимо получить зна
чение С"" т то / должно изменяться от 1 до т - 1. Блок-схема алгоритма приведена на рис. 1.13. Его текстовая форма такая.
Шаг 1. Ввести п, т.
Шаг 2. Если п вывести «Повторить ввод, п и вернуться к шагу 1.
Шаг 3. Если п = 1, перейти к шагу 10.
Шаг 4. Если п = т, перейти к шагу 9.
Шаг 5. Положить С= п, /= 1.
Шаг 6. Если / > т - 1, перейти к шагу 11.
Шаг 7. Вычислить С =- --С.
Шаг 8. Положить /= /+ 1 и вернуться к шагу 6.
Шаг 9. Положить С= 1 и перейти к шагу 11.
Шаг 10. Положить С=п.
Шаг 11. Вывести С.
Шаг 12. Остановиться.
Заметим, что в приведенной блок-схеме предусмотрен контроль правильности ввода чисел т так, чтобы п> т.
Задача 1.12. Сконструировать алгоритм вычисления многочлена (полинома) Р п (х) степени п для некоторого действительного значения х
Используя традиционную форму представления многочлена р п (х) =а п х п + а п _ х х п ~ х + ... + а 2 х 2 + а х х + а 0 , алгоритм можно
было бы изобразить, как на рис. 1.14.
Ввести #о» 5 а п, х
|
У=УХ, Р =Р+а,у |
||
Рис. 1.14. Алгоритм вычисления полинома, представленного
в канонической форме
В этом алгоритме в цикле используются две операции умножения и одна операция сложения. Существует, однако, другой более быстрый способ вычисления значения многочлена. Он основан на использовании схемы Горнера, согласно которой полином представляется следующим образом:
Р»(х) = (...((а п х + а п _)х + а п _ 2)х + ... + а х)х + а 0 .
Например, для п = 4 он имеет такой вид:
Р„(х) =(((а п х + а ъ)х + а 2)х + а х)х + а 0 .
Алгоритм, вычисляющий полином по схеме Горнера, приведен на рис. 1.15. В цикле он выполняет всего одну операцию умножения.
Задача 1.13. Разработать алгоритм табулирования функции у = /(х) на интервале [а, Ь], а с шагом Ах.
Под табулированием функции обычно подразумевают составление таблицы значений функции в точках а, а + Ах, а + 2Ах, а + /Ах, а + пАх заданного интервала. Алгоритм решения этой задачи может быть построен как с использованием арифметического, так и итерационного циклов. Для того чтобы применить арифметический цикл, необходимо предварительно определить число точек табуляции п = --- . Затем организовать по-
вторение п раз вычисления значений функции в точках а + Ах, а + пАх и добавить к найденным ее значениям значение /(а). Алгоритм, построенный с использованием указанных замечаний, приведен на рис. 1.16.
Ввести а , Ь, Ах
Рис. 1.16. Алгоритм табулирования функции /(х ) с использованием
арифметического цикла
Его текстовая форма следующая. Шаг 1. Ввести а , Ь, Ах.
Шаг 2. Вычислить п = --- .
Шаг 3. Вычислить у = /(а ), положить х= а.
Шаг 4. Вывести а , у.
Шаг 5. Положить /= 1.
Шаг 6. Если /> я, перейти к шагу 10.
Шаг 7. Положить х = х + Ах, вычислить у = Дх).
Шаг 8. Вывести х, у.
Шаг 9. Положить /= /"+ 1 и вернуться к шагу 6.
Шаг 10. Остановиться.
Алгоритм решения задачи с применением итерационного цикла приведен на рис. 1.17.
В этом алгоритме шаги 7, 8 проверяют, совпадает ли последняя точка табуляции функции со значением конца интервала Ь.
Задача 1.14. Составить алгоритм поиска наибольшего общего делителя (НОД) двух целых чисел a, b и наименьшего общего кратного (НОК) этих чисел.
Как известно, НОД чисел a, b - такое наибольшее целое число, которое делит эти числа без остатка. Наименьшим общим кратным целых чисел а , b является целое число, которое делится на а и Ь. Если известен НОД, то НОК вычисляется по следующей формуле: НОК (а , b) = ab/Oj(a, b). Поэтому прежде чем вычислять НОК, необходимо найти НОД.
Существует несколько алгоритмов вычисления НОД. Приведем простейший из них, который принадлежит древнегреческому математику Евклиду. Он заметил, что НОД (а , b ) равен НОД ((а - b), Ь), где а > Ь. Поэтому суть его алгоритма сводится к последовательному вычитанию из большего числа меньшего до тех пор, пока эти числа станут равными между собой. Алгоритм приведен на рис. 1.18 и содержит цикл итерационного типа.
Текстовая форма алгоритма вычисления НОД, НОК следующая.
Шаг 1. Ввести а, Ь.
Шаг 2. Положить и = a, v = b.
Шаг 3. Если а = Ь, перейти к шагу 7.
Шаг 4. Если а> Ь, перейти к шагу 6.
Рис. 1.17.
итерационного цикла
Рис. 1.18. Алгоритм вычисления наибольшего общего делителя чисел а, Ь и наименьшего их кратного
Шаг 5. Положить х = а, а = Ь, Ь = х.
Шаг 6. Положить х = а - Ь, а = х и вернуться к шагу 3.
Шаг 7. Положить НОД = а.
Шаг 8. Вычислить НОК = и г/НОД.
Шаг 9. Вывести а , Ь, НОД, НОК. Шаг 10. Остановиться.
Задача 1.15. Разработать алгоритм вычисления значения цеп-
ной дроби У =---для х ф 0.
Как следует из записи дроби, последним в ней делителем яв-
ляется выражение С=х + -, значение которого при задан- ном х легко может быть найдено. Предпоследним делителем яв-
ляется выражение С = х +
А предшествую-
х щим ему делителем является выражение С =х + - , где С -
найденное перед этим значение делителя. Таким путем может
быть найдено значение делителя С =х + - , а затем значение дроби У = -.
Очевидно, что повторяющимся действием в этой задаче является поиск очередного делителя. Учитывая, что 2 = 2 1 , а 256 = 2 8 , всего необходимо найти восемь делителей. Исключая последний делитель, всего получаем семь повторяющихся действий. На основании изложенных рассуждений конструируем алгоритм, вычисляющий заданное выражение (рис. 1.19). Его текстовая форма такая.
Шаг 1. Ввести х.
Шаг 2. Положить а = хх, Ь = 256.
Шаг 3. Вычислить с = а + Ь/а.
Шаг 4. Положить і = 7.
Шаг 5. Если і 1, перейти к шагу 8.
Шаг 6. Вычислить b = 0,56, с = а + Ь/с.
Шаг 7. Положить і - і - и вернуться к шагу 5.
Шаг 8. Вычислить Y=x/C.
Шаг 9. Вывести у, х.
Шаг 10. Остановиться.
Задача 1.16. Дан ряд чисел а х, а 2 , ..., а„ ..., а п. Разработать алгоритм поиска наибольшего и наименьшего числа в этом ряду с указанием номера (индекса) его расположения.
Очевидный способ поиска наибольшего (наименьшего) числа в заданном ряду п чисел включает следующие действия. Взять первое число ряда и сказать, что оно наибольшее (наименьшее), а индекс его равен 1. Затем взять второе число ряда и сравнить с предполагаемым максимальным (минимальным) первым числом. Если второе число больше предполагаемого максимального (минимального) первого числа, заменить этим числом первое число и положить его индекс равным двум. Если же второе число окажется меньше первого числа, взять третье число ряда и сравнить с первым. Так следует действовать до тех пор, пока не будет выбрано последнее а п число. В результате на месте первого числа окажется наибольшее (наименьшее) число с указанным его номером в ряду чисел. Реализующий эти действия алгоритм приведен на рис. 1.20. Текстовая его форма следующая.
Шаг 1. Ввести а х, ..., а п, п.
Шаг 2. Положить max = а х, і - 1, min - а х, j - 1.
Шаг 3. Положить к = 2.
Шаг 4. Если а к max, перейти к шагу 6.
Шаг 5. Положить max = а к, і = к.
Шаг 6. Если а к > min, перейти к шагу 8.
Шаг 7. Положить min = а к, j = к.
Шаг 8. Положить к= к+ 1.
Шаг 9. Если к вернуться к шагу 4.
Шаг 10. Вывести max, /", min, у.
Шаг 11. Остановиться.
Задача 1.17. Дан ряд чисел а х, а 2 , ..., а„ ..., а п и число Ь. Сконструировать алгоритм поиска в ряду числа а к, равного Ь, и сообщения, найдено число или нет.
Рис. 1.20.
в последовательности чисел
Решение этой задачи сводится к последовательному сравнению чисел ряда а { , а 2 , ..., а п с числом Ь, выводу числа а к, совпадающего с Ь, и его индекса к или выводу сообщения, что необходимое число не обнаружено. Очевидный алгоритм ее решения приведен на рис. 1.21.
Ввести СЛи ...,7, Ь
Этот алгоритм в худшем случае, т. е. когда число не обнаружено, выполняет 2п сравнений. Вместе с тем есть алгоритм, который при п > 8 заметно сокращает это число, а следовательно, и время поиска. Улучшенный алгоритм приведен на рис. 1.22. Уменьшение количества сравнений достигается за счет исключения постоянных сравнений / с п, характерных для первого алгоритма. Выход из цикла осуществляется либо когда а , = Ь , либо когда на (п+ 1)-м повторении обнаружится число Ь, записанное в (п + 1)-й ячейке массива.
Последние две задачи относят к задачам обработки массивов - наборов данных одного вида - чисел или символов. В программировании различают массивы одномерные и многомерные. Одномерный массив образуют последовательные его элементы. Место элемента в массиве определяется его номером - индексом, представляющим собой положительное число. Рассмотренные последовательности чисел а ., а ъ
Ь являются одномерными массивами.
Двумерные массивы - это прямоугольные таблицы данных, состоящие из заданного количества строк и колонок (столбцов). В математике такие таблицы называются матрицами и весьма широко используются как непосредственно при математических вычислениях, так и в программировании. Элемент матрицы размещается на пересечении строки и столбца и идентифицируется двумя индексами: номером строки, например /, и номером столбца, например у. Если матрица содержит т строк и п столбцов, всего элементов этой матрицы тп и а ] - произвольный ее элемент. Матрица, содержащая т строк и т столбцов, называется прямоугольной.
В квадратной матрице выделяют главную и побочную диагонали. Матрица А = а ц размером т х п, т. е. содержащая т строк
и п столбцов, т = п, имеет вид:
|
Главную диагональ матрицы образуют элементы а и, а 22 , ..., а тп, т. е. элементы, лежащие на прямой, проведенной слева направо от элемента а п к элементу а тп.
Побочную диагональ образуют элементы матрицы а 1п, а 2п _ х, ..., а т1 , лежащие на прямой, проведенной от элемента а 1п к элементу а т{ , т. е. справа налево.
Элементы матрицы А, лежащие справа и вверху от главной диагонали, образуют верхнюю треугольную матрицу. Элементы, лежащие слева внизу от главной диагонали, образуют нижнюю треугольную матрицу.
Матрица называется симметричной, если элементы, симметричные относительно главной диагонали, равны между собой, т. е. а и = й / (.
Одной из важнейших задач обработки одномерных массивов является их сортировка - расположение элементов массивов в определенном порядке. Чаще всего рассматривается упорядочение элементов числовых массивов по возрастанию или убыванию. По статистическим данным, примерно 25 % времени работы ЭВМ расходуется на сортировку данных, потому что отсортированные данные обрабатывать значительно проще. Когда элементы массива отсортированы, их быстрее найти, обновить, исключить из массива и т. п.
Существует целый ряд алгоритмов сортировки. Среднее время их работы или временная сложность лежит в пределах от 0(п 2 / 4) до 0(ппп), где п - число элементов массива. К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае.
Рассмотрим простейшую сортировку, называемую сортировкой вставками. Идея этой сортировки состоит в том, что очередной (сортируемый) элемент массива, упорядочиваемого, например, по возрастанию, сравнивается с предшествующими его элементами до тех пор, пока не встретится элемент, меньший или равный ему. Тогда все элементы, следующие за меньшим элементом, сдвигаются на одну позицию вправо, а очередной элемент ставится на освободившееся место за меньшим элементом. Если же в результате сравнения сортируемого элемента с предшествующими элементами массива меньший элемент не будет обнаружен, сортируемый элемент оставляют на старом месте и переходят к очередному элементу массива. Сравнения начинают со второго элемента массива и заканчивают последним его элементом.
Рассмотрим эту сортировку на массиве целых чисел
- 71 27 412 81 59 14 273 87, который требуется упорядочить по возрастанию. Первым сортируемым элементом массива является второй элемент - число 27. Образно говоря, «вынимаем» его из массива, т. е. освобождаем место для будущего сдвига чисел вправо, и сравниваем второй элемент (число 27) с первым элементом (число 71). Так как 27
- 27 71 412 81 59 14 273 87,
в которой часть массива 27, 71 предварительно отсортирована.
Теперь выбираем третий элемент массива - число 412. Запоминаем его и сравниваем с предшествующим элементом массива. Так как 412 > 71, а 71 > 21, оставляем число 412 на своем месте, т. е. получаем прежний массив
27 71 412 81 59 14 273 87.
Выбираем четвертый элемент массива - число 81. Запоминаем его и сравниваем с предшествующим элементом - числом 412. Так как 81
27 71 81 412 59 14 273 87.
Выбираем пятый элемент массива - число 59. Запоминаем это число и сравниваем с предшествующим элементом массива - числом 412. Так как 59 59, сдвигаем его на одну позицию вправо. Нетрудно видеть, что процесс сравнения и сдвига элементов закончится на числе 27. В результате получим
27 59 71 81 412 14 273 87.
Шестым элементом массива является число 14. Путем сравнения его с предшествующими элементами и сдвигов их вправо получим массив
14 27 59 71 81 412 273 87.
Выполнив описанные действия с седьмым и восьмым элементами массива, получим отсортированный список
14 27 59 71 81 87 273 412.
Задача 1.18. Разработать алгоритм сортировки вставками.
Согласно изложенному методу сортировки общим повторяющимся действием является выбор очередного сортируемого элемента и его запоминание. Элементы выбираются, начиная со второго и заканчивая последним п-м элементом массива. Эти действия составят внешний цикл алгоритма. Внутренний цикл алгоритма образуют действия сравнения и, если необходимо, сдвига элементов, а также его вставки в необходимую позицию массива. Поэтому алгоритм, реализуемый рассматриваемым методом, будет иметь такой вид (рис. 1.23). Его текстовая форма следующая.
Шаг 1. Ввести я, ..., а п, п.
Шаг 2. Положить / = 2.
Шаг 3. Положить к = я,
Шаг 4. Положить у = /"- 1.
Шаг 5. Если к > а р перейти к шагу 8.
Шаг 6. Если у
Шаг 7. Положить а ]+х = а р у = у - 1 и вернуться к шагу 5.
Шаг 8. Положить я /+1 = к, /= / + 1.
Шаг 9. Если / п, вернуться к шагу 3.
Шаг 10. Вывести я, ..., я„.
Шаг 11. Остановиться.
Проверка условия у > 0 в приведенной блок-схеме необходима для того, чтобы при сравнении сортируемого элемента к с предшествующими а р я-_, я, не выйти за пределы массива. Иначе алгоритм не будет определен. В заключение отметим, что сортировка вставками согласно достаточно эффективна для массивов с максимальным количеством элементов п 0(п 3/2), и быстрой сортировке, средняя сложность которой 0(1п(я)). Как правило, такая сортировка применяется для массивов с числом элементов п > 1000.
В тех случаях, когда в некотором массиве постоянно осуществляется поиск элементов, этот массив предварительно сортируется и в дальнейшем поиск осуществляется в упорядоченном
Рис. 1.23.
массиве. В качестве алгоритма поиска чаще всего используется так называемый бинарный поиск. Практика показывает, что такой подход существенно уменьшает средние временные затраты на поиск.
Суть бинарного поиска следующая. Пусть задан упорядоченный по возрастанию массив чисел а х, а 2 , а п а п и число Ь. Требуется найти элемент массива а к, равный Ь, или сообщить, что такого элемента в массиве нет. Обозначим первый индекс массива /, а последний и. Тогда индекс у числа а р стоящего примерно в середине массива, может быть найден по выражению у = |(/ + и)/ 2_|, где символы |_ ] определяют целую часть числа (/ + и)/ 2. Если
я- = Ь, процесс поиска завершен. Если же Ь то в силу упорядоченности массива я, ..., а п искомое число будет находиться в подмассиве а„ ..., а ] _ 1 . Когда же Ь > а р то по той же причине число следует искать в подмассиве я у+1 , ..., а п. Таким образом, в результате выбора числа а ] и сравнения его с числом Ь можно перейти к поиску в массиве с числом элементов, меньших в 2 раза, чем п. Далее процесс выбора элемента я. осуществляется в одном из подмассивов, сокращая поиск в массиве с числом элементов, меньших в 2 раза, чем в подмассиве. Этот процесс выбора а ] и деления очередного массива пополам продолжается до тех пор, пока не будет найдено заданное число либо установлено, что его в массиве нет. Описанный процесс продемонстрируем на поиске элемента Ь = 59 в следующем массиве
14 27 59 71 81 87 273 412 501.
Массив содержит девять элементов, поэтому у = |_(1 + 9)/2_| =
5. Элемент с индексом 5 - это а 5 = 81. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 14 27 59 71 (/= 1, и =у - 1 = 5 - 1 = 4). Теперь вычисляем индекс у = |_(1 + 4)/2_| = 2.
Элемент с индексом 2 - это а 2 = 27. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 59 71 (/=у+1 =
2+1 = 3, и = 4). Вычисляем индекс у = |_(3 + 4)/2_| = 3. Элемент
с индексом 3 - это я 3 = 59. Сравниваем его с Ь = 59 и устанавливаем, что это искомый элемент массива.
Теперь рассмотрим случай, когда элемент Ь= 12, т. е. он не принадлежит массиву. Первый индекс у = 5 и мы переходим к поиску в массиве 14 27 59 71 (/ = 1, и = 4). Второй индекс у = 2, что дает очередной массив поиска 14 27 (/= 1, и = 2). Третий индекс поиска у = 1(1 + 2)/2 I = 1 и мы переходим к массиву поиска 14
(/ = 1, и = 0). Однако в массиве нет элемента с индексом и = 0. Это означает, что мы проверили весь массив и не нашли элемента я; = Ь. Таким образом, можно сделать вывод, что признаком отсутствия элемента в массиве служит неравенство и
Задача 1.19. Составить алгоритм бинарного поиска.
Учитывая изложенное, можно предложить следующий алгоритм решения указанной задачи (рис. 1.24). Его текстовая форма приведена ниже.
Рис. 1.24.
Шаг 1. Ввести а х, а п, п, Ь.
Шаг 2. Положить / = 1, и = п.
Шаг 3. Если и перейти к шагу 9.
Шаг 4. Вычислить |_(/ + «)/2_|.
Шаг 5. Если а ] = Ь, перейти к шагу 8.
Шаг 6. Если а / положить и =у - 1 и вернуться к шагу 3.
Шаг 7. Положить / = у + 1 и вернуться к шагу 3.
Шаг 8. Вывести «Элемент найден», у = и перейти к шагу 10.
Шаг 9. Вывести «Элемент не найден».
Шаг 10. Остановиться.
Идея бинарного поиска используется и в других случаях, в частности при вычислении корней трансцендентных и алгебраических уравнений. Пусть задано трансцендентное уравнение, например е х - х - 2 = 0, и известно, что его корень принадлежит интервалу [а, Ь. Требуется найти значение этого корня.
В общем виде уравнение может быть записано как /(х) = 0, где Дх) - непрерывная функция, рассматриваемая на интервале [а, Ь]. Поскольку решение уравнения, т. е. его корень, х е [а, Ь] обращает уравнение в тождество, то левая часть равенства /(х) = 0 в точке х е а,Ь] должна быть равна нулю. С геометрической точки зрения это означает, что функция /(х) в точке х пересекает ось абсцисс. Эту точку пересечения и необходимо найти.
Для этого поступаем следующим образом. По выражению IV= (а + Ь)/2 находим координату IV середины отрезка [а, Ь. Если Дх) = 0, то корень уравнения х= IV найден. Если /(а )/(ВО > 0, т. е. /(а ) и /(ВО одного знака, корня на интервале нет (рис. 1.25), и мы переходим к его поиску на интервале , который вполовину короче исходного интервала [а, Ь ]. Если /(а )/(ВО а) и /(ВО разных знаков, корень находится на интервале [а, IV], и его поиск осуществляется на этом интервале, а интервал [ IV, Ь] забывается.
Таким образом, вычисляя выражение Ц^=(а+Ь)/2 и выполняя сравнение /(я) /(IV) > 0, мы сокращаем интервал поиска ровно вдвое. В результате после п таких действий получим интервал [а п, Ь п ], которому принадлежит корень уравнения, в 2" раз меньший исходного интервала [а, Ь, т. е. а п - Ь п = а - ^/2". Приняв в качестве точности вычисления корня а длину интервала |а п - Ь п, можно определить, что для получения этой точности необходимо сделать п = па - Ь |/е шагов. Описанный метод по-
Рис. 1.25.
иска корня получил название метода половинного деления, или дихотомии.
Задача 1.20. Разработать алгоритм уточнения корня уравнения /(х) = 0 методом дихотомии.
Метод предполагает, что задан интервал а, Ь, которому принадлежит корень, функция /(х) = 0 непрерывна и ограничена на этом интервале и f(a) f(b )
Шаг 1. Ввести а, Ь, е.
Шаг 2. Положить и = /(я), v = f(b).
Шаг 3. Вычислить х = а + , w = f(x).
Шаг 4. Если w = 0, перейти к шагу 10.
Шаг 5. Если uw> 0, перейти к шагу 7.
Шаг 6. Положить b = x, v=w и перейти к шагу 8.
Шаг 7. Положить а = х, u=w.
Шаг 8. Если а - Ь > с, вернуться к шагу 3.
Шаг 9. Положить х = а - Ь.
Шаг 10. Вывести х, s.
Шаг 11. Остановиться.
При решении различных задач часто приходится использовать значения элементарных функций, таких как sin (х), cos (х), log (х), In (х), е х и др. Для того чтобы облегчить процесс вычис-
и=/(а), у=/(6)
х = (а + Ь)/ 2, №=Ах)
Ь=х,у = 1Г
Рис. 1.26.
ления этих функций, в системной библиотеке компьютера хранятся заранее составленные программы вычисления их значений. Для их использования достаточно лишь упомянуть имя функции и указать ее аргумент. В свою очередь указанные программы составлены на основании формул разложения той или иной функции в ряд. Например, функция е х представляется сле-
дующим бесконечным рядом е х = 1 + X +-+
Для функций sin (х), cos (х) соответственно имеем:
. , V X X
В каждом из указанных разложений точность представления той или иной функции определяется числом членов ряда. Чем больше это число, тем точнее вычисляется функция при одном и том же х. Поэтому для вычисления значения функции с заданной точностью с поступают следующим образом. Вычисляют и суммируют члены ряда до тех пор, пока очередное слагаемое не станет по модулю меньше 8.
Звдача 1.21. Составить алгоритм вычисления функции зт(х) с точностью 8 при помощи разложения ее в ряд.
Из формулы, которая приближенно представляет функцию бш(х) в виде бесконечного ряда, следует, что алгоритм вычисления значения 8ш(х) с заданной точностью е будет включать повторяющиеся действия вычисления очередного члена ряда, суммирования членов ряда и изменения знака перед соответствующим членом ряда. Нетрудно видеть, что каждый очередной член ряда У п и может быть вычислен по рекуррентной формуле У п =
Например,
у хх2 _ * 3 у _у
- 1 2 1 (2 1+1) 3!’ 2 1
- 2л(2т ) 3!- 4-5 5!
Знаки членов ряда меняются поочередно, если начинать с У х.
Поэтому начальными установками алгоритма будут такие ?=х , 6’ = х, Z= хх, а = - 1. В цикле будем вычислять очередной
член ряда ? = --- и прибавлять его к предшествующей
2п(2п + 1)
сумме с соответствующим знаком. Блок-схема алгоритма приведена на рис. 1.27. Его текстовая форма дана ниже.
у =х, 8=х,
?-хх,а -~
Рис. 1.27.
Шаг 5. Вычислить 6’= 5 + у.
Шаг 6. Если у
Шаг 7. Положить а = -а, п = п + 1 и вернуться к шагу 4. Шаг 8. Вывести 5, х, е.
Шаг 9. Остановиться.
Задача 1.22. Составить алгоритм вычисления следа квадрат
а 2 а
а, Л а
|
... сі пп |
Шаг 1. Шаг 2. Шаг 3.
Ввести х, е.
Положить у = х, 5 = х, Z= хх, а = Положить п= 1.
Вычислить к= 2п, У =
к(к + 1)
а , а
ной матрицы А =
Как было сказано раньше, след матрицы - это сумма эле-
ментов ее главной диагонали, т. е. Я, - ^а и. Поэтому алгоритм
определения следа сводится к вычислению суммы Блок-схема этого алгоритма приведена на рис. 1.28.
Вместе с тем есть способ построить более эффективный алгоритм решения этой задачи. Он основан на вычислении адреса очередного диагонального элемента матрицы А не в двумерном, а в одномерном массиве.
Известно, что элементы двумерных и больших измерений массивов в памяти компьютера записываются линейно. Ниже в качестве примера приведена линейная запись элементов матрицы А с тремя строками и столбцами.
Через индексы строк и столбцов /, у номер любого элемента в линейном массиве вычисляется по формуле х = (/ - 1)я+/ Например, номер элемента а 22 определяется так (2 - 1)3 + 2 = 5. Таким образом, чтобы выбрать какой-либо элемент из линейного
Рис. 1.28.
массива, необходимо вычислять его номер по выражению А / "= (/- 1 )п + у, т. е. выполнить три арифметические операции.
В то же время можно видеть, что номер очередного диагонального элемента в линейном массиве отличается от номера предшествующего диагонального элемента на постоянную величину к = п + 1. Например, номер а 22 - 5 равен номеру а п - 1, т. е. 1 +4 = 5. Поэтому в линейном массиве очередной диагональный элемент определяется по номеру / = / + к. В результате его вычисление требует выполнить вместо трех всего одну арифметическую операцию, что в целом приводит к уменьшению объема вычислений и повышению быстродействия алгоритма. Блок-схема этого алгоритма приведена на рис. 1.29.
Задача 1.23. Разработать алгоритм вычисления суммы элементов побочной диагонали квадратной матрицы А.
В качестве примера рассмотрим матрицу с тремя строками и
тремя столбцами А =
Рис. 1.29. Эффективный алгоритм вычислени следа матрицы А
Через элементы побочной
диагонали этой матрицы для их выделения проведена прямая линия. Первый индекс диагональных элементов - это номер строки /, второй, как нетрудно видеть, вычисляется по выражению у = п + 1 - /", где к - п + 1. Поэтому блок-схема алгоритма, решающего эту задачу, будет иметь вид, представленный на рис. 1.30. Его текстовая форма приведена ниже.
Рис. 1.30. Блок-схема алгоритма вычисления суммы элементов побочной
диагонали квадратной матрицы А
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить? = 0, / = 1, к= п + 1.
Шаг 3. Вычислить? р = + а 1к _ г
Шаг 4. Положить / = /" + 1.
Шаг 5. Если /п, вернуться к шагу 3.
Шаг 6. Вывести $ р.
Шаг 7. Остановиться.
Очевидно, что для решения этой задачи также можно построить более быстрый алгоритм, в основу которого положить выбор элементов из линейного массива.
Задача 1.24. Нарисовать блок-схему алгоритма, вычисляющего сумму элементов верхней треугольной матрицы А.
Рассмотрим матрицу А, состоящую из п строк и п столбцов.
|
С1 пп |
Нетрудно видеть, что первый индекс эле
мента верхней треугольной матрицы - это индекс строки /. Второй индекс определяется по выражению у = / + 1. Поэтому блок-схема алгоритма будет иметь вид, представленный на рис. 1.31. В алгоритме имеется два цикла: один внешний и второй внутренний. Такие циклы называются вложенными. Текстовая форма алгоритма приведена ниже.
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить А т = 0, /"= 1.
Шаг 3. Положить у = / + 1.
Шаг 4. Вычислить А, = 5 Т + а ц.
Шаг 5. Положить у =у + 1.
Шаг 7. Положить /"=/"+ 1.
Шаг 9. Вывести А т.
Шаг 10. Остановиться.
Задача 1.25. Нарисовать блок-схему алгоритма получения транспонированной матрицы А, на месте исходной квадратной матрицы А.
Квадратная матрица А, называется транспонированной по отношению к заданной матрице А, если ее элементы получены обменом элементов, симметричных относительно главной диаго-
. Мы видим, что в ней
элементы я 12 и а 2{ , а п = а р Тогда для получения А,. в цикле необходимо запомнить элемент и = а 1р на место элемента а ] поставить элемент а р а на место элемента а м - элемент а 1} . Блок-схема алгоритма, решающего эту задачу, приведена ниже на рис. 1.32. Текстовая его форма такая.
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить / = 1.
Шаг 3. Положить у = 1.
Шаг 4. Положить и =
« = а Р
Шаг 5. Положить у =у + 1.
Шаг 6. Если у п, вернуться к шагу 4.
Шаг 7. Положить /"=/"+ 1.
Шаг 8. Если /п, вернуться к шагу 3.
Шаг 9. Вывести А,.
Шаг 10. Остановиться.
В матричной алгебре и ее приложениях весьма часто приходится выполнять умножение матрицы А на вектор-столбец Ь и умножение матрицы А на матрицу В. Как выполняется операция умножения А на Ь , рассмотрим на примере матрицы
результате умножения мы получим вектор-столбец АЬ с элементами скалярных произведений строк матрицы А на столбец Ь. Первый элемент этого вектор-столбца
а х Ь = а и Ь х + а п Ь 2 + а п Ь 3 = ^ а и ь ] -
Второй его элемент
а 2 Ь = а 2 Ь + а 22^2 + «2з^з = У,«?/
Третий элемент столбца
«з Ь = а 31 Ь 1 + а 32 Ь 2 + Ь 3 = ? а у Ь } .
Рис. 1.32. Блок-схема алгоритма транспонирования квадратной матрицы А
Таким образом, чтобы выполнить умножение матрицы А на вектор Ь, необходимо последовательно умножить вектор строки А на столбец Ь. При этом умножение А на Ь имеет место только тогда, когда количество столбцов матрицы А равно количеству элементов вектора Ь.
Задача 1.26. Разработать алгоритм умножения матрицы А на вектор Ь. Очевидно, что в алгоритме должно циклически вычисляться скалярное произведение каждой вектор-строки матрицы А на вектор Ь и запоминаться как элемент результирующего вектора-столбца Л т. Блок-схема алгоритма приведена на рис. 1.33. Текстовая форма дана ниже.
Шаг 1. Ввести п, т, элементы Ли Ь.
Шаг 2. Положить /= 1.
Шаг 3. Положить у = 1, А* = 0.
Шаг 4. Вычислить А* = 5* + а^Ь г
Шаг 5. Положить у =у + 1.
Шаг 6. Если у п, вернуться к шагу 4.
Шаг 7. Положить А” = 5*.
Шаг 8. Положить /= /"+ 1.
Шаг 9. Если /т, вернуться к шагу 3.
Шаг 10. Вывести А"".
Шаг 11. Остановиться.
|
Умножение матрицы А = |
на матрицу В = |
|||||
возможно только тогда, когда число столбцов матрицы А равно числу строк матрицы В.
Умножение выполняют последовательно. Сначала матрицу А умножают на первый вектор-столбец В и получают вектор С,. Затем А умножают на второй вектор-столбец В и получают вектор С 2 . Этот процесс продолжают до исчерпания столбцов матрицы В. В результате получают матрицу С с количеством столбцов второй матрицы В.
Задача 1.27. Разработать алгоритм умножения матрицы А на матрицу В.
Очевидно, что в алгоритме как его фрагмент можно использовать алгоритм умножения матрицы на вектор. Блок-схема алгоритма приведена на рис. 1.34. На этой блок-схеме к -
количество столбцов матрицы В,
Шаг 1. Ввести п, т , к , элементы А, В.
Шаг 2. Положить д = 1.
Шаг 3. Положить /"= 1.
Шаг 4. Положить у = 1, 5* = 0.
Шаг 5. Вычислить 5* = Я к + а 1} Ь к.
Шаг 6. Положить у =у + 1.
Шаг 7. Если у
Шаг 8. Положить А," =
Шаг 9. Положить /"=/"+ 1.
Шаг 10. Если /"
Шаг 11. Положить д = д + 1.
Шаг 12. Если д вернуться к шагу 3.
Шаг 13. Вывести А™.
Шаг 14. Остановиться.
Обратим внимание на то, что в этом алгоритме имеется система из двух вложенных циклов. Предшествующая схема алгоритма имеет один вложенный цикл.
Задача 1.28. Разработать алгоритм решения системы п линейных уравнений с п неизвестными
|
+ а 1п х п |
||||
|
Н" ?/97 X ?) |
+ а 2п х п |
|||
|
+ а п2 х 2 |
+ а пп Х п |
методом исключения Гаусса.
Суть метода Гаусса состоит в том, что сначала исключается первое неизвестное х, из всех уравнений, кроме первого. Затем исключается второе неизвестное х 2 из всех уравнений, кроме первых двух. Последним исключается п - 1 неизвестное х„_, из последних двух уравнений. В результате получают систему уравнений треугольного вида
а" п х 1 + а[ 2 х 2 + ... + а п х п = Ь[ а 22 х 2 + ... +а 2 п х п = Ь 2
из которой сначала находят неизвестное х п = Ь" п 1а" пп, затем методом подстановки значения х п в предшествующее уравнение очередное неизвестное потом
х „-2 = (Ь "„-2 -а"ь--а" т х„)/а" т _.
и заканчивают этот процесс вычислением значения
Хі = (Ь[ -а" 22 х 2 -... -а" пп х п)/а" п.
Таким образом, метод содержит два этапа: последовательное исключение неизвестных и последовательное их вычисление. Рассмотрим технику исключения неизвестных на примере трех уравнений с тремя неизвестными. Для этого систему уравнений
ры-столбцы неизвестных и правых частей уравнений. Далее рас
а 2 а 2 2 а 23
смотрим расширенную матрицу А" =
В первом столбце матрицы А" найдем наибольший по модулю, не равный нулю элемент. Если ненулевого элемента в столбце нет, рассмотренная система уравнений не имеет решений. Если наибольший ненулевой элемент содержится в любой строке матрицы А", кроме первой, поменяем местами эту строку матрицы А" с первой ее строкой. Этими действиями осуществляется контроль совместности системы уравнений и уменьшается чувствительность метода к округлению чисел, сопровождающему вычисления на ЭВМ.
Для того чтобы исключить первое неизвестное х, из второго уравнения системы, вычислим множитель т 2 = а 2х /а п, умножим первую строку матрицы А" на этот множитель и вычтем результат умножения из второй строки А".
(я 21 - т 2 а и)х у - (а 22 - т 2 а п)х 2 - (а 23 - т 2 а хз)х 3 = Ь 2 - т 2 Ь х. Обозначив я 2! - т 2 а и =а" 2х = 0, будем иметь
Я 13 х 3 + я 23 х 3
а и Х 1 + а п Х 2 О + а" 22 х 2
«31* | + а 32 х 2
Для исключения неизвестного х { из третьего уравнения полученной системы вычислим множитель т 3 = а зх /а и, умножим этот множитель на первую строку матрицы А" и вычтем результат умножения из третьей строки.
Тогда ввиду того, что а м - т 3 а и = 0 и вводя соответствующие обозначения, получим систему
Я 13 х 3 + а 23 х 3
О Х + а 12 х 2 О + а" 22 х 2 О + я 32 х 2
в которой исключено неизвестное х, из всех остальных уравнений, кроме первого.
Теперь задача состоит в том, чтобы исключить неизвестное х 2 из третьего уравнения. Для этого поступим аналогичным образом. Найдем множитель т" 3 =а" 32 /о" 22 , умножим на него второе уравнение и вычтем результат умножения из третьего уравнения. В итоге получим
(«32 - ^з«22)*2 “(«33 - ^3«2з)*3 = ^3 - т Ъ ^2
Учитывая, что а" 32 - т" 3 а" 22 = 0 и обозначив а" 33 - т" 3 а" 23 =а 33 , Ь" 3 - т" 3 Ь" 2 = Ь 3 , придем к треугольной системе
из которой методом последовательной подстановки получим значения неизвестных
*3 =?з"Мз> *2 =(Ь" 2 -а" 23 х 3)/а 22 , х 1 ={Ь Х -я 13 х 3 -а п х 2)/а п.
Обобщая изложенное, можно сказать, что алгоритм должен выполнить п - 1 действие по исключению п - 1 неизвестных. Если к - номер исключаемого переменного, то необходимо в каждом из этих действий сделать от / = к + 1 до п вычитаний уравнений. При этом каждое вычитание осуществляется выполнением у = к + 1 до п арифметических действий. Кроме этого, при каждом исключении переменной необходимо найти максимальный элемент в соответствующем столбце матрицы А. И последнее, что нужно сделать, вычислить значения неизвестных х п, ..., х,. Таким образом, общая укрупненная блок-схема алгоритма представляется такой (рис. 1.35).
Теперь составим алгоритмы поиска максимального элемента, вычитания строк и вычисления значений переменных, которые на этой схеме представлены укрупненными блоками.
Поиск индекса максимального элемента в ряду чисел рассмотрен в задаче 1.16. В данном случае он ничем не отличается от метода, который изложен там. Полагаем, что максимальный элемент первый в столбце Ли 1= к. Затем в цикле сравниваем с этим элементом остальные элементы этого столбца и тем самым выделяем наибольший элемент и устанавливаем его индекс. Алгоритм поиска минимального элемента в столбце матрицы А приведен на рис. 1.36. Там же показан фрагмент проверки условий совместности системы уравнений. На рис. 1.37 показана блок-схема алгоритма вычитания строк.
Алгоритм определения значений переменных х п, х п _ х, ..., х, последовательно реализует формулы, по которым вычисляются эти переменные х п = Ь п /а пп, х я _, = {Ь п _ х - а п _ х х п)/а п _ х .... Его блок-схема приведена на рис. 1.38. Ниже приведена текстовая форма полного алгоритма.
Шаг 1. Ввести п, А, В.
Шаг 2. Положить к= 1.
Шаг 3. Положить 1= к, / = к + 1.
Шаг 4. Если |а 1к >а, к, положить / = 1.
Шаг 5. Положить / = / + 1, если / п, вернуться к шагу 4.
Рис. 1.35.
|
Система |
||
|
несовместна |
||
|
* &кр Я к/ Щр а и =г, 7=7 + 1 |
|
|
^=6*, = Ьі, |
|
Рис. 1.36.
и замены строк А"
Рис. 1.37.
Шаг 6. Если а 1к = 0, перейти к шагу 29.
Шаг 7. Если 1= к, перейти к шагу 12.
Шаг 8. Положить у = к.
Шаг 9. Положить I = а кр а к] = а /р а у = I-
Шаг 10. Положить у = у + 1, если / п, вернуться к шагу 9.
Шаг 11. Положить? = Ь к, Ь к = Ь„ Ь, = I-
Шаг 12. Положить /=? + 1.
Шаг 13. Вычислить т = а)к /а кк, положить а 1к = 0.
Шаг 14. Положить у = к + 1.
Шаг 15. Вычислить а 0 = а и - та 1к .
К выводу
Шаг 16. Положить у =у + 1, если / п, вернуться к шагу 15. Шаг 17. Вычислить Ь і = Ь; - т Ь к.
Шаг 18. Положить / = / + 1, если /" п, вернуться к шагу 13. Шаг 19. Положить к - к + 1, если к - 1, вернуться к шагу 3. Шаг 20. Вычислить х п = Ь п /а пп.
Шаг 21. Положить і = п - 1.
Шаг 22. Положить 5=0.
Шаг 23. Положитьу= / + 1.
Шаг 24. Вычислить 5=5+ а и х ] .
Шаг 25. Положить у = у + 1, если у = я, вернуться к шагу 24. Шаг 26. Вычислить х, = (6, - 5)/я„-.
Шаг 27. Положить / = /- 1, если /> 1, вернуться к шагу 22. Шаг 28. Вывести х, ..., л:, и перейти к шагу 30.
Шаг 29. Вывести «Система несовместна».
Шаг 30. Остановиться.
Задача 1.29. Сконструировать алгоритм записи последовательности чисел 1, 2, 3, ..., 49 в квадратную матрицу А с 7 строками и 7 столбцами по спирали (рис. 1.39).
Рис. 1.39.
Самое простое решение этой задачи следующее. Двигаясь по спирали, составить две последовательности индексов элементов матрицы А. В первую последовательность занести значение индексов строк 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, ..., во вторую последовательность - значения индексов столбцов 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, ... . Затем организовать цикл от 1 до 49, в котором последовательно выбирать числа из двух последовательностей - индексы соответствующего элемента матрицы А и по этим индексам на место элемента матрицы а ] заносить значение управляющей переменной цикла к.
Пусть / - строчные индексы матрицы А, у - индексы ее столбцов, к - управляющая переменная цикла. Пусть далее 4 - к-е значение строчного индекса, а ] к - к-е значение ее столбцевого индекса. С учетом этих обозначений алгоритм будет иметь вид, показанный на рис. 1.40.
Рис. 1.40. Алгоритм записи чисел натурального ряда 1, ..., 49 в матрицу А
по спирали
Недостаток этого алгоритма заключается в том, что сначала необходимо составить последовательности индексов, отображающих движение по спирали, а затем программировать.
Можно предложить другой алгоритм, в котором записываются только начальные и конечные индексы сторон спирали. Например, для первых четырех ее сторон получим:
/= 1, у = от 1 до 7;
/" = от 2 до 7, У = 7;
/ = 7, у = от 6 до 1;
/ = от 7 до 2, у = 1.
Для остальных двух спиралей индексы найдем аналогичным путем, исходя из рисунка спирали.
Таким образом, согласно этому подходу для записи в матрицу А чисел одной спирали требуется выполнить четыре цикла: два в прямом направлении и два в обратном. Чтобы ограничиться использованием только этих четырех циклов, необходимо найти, как изменятся индексы от номера спирали. Тогда алгоритм будет содержать один внешний и четыре внутренних цикла, начальные и конечные индексы которых зависят от индексов внешнего цикла. Доработку этого алгоритма мы выносим в качестве самостоятельного упражнения.
Задача 1.30. Рассмотрим шахматную доску и два положения коня на ней (рис. 1.41). Возможные ходы коня показаны стрелками и пронумерованы. Конь слева (поле (1,2)), не выходя за пределы доски, может пойти только на три поля. Конь справа (поле(5,6)) может пойти на восемь полей, что является макси-
мальным количеством допустимых ходов коня из одного ПОЛЯ. Маршрутом коня называется последовательное перемещение коня по полям доски такое, что он не попадает на одно и то же поле дважды. Конечной точкой маршрута является поле, с которого нет допустимого хода либо по причине выхода коня за пределы доски, либо по причине повторного попадания на какое-либо поле маршрута. Составить алгоритм, строящий маршрут коня, возможно наибольшей длины.
Очевидно, что наибольшая длина маршрута - это 63 поля шахматной доски. Попытаться найти такой маршрут можно путем перебора всех маршрутов коня, начинающихся из всех 64 полей. Поэтому, кроме процедуры построения маршрута, алгоритм должен содержать цикл из 64 повторений задания исходного поля.
Для того чтобы построить маршрут коня, начинающийся с любого поля доски, кроме учета ограничений, обеспечивающих допустимый ход, необходимо определить стратегию выбора очередного хода. Возможной такой стратегией может быть первый допустимый ход коня, если просматривать его ходы по часовой стрелке (см. 2-е положение коня, рис. 1.41). В том случае, когда допустимого хода нет, маршрут считается законченным.
В свою очередь, допустимость хода по условию непопадания на уже пройденное поле маршрута может быть определена так. Запишем во все поля доски значение нуль, а дальнейшие ходы коня с некоторого поля будем нумеровать числами, на которые конь делает очередной ход. Тогда допустимым полем будет поле доски со значением нуль, а максимальное число натурального ряда в конце маршрута определит его длину.
Выход коня за пределы доски может фиксироваться путем обрамления доски двумя полями, в которые записано произвольное число больше нуля, например 66. На рис. 1.42 приведены исходные данные о доске и показано начало маршрута коня из поля (7, 8).
На основании изложенного алгоритм поиска лучшего маршрута коня должен включать следующие этапы:
- 1) инициализацию полей обрамления доски, т. е. запись в эти поля числа 66 или любого другого, например 99;
- 2) инициализацию начала цикла по всем маршрутам с указанием начальной длины маршрута / = -1 для выбора лучшего маршрута;
Рис. 1.42. Исходные данные о доске и начало маршрута коня
- 3) инициализацию полей доски, т. е. запись в эти поля числа 0;
- 4) построение маршрута коня, запоминание его длины и выделение лучшего текущего маршрута;
- 5) вывод лучшего маршрута и его длины.
Укрупненная блок-схема алгоритма поиска лучшего маршрута коня приведена на рис. 1.43.
На рис. 1.44 приведена блок-схема алгоритма инициализации верхнего обрамления доски с учетом того, что вся доска с обрамлением представляет собой квадратную матрицу /) = 11
с 12 столбцами и 12 строками, т. е. двумерный массив.
Аналогичный вид будет иметь блок-схема инициализации нижнего обрамления доски. Другими будут только начальные и конечные значения управляющей строки / 5 = 11, 1 Р = 12.
Что касается инициализации левого и правого краев доски, то в этом случае можно обойтись без вложенного цикла по у. Блок-схема этого алгоритма приведена на рис. 1.45. Соединенные последовательно блок-схемы инициализации верхнего, нижнего, а также левого и правого обрамлений доски образуют общую блок-схему инициализации обрамления доски.
Определение длины п маршрута
Запоминание лучшего маршрута и его длины / = /7
I*-:
Рис. 1.44. Блок-схема алгоритма инициа- Рис. 1.45. Блок-схема алгоритма
лизации верхнего обрамления доски инициализации левого и правого
обрамления доски
Блок-схема инициализации непосредственно шахматной доски реализует процедуру занесения в двумерный массив /) = dyW с индексами / 5 =3, 1 Р = 10, у 5 =3, ] р = 10 значений с1 1Г Она
легко может быть построена, в связи с этим не приводится.
Теперь рассмотрим, как может быть представлен алгоритм построения маршрута коня. Условимся, что последовательность полей, с которого начинается маршрут коня, будет задаваться с помощью двух индексов-строки / матрицы О и ее столбца у. Тогда согласно рис. 1.42 индексы всех полей, на которые может попасть конь, с произвольного поля (/, у) идя по часовой стрелке, будут следующими.
|
1 = 1 + 2 |
||
Таким образом, для исходного поля очередного маршрута и каждого допустимого поля (/,_/") необходимо организовать просмотр максимум 8 полей. Для этого следует организовать цикл переменной по к от 1 до 8. В свою очередь изменение индекса удобно вычислять как / = / + 4, у =у + у*. Для этого значения 4? Л необходимо представить двумя одномерными массивами 4 = (-2 -112 2 1-1 -2), у4 = (1 2 2 1-1-2-2 -1).
На основании изложенного построение маршрута может быть организовано следующим образом. Получив поле (/,у) начала очередного маршрута, установить его номер п= 1, положить т 1 и т р каждый длиной п 64. Затем приступить к выявлению первого допустимого поля в цикле по к. Если такое поле обнаружено, занести индексы /, у в массивы т { т р значение п = п + 1 - в и перейти к началу очередного цикла по к. Если же оно не обнаружено, изменить к = к + 1 и продолжить цикл.
В том случае, когда допустимое поле не будет обнаружено, следует перейти к замене полученного маршрута на лучший маршрут и вывести лучший маршрут и его длину. Блок-схема алгоритма построения маршрута приведена на рис. 1.46. Очевидно, что для хранения лучшего маршрута еще необходимы два массива индексов / и у - т п, т р длиной п
В заключение приведем укрупненную текстовую запись алгоритма поиска лучшего маршрута коня.
Шаг 1. Инициализировать обрамление доски.
Шаг 2. Положить / = -1.
Шаг 3. Установить /, у.
Шаг 4. Инициализировать доску.
Шаг 5. Положить п = 1, с1 (] = 1, к= 1.
Шаг 6. Если /:> 8, перейти к шагу 10.
Шаг 7. Положить / = / + / А, у = у + у*.
Шаг 8. Если ф о 0, положить к = к+ 1 и вернуться к шагу 6.
Шаг 9. Положить я = п + 1, т 1 = /, т у = у, к = 1 и вернуться к шагу 6.
Шаг 10. Если л > /, перейти к шагу 12.
Шаг 11. Заменить текущий маршрут (т; , т^) на лучший (т,„ т м).
Шаг 12. Положить /? = /?+ 1.
Шаг 13. Если И 64, вернуться к шагу 3.
Шаг 14. Вывести лучший маршрут и его длину /.
Шаг 15. Остановиться.
Задача 1.31. Рассмотрим еще одну задачу на шахматной доске. Требуется найти все варианты расстановки восьми ладей на доске так, чтобы они не били друг друга.
Тот, кто играет в шахматы, знает, что ладья бьет любую фигуру по вертикали и горизонтали. Поэтому ладьи не должны быть расположены на одной вертикали и горизонтали. Два варианта расположения фигур показаны на рис. 1.47.
Рис. 1.47. Возможные допустимые варианты расположения ладей на доске
В шахматной нотации первый вариант записывается как а! Ь2 сЗ 64 е5 Гб g7 Й8, второй - как а 8 Ь 7 с 6 ф е 4 Т 3 g 2 й,. Из этих
записей легко видеть, что любой допустимый вариант расстановки ладей определяется перестановкой первых восьми чисел натурального ряда. В связи с тем, что число перестановок Р п = 1 2 3 ... п = я!, в данном случае будем иметь Р% = I х х2-3-4-5-6-7-8 = 8! = 40 320 вариантов допустимых размещений ладей на доске. Для того чтобы получить все эти расстановки, необходимо сконструировать алгоритм построения всех перестановок п чисел натурального ряда. Известно несколько таких алгоритмов. Простейший из них рассмотрим на построении всех перестановок первых трех чисел натурального ряда 1, 2, 3.
Идея алгоритма состоит в последовательном вращении последовательности всех указанных чисел до тех пор, пока не будут получены все перестановки. Вращение начинают с первой перестановки 123 и продолжают до тех пор, пока не получат исходную перестановку. Таким образом, в данном случае будем иметь три перестановки. Очередная перестановка 123 1 будет повторять первоначальную перестановку. Чтобы фиксировать этот момент, необходимо все время сравнивать число вращаемых чисел (в данном случае 3) с последним числом перестановки и когда они совпадут, перейти к очередному действию алгоритма. Очередное действие состоит в проверке, равно ли число вращаемых чисел, в данном случае 3, двум. Если это так, все количество перестановок получено. Иначе уменьшается число вращаемых чисел на единицу и продолжается вращение, в данном случае первых двух чисел. Получаем перестановку 213. Сравниваем 2 с последним числом перестановки 3. Они не равны. Восстанавливаем число вращаемых чисел до 3 и вращаем перестановку 213. Получаем 132. Сравниваем число вращаемых чисел 3 с последним числом 2. Они по-прежнему не равны. Вращаем 132 и получаем 321. Дальнейшее вращение перестановки 321 дает 213 , т. е. перестановку, которая уже была получена в начале второго этапа вращений. Сравниваем число вращаемых чисел 3 с двойкой. Они не равны. Уменьшаем число вращаемых чисел до двух и вращаем первых два числа в перестановке 213. Получаем 123, сравниваем число вращаемых чисел 2 с последним числом вращаемых чисел 2. Они равны. Далее сравниваем число вращаемых чисел 2 с двойкой и заканчиваем построение перестановок. Все перестановки построены. Они приведены ниже. Повторяющиеся перестановки заключены в прямоугольники.
Пусть 1,2, ..., п - последовательность чисел натурального ряда; т - количество вращаемых чисел в перестановке; к - последнее число вращаемой перестановки. С учетом этих обозначений блок-схема алгоритма построения всех перестановок п чисел натурального ряда будет такой (рис. 1.48).
На рис. 1.49 изображены фрагменты алгоритма «сформировать перестановку 1, 2, ..., п» и «произвести вращение первых т чисел в последней перестановке», где Р, - /"-е число в перестановке.
Задача 1.32. Рассмотрим следующую задачу. На закрытом интервале [а , Ь задана унимодальная функция у = /(х), х е [а, Ь.
Требуется сконструировать алгоритм поиска точки х* е [а, Ь, которая доставляет наибольшее значение функции у*.
Прежде чем приступить к решению этой задачи, напомним, что функция унимодальна, если она одногорбая. Различные виды унимодальной функции представлены на рис. 1.50.
То обстоятельство, что унимодальная функция одногорбая, позволяет по двум различным точкам х 2 , х 2 е [а, Ь ] определить интервал а, Ь, которому принадлежит х*. Различные варианты соотношений /(х,) (х 2), /(х,) >/(х 2), /(х,) =/(х 2) выделяют свои подынтервалы [х, Ь], [а, х 2 ], [х, х 2 ], которым принадлежит х*. Все они меньше первоначального интервала [а, Ь. Для наглядности на рис. 1.51 эти подынтервалы заштрихованы.
Унимодальность функции у=/(х) и возможность вычислять ее в двух точках х, х 2 позволяют построить следующую процедуру поиска х* с определенной погрешностью?. Возьмем точку х = (а + Ь)/ 2, делящую интервал [а , Ь ] пополам. Сместимся влево
Рис. 1.48. Блок-схема алгоритма построения всех перестановок п чисел
натурального ряда
Рис. 1.49.
от нее и вправо на расстояние е/2, т. е. получим точки х, = = х - е/2, х 2 = х + е/2, где е - малое расстояние между этими точками, равное принятой погрешности вычисления х*. В точках х 1? х 2 вычислим значения функции у, у 2 . Если у, то х* находится в интервале [х |} Ь. Если у, >у 2 , то х* находится в интервале [а, х 2 . Если же у, = у 2 , то точка х - это значение х*, найденное с погрешностью е. В связи с этим процедуру считаем завершенной. В противном случае полагаем х, = а или х 2 = Ь и приступаем к делению пополам интервала [х, Ь] или [а, х 2 ] с дальнейшим получением изложенным способом точек х, х 2 , вычислением у, у 2 , сравнением их между собой и остановкой в случае у х = у 2 или
продолжением дальнейшего деления. Процесс завершаем в том случае, когда будет получен интервал
Заметим, что после первого деления мы переходим к оче-
редному интервалу длиной
Рис. 1.50. Унимодальные функции:
а - выпуклая; б - непрерывная негладкая; в - негладкая с разрывами
конечного ряда
а - Ь е
- -- + - , после второго перходим
к интервалу длиной
третьего деления - к интервалу длиной
а-Ь (2 3 -1)7
а - Ь 3
- -+ - с.
а - Ь 3
- - + -Є
а - Ь | 7
- - + - 8 -
є. Таким образом, после п деле-
ний исходного интервала [а , Ь ] будет получен интервал длиной а-Ь (2"-1)
є. Откуда при заданных значениях а, Ь, є мож-
но вычислить значение п, показывающее, сколько делений [а, Ь ] нужно выполнить, чтобы получить заданную точность.
Блок-схема алгоритма, реализующая эту процедуру, приведена на рис. 1.51. Описанный метод поиска наибольшего значения
Ввести а, Ь, с
Х -Х-е/2, Х2=Х+е/2
x*=x,y=f(x)
Вывести * * X ,у
Рис. 1.51. Блок-схема алгоритма поиска наибольшего значения унимодальной
функции методом половинного деления
унимодальной функции известен под названием метода половинного деления, или дихотомии. Существуют, однако, более эффективные методы решения этой задачи. Это методы золотого сечения и Фибоначчи.
Рассмотрим простейший из них - метод золотого сечения.
Согласно этому методу вначале вычисляются два значения функции х, х 2 , как и в методе дихотомии. Затем в полученном подинтервале [х, Ь] от точки х 2 вправо откладывается величина |х 2 - х, | и вычисляется значение функции в точке х 2 +|х 2 - х, |.
Если в результате первых двух вычислений функции в точках х, х 2 получен интервал неопределенности [а, х 2 ], от точки х, влево откладывается величина Х[ - х 2 и вычисляется функция в точке х, - | х, -х 2 |. Процесс продолжается до тех пор, пока не будет
достигнута заданная точность сокращения интервала. Схематично он показан на рис. 1.52.
Рис. 1.52.
методом золотого сечения
Метод получил название от известного с древности способа деления интервала а, Ь точкой с на две неравные части так, что отношение всей длины интервала к длине большей части равно отношению длины большей части к длине меньшей части. В данном случае интервал неопределенности [х, Ь ] или [а, х 2 ] делится точкой х, или х 2 именно в таком отношении.
По схематично описанной процедуре легко построить алгоритм вычисления наибольшего значения унимодальной функции, что и будет предложено в п. «Задачи для самостоятельного решения».
Известны три типа алгоритмов – линейные, разветвляющиеся, циклические.
Линейный тип алгоритмов
Алгоритмы, в которых команды выполняются друг за другом, независимо от каких-либо условий, называются алгоритмами линейного типа.
Например, алгоритм вычисления по самым простейшим формулам, не имеющих ограничений на значения входящих в них переменных.
Пример
Постановка задачи : вычислить площадь круга, если известен радиус.
Дано: R– радиус круга.
Найти: S– площадь круга.
Решение: S=3,14R 2
Словесная форма записи алгоритма
Выберем русский язык для записи алгоритма в этой форме и запишем последовательность команд, выполнение которых при заданном значении радиуса позволит найти площадь:
Прочесть значение R.
Умножить значение Rна 3,14.
Умножить результат второго действия на значение R.
Записать полученный результат как значение S.
На языке блок-схем – рис. 8
Разветвляющийся тип алгоритмов
Решение задач не всегда можно представить в виде линейного алгоритма.
Алгоритмы, в которых требуется организовать выбор последовательности действий в зависимости от каких-либо условий, называют алгоритмами разветвляющегося типа.
При графическом способе ветвление организуется с помощью логического элемента (ромб), имеющего один вход и два выхода. Назначение логического элемента – проверка заданного условия. В зависимости от выполнения (истинности) или невыполнения (ложности) проверяемого условия возможен выход соответственно на ветвь «Да» или «Нет».
Пример
Постановка задачи
: вычислить
.
Дано : х – значение аргумента.
Найти : у – значение функции.
Решение:
y= x , если х 0
- x , если х<0
Блок-схема - см. рис. 9.
Словесное представление
На псевдокоде :
Прочесть значение х
Если х>0, то
Конец ветвления
Записать значение у
Выделяют полную и неполную условную конструкцию .
Циклический тип алгоритмов
При составлении алгоритмов решения достаточно большого круга задач нередко возникает потребность в неоднократном повторении одних и тех же команд.
Алгоритм, составленный с использованием многократных повторений одних и тех же действий (циклов), называется алгоритмов циклического типа .
Однако, «неоднократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое зацикливание), является нарушением требования его результативности.
При разработке алгоритма циклической структуры выделяют следующие понятия:
параметр цикла – величина, с изменением которой связано многократное выполнение цикла;
начальное и конечное значение параметра цикла ;
шаг цикла – это значение, на которое изменяется параметр цикла при каждом повторении.
Циклический алгоритм состоит из подготовки цикла, тела цикла, условия продолжения цикла .
В подготовку цикла входят действия, связанные с заданием исходных значений для параметра цикла (начальное и конечное значения, шаг параметра).
В тело цикла входят: многократно повторяющиеся действия для вычисления искомых величин; подготовка следующего значения параметра цикла, подготовка других значений, необходимых для повторного выполнения действий в теле цикла.
В условии продолжения определяется необходимость дальнейшего выполнения повторяющихся действий. Если параметр цикла превысил конечное значение, то выполнение цикла должно быть прекращено.
Рассмотрим графическое представление циклического блока алгоритма (см. рис. 10).
Циклы могут быть с предусловием (когда условие проверяется перед началом тела цикла) и спостусловием (когда условие проверяется после первого прохождения тела цикла).
Цикл с постусловием
Цикл с предусловием
В алгоритмах команды записываются друг за другом в определённом порядке.
Линейные алгоритмы
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным .
Например, линейным является следующий алгоритм посадки дерева (рис. 58):
- выкопать в земле ямку;
- опустить в ямку саженец;
- засыпать ямку с саженцем землёй;
- полить саженец водой.
Рис. 58
С помощью блок-схемы данный алгоритм можно изобразить так (рис. 59).
Рис. 59
Алгоритмы с ветвлениями
В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идёт дождь, мы берём зонт и надеваем плащ; если жарко, надеваем лёгкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ ТО ИНАЧЕ
Пример:
ЕСЛИ хочешь быть здоров, ТО закаляйся, ИНАЧЕ валяйся весь день на диване.
В некоторых случаях могут отсутствовать: ЕСЛИ ТО
Пример:
ЕСЛИ назвался груздем, ТО полезай в кузов.
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением .
Изобразим в виде блок-схемы последовательность действий ученика 6 класса Мухина Васи, которую он представляет себе так: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение» (рис. 60).
Рис. 60
А вот так, с помощью блок-схемы можно очень наглядно представить рассуждения при решении следующей задачи (рис. 61).
Рис. 61
Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?
Алгоритмы с повторениями
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением). Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями .
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием . Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим пример из жизни. Вот так может выглядеть блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике (рис. 62).
Рис. 62
Это циклический алгоритм. При его исполнении действие «Решить задачу» будет выполнено столько раз, сколько задач содержит домашнее задание ученика.