Основы программирования (947332), страница 16

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

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

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

пример 4.19).Чаще всего при программировании поисковых задач используют циклыдо или циклы-пока, в которых условие выхода формируется из двух условий(см. параграф 3.6): первое условие - пока искомый элемент не найден, а вто­рое - пока есть элементы массива. После выхода из цикла осуществляютпроверку, по какому из условий произошел выход.Пример 4.8. Разработать программу, определяющую первый отрица­тельный элемент массива.Для решения задачи необходимо разработать поисковый цикл, т.е.

орга­низовать последовательный просмотр массива, пока не будет обнаружен пер­вый отрицательный элемент. Из материала параграфа 3.6 известно, что этуоперацию можно выполнить структурно и неструктурно.944. Структурные типы данныхН е с т р у к т у р н ы й а л г о р и т м , в котором просмотр осуществля­ется с помощью счетного цикла, а выход обеспечивается операторами gotoили break, рассматривать не будем.Реализуем с т р у к т у р н ы й а л г о р и т м , в котором для просмот­ра элементов используется цикл-пока со сложным условием: пока элементыне отрицательны и индекс элемента не вышел за границы массива. Элемент,на котором прервался цикл, если его индекс не превышает размера массива,и есть искомый.Program ex;Var а: array[L, 100] of integer;iJ,n: integer;BeginWriteLn(*Beedume количество элементов n <= J00');ReadLn(n);WriteLn(*Введите \n, * элементов массива *);for i:=I to n do Read(a[i]);ReadLn;WriteLnC Исходный массив ');for i:=I to n do Write(a[i]:5); WriteLn;i:-l; {начальное значение индекса массива}while (afij>=0) and (i<n) do i:=i+l; {пока элемент не отрицателени индекс меньше п - переходим к следующему элементу}ifi<-n thenWriteLnCnepebiu отрицательный элемент ^,afij:5,* имеет индекс %'4)else WriteLnCTuKux элементов в массиве нет, У;EndЗадания для самопроверкиЗадание 1.

Дан одномерный массив вещественных чисел А(п), где п < 50. Раз­работайте профамму, формирующую новый массив В из элементов массива А, ко­торые превышают среднее арифметическое элементов массива А, стоящих на местахс четными индексами. Выведите среднее арифметическое значение элементов мас­сива А, исходный и сформированный массивы.Задание 2. Дан одномерный целочисленный массив С(п), где п < 40, содержа­щий как положительные, так и отрицательные элементы. Разработайте профамму,которая определяет номер первого отрицательного элемента, по абсолютной величи­не превышающего максимальный элемент этого массива.

Выведите массив С, а так­же номер найденного элемента, или соответствующее сообщение, если такого эле­мента нет.Задание 3. Разработайте программу, которая формирует массив В(п), п < 30, со­держащий элементы целого типа в диапазоне от -20 до 130, используя датчик слу95Часть I. Основы алгоритмизации и процедурное программированиечайных чисел. В сформированном массиве определите количество и среднее ариф­метическое положительных и отрицательных элементов массива.

Переменной логи­ческого типа Flag присвоить True, если среднее арифметическое отрицательных чи­сел по абсолютной величине больше среднего арифметического положительных чи­сел, и False, если нет. Выведите массив В, а также все найденные в программе вели­чины.Задание 4. Дан массив Т(п), п < 20, вещественного типа. Разработайте програм­му, которая вычисляет произведение максимального по абсолютной величине эле­мента заданного массива на его же первый отрицательный элемент, если таковойимеется. Выведите исходный массив и произведение, или сообщение о невозможно­сти вычисления произведения.Задание 5. Дан массив D(n), п < 10, вещественного типа.

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

Цель сортировки - облегчение последующего поиска элемен­тов. Это почти универсальный вид обработки информации, с которым мывстречаемся в жизни повсеместно.Существует огромное количество методов сортировки и, соответствен­но, алгоритмов их реализации. Часть из этих алгоритмов в некотором смыс­ле оптимальна, другие имеют свои достоинства и недостатки. Поэтому,прежде чем использовать алгоритм, реализующий какой-либо метод, следу­ет выполнить анализ его производительности в конкретных условиях.В качестве оценки производительности методов обычно используютфункциональную зависимость времени работы программы от размерностиисходного массива t(n). При анализе алгоритмов в первую очередь интереспредставляет характер зависимости при достаточно больших значениях раз­мерности задачи (п -»оо).Б математике характер зависимости часто определяют ее порядком.

