猴子选大王的解法_JAVA_编程开发_程序员俱乐部

1.简单版本，代码简单但是不容易理解
   

public class TT {
	
	
	public void King(int n, int m) {
		// 总人数 M ，数到第 N 个排除。
		int k = 0;
		for (int i = 2; i <= n; i++){
		k = (k + m) % i;
		System.out.println("k=" + k);
		}
		System.out.println("第" + (++k) + "位当上了猴子大王。");
		}

	public static void main(String[] args) {
		TT  TT =new TT ();
		TT.King(10, 2);
	}
}

解释：
这是反推。（k从0到n-1计数）
n==1时，k1==0
n==2时，k2==m%2
n==3时，k3==(k2 + m%3)%3==(k2 + m)%3，这是因为m%3的那位被请走，从k3到k2的序号值需要用m%3调整差异，因为调整后值可能突破3所以再%3
最终确立前述程序中的
k''=(k' + m) % n

这也反映了运行效率高的算法可读性往往差。这个题用链表做，哪个都能看懂。


代码二：

＃i nclude<iostream.h> 

int choose(int num,int del) 
{ 
int i; 
int a[100]; 
for(i=0;i<num;i++) 
a[i]=1; //猴子状态初始化，为1表示可能被选上，为0表明没希望了； 

int sum=0, //循环记数； 
countOne=num; //累积记数初始化，大于1表明还有大王候选人； 

while(countOne>1) 
{ 
countOne=0; 
for(i=0;i<num;i++) 
{ 
sum+=a[i]; 
if(sum==del) 
sum=a[i]=0; //淘汰倒霉猴子； 
countOne+=a[i]; 
} 
} 

for(i=0;i<num;i++) 
if(a[i]!=0) 
return i; //找到幸运猴子编号（从0开始的）； 
} 

void main() 
{ 
int num,del; 
cout<<"请输入猴子总数和淘汰数："; 
cin>>num>>del; 
cout<<"第"<<choose(num,del)+1<<"个猴子为王！"<<endl; 
}

这是c语言写的，但是转换一下变成java也没有什么难度