![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Многофазная сортировка.В основе данной сортировки лежит отказ от жесткого понятия прохода и разделения файлов на две категории. Рассмотрим этот метод сортировки на примере:
Таким образом, необходимо, чтобы числа начальных серий в двух входных последовательностях были двумя соседними числами Фибоначчи.
Подставляя
Такие числа называются числами Фибоначчи четвертого порядка. В общем случае числа Фибоначчи порядка р определяются следующим образом:
Заметим, что обычные числа Фибоначчи – числа первого порядка. Теперь уже ясно, что исходные числа серий для идеальной многофазной сортировки с N последовательностями (файлами) представляют собой последовательность чисел Фибоначчи порядка N – 2. Отсюда следует, что метод применим для лишь входов, сумма серий на которых есть сумма N – 1 таких чисел Фибоначчи. В том случае, когда сумма серий отличается от идеальной суммы, то вводим фиктивную серию.
|