模拟"九连环"的小算法

首页发现

博客园 - ScorpioLove

一个小题目 [面试]内存泄漏查找位置 1000 的阶乘有几位数? - 后续, 求解终于又能登录了 [转] vim 中关于 tab 的使用技巧 ASCII Table 排列组合 1000 的阶乘有几位数? 总结一下最近做得事 Debian 下安装 Java 开发环境 Debian etch 下安装配置支持 CJK 的 tex 系统行频、场频与分辨率、刷新率一些 Java 语言的基础细节 Some good articles for me Vim 命令 Big Integer Multiplication [转]Debian/Ubuntu下tetex3的gbk字体配置方法 - giv@kyxk.net [转]FVWM的配置文件 - archerC@kyxk.net I do

模拟"九连环"的小算法

ScorpioLove · 2006-10-27 · via 博客园 - ScorpioLove

前几天无聊, 舍友拿来一玩具"九连环". 把玩之中, 觉得过程类似"汉诺塔", 遂考虑写个程序模拟一下.

其实过程挺简单的, 关键在于, "九连环"中除了第一个环, 其它所有的环都套着它前面的环, 因此, 要操作第 n 个环 (安装或者拆卸), 则第 n-1 个环必须在上面, 而第 n-2 个之前的所有环都不能在上面.

两个关键函数:
1. 装上所有的环:
Fill(int rings) {
    // 两个基本情况
    if rings == 1 then
        把第一个装上;
    endif

    if rings == 2 then
        把第一个装上;
        把第二个装上;
    endif

    // 第

rings-1 个要在上面, 第 rings-2 个之前的都不能在上面
把前 rings-1 个都装上; // 调用 Fill(rings-1)
把前 rings-2 个都卸下; // 调用 Clean(rings-2)

把第

rings 个装上;

把前

rings-2 个都装上; // 调用 Fill(rings-2)
}

卸下所有的环:
Clean(int rings) {
    // 两个基本情况
    if rings == 1 then
        把第一个卸下;
    endif

if rings == 2 then

        把第二个卸下;
        把第一个卸下;
    endif

    // 第 rings-1 个要在上面, 第 rings-2 个之前的都不能在上面
    把前 rings-2 个都卸下; // 调用 Clean(rings-2)

把第

rings 个卸下;

// 卸掉第 rings-1 个, 需要将前 rings-2 个都在装上
把前

rings-2 个都装上; // 调用 Fill(rings-2)
把前 rings-1 个都卸下; // 调用 Clean(rings-1)
}

Java 语言版本的具体实现如下:

import java.io.*;
import java.util.*;public class NineRingsNew {private Vector<Integer> rings;

    private void fill(int nRings) {
        if (nRings == 1) {
            rings.add(1);
            System.out.println("Put ON  Ring<1> ---> " + rings.toString());
            return;
        } else if (nRings == 2) {
            rings.add(1);
            System.out.println("Put ON  Ring<1> ---> " + rings.toString());
            rings.insertElementAt(2, rings.indexOf(1));
            System.out.println("Put ON  Ring<2> ---> " + rings.toString());
            return;
        }

fill(nRings - 1);

clean(nRings - 2);

rings.insertElementAt(nRings, rings.indexOf(nRings - 1));
System.out.println("Put ON Ring<" + nRings + "> ---> " + rings.toString());

fill(nRings - 2);
}

private void clean(int nRings) {
        if (nRings == 1) {
            rings.removeElement(1);
            System.out.println("Put OFF Ring<1> ---> " + rings.toString());
            return;
        } else if (nRings == 2) {
            rings.removeElement(2);
            System.out.println("Put OFF Ring<2> ---> " + rings.toString());
            rings.removeElement(1);
            System.out.println("Put OFF Ring<1> ---> " + rings.toString());
            return;
        }

clean(nRings - 2);

rings.removeElement(nRings);
System.out.println("Put OFF Ring<" + nRings + "> ---> " + rings.toString());

fill(nRings - 2);

clean(nRings - 1);
}

public void opRings(int nRings, boolean on_off) {
        rings = new Vector<Integer>(nRings);
        if (on_off) {
            System.out.println("The intial state of rings is : " + rings.toString());
            fill(nRings);
            System.out.println("Finished! The rings state is : " + rings.toString());
        } else {
            for (int i = rings.capacity(); i > 0; i--) {
                rings.add(i);
            }
            System.out.println("The intial state of rings is : " + rings.toString());
            clean(nRings);
            System.out.println("Finished! The rings state is : " + rings.toString());
        }
    }public static void main(String[] args) {
        NineRingsNew nrn = new NineRingsNew();

        System.out.println("\n" +
                "----------------------------------------------------------\n" +
                "---------------------   NINE RINGS   ---------------------\n" +
                "----------------------------------------------------------\n" +
                "   This program is to simulate a Chinese traditional \n" +
                "   intellectual toy called \"Jiu Lian Huan\". \n" +
                "   Please input two values:\n" +
                "      Num of Rings: an integer belongs in [1, 9];i\n" +
                "      Operation   : a String \"on\" or \"off\" indicates\n" +
                "                    whether you want to put all rings\n" +
                "                    ON or OFF (ignore case)\n" +
                "   Input \"q\" to quit.\n" +
                "----------------------------------------------------------");

Scanner sc =

new Scanner(System.in);
        int nRings = 1;
        String quit = "";boolean on_off = false;
        while (true) {
            System.out.print("How many rings to operation([1~9]): ");
            nRings = sc.nextInt();
            System.out.print("How to deal with them(put ON, OFF): ");
            on_off = sc.next().equalsIgnoreCase("ON");
            System.out.println();

nrn.opRings(nRings, on_off);

            System.out.println();
            System.out.print("Do you want to quit(q/y/n)? ");
            quit = sc.next();
            System.out.println("---------------------------------------------");

if (quit.equalsIgnoreCase("q") ||
                    quit.equalsIgnoreCase("quit") ||
                    quit.equalsIgnoreCase("y") ||
                    quit.equalsIgnoreCase("yes"))
                break;
        }

System.out.println("Thank you for using this program. Goodbye!\n"

);
}

}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - ScorpioLove