Скачать программы    Все программы автора

1.4. Типовые приемы алгоритмизации

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

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

Для ввода - вывода элементов одномерного массива открывается цикл с количеством повторений, равным количеству членов массива, а затем в цикле осуществляется поэлементный ввод (вывод) значений каждого из членов массива A_i (рис. 1.12a). При этом переменная цикла I отслеживает месторасположение вводимого или выводимого элемента в массиве. В практике программирования допускается при графической записи алгоритмов использовать сокращенный вариант фрагмента схемы ввода-вывода (рис. 1.12б). При этом подразумевается, что при изменении I от начального до конечного значения с заданным шагом (например, от 1 до N с шагом 1) будут введены значения всех лементов одномерного массива (от А₁ до A_N).

 

Рис1.12. Фрагмент схемы алгоритма ввода-вывода одномерного массива: а) - в полном виде; б) - в сокращенном виде

 

Ввод-вывод двумерного массива может производиться как по строкам, так и по столбцам при использовании вложенных циклов с заданным числом повторений. При вводе - выводе элементов массива B_I,J строкам первым открывается цикл с изменением переменной, отслеживающей изменение нумерации строк массива (в приводимом примере переменная цикла I), а переменная вложенного цикла (переменная J) отслеживает изменение последовательности номеров столбцов элементов в строке (рис. 1.13а). При вводе-выводе по столбцам - наоборот, первым следует цикл с переменной, отслеживающей изменение нумерации столбцов (для массива B_I,J с переменной цикла J), а во втором переменная цикла (переменная I) отслеживает изменение номеров строк в столбце (рис. 1.13б).

Определение суммы или произведения членов числовой последовательности производится в цикле с заданным числом повторений или итерационном, в зависимости от того, известно число членов этого ряда, входящих в сумму (произведение), или оно будет определяться каким-то условием, проверяемым каждый раз после очередного увеличения суммы (произведения). При этом предварительно, перед открытием цикла, для вычисления суммы переменная, отслеживающая сумму, обнуляется (S=0), а при вычислении произ­ведения - прирав­нивается к 1 (Р=1). Сумма элементов одномерного массива А_1, A₂,...,A_N вычисляется в цикле с заданным числом повторений путем прибавления каждого очередного элемента массива к сумме предыдущих элементов. При этом используется операция прис­ваивания для накопления суммы: S = S + А_I,. Она указывает на необходимость прибавления к уже известному значе­нию суммы (пере­менная S в правой части арифметического выражения) значения очередного слагаемого A_I и присваивания полученного значения в качестве нового значения переменной S.

Повторяя в цикле операцию присваивания, получаем процесс, реализующий вычисление требуемой суммы: S = S + А,+ А₂ + А₃ + ... + A_N(pиc. 1.14a). В процессе вычисления суммы при первом прохождении цикла первоначальное значение переменной S прибавляется к значению первого элемента массива А,, следовательно, начальное значение S не должно влиять на конечный результат, что возможно, только если оно равно 0. Поэтому перед выполнением цикла переменной S присваивается нулевое значение.

На рис. 1.146 приведена схема вычисления произведения элементов одномерного массива. Как видим, произведение элементов массива накапливается по аналогичной формуле Р = Р*А_I, при обязательном присвоении переменной начального значения Р, равного 1 (Р=1).

Пример 1.11. В урне находится 57 шаров, на каждом из

которых записано положительное или отрицательное число очков. Определить сумму положи­тельных очков, записанных на шарах, и количество шаров с отрицательными очками.

Если число очков на каждом шаре рассматривать как элемент массива, то задача сводится к определению суммы положительных и количества отрица­тельных элементов массива, состоящего из 57 элементов, например, D₁, D₂, ..., D₅₇. Операция при­сваивания для подсчета суммы положительных очков известна. Для подсчета количества отрицательных элементов в качестве очередного слагаемого принимаем единицу, то есть N = N + 1. Схема алгоритма приведена на рис. 1.15.

Вычисление факториала натурального числа. Факториал числа N (N!) равен произведению натуральных чисел от единицы до N, то есть 1-2-3-...-N или (N-1)! • N. Следовательно, при вычислении факториала необходимо организовать цикл с заданным числом повторений и в цикле по рекуррентной формуле осуществить перемножение всех натуральных чисел начиная с 1.

Пример 1.12. Составить алгоритм вычисления факториала натурального числаN, если известно, что при N = 0 N! = 1 и при N>0 N!=l*2*3*...*N.

Из пояснений к задаче следует, что в алгоритме необходима проверка условия N = 0. В случае выполнения данного условия результирующая переменная Р должна получить значение 1, в противном случае следует организовать цикл для перемножения элементов натурального ряда чисел от 1 до N. Полученное произведение будет искомым значением результирующей переменной Р. Схема алгоритма приведена на рис. 1.16.

 

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

Как видим, некоторое упрощение уже достигнуто при переходе от алгоритма с анализом всевозможных сравнений (рис. 1.6) к алгоритму с введением дополнительной переменной max (рис. 1.7). Введение промежуточной переменной max позволило организовать повторение по своей сути одинаковых блоков проверки условия (блоки 4,6 и 8) и присваивания (блоки 5,7 и 9), причем число

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

Использование массивов позволяет осуществить дальнейшее упрощение алгоритма поиска наибольшего (наименьшего) значения в последовательности чисел, избавляясь от сложной разветвляющейся структуры и переходя к алгоритмам более простой циклической структуры. Для этого исходные простые переменные а, Ь, с, ... представим в виде элементов одномерного массива, например X, то есть: Х,=а, Х₂=6, Х₃=с, ... После такой замены, используя простейший детерминированный цикл с переменной цикла, отслеживающей изменение индексов массива X, получаем сравнительно простой алгоритм поиска наибольшего значения в последовательности чисел (рис. 1.17). Отметим, что в подобном алгоритме количество блоков остается без изменений при любом увеличении количества исходных переменных а, Ь,с,..., изменяется только размер массива X, то есть количество его элементов X,, Х₂, Х₃,...

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

