Знакомство с Ханойской башней
Недавно я изучал структуры данных и алгоритмы и столкнулся с очень интересной проблемой — проблемой Ханойской башни.
Давайте посмотрим, как энциклопедия Baidu определяет правила Ханойской башни:
Ханойская башня (также известная как Ханойская башня) — развивающая игрушка, возникшая из древней индийской легенды. Когда Брахма сотворил мир, он сделал три алмазных столба, на которых по порядку снизу вверх были уложены 64 золотых диска. Брахма приказал брамину переставить диск на другой столб в порядке размера, начиная снизу. И оговорено, что диск нельзя увеличить на маленьком диске, а перемещать между тремя колонками можно только один диск за раз.
Ну, это кажется немного затянутым. На самом деле, одним словом, переместите тарелку между тремя столбцами, только по одной за раз, и убедитесь, что тарелка наверху каждой ступени меньше, чем тарелка внизу, и, наконец, переместите все тарелки из крайнего левого столбца. до самой .на правой стойке.
Я нашел небольшую игру, в которую я могу играть и наблюдать за процессом. Поверьте мне, вы не можете пройти уровень 5! Эй, если вы не можете играть в нее, приходите и посмотрите, как я сделал руководство по игре (читерство) для вас.
адрес:Woohoo.4399.com/flash/10950…
Я полагаю, что многие дети столкнутся с этой проблемой, когда будут изучать рекурсию. Не волнуйтесь, вы не одиноки. Когда я впервые увидел это, я был ошарашен. Что, черт возьми, это такое? Это так сложно. Ниже я продемонстрирую весь процесс перемещения схематично, чтобы помочь вам понять идею использования рекурсии для решения этой проблемы.
Иллюстрация Ханойской башни
Идем от простого к сложному шаг за шагом. Для удобства я называю три столбца A, B и C слева направо. Количество пластин увеличивается сверху вниз.
тарелка
Когда есть только одна тарелка, это проще. Как показано на рисунке, для полного перемещения первой пластины из точки А в точку С требуется всего один шаг.
две тарелки
Когда есть две пластины, это относительно просто, как показано на рисунке ниже, нужно только использовать столбец B для завершения.
Этот процесс может быть выражен как:
把第1个盘子从A移到B
把第2个盘子从A移到C
把第1个盘子从B移到Cтри тарелки
Когда есть три тарелки, это немного сложнее, но мы обычно можем вывести процесс с помощью арифметики в уме.
把第1个盘子从A移到C
把第2个盘子从A移到B
把第1个盘子从C移到B
把第3个盘子从A移到C
把第1个盘子从B移到A
把第2个盘子从B移到C
把第1个盘子从A移到Cп тарелки
Dangdangdang, сейчас четвертый уровень, я полагаю, что некоторые из моих друзей начали чувствовать себя уставшими, и это будет трудно сделать расчетным путем. Если вы не можете понять это, мы используем компьютер, чтобы помочь нам понять процесс (ха-ха, я очень остроумный).
Фактически, из предыдущих трех примеров мы можем обнаружить, что движение плиты является регулярным.
Внимательно, заметили ли вы, что в процессе перемещения тарелки на каждом шагу всегда есть шаг, которым является самая большая тарелка внизу, двигающаяся от А к С. Например, две тарелки означают, что вторая тарелка перемещается из A в C, а три тарелки — третья тарелка перемещается из A в C.
Внимательно наблюдайте, возьмите в качестве примера три плиты, переместите третью плиту из А в С. На самом деле первая и вторая плиты поставлены по порядку, то есть В посередине.
Следовательно, мы можем абстрагироваться от этого действия и рассматривать все, кроме нижней пластины, как единое целое. При этом весь процесс ничем не отличается от процесса перемещения двух пластин. Всего есть три шага, и я использую четыре пластины в качестве примера. Посмотрите анимацию ниже,
Весь процесс можно выразить так:
把1,2,3盘子整体从 A 移到 B （可以认为是借助 C 柱子移动的），
把第 4 个盘子从 A 移到 C（不需要借助额外的柱子），
把1,2,3盘子整体从 B 移到 C（借助 A 柱子）Однако это всего лишь процесс абстрагирования, игра не позволяет нам двигаться как единое целое, что нам делать?
Ну, я разделил все на 1, 2 и 3. Разве это не просто процесс движения трех тарелок. Видно, что 1 и 2 двигаются вместе как единое целое, а 3 ходят по отдельности, что также завершается в три приема. Затем разделите снова, пока не останется только одна последняя тарелка, и весь процесс будет завершен.
Следовательно, можно видеть, что этот процесс расщепления является процессом непрерывной рекурсии. И каждый раз, когда вы рекурсируете, вы можете обрабатывать 1-ю пластину до n-1-й пластины целиком. Каждая рекурсия представляет собой трехэтапное перемещение от текущего столбца к целевому столбцу с помощью другого столбца. посмотри на код,
public class HanioTest {
public static void main(String[] args) {
int n = 4;
char a = 'A',b = 'B',c = 'C';
hanio(n,a,b,c);
}
/**
*
* @param n 一共需要移动的盘子
* @param a 盘子移动的起始柱子
* @param b 借助的柱子
* @param c 盘子需要移动到的目标柱子
*/
public static void hanio(int n,char a, char b, char c){
//只有一个盘子的时候，就直接从A移到C
if(n == 1){
move(n,a,c);
}else{
//三步曲，注意观察，a,b,c三个的位置变化
//1.把 n-1 个盘子看成一个整体，借助 C 从 A 移动到 B
hanio(n-1,a,c,b);
//2.把第 n 个盘子从 A 移动到 C
move(n,a,c);
//3.再把 n-1 盘子整体，借助 A 从 B 移动到 C
hanio(n-1,b,a,c);
}
}
public static void move(int n , char a, char b){
System.out.println("把第"+ n +"个盘子从"+ a +"移到"+ b);
}
}Вы сообразительны, если четвертый уровень игры пройден, вы можете использовать его, чтобы проверить, соответствует ли процесс выполнения кода вашему процессу перемещения.
Пятый уровень, если вы сможете сообразить в голове без помощи программы, я могу только сказать, что вы слишком сильны.
Так что насчет шестого и седьмого уровней?
Эпилог
Возвращаясь к началу, Baidu Baike сказал переместить 64 золотых диска, OMG, если кто-то может понять это вручную, то это настоящий бог (но, другими словами, кто будет таким скучным, ха-ха).
Если вам интересно, вы также можете попробовать использовать программу для запуска планшетов 64. Я полагаю, что даже если ваша машина имеет хорошую производительность, она будет работать долго. . .
Напоминание: не вините меня, если машина взорвется~
Если эта статья была вам полезна, ставьте лайк, комментируйте и пересылайте.
Учиться скучно и весело. Меня зовут Yanyu Xingxing, добро пожаловать, вы можете получать сообщения о статьях как можно скорее.