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

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

моделирование процесса поступления заявок в ЭВМ на GPSS + Пояснительная ...
Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Лабораторная работа по динамическим спискам на Turbo Pascal (удаление ду...

Реклама



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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Открытие Cd-ROM'a...
PDA версия сайта
Java в примерах -...
Расширенный загру...
Основы программир...
Pass [Исходник на...
Microsoft Press -...
WAP версия сайта
Zoom [Исходник на...
FreeSMS v1.3.1
Панель для реклам...
Assembler. Практикум
Srinilist
CoolControls v3.0...
SUIPack
EditNew
KOL & MCK v1.69
PHP 5 на примерах
Отключение и вклю...
Delphi 2005. Разр...

Топ загрузок
Приложение Клие... 100384
Delphi 7 Enterp... 83530
Converter AMR<-... 20051
GPSS World Stud... 11301
Borland C++Buil... 11234
Borland Delphi ... 8176
Turbo Pascal fo... 6987
Visual Studio 2... 4970
Калькулятор [Ис... 4416
FreeSMS v1.3.1 3516
Случайные статьи
Автоматическое р...
Обратная связь
• Для шифрования и...
Утверждения в сред...
Адресация по базе ...
Я запустил все три...
9. На все участвую...
Продолжительность ...
Слоты 777
16-Ю)
Работа с изображен...
Козырек для мытья ...
Изменение размеров...
Упражнение 2: адми...
Основное -- адеква...
Обычно файлы PostS...
Драйвер seg_vn
ЛОГИЧЕСКИЕ КЛЮЧИ В...
Добавление свободн...
Источник данных
Что такое резидент...
Apache + Perl + PH...
Режим воспроизведе...
где:/DB имя_файла ...
административных г...
Статистика



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


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