Навигация
Главная
Поиск
Форум
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
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
ТЕХНОЛОГИИ ДОСТ... 62974
Имитационное мо... 58319
Реклама
Сейчас на сайте
Гостей: 11
На сайте нет зарегистрированных пользователей

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

База данных - рабочее место кассира на Delphi + бд Access
Меры близости на векторах в Delphi + Блок схемы
Создание последовательности окон и передвижение окон по экрану на Turbo ...

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Поиск в упорядоченных массивах
Под упорядоченными в дальнейшем будут пониматься неубывающие массивы, если не оговорено иное. То есть, a[1] <= a[2] <= … <= a[N].
Сначала приведем пример реализации широко известного алгоритма двоичного (бинарного) поиска элемента, равного K, в уже упорядоченном массиве. Оказывается, досрочный выход из цикла в случае нахождения элемента выигрыша по скорости практически не дает, а лишние проверки делают программу более громоздкой. Поэтому рекомендуется производить поиск, пока диапазон рассматриваемых элементов состоит более, чем из одного элемента.
L:=1; R:=N+1;
while L begin
m:=(L+R)div 2;
if a[m] else R:=m
end;
if a[m]=K then write(m) else write(0)



На полуфинале чемпионата мира по программированию среди студенческих команд вузов, проходившем в г.Санкт-Петербург в 2000 году предлагалась следующая обратная двоичному поиску задача (см. сайт neerc.ifmo.ru на котором можно найти тесты и ответы к ним для указанной задачи). Известно, что алгоритм бинарного поиска, аналогичный приведенному выше, но заканчивающий свою работу в случае досрочного обнаружения элемента, за Q сравнений определил, что искомым является элемент с номером I. Какова могла быть при этом размерность массива (указать все допустимые диапазоны значений N). Несмотря на кажущуюся сложность, при заданных в условии ограничениях задача решалась путем простого перебора различных значений N и обращения с каждым из этих значений к функции бинарного поиска. Конструктивный же подход к решению задачи намного сложнее. Однако и в случае подбора можно использовать немало интересных фактов. Например, длина каждого из диапазонов возможных значений N, является степенью двойки, а каждый следующий диапазон не меньше предыдущего. Это позволяет значительно сократить количество рассматриваемых значений N. Кроме того, максимальное допустимое значение для N легко найти аналитически.
Рассмотрим теперь задачу поиска в упорядоченном массиве наибольшего "равнинного" участка. То есть, требуется найти такое число p, что в массиве имеется последовательность из p равных элементов и нет последовательности из p + 1 равных по значению элементов. Оказывается, существует алгоритм решения этой задачи, количество операций в котором может оказаться существенно меньше, чем N. Так, если мы уже нашли последовательность из p1 равных между собой чисел, то другую последовательность имеет смысл теперь рассматривать только если ее длина не менее p1 + 1. Поэтому, если a[i] — первый элемент предполагаемой новой подпоследовательности, то сравнивать его надо сразу с элементом a[i+p], где p — максимальная величина для уже рассмотренных подпоследовательностей из равных элементов. Приведем фрагмент программы, решающий данную задачу. В качестве результата мы получаем длину максимальной подпоследовательности p, номер элемента, с которого эта подпоследовательность начинается, k и значение элементов в найденной подпоследовательности:
p:=1; k:=1;
i:=1; f:=false;
while i+p<=N do
if a[i+p]=a[i] then
begin
p:=p+1; f:=true
end
else if f then
begin
k:=i; i:=i+p; f:=false
end
else i:=i+1;
writeln(p,’ ’,k, ’ ’,a[k])



