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

Определение 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;

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

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

л/Г

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

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

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

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

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

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

Шаг 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. Разные действительные корни вычисляются по формулам

Начало

Вывести х, У

I

Конец

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

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

2 а " 2 а

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

м

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

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

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

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

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

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

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

Шаг 4. Если <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 . Нетрудно видеть, что если в качестве

-v-

пкорней

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

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

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

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

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

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

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

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

Задача 1.9. Составить алгоритм вычисления выражения S = = sin л: + sin2* ... + 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п. Поэтому ал-

V п

горитм будет таким (рис. 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. Этот алгоритм основан на использовании рекуррентного сотношения для вычисления С"'.
  • ?

/ Ввести

/ X1 , . . . , X/; , И

г~

/ = 1

Да

& = 0

Вывести

Алгоритм вычисления среднего квадратического

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

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

Сі =

^ п

з л — 2 2

-— С,, и т. д.

Для построения алгоритма запишем общее выражение для вычисления С"!, которое будем вычислять в цикле. Согласно рекуррентному соотношению при т = 0 число сочетаний С^1 = С1 =

При т = і число со-

= п. При т = 1 число сочетаний С2п

и І+1 ^ I

четании С , =-

и • і

/ + 1

пи-1 У1 — 171 ^ щ і

Оно записывается так: С =

С'”, Сп = п и позволяет вычислять сочетания последовательно С =п, С2 = ——-С'п,

т + 1

С'п. Так как в итоге необходимо получить зна

чение С"' т < п, то / должно изменяться от 1 до т - 1. Блок-схема алгоритма приведена на рис. 1.13. Его текстовая форма такая.

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

Шаг 2. Если п < т, вывести «Повторить ввод, п <т» и вернуться к шагу 1.

Шаг 3. Если п = 1, перейти к шагу 10.

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

Шаг 5. Положить С= п, /= 1.

Шаг 6. Если / > т - 1, перейти к шагу 11.

Шаг 7. Вычислить С =--С.

/ + 1

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

Шаг 9. Положить С= 1 и перейти к шагу 11.

Шаг 10. Положить С=п.

Шаг 11. Вывести С.

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

Заметим, что в приведенной блок-схеме предусмотрен контроль правильности ввода чисел т так, чтобы п> т.

Задача 1.12. Сконструировать алгоритм вычисления многочлена (полинома) Рп(х) степени п для некоторого действительного значения х

Используя традиционную форму представления многочлена рп(х) =апхп + ап_ххп~х + ... + а2х2 + ахх + а0, алгоритм можно

было бы изобразить, как на рис. 1.14.

Начало

Ввести #о» • • • 5 ап, х

Г

Р=а0

,У=1

1

/ =

=1

/>/??

У=УХ,

Р =Р+а,у

/ = / +1

Вывести

Р,Х

I

Конец

Рис. 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. Разработать алгоритм вычисления значения цеп-

X

ной дроби У =---для х ф 0.

х2 +

х2 +

х2 +

8 х2 +

х

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

^ 2 х

ляется выражение С=х + —, значение которого при задан- ном х легко может быть найдено. Предпоследним делителем яв-

2 128 2 128

ляется выражение С = х +

х2 +

256

= х +

С

, а предшествую-

х щим ему делителем является выражение С =х + — , где С —

(2

найденное перед этим значение делителя. Таким путем может

2 2

быть найдено значение делителя С =х + — , а затем значение дроби У = —.

Очевидно, что повторяющимся действием в этой задаче является поиск очередного делителя. Учитывая, что 2 = 21, а 256 = 28, всего необходимо найти восемь делителей. Исключая последний делитель, всего получаем семь повторяющихся действий. На основании изложенных рассуждений конструируем алгоритм, вычисляющий заданное выражение (рис. 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)-й ячейке массива.

а

а»

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

Ь являются одномерными массивами.

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

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

и п столбцов, т = п, имеет вид:

А =

а

а2

(1п

а2

а22

“2п

• • •

а т

• • •

ат2

  • • • • • • •
  • (1

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

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

Элементы матрицы А, лежащие справа и вверху от главной диагонали, образуют верхнюю треугольную матрицу. Элементы, лежащие слева внизу от главной диагонали, образуют нижнюю треугольную матрицу.

Матрица называется симметричной, если элементы, симметричные относительно главной диагонали, равны между собой, т. е. а и = й/ ( .

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

Существует целый ряд алгоритмов сортировки. Среднее время их работы или временная сложность лежит в пределах от 0(п2/4) до 0(ппп), где п — число элементов массива. К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае.

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

Рассмотрим эту сортировку на массиве целых чисел

  • 71 27 412 81 59 14 273 87, который требуется упорядочить по возрастанию. Первым сортируемым элементом массива является второй элемент — число 27. Образно говоря, «вынимаем» его из массива, т. е. освобождаем место для будущего сдвига чисел вправо, и сравниваем второй элемент (число 27) с первым элементом (число 71). Так как 27 < 71, сдвигаем первый элемент на одну позицию вправо, а на его место ставим второй элемент. В результате получаем последовательность чисел
  • 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 <412, сдвигаем число 412 на одну позицию вправо и сравниваем 81 с очередным предшествующим элементом массива — числом 71. Помещаем число 81 на место третьего элемента массива и получаем

27 71 81 412 59 14 273 87.

Выбираем пятый элемент массива — число 59. Запоминаем это число и сравниваем с предшествующим элементом массива — числом 412. Так как 59 <412, сдвигаем число 412 на одну позицию вправо и сравниваем 59 с очередным предшествующим элементом массива — числом 81. Так как 81 >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. Если у < 0, перейти к шагу 8.

Шаг 7. Положить а]+х = ар у = у - 1 и вернуться к шагу 5.

Шаг 8. Положить я/+1 = к, /= / + 1.

Шаг 9. Если / < п, вернуться к шагу 3.

Шаг 10. Вывести я,, ..., я„.

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

Проверка условия у > 0 в приведенной блок-схеме необходима для того, чтобы при сравнении сортируемого элемента к с предшествующими ар я-_,, я, не выйти за пределы массива. Иначе алгоритм не будет определен. В заключение отметим, что сортировка вставками согласно [7] достаточно эффективна для массивов с максимальным количеством элементов п < 25. Она также используется как фрагмент алгоритмов в сортировке Шелла, имеющей среднюю сложность 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. Это означает, что мы проверили весь массив и не нашли элемента я;= Ь. Таким образом, можно сделать вывод, что признаком отсутствия элемента в массиве служит неравенство и < I.

Задача 1.19. Составить алгоритм бинарного поиска.

Учитывая изложенное, можно предложить следующий алгоритм решения указанной задачи (рис. 1.24). Его текстовая форма приведена ниже.

Алгоритм бинарного поиска

Рис. 1.24. Алгоритм бинарного поиска

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

Шаг 2. Положить / = 1, и = п.

Шаг 3. Если и < I, перейти к шагу 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, Ь], который вполовину короче исходного интервала [а, Ь]. Если /(а)/(ВО < 0, т. е. /(а) и /(ВО разных знаков, корень находится на интервале [а, IV], и его поиск осуществляется на этом интервале, а интервал [ IV, Ь] забывается.

Таким образом, вычисляя выражение Ц^=(а+Ь)/2 и выполняя сравнение /(я) /(IV) > 0, мы сокращаем интервал поиска ровно вдвое. В результате после п таких действий получим интервал п, Ьп], которому принадлежит корень уравнения, в 2" раз меньший исходного интервала [а, Ь, т. е. ап - Ьп = а - ^/2". Приняв в качестве точности вычисления корня а длину интервала |ап - Ьп, можно определить, что для получения этой точности необходимо сделать п = па - Ь|/е шагов. Описанный метод по-

Иллюстрация к уточнению корня методом половинного деления

Рис. 1.25. Иллюстрация к уточнению корня методом половинного деления

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

Задача 1.20. Разработать алгоритм уточнения корня уравнения /(х) = 0 методом дихотомии.

Метод предполагает, что задан интервал а, Ь, которому принадлежит корень, функция /(х) = 0 непрерывна и ограничена на этом интервале и f(a) f(b) < 0. Блок-схема алгоритма изображена на рис. 1.26, текстовая форма приведена ниже.

Шаг 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 (х), ех и др. Для того чтобы облегчить процесс вычис-

V

и=/(а), у=/(6)

>

х = (а + Ь)/ 2, №=Ах)

Да

Да

Ь=х,у = 1Г

Алгоритм вычисления корня уравнения /(х) = 0 методом дихотомии

Рис. 1.26. Алгоритм вычисления корня уравнения /(х) = 0 методом дихотомии

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

X

п

дующим бесконечным рядом ех = 1 + X +-+

2. 3.

Для функций sin (х), cos (х) соответственно имеем:

I • • • •

п

3 5

. , V X X

sin(x) = X--+

3! 5! 7!

+ ... + (-1)"

X

2л+1

+

(2/7 + 1)!

X

cos(x) = 1--+

X

X

2! 4! 6!

+ ... + (-1)”

х

2 я

+

(2/7)!

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

Звдача 1.21. Составить алгоритм вычисления функции зт(х) с точностью 8 при помощи разложения ее в ряд.

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

= У

л-1

X

2/7(2/7 + 1)

. Например,

у хх2 _ *3 у _у

  • 1 2 1 (2 1+1) 3!’ 2 1
  • 2л(2т) 3!- 4-5 5!

И т. д.

Знаки членов ряда меняются поочередно, если начинать с Ух.

Поэтому начальными установками алгоритма будут такие ?=х, 6’ = х, Z= хх, а = -1. В цикле будем вычислять очередной

?7

член ряда ? =--- и прибавлять его к предшествующей

2п(2п + 1)

сумме с соответствующим знаком. Блок-схема алгоритма приведена на рис. 1.27. Его текстовая форма дана ниже.

у =х, 8=х,

?—хх,а —~

V

/7 = 1

Блок-схема вычисления значения функции 8Іп(х)

Рис. 1.27. Блок-схема вычисления значения функции 8Іп(х)

Шаг 5. Вычислить 6’= 5 + у.

Шаг 6. Если у < є, перейти к шагу 8.

Шаг 7. Положить а = -а, п = п + 1 и вернуться к шагу 4. Шаг 8. Вывести 5, х, е.

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

Задача 1.22. Составить алгоритм вычисления следа квадрат

а2 а

а,Л а

12

... Я]„

22

а2п

• •

п2

• • • • • •

... сіпп

Шаг 1. Шаг 2. Шаг 3.

Шаг 4.

Ввести х, е.

Положить у = х, 5 = х, Z= хх, а = Положить п= 1.

ау7

-1

Вычислить к= 2п, У =

к(к + 1)

а,, а

ной матрицы А =

Как было сказано раньше, след матрицы — это сумма эле-

т

ментов ее главной диагонали, т. е. Я, - ^аи. Поэтому алгоритм

ы

определения следа сводится к вычислению суммы Блок-схема этого алгоритма приведена на рис. 1.28.

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

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

а

ап

«13

«21

«22

«23

«31

«31

«33

1

2

3

4

5

6

7

8

9

Через индексы строк и столбцов /, у номер любого элемента в линейном массиве вычисляется по формуле х = (/ — 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. Вычислить ?р = + а_г

Шаг 4. Положить / = /' + 1.

Шаг 5. Если /< п, вернуться к шагу 3.

Шаг 6. Вывести $р.

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

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

Задача 1.24. Нарисовать блок-схему алгоритма, вычисляющего сумму элементов верхней треугольной матрицы А.

Рассмотрим матрицу А, состоящую из п строк и п столбцов.

А =

ап

а 12

йп

а2

а п

^2 п

• • •

а п

• • •

ап2

• • • • • •

С1пп

. Нетрудно видеть, что первый индекс эле

мента верхней треугольной матрицы — это индекс строки /. Второй индекс определяется по выражению у = / + 1. Поэтому блок-схема алгоритма будет иметь вид, представленный на рис. 1.31. В алгоритме имеется два цикла: один внешний и второй внутренний. Такие циклы называются вложенными. Текстовая форма алгоритма приведена ниже.

Шаг 1. Ввести п, элементы матрицы А.

Шаг 2. Положить Ат = 0, /'= 1.

Шаг 3. Положить у = / + 1.

Шаг 4. Вычислить А, = 5Т + ац.

Шаг 5. Положить у =у + 1.

Шаг 6. Если у < п, вернуться к шагу 4.

Шаг 7. Положить /'=/'+ 1.

Шаг 8. Если /< п, вернуться к шагу 3.

Шаг 9. Вывести Ат.

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

Задача 1.25. Нарисовать блок-схему алгоритма получения транспонированной матрицы А, на месте исходной квадратной матрицы А.

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

31

а

а

12

а 13

22

а23

32

й33

а

а

а

а

нали. Пусть задана исходная матрица А =

Согласно определению транспонированная к ней матрица

а

будет иметь такой вид: А,. =

а

п

а

а

аъ а

21

«31

22

«32

23

«33

. Мы видим, что в ней

Конец

элементы я12 и а2{, <713 и <731, и т. д. поменялись местами. Это означает, что первый индекс элемента <72, стал равен второму индексу элемента <712, а второй индекс элемента <72, стал равен первому индексу элемента <7,2. В общем виде это может быть записано так: ап = ар Тогда для получения А,. в цикле необходимо запомнить элемент и = а на место элемента а] поставить элемент ар а на место элемента ам элемент а1}. Блок-схема алгоритма, решающего эту задачу, приведена ниже на рис. 1.32. Текстовая его форма такая.

Шаг 1. Ввести п, элементы матрицы А.

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

Шаг 3. Положить у = 1.

Шаг 4. Положить и = <7„

и’

«= аР

«/< = Ы?

Шаг 5. Положить у =у + 1.

Шаг 6. Если у < п, вернуться к шагу 4.

Шаг 7. Положить /'=/'+ 1.

Шаг 8. Если /< п, вернуться к шагу 3.

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

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

В матричной алгебре и ее приложениях весьма часто приходится выполнять умножение матрицы А на вектор-столбец Ь и умножение матрицы А на матрицу В. Как выполняется операция умножения А на Ь, рассмотрим на примере матрицы

«п

«12

«13

Ь

А =

«21

«22

«23

и столбца Ь=

ь2

. Сразу же отметим, что в

«31

«32

«33 _

  • 1
  • 1_

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

п

ахЬ = аиЬх + апЬ2 + апЬ3 = ^аиь]-

7=1

Второй его элемент

п

а2Ь = а2Ь + а22^2 + «2з^з = У,«?/ •

7 = 1

Третий элемент столбца

п

«з Ь = а31Ь1 + а32 Ь2 + <733 Ь3 = ? ау Ь}.

