Навигация
Главная
Поиск
Форум
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
Бип из системно... 62637
Организация зап... 59823
Invision Power ... 59450
Приложение «Про... 58710
Оператор выбора... 57815
Модуль Forms 57737
Подключение Mic... 57076
Создание отчето... 57027
ТЕХНОЛОГИИ ДОСТ... 53313
Программируемая... 51111
Пример работы с... 49201
Имитационное мо... 48794
21 ошибка прогр... 43554
Реклама
Все для бара www.daisybar.ru. .
Светодиодные светильники line style ip65 "Профсвет".
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Моделирование работы аэропорта на GPSS + Пояснительная записка
Моделирование регулировочного участка цеха на GPSS + Пояснительная записка
Моделирование интернет магазина (Apache, Php, Html) на 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 Комментариев · 17520 Прочтений · Для печати

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


Комментарии
Катя 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...
Шаблон для новост...

Случайные загрузки
Пример клиента ФТ...
PHP5. Профессиона...
Библия для програ...
C++ Builder: Книг...
CS:Source - монит...
Алгоритмы шифрова...
Язык программиров...
Песочные часы
Dreamsoft Progres...
Geo-Whois
IconCut [Исходник...
Page Promoter 7.7...
PHP/MySQL для нач...
3D Октаэдр
PHP/MySQL для нач...
Plasma
Программа рисует ...
Разработка интерн...
Анимированное поя...
HTMLredaktor

Топ загрузок
Приложение Клие... 100333
Delphi 7 Enterp... 79846
Converter AMR<-... 20025
Borland C++Buil... 10823
GPSS World Stud... 9748
Borland Delphi ... 7849
Turbo Pascal fo... 6910
Visual Studio 2... 4926
Калькулятор [Ис... 4128
FreeSMS v1.3.1 3488
Случайные статьи
Класс TGraphic
Компонент изображение
Идея регулярных вы...
Раскрутка сайта в ...
расположены в разн...
Соображения по пов...
Адресное пространство
Ввод-вывод методом...
RTTI
Однополярное кодир...
Основные преимущес...
ОПЕРАТОРЫ БЛОКОВ
Ключевые факты об ...
Содержание
Операции insert и ...
Линия границы надписи
Введение в язык XSLT
Создание содержани...
Подпрограмма Input...
ПРЕДИСЛОВИЕ КО ВТО...
Удаление экземпляр...
Применение модульн...
Дополнительный ша...
Создание нового са...
Фильтр "не"
Статистика



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


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