То есть, если нам захочется странного, например записать решение ханойской башни для 64 дисков, то никаких современных носителей информации не хватит

Быстрая сортировка

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов); из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

 

 

 

 

Признак того, массив (часть массива) отсортирован (дальнейшее деление невозможно):

1) i > j;

2) j= start;

3) i = end.

Проект 7_4

 

 

 

Задача о ханойских башнях

 

Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу.

Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.

 

Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

За один раз можно переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

 

		Перекладывание стека из 3 дисков — это: 1. Перекладывание стека из 2 дисков на вспомогательную ось. 2. Перекладывание 3-го диска на нужную ось. 3. Перекладывание стека из 2 дисков на нужную ось.

 

 

Алгоритмическая сложность

Если мы перемещаем стек из одного диска — то нам нужно 1 действие.

Если стек из двух — то 1 * 2 (переместить дважды стек из одного диска ) + 1 (перемещаем последний диск)

Если из трех ((1 * 2) + 1) * 2 + 1

Из пяти: (((((1 * 2) + 1) * 2 + 1) * 2 + 1) * 2 + 1)

Итак, добавление одного диска увеличивает в 2 раза количество перемещений.

В итоге, количество перекладываний равно ,

Где n – число дисков.

То есть, если нам захочется странного, например записать решение ханойской башни для 64 дисков, то никаких современных носителей информации не хватит.

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

 

 

 

Записи