Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Эмулятор микроп... 65535
Приложение «Про... 61604
Организация зап... 61314
Invision Power ... 60955
Оператор выбора... 60272
Подключение Mic... 59056
Модуль Forms 58941
Создание отчето... 58515
ТЕХНОЛОГИИ ДОСТ... 54750
Программируемая... 53485
Пример работы с... 51439
Имитационное мо... 50177
21 ошибка прогр... 45140
Реклама
Светодиодные светильники line style ip65 "Профсвет".
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

Пользователей: 13,054
новичок: Prom
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование вычислительного центра на GPSS + Отчет + Блок схема
Обратное размещение элементов ЭВС на Delphi + Пояснительная записка
Моделирование круглосуточного интернет кафе на GPSS + Отчет

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Алгоритмы поиска в неупорядоченных одномерных массивах
Рассмотрим сначала нюансы реализации “технических” задач поиска, которые встречаются в различных алгоритмах. Начнем с, казалось бы, тривиальной задачи поиска элемента в неупорядоченном массиве. Во всех примерах, относящихся к поиску в одномерном массиве будем использовать следующую переменную a:
a:array[0..N] of <скалярный тип>;



при этом собственно элементы массива, которые мы будем рассматривать, пронумерованы от 1 до N, а нулевой элемент будем использовать как вспомогательный в случае необходимости. Конкретный же тип элемента в большинстве описываемых алгоритмов не важен, он может быть как любым числовым, так и символьным или даже строковым. Алгоритм поиска в массиве элемента, значение которого равно K, может выглядеть так:
i:=0;
repeat
i:=i+1
until (i=N) or (a[i]=K);
if a[i]=K then write(i)
else write(0)
{следующее неверно (!!!):
if i=N then write(0)
else write(i) }



При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, что и такую достаточно простую программу можно упростить, заодно продемонстрировав так называемый “барьерный” метод, который часто применяется в программировании в том числе и олимпиадных задач. В данном случае он заключается в том, что мы можем занести в дополнительный элемент массива (например, нулевой) искомое значение K, избавившись тем самым в условии окончания цикла от проверки на выход за границу массива:
a[0]:=K;
i:=N;
while (a[i]<>K) do
i:=i-1;
write(i)



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

imax:=1;

imin:=1;

for i:=2 to N do

if a[i]<a[imin] then imin:=i else

if a[i]>a[imax] then imax:=i