В [7] можно найти еще одну интересную задачу под названием “жулик на пособии” поиска в упорядоченных последовательностях уже практически какой угодно длины. Пусть имеются три упорядоченных по алфавиту списка из фамилий людей, получающий пособие по безработице в трех различных местах. Длина каждого из списков может быть как угодно большой (каждый из списков можно хранить в отдельном файле). Известно, что по крайней мере одно лицо фигурирует во всех трех списках. Требуется написать программу поиска такого лица, порядок количества операций в которой не будет больше, чем сумма длин всех трех списков. Приведем фрагмент программы, работающий с тремя файлами, обращение к элементам которых (они могут быть любого типа, в том числе и string, к элементам которого в Паскале применимы операции сравнения, чтения и записи) из программы происходит с помощью файловых переменных x, y, z типа text:
readln(x,p); readln(y,q); readln(z,r);
while not((p=q)and(q=r)) do
begin
if p else if q else if r

end;
writeln(p);{p=q=r}



Покажите, что для поставленной задачи чтение из файла всегда будет производиться корректно и на каждом шаге цикла значение одной из трех переменных p, q, r будет изменено. Кроме того докажите, что с помощью этой программы всегда будет найден именно минимальный из элементов, присутствующих во всех трех файлах.
Наконец, рассмотрим задачу поиска элемента, значение которого равно K, в двухмерном массиве, упорядоченном по строкам и столбцам: a[i,j] <=a [i,j+1], a[i,j] <= a[i+1,j], 1 <= i < N, 1 <= j < M. Данная задача решается за M + N действий, а не за M*N, как в произвольном массиве. Поиск следует начинать с элемента a[N,1]. Этот элемент самый маленький в своей строке и самый большой в своем столбце (в математике подобные элементы называют “седловыми точками”). Поэтому, если он окажется меньше, чем K, то из рассмотрения первый столбец можно исключить, а если больше — из рассмотрения исключается последняя строка и т. д. Вот возможная реализация этого алгоритма:
i:=N; j:=1;
while (i>0)and(jK) do
if a[i,j] else i:=i-1;
if (i>0)and(j


Программа могла бы быть еще короче и эффективней, если бы в ней использовался упоминавшийся выше барьерный метод. В данном случае для организации барьера требуется дополнить массив нулевой строкой и m+1-м столбцом. Во все созданные барьерные элементы следует поместить значение K. Тогда условие в цикле можно сократить до следующего: a[i,j]<>K.




Опубликовал Kest February 25 2010 22:31:20 · 0 Комментариев · 8607 Прочтений · Для печати

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


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



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

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

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

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

Пароль



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

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

Случайные загрузки
Battle.Net - мони...
RAS
PHP в примерах
Delphi World 6.0
Apollovcl61
Bitmap [для кнопок]
HTMLredaktor
Report
3D Октаэдр
Задача о 8ми ладьях
Preview
Электронный магаз...
39 статьи по Delphi
С. Г. Горнаков - ...
Socoban
PHP: Полезные приемы
TmxOutlookBarPro
Измерение тактово...
Программирование ...
Экспорт базы данн...

Топ загрузок
Приложение Клие... 100477
Delphi 7 Enterp... 87853
Converter AMR<-... 20082
GPSS World Stud... 13477
Borland C++Buil... 12053
Borland Delphi ... 8667
Turbo Pascal fo... 7048
Visual Studio 2... 5005
Калькулятор [Ис... 4906
FreeSMS v1.3.1 3545
Случайные статьи
Программа сертифик...
Как работать с абз...
Блок TEST
Группа блоков изме...
Многофункциональны...
Фильтрация таблиц ...
Прозрачные команды...
Технология маркиро...
Схемы, определяющи...
Если вы применяете...
Процедура обращени...
Работа с объектом ...
службы, связанную ...
Убедитесь, что в п...
Использование комп...
Операторы is и as
Средства системы O...
Произвольные фигуры
СТАНДАРТНЫЕ ЧИСЛОВ...
Если импульсный от...
Анализ посещаемост...
Продолжение
Константы основных...
Хакинг приставок X...
OpenGL. Шесть куби...
Статистика



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


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