7=1

Конец

Рис. 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. Остановиться.

«і і

«12

«13

Ьп

Ь2

Умножение матрицы А =

«2.

«22

«23

на матрицу В =

Ь2

Ь22

_«з.

«32

«33 _

_Ь}

^52 _

возможно только тогда, когда число столбцов матрицы А равно числу строк матрицы В.

Умножение выполняют последовательно. Сначала матрицу А умножают на первый вектор-столбец В и получают вектор С,. Затем А умножают на второй вектор-столбец В и получают вектор С2. Этот процесс продолжают до исчерпания столбцов матрицы В. В результате получают матрицу С с количеством столбцов второй матрицы В.

Задача 1.27. Разработать алгоритм умножения матрицы А на матрицу В.

Очевидно, что в алгоритме как его фрагмент можно использовать алгоритм умножения матрицы на вектор. Блок-схема алгоритма приведена на рис. 1.34. На этой блок-схеме к — количество столбцов матрицы В, <7 — текущий индекс ее столбца. Текстовая форма алгоритма дана ниже.

Шаг 1. Ввести п, т, к, элементы А, В.

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

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

Шаг 4. Положить у = 1, 5* = 0.

Шаг 5. Вычислить 5* = Як + а1}Ьк.

Шаг 6. Положить у =у + 1.

