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