Пример 1.13. Ежедневные замеры влажности почвы в течение месяца дали следующие результаты: V,, V₂, ..., V₃₁. Определить наименьшую наблюдавшуюся влажность почвы и число месяца, когда она была зарегистрирована в первый раз.

Для решения задачи необходимо найти наименьший элемент массива V,, V₂, ..., V_3| и его порядковый номер в массиве. Схема алгоритма приведена на рис. 1Л 8. В алгоритме в качестве начального значения переменной М, отслеживающей наименьший элемент, принято значение первого элемента массива и, соответственно, переменная К, указывающая месторасположение наименьшего элемента, принимает значение 1. Далее все элементы V, (со 2-го по 31-й) в цикле сравниваются с М. При этом если очередной элемент массива меньше М, то переменная М становится равной значению этого элемента, а номер его месторасположения присваивается К. По завершении цикла переменной М будет присвоено значение наименьшего элемента массива, а переменной К - номера первого наименьшего элемента.

Определение кратности чисел. Для определения кратности чисел какому-то заданному числу N используют проверку на равенство результатов, полученных при делении проверяемого числа на заданное число М (при N=2 в схеме обозначенное как 1/2) и при целочисленном делении этих чисел (нахождении целой части числа, получаемого от деления двух целых операндов, в схеме обозначенное как [1/2]). Если полученные результаты совпадают, то проверяемое число кратно числу N, в противном случае - нет.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример 1.14. Дан натуральный ряд чисел от 1 до N. Вычислить сумму четных и произведение нечетных чисел этого ряда. Схема алгоритма представлена на рис. 1.19.

Удаление и вставка членов последовательности.

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

Пример 1.15. Дана последовательность натуральных чисел X ₁ X₂ , ..., X_N и натуральное число А. Найти и удалить из последовательности элементы, рапные А.

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

 

Пример 1.16. Дана упорядоченная по возрас­танию последовательность попарно различных нату­ральных чисел Х_1,X ₂,..., X _N и число А. Вставить в эту последовательность число А, не изменяя ее упорядо­ченности.

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

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

Схема алгоритма без использования специальных способов сокращения числа сравнений (например, деления отрезка поиска пополам), приведена на рис. 1.21.

Вычисление степенных многочленов (по схеме Горнера) типа Y = A_1*X^N + A_2*X^N-1+A₃-X^N-2+...

+A_N-1*X²+A_N-X + A_N+1, (например, Y = 5Х⁴ - 8Х³ + ЗХ² + 9Х - 4) часто приходится производить при переводе чисел из одной системы счисления в другую с основанием, большим исходного. Организация вычислений непосредственно по приведенному выражению приводит к значительному накоплению ошибки результата из-за многократного возведения в степень. Использование схемы Горнера значительно уменьшает ошибку и сокращает количество операций, поскольку возведение переменной X в любую степень заменяется простым умножением.

Схема Горнера основана на изменении вида представления степенного многочлена, исклю­чающего операции возведения в степень: Y = (...(A_1*X + A₂)*X + A₃ )*X+...+A_N._l)*X + A_N)*X+ A_N+1 например, Y = ((((5 *Х - 8)*X + 3)*X + 9)* X - 4). Обозначив через Y арифметическое выражение в любых внутренних скобках и используя операцию присваивания: Y= Y*X + А₁, легко получим выражение в смежных внешних скобках. При этом для получения результата приведенная операция должна повториться в цикле N раз при изменении переменной цикла I = 2,3,..., N+1 и начальном значении Y = A,.Схема алгоритма вычисления значения степенного многочлена по схеме Горнера представлена на рис. 1.22. Здесь коэффициенты многочлена заданы в виде массива, содержащего N+1 элемент. Начальное значение переменной Y, определенное перед началом цикла, равно коэффициенту А,. Если в многочлене отсутствуют члены с некоторыми степенями переменной X, то соответствующие элементы массива коэффициентов задаются при вводе равными нулю.

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

 

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

 

 

 

 

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

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

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

 

 

 

 

 

Учитывая, что N!=(N-1)!-N, x^N=x^(N-1)-x и (-1)^N+1 = (-1)^N *(-1), после элементарных сокращений получаем Dh =-x/N. Следовательно, каждый последующий член N рассматриваемого ряда может быть получен простым перемножением значения предыдущего члена ряда на найденное приращение с использованием при этом операции присваиваниях h= -x/N*h. Как видим, эта операция избавила нас от необходимости вычисления факториала N! и N-й степени числа X^N, что существенно уменьшило количество производимых операций и повысило точность вычислений.

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

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

Таблицу оценок 25 абитуриентов по 5 предметам представим в виде двумерного массива А_25;, содержащего 25 строк и 5 столбцов:

Каждая строка массива содержит оценки соответствующего абитуриента по всем дисциплинам, столбец - оценки всей группы по одной соответствующей дисциплине. Элемент массива Aj_t -это оценка 1-го абитуриента по J-й дисциплине 1=1, 2,..., 25; J = 1, 2,..., 5.

 

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

2,..., 25. Для вычисления суммы элементов одной строки организуем вложенный цикл с переменной цикла J = 1, 2,..., 5. По завершении работы вложенного цикла определим среднее арифметическое значение элементов строки. Повторяя приведенные действия для каждой строки, вычислим все искомые значения среднего балла каждого абитуриента. Для который будет внешним по отношению к вложенному циклу спеременной.1. Схема алгоритма приведена на рис. 1.24.