Шаг 7. Если у < л, вернуться к шагу 5.

Шаг 8. Положить А," =

Шаг 9. Положить /'=/'+ 1.

Шаг 10. Если /'< т, вернуться к шагу 4.

Шаг 11. Положить д = д + 1.

Шаг 12. Если д < к, вернуться к шагу 3.

Шаг 13. Вывести А™.

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

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

Задача 1.28. Разработать алгоритм решения системы п линейных уравнений с п неизвестными

ах

+ <212*2

+ . . .

+ а1пхп

= ь

а2Х

Н" ?/97 X ?)

+ . . .

+ а2пхп

= ь2

я„|*|

+ ап2х2

+ . . .

+ аппХп

= ьп

методом исключения Гаусса.

Суть метода Гаусса состоит в том, что сначала исключается первое неизвестное х, из всех уравнений, кроме первого. Затем исключается второе неизвестное х2 из всех уравнений, кроме первых двух. Последним исключается п - 1 неизвестное х„_, из последних двух уравнений. В результате получают систему уравнений треугольного вида

а'пх1 + а[2х2 + ... + апхп = Ь[ а22х2 + ... 2пхп = Ь2

= К,

из которой сначала находят неизвестное хп = Ь'п1а'пп, затем методом подстановки значения хп в предшествующее уравнение очередное неизвестное потом

