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

金山笔试题：九环问题，挺有趣的题，高手们都来试试看呗！！
九环问题
有九个环，每个环有“上”、“下”两种状态，记为：“∧”和“∨”。开始时九个环均为“上”态，即：∧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);

}
//右边大于等于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
[解决办法]
第一眼看到问题我以为是九连环，进来看到问题发现不是，仔细看看问题发现真的是。。。。。
我了个去的现在公司怎么流行出这鸟鬼题目，百度去搜索九连环解法，就是一个递归

而且题目给的条件也不全，应该给的条件是1号环不受控制

方法就是下1 下3 上1 下2 下1 下5 上1 2 3 下2 下1 下4 上12 下1 下3 上1 下2 下1 下7......继续吧
[解决办法]
代码不是我写的，我只是把别人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&gt;2) DownRing(n-2);
    downstep++;
    if(n&gt;2) UpRing(n-2);
    if(n&gt;1) DownRing(n-1);
}

public static void UpRing(int n)         /*上环的逻辑则体现在这里*/ 
 
{
    if(n&gt;1) UpRing(n-1);
    if(n&gt;2) DownRing(n-2);
    upstep++;
    if(n&gt;2) UpRing(n-2);
}

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

[解决办法]

引用:

//数组circle即为9个环，circle[8]为最左边的第九环，circle[0]为最右边的第一环
//true表示向下“∨”,false表示向上“∧”
/**
*
* @author afunx
*/
public class NineCircle {
public static final int N = 9;
static boolean circ……

大哥你运行后也看看答案啊，9环要341步，一个环动一次就算1步了，你的结果也差太远了吧
[解决办法]
写了个测试，不知道是否正确


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&lt;9; i++) {
            h[i] = new Huan();
        }

        int step = 0;
        for (int i=8; i&gt;=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&gt;=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;
    }
}

[解决办法]
我用最笨的方法


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 &lt; 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&gt;=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 &lt; a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}

金山笔试题：九环有关问题挺有趣的题

热点推荐