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

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

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

Для ввода - вывода элементов одномерного массива открывается цикл с количеством повторений, равным количеству членов массива, а затем в цикле осуществляется поэлементный ввод (вывод) значений каждого из членов массива 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,, Х₂, Х₃,...

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

Дата добавления: 2015-07-14