Навигация
Главная
Поиск
Форум
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
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
21 ошибка прогр... 64876
Реклама
Сейчас на сайте
Гостей: 1
На сайте нет зарегистрированных пользователей

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

Моделирование работы класса персональных компьютеров на GPSS + Отчет + Б...
Создание последовательности окон и передвижение окон по экрану на Turbo ...
Метод конечных разностей для интерполяции/экстраполяции на Delphi

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Обратные сортировке задачи
Пусть задана конкретная реализация алгоритма сортировки и значение N. Требуется восстановить некоторые его характеристики. Подобная задача предлагалась на открытой командной олимпиаде по программированию в Санкт-Петербурге в 1996 году.

Ниже приведен алгоритм MSort, который сортирует слиянием заданный массив A из N целых чисел.
Требуется написать программу, которая для заданного N строит пример массива A, на котором достигается максимальное число сравнений. Все элементы массива A должны быть различными и находиться в диапазоне от 1 до N.
Обратные сортировке задачи
procedure MSort (N: integer; var A: list);
var Help: list;
procedure Make (u, v: integer);
var i, j, m, k: integer;
begin
if u < v then
begin
m := (u+v) div 2;
Make (u, m);
Make (m+1, v);
i := u; j := m+1; k := u;
while (i<=m) and (j<=v) do
begin
if A [i] < A [j] then begin Help[k] := A[i]; i := i+1 end
else begin Help[k] := A[j]; j := j+1 end;
k := k+1
end;
while i<=m do begin Help[k] := A[i]; i:=i+1; k:=k+1 end;
while j<=v do begin Help[k] := A[j]; j:=j+1; k:=k+1 end;
for i := u to v do A[i] := Help[i]
end
end
begin {MSort}
Make (1, N)
end;



Приведем рекурсивную процедуру, решающую эту задачу:
procedure Fill (var A: list; u, v: integer; start, step: integer);
begin
if u = v then A [u] := start
else begin
Fill (A, u, (u+v) div 2, start, step*2);
Fill (A, (u+v) div 2 + 1, v, start + step, step*2)
end
end;



Массив А будет заполнен в результате следующего обращения к такой процедуре: Fill(A, 1, N, 1, 1). Кроме того, можно потребовать определить количество сравнений, выполняемых алгоритмом в худшем случае, причем в такой задаче ограничения на величину N уже практически отсутствуют, поэтому решить ее путем подстановки заполненного массива A в исходную процедуру сортировки и включения в нее счетчика сравнений невозможно. Попробуйте написать программу, подсчитывающую количество сравнений, выполняемых приведенной выше процедурой сортировки массива слиянием, по введенному значению N. Саму процедуру сортировки, а также рекурсию, в программе использовать не нужно. Подобные задачи можно поставить и для других алгоритмов сортировки. Постройте пример массива, на котором стандартная процедура QuickSort будет выполнять максимальное количество сравнений. Эта задача имеет и практическое значение. По построенным для различных значений N примерам можно понять для каких именно массивов быстрая сортировка не является эффективной и действительно ли в этом случае количество сравнений имеет порядок O(N2).
Литература
1. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
2. Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989.
3. Окулов С.М. Основы программирования. “Информатика”, №23, 2001.
4. Окулов С.M. Сортировка и поиск. “Информатика”, №33, 35, 2000.
5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
6. Кнут Д. Искусство программирования. Том 3: Поиск и сортировка. М.: “Вильямс”, 2000.
7. Окулов С.М., Шулятников Д.С. Разбор задач международной олимпиады 2000 года. “Информатика”, №12, 2001.
8. Хачиян Л.Г. Проблемы оптимальных алгоритмов в выпуклом программировании, декомпозиции и сортировке. В кн.: Компьютер и задачи выбора. M.: Наука, 1989.
9. Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.




Опубликовал Kest Март 03 2010 11:28:44 · 0 Комментариев · 6521 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Berg
netBIOS
Разработка распре...
Работа с базами д...
Task Shedule
Популярные загрузки
Шифрование по алг...
Алгоритм трассиро...
Создание оригинал...
Работа с картотеками
С. Г. Горнаков - ...
Таймер и секундомер
PHP 5 в подлинник...
TelBook
DS_Group
THttpScan v4.1
Андрей Боровский....
Pro-Download Sys...
Run
MPTools

Топ загрузок
Приложение Клие... 100620
Delphi 7 Enterp... 94322
Converter AMR<-... 20149
GPSS World Stud... 16288
Borland C++Buil... 13575
Borland Delphi ... 9559
Turbo Pascal fo... 7177
Калькулятор [Ис... 5398
Visual Studio 2... 5075
FreeSMS v1.3.1 3592
Случайные статьи
PowerShell для Вин...
Pointer expression...
Порталы для электр...
Cannot evaluate th...
Межмодульное взаим...
Идентификация объе...
Процедуры ShowMess...
В каких поисковика...
Состав нового меню...
5.1. Принципы
15.5. Задачи
Программирование п...
Строки в стиле язы...
Составной оператор
Зачем нужен цифров...
Типы блогов по наз...
DTABLE (РАЗНОСТНАЯ...
Игры. Игровые авто...
Request Information
Программа сертифик...
Google и тематика ...
Зарегистрируйте из...
Выкуп авто
Частоты, использую...
Нерешенные вопросы
Статистика



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


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