日期:2014-05-20  浏览次数:20731 次

金山笔试题:九环问题,挺有趣的题,高手们都来试试看呗!!
九环问题
有九个环,每个环有“上”、“下”两种状态,记为:“∧”和“∨”。开始时九个环均为“上”态,即:∧9∧8∧7∧6∧5∧4∧3∧2∧1。假设我们要改变第i个环的状态(∧i -> ∨i或者∨i ->∧i),则必须满足 ∧i-1∨i-2...∨1 。即只有第i-1环为上态,其他在它前面的环(1->i-2)均为下态,才能够改变i环的状态。现需要将九个均为“上”态的环,改为九个均为“下”态,问至少需要多少步操作(在条件许可下改变任何一个环的状态称为一步)?(请编程实现,给出代码)


------解决方案--------------------
//数组circle即为9个环,circle[8]为最左边的第九环,circle[0]为最右边的第一环
//true表示向下“∨”,false表示向上“∧”
/**
 *
 * @author afunx
 */
public class NineCircle {
    public static final int N = 9;
    static boolean circle[] = new boolean[N];
    static int count = 0;
    public static void main(String args[]){
        //8变化,使得circle[8]=true,即“∨”
        change(N-1);
        //7开始,先判断目前状态是否为true,即“∨”
        //若不符合,则逐个转换
        for(int k=N-2;k>=0;k--){
            if(circle[k]!=true)
                change(k);
        }
        System.out.println(count);
    }

    static void change(int index){
        //计数器加1
        count++;
        //右边有0位,直接变换
        if(index==0){
            inverse(index);
            return;
        }
        //右边仅有1位
        else if(index==1){
            //右边的1位如果不为false(“∧”),即要求变换
            if(circle[index-1]!=false)change(index-1);