+7(967)234-82-75
Заказать звонок
+7(967)234-82-75
Заказать звонок

Алгоритм поиска кратчайшего пути Ханойской башни

Давно, года наверно где-то 4-5 лет назад в колледже преподаватель дал мне задание, написать программу, которая ищет кратчайший путь в Ханойской башни и в данной статье будет описан алгоритм нахождения шагов этой головоломки.

Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.



Так, давайте для начала разберемся, что такое алгоритм.
Алгоритм — это точный набор инструкций, описывающих порядок действий некоторого исполнителя для достижения результата. Более простыми словами — это набор запланированных действий/шагов исполнителя/человека для достижения результата.

Для решения нашей задачи будем использовать рекурсию. Рекурсия — это функция, которая вызывает саму себя.
И писать код я буду на JavaScript. Так как будем пользоваться рекурсией, то нам нужно создать функцию или метод, если в классе собрались писать это:

function hanoi() {
	// code
}

Так, мы создали функцию под названием hanoi, и теперь нам нужно будет передать ей данные, давайте подумаем.
Наша головоломка имеет 3 стержня и неизвестное кол-во дисков, и нам нужно это n-е кол-во дисков переместить из одного стержня в другое и для нам нужно будет передавать в функцию: кол-во дисков(n), откуда(p), куда(p2):

function hanoi(n, p, p2) {
	// code
}

Далее мы уже напишем тело функции:

function hanoi(n, p, p2) {
	if (n > 0) {
		hanoi(n-1, p, 6-p-p2);
		console.log(p + '-' +p2);
		hanoi(n-1, 6-p-p2, p2);
	}
}

Тут мы сначала проверяем кол-во дисков больше ли нуля "if (n > 0)"?, иначе не имеет смысла выполнять код, если все замечательно, то дальше же происходит рекурсию, вызываем саму себя, только уже немного с другими параметрами.
Давайте сначала определимся, мы будем перемещать диски из перового стержня во второй.
Во-первых, мы уменьшаем кол-во дисков, во-вторых, мы должны последний диск переместить во 2-ой стержень и для того, чтобы определить 2-й стержень, мы написали формулу "6-p-p2".

Прошу заметить, функцию в самой себя вызываем дважды, чтобы первый (самый малый) диск положить во второй стержень, а второй в третий стержень.

Для вывода результата воспользовался функцией console.log для вывода в консоль.
Надеюсь да где-нибудь вам понадобится этот алгоритм, всего хорошего!

А демо можете посмотреть по этой ссылке.

Просмотров 71
Автор Вусал Мамедов
Заказать звонок
*
*
Заказать звонок
В ближайшее время мы с Вами свяжемся!
Заказать
*
*
*
Отправить
Мы уже обрабатываем ваш заказ.
В ближайшее время мы с Вами свяжемся!
Спасибо
Информация отправлена, мы скоро свяжемся с вами!