Бинарное слияние

← →
TRyaSS © (2004-10-09 20:33) [0]

Может у кого нить есть алгоритм бинарного слияния,бинарного поиска.Напишите плз.

← →
begin...end © (2004-10-09 20:39) [1]

Бинарное слияние - не в курсе я что-то, а бинарный поиск - это ж поиск делением пополам, так?

← →
Palladin © (2004-10-09 20:43) [2]

Да это так... а что есть бинарное слияние в воспаленном воображении автора вопроса никогда не учившегося в школе и имеющего незаконченное высшее оразование... одному ему и известно... хотя это может ему только кажется...

← →
Vit@ly © (2004-10-09 20:48) [3]

Palladin © (09.10.04 20:43) [2] ПРАВ
Заляни в http://delphimaster.net/view/1-1096054352/
Собирался закрыть ветку, да они вроде бы сами образумились

← →
TRyaSS © (2004-10-09 20:50) [4]

> хотя это может ему только кажется...

Ну если серьезно, то такой чушью нас мучают преподы из университета...и нас и без того "с воспаленным воображением" заставляют это реализовать в TP.

← →
begin...end © (2004-10-09 20:54) [5]

> TRyaSS

Код писать не буду, объясню идею на примере. Допустим, есть у тебя упорядоченный набор букв русского алфавита (массив). Требуется найти букву "Ж", например, т.е. определить её индекс в массиве. Поступают так: делят массив пополам, в левой половине оказываются буквы от "А" до "О", например; тогда в правой - от "П" до "Я". Очевидно, "Ж" находится в левой половине, поэтому отбрасываем правую и делим пополам левую. И так продолжаем, пока не найдём "Ж". Ещё этот метод используется, например, для нахождения корня функции на отрезке (т.е. значения аргумента, при котором функция обращается в нуль). Там тоже делят этот отрезок на две части и оставляют ту из половинок, на концах которой функция имеет разные знаки.
Материала по этой теме - туева хуча. Так что в Инете уж можно найти. Даже вместе с кодом.

> [4] TRyaSS © (09.10.04 20:50)

> такой чушью нас мучают преподы из университета

Ну ты даёшь... Нафига ты тогда в этот университет поступал?

> [3] Vit@ly © (09.10.04 20:48)

Туда перед сном лучше не заглядывать 8-)

← →
TRyaSS © (2004-10-09 21:00) [6]

В чем и дело мне нужен не бинарный поиск,а бинарное слияние.Смысл такой:
Два упорядоченных файла.Нужно из них сделать один упорядоченный с минимальным числом сравнений.

← →
Palladin © (2004-10-10 02:52) [7]

В общем случае, это невозможно.

← →
CDF (2004-10-10 03:27) [8]

Попробую угадать: бинарное сляние это алгоритм сортировки?

← →
Германн © (2004-10-10 03:35) [9]

Да чё тут угадывать! По [6] есть "два упорядоченных файла.Нужно из них сделать один упорядоченный с минимальным числом сравнений."
Ничего нельзя ответить в общем случае. Поскольку не известно "как именно упорядочнены исходные файлы и как должен быть упорядочен файл-результат".!

← →
TUser © (2004-10-10 07:16) [10]

> Попробую угадать: бинарное сляние это алгоритм сортировки?

КвикСорт? Но это на сличение как-то не тянет.

А файлы сливать можно гораздо проще - читаешь их последовательно, пока не дойдешь до конца каждого файла и выписываешь результат.

> TRyaSS © (09.10.04 20:33)

> Может у кого нить есть алгоритм бинарного слияния,бинарного поиска.

> [6] TRyaSS © (09.10.04 21:00)

> В чем и дело мне нужен не бинарный поиск,а бинарное слияние

Как быстро меняются задания в современных университетах...

> [10] TUser © (10.10.04 07:16)

> КвикСорт? Но это на сличение как-то не тянет.

Больше похоже, ИМХО, на внешнюю сортировку (сортировку файлов). Может быть, это прямое слияние? У Вирта это точно было описано...

MergeSort - сортировка слиянием. Там на каждом шаге два отсортированных массива "сливаются" в один тоже отсортированный. Догадываюсь, что с файлами именно это и надо сделать. Действия те же самые, что и с массивами, только надо оптимизировать доступ к файлу.

> Aldor © (10.10.04 10:01) [13]
> MergeSort - сортировка слиянием. Там на каждом шаге два
> отсортированных массива "сливаются" в один тоже отсортированный.

именно что нужно.Алгоритм где можно найти не подскажеш?

http://www.google.com/search?hl=ru&q=MergeSort&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA+%D0%B2+Google&lr=lang_ru

Бинарное слияние Найти похожие ветки