х„-2 = (Ь'„-2 -а'ь--а'тх„)/а'т_.

и заканчивают этот процесс вычислением значения

Хі = (Ь[ -а'22х2 -... -а'ппхп)/а'п.

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

«11*1

+ а2Х2

< ах|

С1 ~)~)Х

аъх

+ я32х2

+ я, 3х3 = Ьх + а22х3 = Ь2

+ «зз*з = Ь,

представим в матричном виде АХ = В, где А — матрица коэффи-

«п

«12

«13

"V

циентов уравнений А =

«21

«22

«23

> X =

*2

5 В =

ь2

.«31

«32

«33 _

_*з_

Л.

— векто

ры-столбцы неизвестных и правых частей уравнений. Далее рас

а

а

а

а2 а22 а23

смотрим расширенную матрицу А' =

а

а

а

зз

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

Для того чтобы исключить первое неизвестное х, из второго уравнения системы, вычислим множитель т2 = ап, умножим первую строку матрицы А' на этот множитель и вычтем результат умножения из второй строки А'.

Получим

21 - т2аиу - 22 - т2ап2 - (а23 - т2ахз3 = Ь2 - т2Ьх. Обозначив я2! - т2аи =а' = 0, будем иметь

+ я13х3 + я23х3

+ «зз*з

<

аиХ 1 + апХ2 О + а'22х2

«31* | + а32х2

Для исключения неизвестного х{ из третьего уравнения полученной системы вычислим множитель т3 = азхи, умножим этот множитель на первую строку матрицы А' и вычтем результат умножения из третьей строки.

Тогда ввиду того, что ам - т3аи = 0 и вводя соответствующие обозначения, получим систему

+ я13х3 + а23х3

+ «33*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а'2333, Ь'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.

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

Укрупненная блок-схема алгоритма решения системы линейных уравнений методом исключения Гаусса

Рис. 1.35. Укрупненная блок-схема алгоритма решения системы линейных уравнений методом исключения Гаусса

Да .

Система

несовместна

Да

У=?

-?

* &кр Я к/ Щр

аи=г, 7=7 + 1

Да

у<«?

Нет

^=6*, = Ьі,

Ь,=г

Блок-схема алгоритма поиска максимального элемента

Рис. 1.36. Блок-схема алгоритма поиска максимального элемента

и замены строк А'

Блок-схема вычитания строкА'

Рис. 1.37. Блок-схема вычитания строкА'

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

Шаг 7. Если 1= к, перейти к шагу 12.

Шаг 8. Положить у = к.

Шаг 9. Положить I = акр ак] = а а у = I-

Шаг 10. Положить у = у + 1, если / < п, вернуться к шагу 9.

Шаг 11. Положить ? = Ьк, Ьк = Ь„ Ь, = I-

Шаг 12. Положить /=? + 1.

Шаг 13. Вычислить т = акк, положить а = 0.

Шаг 14. Положить у = к + 1.

Шаг 15. Вычислить а0 = аи - та .

К выводу

Шаг 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, ..., 49 в матрицу А

Рис. 1.40. Алгоритм записи чисел натурального ряда 1, ..., 49 в матрицу А

по спирали

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

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

/= 1, у = от 1 до 7;

/' = от 2 до 7, У = 7;

/ = 7, у = от 6 до 1;

/ = от 7 до 2, у = 1.

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

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

Задача 1.30. Рассмотрим шахматную доску и два положения коня на ней (рис. 1.41). Возможные ходы коня показаны стрелками и пронумерованы. Конь слева (поле (1,2)), не выходя за пределы доски, может пойти только на три поля. Конь справа (поле(5,6)) может пойти на восемь полей, что является макси-

  • 2
  • 4
  • 6
  • 8

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

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

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

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

Выход коня за пределы доски может фиксироваться путем обрамления доски двумя полями, в которые записано произвольное число больше нуля, например 66. На рис. 1.42 приведены исходные данные о доске и показано начало маршрута коня из поля (7, 8).

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

  • 1) инициализацию полей обрамления доски, т. е. запись в эти поля числа 66 или любого другого, например 99;
  • 2) инициализацию начала цикла по всем маршрутам с указанием начальной длины маршрута / = -1 для выбора лучшего маршрута;

