欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 汉诺塔Hanoi递归、非递归(仿系统递归)和非递归规律 实现代码

程序员文章站 2023-12-17 08:35:04
程序如下:复制代码 代码如下:view code  /*  * hanoi塔游戏 问题描述:  * 汉诺塔:汉诺塔(又称河内塔)问题是源于印度...
程序如下:
复制代码 代码如下:

view code
 /*
  * hanoi塔游戏 问题描述:
  * 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。
  * 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照
  * 大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小
  * 顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在
  * 三根柱子之间一次只能移动一个圆盘。
  *
  * fuction:实现 hanoi塔
  *             1.递归实现
  *             2.非递归实现
  * author:igeneral
  * date:2013.04.26
  *
  * expe:
  *         1.注意:塔的状态:当status=1时,表示可以直接将该disk移动到目标塔
  *                 而不是用disk的id来判断输出
  *         2.system.out.println();
           system.out.println((int)3.3%3);
           没有(int)时,输出:0.299999
           加上(int)后,输出:0
  */
 package part03.chapter10;

 import java.util.scanner;

 public class _2exercise {

     public static void main(string[] args) {

         scanner scanner = new scanner(system.in);
         system.out.println("请输入hanoi碟子的数量:");
         int disknum = scanner.nextint();
         hanoi hanoi = new hanoi();
         system.out.println("递归实现:");
         hanoi.play_recursive(disknum, 'a', 'b', 'c');
         system.out.println("非递归实现(模仿递归思想):");
         hanoi.play_non_recursive(disknum);
         system.out.println("非递归实现(根据hanoi规律):");
         hanoi.play_regular(disknum);

     }

 }

 class hanoi {

     // 递归实现
     public void play_recursive(int num, char a, char b, char c) {
         if (num == 1) {
             system.out.println(a + " -> " + c);
             return;
         } else {
             play_recursive(num - 1, a, c, b);
             system.out.println(a + " -> " + c);
             play_recursive(num - 1, b, a, c);
         }

     }

     // 非递归实现:模仿递归思想
     public void play_non_recursive(int disknum) {
         stack stack = new stack();
         stack.push(new disk(disknum, 'a', 'b', 'c'));
         disk popdisk = null;
         while ((popdisk = stack.pop()) != null) {
             if (popdisk.status == 1) {
                 system.out.println(popdisk.a + " -> " + popdisk.c);
             } else {
                 // 反顺序添加
                 // 将执行移动 popdisk 的下一步的disk添加到stack
                 stack.push(new disk(popdisk.status - 1, popdisk.b, popdisk.a,
                         popdisk.c));
                 // 将一个status为 "1" 且移动顺序与 popdisk 相同的disk 添加到stack中
                 stack.push(new disk(1, popdisk.a, popdisk.b, popdisk.c));
                 // 将执行移动 popdisk 的前一步的disk添加到stack中
                 stack.push(new disk(popdisk.status - 1, popdisk.a, popdisk.c,
                         popdisk.b));
             }
         }
     }

     // 非递归实现:根据hanoi规律
     public void play_regular(int disknum) {

         // 根据规律,需要根据 disk 的个数,多塔的位置进行调整
         // 塔的个数为偶数时,将三个塔按“a->b->c”的顺序排列成三角形
         // 塔的个数为奇数时,将三个塔按"a->c->b"的顺序排列成三角形
         // 将disknum个disk按”上小下大“的顺序放在a塔中(堆栈实现),同时将b塔和c塔置空
         stack_play_regular a = new stack_play_regular('a');
         stack_play_regular b = new stack_play_regular('b');
         stack_play_regular c = new stack_play_regular('c');
         for (int i = disknum; i > 0; i--) {
             a.push(i);
         }
         // 将三个塔模拟成三角形形状排列
         stack_play_regular[] towers = new stack_play_regular[3];
         towers[0] = a;
         if (disknum % 2 == 0) {
             towers[1] = b;
             towers[2] = c;
         } else {
             towers[1] = c;
             towers[2] = b;
         }
         // 最小dish所在的塔,通过该塔在towers中的
         int towerofminimundisk = 0;
         // 根据证明:n个disk移动完成至少需要2^n-1次
         // 不断交替进行以下两步
         // 将最小的disk按以上塔的顺序下移到下一个塔
         // 对除了最小disk所在的塔的另外两个塔进行操作,可能出现两种情况
         // 情况一:一个塔中没有disk,此时将存在disk的塔最上面的disk移动到没disk的塔上
         // 情况二:两个塔都有disk,此时对他们最上面的塔进行比较,将较小的disk移动到较大的disk上
         // 不会存在两个塔都没有disk的情况,除非移动已经完成或未开始或只有一个盘子时的移动
         int ii = 0;
         for (int i = 0; i < (math.pow(2, disknum) - 1);) {// --------------注意在此处不进行i++
             // 取出三个塔,使代码更清晰
             stack_play_regular tower = towers[towerofminimundisk];
             stack_play_regular tower_1 = towers[(int) ((towerofminimundisk + 1) % 3)];
             stack_play_regular tower_2 = towers[(int) ((towerofminimundisk + 2) % 3)];
             // 移动最小的盘子
             system.out.println(tower.name + " -> " + tower_1.name);
             tower_1.push(tower.pop());
             i++;// --------------注意在此处进行i++
             towerofminimundisk = (int) ((towerofminimundisk + 1) % 3);
             // ------------注意此时对三个tower进行重新赋值
             tower = towers[towerofminimundisk];
             tower_1 = towers[(int) ((towerofminimundisk + 1) % 3)];
             tower_2 = towers[(int) ((towerofminimundisk + 2) % 3)];
             // 对另外两个塔进行处理
             if ((tower_2.gettop() != -1 && (tower_1.showtopdisk() > tower_2
                     .showtopdisk()))
             // --------------注意要再加上 tower_2.gettop() != -1
             // 进行判断,否则可能数组访问越界
                     || (tower_1.gettop() == -1 && tower_2.gettop() != -1)) {
                 system.out.println(tower_2.name + " -> " + tower_1.name);
                 tower_1.push(tower_2.pop());
                 i++;// --------------注意在此处进行i++
             } else if (((tower_1.gettop() != -1 && tower_1.showtopdisk() < tower_2
                     .showtopdisk()))
             // --------------注意要再加上 tower_1.gettop() != -1
             // 进行判断,否则可能数组访问越界
                     || (tower_1.gettop() != -1 && tower_2.gettop() == -1)) {
                 system.out.println(tower_1.name + " -> " + tower_2.name);
                 tower_2.push(tower_1.pop());
                 i++;// --------------注意在此处进行i++
             }
             ii = i;
         }
         system.out.println(ii);
     }

 }

 // 存放信息的结构体
 class disk {
     // 从a塔通过b塔移动到c塔
     char a;
     char b;
     char c;
     // 塔的状态:当status=1时,表示可以直接将该disk移动到目标塔
     int status;

     // 重写构造函数
     public disk(int status, char a, char b, char c) {
         this.status = status;
         this.a = a;
         this.b = b;
         this.c = c;
     }
 }

 // 存放disk的栈
 class stack {
     // 用来存储盘子的数组
     disk[] disks = new disk[10000];
     // 塔顶
     private int top = 0;

     // 查看栈顶
     public disk stacktop() {
         return disks[top];
     }

     // 出栈
     public disk pop() {
         if (top != 0) {
             top--;
             return disks[top + 1];
         } else {
             return null;
         }
     }

     // 入栈
     public void push(disk disk) {
         top++;
         disks[top] = disk;
     }
 }

 // 为 play_regular(int disknum) 创建的 stack 类
 // 以 diskid 来表示 disk 对象
 class stack_play_regular {
     // 塔名
     char name;
     // 塔顶
     private int top = -1;

     public int gettop() {
         return top;
     }

     // 通过数组实现stack,最多64个disk
     int[] stack = new int[64];

     // 重写构造函数,初始化塔的名字name
     public stack_play_regular(char name) {
         this.name = name;
     }

     // 查看栈顶
     public int showtopdisk() {
         if (top == -1) {
             return -1;
         }
         return stack[top];
     }

     // 入栈
     public void push(int diskid) {
         stack[++top] = diskid;
     }

     // 出栈
     public int pop() {
         return stack[top--];
     }
 }

上一篇:

下一篇: