Навигация
Главная
Поиск
Форум
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
Создание отчето... 63517
Модуль Forms 63358
ТЕХНОЛОГИИ ДОСТ... 60109
Пример работы с... 59162
Имитационное мо... 55570
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

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

Реклама



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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Exe in exe
Библия хакера 2 К...
Delphi. Готовые а...
Просмотр файлов и...
Доступа к БД Fire...
ADVstatusbar
Error mod
DFileDeleter
Page Promoter 7.7...
Добавление басса ...
WinPopup
Открытие Cd-ROM'a...
Мод "проверочный ...
Основы Delphi
Программирование ...
База англоязычных...
AID антивирус
Отключение и вклю...
Delphi 7: Для про...
Java в примерах -...

Топ загрузок
Приложение Клие... 100443
Delphi 7 Enterp... 85583
Converter AMR<-... 20065
GPSS World Stud... 12439
Borland C++Buil... 11512
Borland Delphi ... 8474
Turbo Pascal fo... 7020
Visual Studio 2... 4987
Калькулятор [Ис... 4722
FreeSMS v1.3.1 3533
Случайные статьи
Для постоянных при...
Виртуальное наслед...
Операция VOP_LOOKUP
Стандартные потоки
Другие типы вращен...
В этих двух пример...
Имитационное модел...
3. Драйвер IPSec п...
сервер DNS, один к...
Рабочий стол, меню...
СGІ-запрос
Конструкторы
Сообщения протокол...
Запрограммировать ...
Управляющие элемен...
Сообщения протокол...
Изоморфизм д.з.к. ...
Сжатие данных
Постоянно продолжа...
Современные телеко...
Лунтик аниматор
Взаимодействие Тур...
Настройте пакетные...
Средства системы O...
определив расширен...
Статистика



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


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