Ничушкина Т.Н., Гуренко В.В. - Разработка алгоритмов простейших программ (1075626), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

В реальной практике тот или иной класс задач в чистом видевстречается редко. Однако при помощи метода пошаговой детализации любая сложнаязадача может быть разбита на более простые задачи, относящиеся к указанным вышеклассам. Следует также учитывать, что существуют особенности решения каждого изназванных классов задач в зависимости от количества индексов массива.3.1. Приемы обработки одномерных массивовОдномерными называют массивы, для доступа к элементам которых необходим одининдекс. Рассмотрим наиболее распространенные приемы обработки одномерныхмассивов, используемые в программировании.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»263.1.1.

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

Этопозволяет использовать счетные циклы, параметр которых обеспечивает доступ кэлементам. Однако возможно применение и других типов циклов, менее эффективных врассматриваемом случае.Рассмотрим некоторые типовые алгоритмы задач.Пример 3.1. Пусть необходимо ввести (вывести) массив. Для этого нужнопоследовательно перебрать все элементы массива.

Как отмечено, при известномколичестве вводимых элементов для этой операции удобно использовать счетный цикл.При неизвестном количестве элементов рациональнее использовать циклы с пред- илипостусловиями. При выводе массива количество элементов может быть известно заранееили задаваться пользователем. Схема алгоритма, при помощи которого осуществляетсяввод количества элементов n и ввод-вывод одномерного массива A(n), представлена нарисунке 3.1, а. Заметим, что при решении реальных задач бывает полезно после вводаэлементов массива перед началом обработки сразу вывести его, например, для удобстваотладки. С этой целью можно использовать тот же цикл, что и для ввода массива,разместив в теле цикла как оператор ввода, так и оператор вывода элемента.Поскольку ввод-вывод массивов всегда осуществляется однотипно, каждый раздетализировать эти операции нет необходимости.

На схемах алгоритмов операции ввода ивывода массивов обычно показывают одним блоком (см. рисунок 3.1, б).ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»27Рисунок 3.1 – Ввод-вывод одномерного массиваПример 3.2. Сравнительно часто встречается задача нахождения наибольшего илинаименьшего элемента массива (например, при построении графика функции).Вспомогательной переменной Аmax присваивается значение первого элементамассива, затем последовательно все элементы массива сравниваются с переменной Аmax.Если значение Аmax оказывается меньше, чем очередной элемент, то Аmax присваиваетсяновое значение (см.

рисунок 3.2).Рисунок 3.2 – Схема алгоритма нахождения максимального элемента массиваОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»28Пример 3.3. Пусть необходимо найти среднее арифметическое значение элементовцелочисленного массива, кратных трем. Для решения этой задачи водятся двевспомогательные переменные – Sum и Kol, которые будут использоваться для накоплениясуммы требуемых элементов и их количества.

Первоначально обеим переменнымприсваиваются нулевые значения. Алгоритм осуществляет полный перебор всехэлементов и, если очередной удовлетворяет условию, его значение добавляется кпеременной Sum, а значение переменной Kol увеличивается на единицу. После просмотрамассива среднее арифметическое определяется делением накопленной суммы наколичество найденных элементов. Схема алгоритма решения задачи приведена на рисунке3.3.Рисунок 3.3 – Схема алгоритма нахождения среднего арифметического элементов, кратных 3Пример 3.4.

Пусть необходимо заменить все отрицательные элементы массива наноль.Несложно понять, что схема алгоритма решения этой задачи (см. рисунок 3.4) оченьпохожа на предыдущую, поскольку вновь требуется последовательная проверка всехэлементов массива.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»29Рисунок 3.4 – Схема алгоритма замены отрицательных элементов массива нулями3.1.2. Выборочная обработка элементов массиваК задачам данного типа относятся задачи, по формулировке схожие задачам первогокласса, но обработка ведется не всех элементов массива, а только тех, которые имеютвполне определенное значение индексов.

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

Схема алгоритмарешения задачи представлена на рисунке 3.5. Возможен вариант решения этой задачи безиспользования вспомогательной переменной k, когда в качестве индекса используетсянепосредственно параметр счетного цикла, который изменяется от двух с шагом два.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»30Рисунок 3.5 – Схема алгоритма поиска максимального элемента, записанного на четном местеПример 3.6. Заменить каждый третий элемент массива на ноль, если элементчетный, и остатком от деления элемента на пять, если он нечетный.В данном случае нас интересует каждый третий элемент, поэтому количествопросматриваемых элементов равно трети от числа элементов массива, а значение индексаk в цикле увеличивается на три (см.

рисунок 3.6). Замечание относительно возможногоиспользования переменной цикла непосредственно в качестве индекса аналогичнопредыдущему примеру, начальное значение равно трем, шаг изменения – плюс три.В задачах данного класса изменяется только порядок следования элементов массива.Размер массива остается неизменным.ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»31Рисунок 3.6 – Схема алгоритма замены каждого третьего элемента массива3.1.3. Изменение порядка следования элементов массива. СортировкаПримерами подобной обработки служат: замена значений некоторых элементов всоответствии с определенными правилами, сортировка массивов по неубыванию,невозрастанию и по любому другому признаку, различного рода перестановки, сдвигиэлементов и другое. Особенностью данного класса задач является необходимость поискаэлемента перед перестановкой или заменой.

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

Вкачестве индекса исходного массива мы, как и ранее, будем использовать переменнуюцикла. А для указания номера элемента в новом массиве понадобится специальный индекс(индексы), который придется изменять с помощью отдельного оператора.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»32И последнее. Осуществить требуемое переформирование массива за один проходневозможно, поскольку количество элементов каждого типа неизвестно.

Задачу можнорешить, используя три цикла, в которых в новый массив последовательно переписываютсясначала положительные элементы, затем отрицательные и, наконец, – нулевые. Однаковозможно использование и двух циклов: в первом перепишем в начало нового массиваположительные элементы, а в конец – нулевые, начиная с последнего, а во втором простодопишем в середину отрицательные элементы.Окончательный вариант алгоритма приведен на рисунке 3.7.Рисунок 3.7 – Схема алгоритма перестановки элементов массиваОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»33Наиболее распространенными задачами второго класса являются сортировкимассивов.Сортировка – это изменение порядка следования элементов массива таким образом,что значения элементов образуют упорядоченную по некоторому закону совокупность. Напрактике сортируемые массивы обычно имеют большую размерность, поэтому для любогоалгоритма сортировки оценивают временнýю вычислительную сложность, котораяопределяется зависимостью времени работы алгоритма (числа него шагов) от размерностизадачи, т.е.

от количества сортируемых элементов. Чем меньше это время, тем болееэффективеналгоритм.Эффективностьалгоритмаоцениваюттакжеёмкостнойвычислительной сложностью, с точки зрения которой существенно, какие ресурсыпамяти требуется для выполнения алгоритма.Поэтому интерес представляют такиеметоды сортировки, которые позволяют экономно использовать оперативную память,например, обходиться без дополнительных массивов.Классических методов сортировки три: выбором, обменом и вставками. Рассмотримих особенности применительно к сортировке по неубыванию.Сортировка выбором. Это один из самых простых методов сортировки. Онпредполагает следующую последовательность действий:выбирается наименьший элемент всего массива;найденный наименьший элемент меняется местами с первым элементом;указанные два действия повторяются с оставшимися n-1 элементами, n-2 элементами и т.д.до тех пор, пока не останется n-ный, наибольший элемент массива.Пример схемы алгоритма сортировки выбором приведен на рисунке 3.8.ОглавлениеНичушкина Т.Н., Гуренко В.В.

Характеристики

Список файлов книги