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

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

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

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

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

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

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

Нахождение суммы есть последовательное нахождение суммы по формулам:

Алгоритм вычисления суммы удобно организовать циклом, взяв за параметр цикла переменную i, которая меняется от 1 до n с шагом 1, и записав в цикле формулу S=S+ai один раз. Схема алгоритма приведена на рис. 1а.

В схеме блок 4 присваивает S нулевое значение, блок 5 счетчику i присваивает начальное значение, блок 6 выполняет накопление суммы, блок 7 изменяет значение i на 1, блок 8 осуществляет проверку условия повторения цикла. При выполнении этого условия управление передается в начало цикла, а при невыполнении – осуществляется выход из цикла, т.к. при i=n+1 суммировать не нужно. n – в схеме предполагается число, но n может быть и переменной, значение которой равно числу элементов массива A, которое нужно вводить перед описанием массива.

При разработке этого алгоритма учащимся можно предложить изменить схему на случай, если нужно найти сумму элементов, расположенных на четных местах в массиве A (Ответ: Блок 5 надо изменить на i=2 и блок 7 на i=i+2) или задать вопрос – что изменится в схеме на рис.1а, если суммировать только положительные элементы массива A? (Ответ: Перед блоком суммирования 6 нужно поставить блок проверки элемента массива ai на положительность и, если он положителен, то его суммировать, а если нет, то обходить блок суммирования.) Схема алгоритма будет иметь вид:

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

(Ответ: Надо ввести переменную k для получения количества положительных элементов и перед циклом присвоить ей значение 0. После блока проверки 7 по пути “+” нужно поставить блок, содержащий k=k+1, который ведет счет количества положительных элементов массива A.) Схема алгоритма приведена на рис.3а.

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

Этот алгоритм предлагается учащимся разработать самостоятельно, взяв за основу алгоритм определения суммы элементов массива (Рис. 1а). Учащиеся должны не только указать на изменения блока 6 на S=S*ai (в S будет направляться произведение элементов), но и дать четкое объяснение изменению блока 4 на S=1. Схема алгоритма представлена на рис.1б.

Алгоритм формирования нового массива

Как положительные элементы массива A сформировать в массив? Обозначим массив положительных элементов B и по пути “+” после блока 7 поставим присвоение соответствующему элементу массива B элемент массива A, т.е. блок, содержимое которого bk=ai.

k будем использовать как меняющийся индекс нового массива. Необходимо обратить внимание учащихся на блок 2, в котором требуется описать массив B, указав количество его элементов равное количеству элементов массива A. Схема алгоритма на рис.3б.

Алгоритм определения максимального элемента

Для получения максимального числа введем переменную M и ей присвоим значение первого элемента массива a1, а затем необходимо сравнить M с текущим элементом массива ai и если текущий элемент будет больше M, то значение M заменить на значение этого элемента. Схема алгоритма на Рис. 4. Очень важно обратить внимание учащихся на начальное значение переменной M. Почему, например нельзя переменной M присвоить значение равное нулю? (Ответ: Для массива с отрицательными значениями элементов максимум не будет найден.)

Алгоритм упорядочения массива методом “Пузырька”

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

Одномерный массив A из n элементов упорядочим по возрастанию. При пузырьковой сортировке элементы массива попарно сравниваются и более “легкие” элементы как бы всплывают на поверхность. При реализации алгоритма возникает проблема в определении количества шагов сортировки. Для решения этой задачи воспользуемся известным методом “расстановки флажков”, благодаря которому однозначно будет определен момент завершения сортировки и выхода из цикла (блок 5).

В качестве “флажка” возьмем числовую переменную F и присвоим ей произвольное начальное значение отличное от нуля (блок 4). Схема алгоритма на рис. 5. По парное сравнивание элементов и их обмен местами происходит в блоках 9-12, здесь же изменяется значение флажка (блок 13). В случае, когда все элементы массива будут упорядочены, значение F останется равным нулю (блок 6). Блоки 3 и 15 являются укрупненными, т.к. алгоритмы ввода и вывода элементов массива подробно не описаны на схеме (Рис. 5).

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