Навигация
Главная
Поиск
Форум
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
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 64162
Модуль Forms 63869
ТЕХНОЛОГИИ ДОСТ... 60754
Пример работы с... 60753
Имитационное мо... 56273
Реклама
Светодиодные светильники line style ip65 "Профсвет".
Сейчас на сайте
Гостей: 12
На сайте нет зарегистрированных пользователей

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

Моделирование процесса обеспечивающего надежность функционирования АСУ Т...
Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...
Создание последовательности окон и передвижение окон по экрану на Turbo ...

Реклама



Подписывайся на 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 Комментариев · 19279 Прочтений · Для печати

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


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

Случайные загрузки
MPTools
DCMintry
Printgrid
AlnComponents
Rotolabel
Библия для програ...
Электронный магаз...
Создание фракталов
Паскаль и Дельфи....
EditButton
GamesBase 3.0
ИНТЕРНЕТ ПРОГРАММ...
Язык программиров...
Illusion
Библия хакера 2. ...
Защита от спама ...
Animation (Пример...
XPButtons
Preview
Панель статистики...

Топ загрузок
Приложение Клие... 100455
Delphi 7 Enterp... 86134
Converter AMR<-... 20071
GPSS World Stud... 12522
Borland C++Buil... 11608
Borland Delphi ... 8522
Turbo Pascal fo... 7035
Visual Studio 2... 4992
Калькулятор [Ис... 4744
FreeSMS v1.3.1 3539
Случайные статьи
Загрузить/скачать ...
Экземпляры элемент...
Персептрону. Пробл...
13.5. Принципы
Настройки приватности
В программе предпо...
Язык С: макросы, п...
Полный локальный в...
Применяйте AsyBEUI...
Погружение LISP в ABC
Инкапсуляция
Декартовое произве...
Программирование C...
Классификация устр...
Этот список опреде...
Представления дере...
Функции выполняют ...
ОСНОВЫ ООП В DELPH...
Унификация доступа...
Точная настройка д...
Целые типы
ЧТО такое XSL
Этап 5 - использов...
Управление доступо...
2000 Professional(...
Статистика



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


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