1

2

3

4

5

6

7

8

9

10

11

12

1

66

66

66

66

66

66

66

66

66

66

66

66

2

66

66

66

66

66

66

66

66

66

66

66

66

3

66

66

0

0

0

0

4 ,

0

0

0

66

66

4

66

66

0

0

0

0

0

0^

ч

0

66

66

5

66

66

0

0

0

0

0

0

0

°

66

66

6

66

66

0

0

0

0

0

0

0

  • 2

66

66

7

66

66

0

0

0

0

0

1"

"0

0

66

66

8

66

66

0

0

0

0

0

0

0

0

66

66

9

66

66

0

0

0

0

0

0

0

0

66

66

10

66

66

0

0

0

0

0

0

0

0

66

66

11

66

66

66

66

66

66

66

66

66

66

66

66

12

66

66

66

66

66

66

66

66

66

66

66

66

Рис. 1.42. Исходные данные о доске и начало маршрута коня

  • 3) инициализацию полей доски, т. е. запись в эти поля числа 0;
  • 4) построение маршрута коня, запоминание его длины и выделение лучшего текущего маршрута;
  • 5) вывод лучшего маршрута и его длины.

Укрупненная блок-схема алгоритма поиска лучшего маршрута коня приведена на рис. 1.43.

На рис. 1.44 приведена блок-схема алгоритма инициализации верхнего обрамления доски с учетом того, что вся доска с обрамлением представляет собой квадратную матрицу /) = 11<^||

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

