猴子选大王的解法
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) {TTTT =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; for(i=0;i<num;i++) a=1; //猴子状态初始化，为1表示可能被选上，为0表明没希望了； int sum=0, //循环记数； countOne=num; //累积记数初始化，大于1表明还有大王候选人； while(countOne>1) { countOne=0; for(i=0;i<num;i++) { sum+=a; if(sum==del) sum=a=0; //淘汰倒霉猴子； countOne+=a; } } for(i=0;i<num;i++) if(a!=0) return i; //找到幸运猴子编号（从0开始的）； } void main() { int num,del; cout<<"请输入猴子总数和淘汰数："; cin>>num>>del; cout<<"第"<<choose(num,del)+1<<"个猴子为王！"<<endl; }
这是c语言写的，但是转换一下变成java也没有什么难度
页:
[1]