Заметим, что использование в качестве начальных значений для минимума и максимума не значение первого элемента массива, а максимальное и минимальное значение в типе элементов, может привести к ошибке. Так, следующая программа не находит значение максимума для убывающего массива целых чисел (!!!):
max:=-MaxInt-1;{это минимальное число типа integer}
min:=MaxInt;{это максимальное число типа integer}
for i:=1 to N do
if a[i] if a[i]>max then max:=i



Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, более эффективных, чем приведенные выше стандартные алгоритмы. Причем именно при решении олимпиадных задач их знание может пригодиться в первую очередь. Итак, в приведенном выше алгоритме поиска максимального и минимального элемента в массиве в худшем случае выполняется 2N – 2 сравнений.Покажем, что ту же задачу можно решить за 3[N/2] – 2 сравнения*. Пусть у нас имеется четное число элементов. Разобьем их на пары и в каждой из N/2 пар за одно сравнение определим, какой элемент больше, а какой меньше. Тогда максимум можно искать уже любым способом только из наибольших элементов в парах, а минимум — среди наименьших. Общее число сравнений при этом равно N/2 + 2(N/2 – 1) = 3N/2 – 2. Для нечетного числа элементов — элемент, не попавший ни в одну из пар, должен участвовать как в поиске максимума, так и минимума.
Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, а именно: разобьем элементы на пары и определим в каждой из пар больший элемент, затем разобьем на пары уже эти элементы и т.д. В “финале” и будет определен максимум. Количество сравнений в таком алгоритме, как и в традиционной схеме, равно N – 1. Однако, максимальный элемент участвовал при этом в [log2N] сравнениях, причем одно из них проходило обязательно со вторым по величине элементом. Таким образом, теперь для поиска этого элемента потребуется всего [log2N] – 1 сравнение (!!!). Попробуйте самостоятельно построить эффективный алгоритм для поиска уже первых трех по величите элементов.
В данном контексте можно поставить также задачу поиска i-го по счету элемента, называемого i-ой порядковой статистикой. Кроме максимума и минимума, специфической порядковой статистикой является медиана — элемент с номером (N + 1)/2 для нечетных N и два соседних элемента для четных. Конечно, задачу поиска любой порядковой статистики можно решить, предварительно отсортировав массив. Но, как будет показано ниже, оптимальные по количеству сравнений универсальные (то есть пригодные для произвольных массивов) алгоритмы сортировки выполняют порядка Nlog2N сравнений. А задачу поиска i-ой порядковой статистики можно решить, производя O(N) сравнений. Алгоритм, который гарантирует эту оценку достаточно сложен, он подробно изложен в [1, 2, 3]. Мы же приведем схему алгоритма, который в худшем случае не является линейным, однако на практике работает существенно быстрее, следовательно именно его и нужно использовать в практике реального программирования:
Алгоритм Выбор(A, L, R, i)
{выбирает между L-ым и R-ым элементами массива A
i-ый по счету в порядке возрастания элемент}
1. if L=R then результат – A[L], конец;
2. Q:=L+random(R-L+1)
{Q – случайный элемент между L и R}
3. Переставляем элементы от L до R в A так, чтобы сначала шли элементы, меньшие A[Q], а затем все остальные, первый элемент во второй группе обозначим K.
4. if i<=(K-L) then Выбор(A, L, K-1, i)
else Выбор(A, K, R, i-(K-L))
5. конец.
Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки.
Наконец, рассмотрим задачу поиска в последовательности из N чисел, хранения которой не требуется вообще, следовательно ее длина может быть очень велика. Пусть известно, что в этой последовательности встречаются по одному разу все числа от 0 до N, кроме одного. Это пропущенное число и требуется найти. Вот возможное решение такой задачи:
S:=0;
for i:=1 to N do
begin
read(a); S:=S+a
end;
writeln(N*(N + 1) div 2 – S)



Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, что среди вводимых чисел каждое имеет ровно одно, равное себе, а одно число — нет. Найдите это число. (Указание. В данном случае можно воспользоваться свойством логической функции “исключающее или”, обозначаемой в Паскале как xor: a xor b xor b = a.)


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





Опубликовал Kest February 25 2010 22:27:01 · 1 Комментариев · 17937 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Катя January 18 2012 21:45:39
Спасибо, пригодилось smiley
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Printgrid
Алгоритмы шифрова...
XPcontrol
около 291 статьи ...
Расширенный загру...
PDPcheck
Дешифратор содерж...
PCXReader. Програ...
PDJXPPack
Таймер и секундомер
Ics
CoolHints2k v1.03
Удаление своего EXE
Простой текстовый...
Киллер окон
Szwavepanel
Генетический алго...
Панель "Случайное...
Самоучитель PHP 4
Java Server Pages...

Топ загрузок
Приложение Клие... 100356
Delphi 7 Enterp... 81290
Converter AMR<-... 20037
Borland C++Buil... 10906
GPSS World Stud... 10004
Borland Delphi ... 7962
Turbo Pascal fo... 6939
Visual Studio 2... 4946
Калькулятор [Ис... 4194
FreeSMS v1.3.1 3500
Случайные статьи
Иерархические стру...
При реализации co...
вкладках службы FT...
Производительность...
Охранная сигнализа...
Функциональные ком...
Нельзя все на один...
Онлайн казино. Игр...
Разделение абонент...
get(X)
Карта RESET
Принципы организац...
Арифметические выр...
Мы часто встречаем...
Первый служит для ...
Этап 5 - использов...
Советы тем, кто же...
Lol boosting
Security; использу...
Пример сеанса рабо...
Кириллица и локаль...
Оригинальная полно...
Этап опытной экспл...
Массив
Онлайн казино. Игр...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?