Аналогичный вид будет иметь блок-схема инициализации нижнего обрамления доски. Другими будут только начальные и конечные значения управляющей строки /5= 11, 1Р = 12.

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

Определение длины п маршрута

Нет

Запоминание лучшего маршрута и его длины / = /7

I*-:

И =И+

V

Да

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

Рис. 1.44. Блок-схема алгоритма инициа- Рис. 1.45. Блок-схема алгоритма

лизации верхнего обрамления доски инициализации левого и правого

обрамления доски

Блок-схема инициализации непосредственно шахматной доски реализует процедуру занесения в двумерный массив /) = dyW с индексами /5=3, 1Р = 10, у5=3, ]р = 10 значений с1 Она

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

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

к

/'

У

1

1 = 1-1

1=1+1

2

1=1-

7=7+2

3

!'=/+ 1

1=1+ 2

4

/ = / + 2

1=1+ 1

5

1 = 1 + 2

У=У- 1

6

/=/+ 1

у=у- 2

7

/=/- 1

У =У-2

8

/'=/- 2

7=7- 1

Таким образом, для исходного поля очередного маршрута и каждого допустимого поля (/,_/') необходимо организовать просмотр максимум 8 полей. Для этого следует организовать цикл переменной по к от 1 до 8. В свою очередь изменение индекса удобно вычислять как / = / + 4, у =у + у*. Для этого значения 4? Л необходимо представить двумя одномерными массивами 4 = (-2 -112 2 1-1 -2), у4 = (1 2 2 1-1-2-2 -1).

На основании изложенного построение маршрута может быть организовано следующим образом. Получив поле (/,у) начала очередного маршрута, установить его номер п= 1, положить <4, = 1, а значения /, у занести на первые места в два рабочих массива т1 и тр каждый длиной п < 64. Затем приступить к выявлению первого допустимого поля в цикле по к. Если такое поле обнаружено, занести индексы /, у в массивы т{ тр значение п = п + 1 — в и перейти к началу очередного цикла по к. Если же оно не обнаружено, изменить к = к + 1 и продолжить цикл.

В том случае, когда допустимое поле не будет обнаружено, следует перейти к замене полученного маршрута на лучший маршрут и вывести лучший маршрут и его длину. Блок-схема алгоритма построения маршрута приведена на рис. 1.46. Очевидно, что для хранения лучшего маршрута еще необходимы два массива индексов / и у — тп, тр длиной п < 64.

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

Шаг 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

Л

л

2

л

л

3

л

л

4

л

л

5

л

л

6

л

л

7

л

л

8

Л

л

а

ь

с

д

е

г

г

и

Рис. 1.47. Возможные допустимые варианты расположения ладей на доске

В шахматной нотации первый вариант записывается как а! Ь2 сЗ 64 е5 Гб g7 Й8, второй — как а8 Ь7 с6 ф е4 Т3 g2 й,. Из этих

записей легко видеть, что любой допустимый вариант расстановки ладей определяется перестановкой первых восьми чисел натурального ряда. В связи с тем, что число перестановок Рп = 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 с двойкой и заканчиваем построение перестановок. Все перестановки построены. Они приведены ниже. Повторяющиеся перестановки заключены в прямоугольники.

  • 231
  • 123
  • 132
  • 213
  • 123_

Пусть 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, сравнением их между собой и остановкой в случае ух = у2 или

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

Заметим, что после первого деления мы переходим к оче-

редному интервалу длиной

в

Рис. 1.50. Унимодальные функции:

а — выпуклая; б — непрерывная негладкая; в — негладкая с разрывами

конечного ряда

а - Ь е

  • -- + - , после второго перходим
  • 2 2

к интервалу длиной

<*-Ъ | ?

4 4

/

ґ

третьего деления — к интервалу длиной

а-Ь (23 -1)7

а - Ь 3

  • -+ — с.
  • 4 4

а - Ь 3

  • - + -Є
  • 4 4

После

а - Ь | 7

  • - + — 8 —
  • 8 8

є. Таким образом, после п деле-

23 23

ний исходного интервала [а, Ь] будет получен интервал длиной а-Ь (2"-1)

2"

+

2"

є. Откуда при заданных значениях а, Ь, є мож-

но вычислить значение п, показывающее, сколько делений [а, Ь] нужно выполнить, чтобы получить заданную точность.

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

Начало

I

Ввести а, Ь, с

Х -Х-е/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 именно в таком отношении.

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

 
< Пред   СОДЕРЖАНИЕ     След >