金山笔试题：九环问题，挺有趣的题，高手们都来试试看呗！！

Question

九环问题
有九个环，每个环有“上”、“下”两种状态，记为：“∧”和“∨”。开始时九个环均为“上”态，即：∧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环的状态。现需要将九个均为“上”态的环，改为九个均为“下”态，问至少需要多少步操作（在条件许可下改变任何一个环的状态称为一步）？（请编程实现，给出代码）

Answer 1

假设我们要改变第i个环的状态（∧i -> ∨i或者∨i ->∧i），则必须满足 ∧i-1∨i-2...∨1 。
即只有第i-1环为上态，其他在它前面的环（1->i-2）均为下态，才能够改变i环的状态。
现需要将九个均为“上”态的环，改为九个均为“下”态
改变第一个环的条件都不满足，怎么改？

Answer 2

//数组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);
        }
        //右边大于等于2位
        else{
            //右边的1位如果不为false（“∧”）,即要求变换
            if(circle[index-1]!=false)change(index-1);
            //右边的第2位起，若不为true（“∨”），即要求变换
            while(index-2>=0){
                if(circle[index-2]!=true)
                    change(index-2);
                index--;
            }
        }
    }    /**
     * ture、false倒置
     * @param index 被倒置的数组位置
     */
    static void inverse(int index){
        if(circle[index]==true)
            circle[index]=false;
        else
            circle[index]=true;
    }
}
运行结果为97

Answer 3

代码不是我写的，我只是把别人C语言改成java罢了...LZ有兴趣可以好好研究下，另外这个也不是最省的，因为实在没办法去考虑1环到底要不要挂上去的难题了（比如你下3环，一环就不用挂回，但是下4环，1环必须先挂回才能下2环~~）public class test1{
private static  int upstep = 0;
private static int downstep = 0;
public static void DownRing(int n)     /*下环的逻辑就体现在这里*/
{
    if(n>2) DownRing(n-2);
    downstep++;
    if(n>2) UpRing(n-2);
    if(n>1) DownRing(n-1);
} public static void UpRing(int n)         /*上环的逻辑则体现在这里*/
{
    if(n>1) UpRing(n-1);
    if(n>2) DownRing(n-2);
    upstep++;
    if(n>2) UpRing(n-2);
}

    public static void main(String[] args) {
     DownRing(9);
     System.err.println(upstep+downstep);
}
}

Answer 4

写了个测试，不知道是否正确
import java.util.*;
class Huan {
    int state = 0;    public Huan() {
        state = 0;
    }    public String toString() {
        return String.format("%d", state);
    }
    
    public static void main(String[] args) {
        Huan[] h = new Huan[9];
        for (int i=0; i<9; i++) {
            h[i] = new Huan();
        }        int step = 0;
        for (int i=8; i>=0; i--) {
            step += change(h, i);
        }        System.out.println(step);
    }    public static int change(Huan[] h, int n) {
        int step = 0;
        if (n == 0) {
            step++;
            h[n].state = (h[n].state+1)%2;
            System.out.println(Arrays.toString(h));
            return step;
        } else if (n == 1) {
            if (h[n-1].state != 0) {
                step++;
                h[n-1].state = (h[n-1].state+1)%2;
                System.out.println(Arrays.toString(h));
            }
            step++;
            h[n].state = (h[n].state+1)%2;
            System.out.println(Arrays.toString(h));
            return step;
        }        if (h[n-1].state != 0) {
            step += change(h, n-1);
        }        for (int i=n-2; i>=0; i--) {
            if (h[i].state == 0) {
               step += change(h, i);
            }
        }
        
        step++;
        h[n].state = (h[n].state+1)%2;
        
        System.out.println(Arrays.toString(h));        return step;
    }
}

Answer 5

我用最笨的方法public class Test10 { static int pc = 0;

public static void main(String[] args) {
int[] test = new int [10];
final Integer start = new Integer(0);
test[0] = start;
for(int i = 1; i < test.length;i++) {
test[i] = 1;
}
move(test,1);
System.out.println(pc); }

public static int m(int[] a,int i) {
int r = 0;
for(int j = i-2;j>=0 ;j--){
r = r | a[j];
}
return r;
}

public static void move(int[] a,int i) {
if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0&&a[7]==0&&a[8]==0&&a[9]==0) {
return;
}
else if(i==1) {//i=1改变自己，向前移动
a[i] = set(a[i]);
table(a);
pc++;
move(a,++i);
}
else if(a[i]==1&&a[i-1]==0) {//前面都向下，自己为上，继续移动
move(a,++i);
}
else if(a[i]==1&&a[i-1]==1&&m(a,i)==0) {//正常判断
a[i] = set(a[i]);
table(a);
pc++;
move(a,1);
}
else if(a[i]==0&&a[i-1]==1&&m(a,i)==0) {
a[i] = set(a[i]);
table(a);
pc++;
move(a,1);
}
else if(a[i]==0&&m(a,i)==0) {//自己和后面都是下，继续移动
move(a,++i);
}
}
public static int set(int a) {
if(a==0) {
a = 1;
}
else {
a = 0;
}
return a;
}
public static void table(int[] a) {
for(int i = 1; i < a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}

Answer 6

我推导了一下，结果就为f(n) = 2^（n-1） + 2^(n - 3) + ……+2^(1) + 1
结果为341