Порядком некоторой функции t(n) при достаточно больших п называют другуюфункцию g(n), такую, чтоt(n)lim= const Ф 0.n->oo g(n)Это обозначается как t(n) = 0[g(n)].964. Структурные типы данныхНапример, для полинома f(rt) = 20"* - Зп^ + 5п - 6, порядком является по­лином п"*, или f(n) = О(п^), так какlimп->оо2п4 - ЗпЗ + 5п - 6=2.j|4В программировании порядок зависимости времени работы программы,реализующей некоторый метод, от размерности исходных данных п называ­ют вычислительной слоэюностъю данного метода.

Так, вычислительнасложность O(const) означает, что время решения задачи с использованиемданного метода не зависит от размерности задачи, 0(п) - время работы про­порционально размерности задачи, 0(v?-) - время работы пропорциональноквадрату размерности задачи и т. д.Примечание, В некоторых случаях целесообразно различать вычислительную сложностьметода и его конкретной реализации, так как неудачная реализация может существенно ухуд­шить предполагаемую вычислительную сложность метода.Временную сложность можно оценить, используя в качестве единиц из­мерения временные единицы (мкс, сит. д.), а можно - используя время вы­полнения основных, характеризующих процесс операций^ количество кото­рых соответствует количеству итераций (повторений) цикла, например, опе­раций сравнения, операций пересылки.

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

Та­кие методы в практике программирования называют прямыми. Самыми про­стыми из прямых методов являются:• метод выбора;• метод вставки;• метод обменов (метод пузырька).Рассмотрим эти методы на конкретном примере.Пример 4.9, Разработать программу сортировки элементов массиваА(п), где п < 20, используя метод выбора, метод вставки и метод обменов.Оценить эффективность применения указанных методов.Метод выбора. Сортировка посредством выбора представляет собойодин из самых простых методов сортировки.

Он предполагает такую после­довательность действий.Сначала находим минимальный элемент массива. Найденный элементменяем местами с первым элементом. Затем повторяем процесс с п-1 элемен97Часть 1, Основы алгоритмизации и процедурноеЬй проход7.8 -6.35.8К,^2-й проходШЩ!^п^1.28.44.58.44.55.81.2iminaminimin5.87.88.4IF] [Т]amin4.5n-34-й проходammм 1n-23-й проходпрограммирование[ID Шaminmwm^f^wtm^xi^f^iminon шamin5-й проходimin7.8imin[тг] H^^тштж^шШЩРис. 4.13.

Сортировка выборомтами, начиная со второго, потом с п-2 элементами, начиная с третьего и т.д.до тех пор, пока не останется один, самый большой элемент массива (рис.4.13).Алгоритм сортировки выбором приведен на рис. 4.14. Ниже приведентекст программы, реализующий данный алгоритм.Program sortl;Var a:array[L.20] of real;y, /, w, imin:mteger;mm:real;BeginWritelnCBeedume количество чисел n<=20: *);Readln(n);Writeln('Введите массив: *);for i:=^l to n do Read(a[i]);Readln;forj:-l to n-l do {цикл поиска минимальных элементов массива}beginmn:^4i[j]; {начальное значение для поиска минимума}imin:^j; {начальное значение индекса минимального элемента}for i:-jH to п do {цикл поиска минимума и его индекса}ifa[i]<min then {если элемент меньше уже найденногоминимального}984.

Структурные типы данныхbeginmin:—a[i]; {запоминаемэлемент}imin:-i{запоминаем егоиндекс}end;{меняем местами найденныйминимум и первый элементтекущего массива}a[imin]:=a[j];a[iJ:=ntin;end;for i:=] to n do Write(a[i]:6:2);Writeln;End.Оценим временную сложность данногометода, используя в качестве основной опе­рации операцию сравнения.Для поиска минимального элемента вкаждом проходе потребуется выполнить:п-1, п-2, ..., 1 операций сравнения, т.е. всегоп(п-1)/2 операций сравнения. Следователь­но, вычислительная сложность данного ме­тода 0(п2).

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

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