约瑟夫环问题

        从n只猴子选猴王，选举方法是：参选猴子按1,2，…，n编号并按照顺序围成一圈，从第k只猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是猴王。

一、模拟过程求结果

由题意，n 只猴子围坐在一起形成首尾相接的环，可用循环链表解决。具体算法如下：

（1）      首先用数组创建循环链表，并使数组下标和猴子编号一致；

（2）      确定第一个开始报数的猴子；

（3）      数到m让这个猴子出列；

（4）      接着让下一个猴子从1开始报数，重复第三步；

（5）      直到剩下一只猴子时，这只猴子就是猴王。

        核心代码如下：

 int a[] = new int[n+1];				// n为猴子总数，m为出局数字，k为起始报数猴子编号	a[0] = 0;	                        		// 使猴子编号和数组下标一致	System.out.PRintln("出局的猴子编号：");	for (int i=1; i<=n; ++i)		a[i] = 1;					// ==1表示编号为i的猴子未出列	for (int i=1; i<=m; ++i) {		if (1==n) {						break;				// 圈内只剩下一只猴子		}		else if (i == m) {			// 有猴子出局			--n;							// 猴子数减1			i = 0;							// 使下一只猴子从1开始报数			a[k] = 0;						// ==0表示k号猴子出列			System.out.print(k + " ");			++s;							// s为计数变量，输出时15个数字一行			if(s%15 == 0) {				System.out.println();			}		}		do {			++k;							// k记的是猴子编号，i记的是数的数字			k = k%n1;						// 实现循环链表		} while(a[k]!=1);					// 跳过已出列的猴子继续进入for循环数数	} 运行结果：
二、只求出最终结果
如果只需求出猴王编号，不需要列出淘汰顺序的话，可以定义一个函数f(n,m)，n为猴子总数，m为淘汰数字，当淘汰一只猴子后，函数可以定义为f’(n-1,m)。易得：
f(n,m) = f’(n-1, m)。通过做映射可推导出：f(n,m) =[f(n-1,m) + m]%n, n>1。据此可以使用循环语句解决问题，核心代码如下：
for (int i=2; i<=n; ++i) { // s为猴王编号，m、k含义同上		s = (s+m)%i;			// 不求具体出局编号，只看结果的算法	}			System.out.println("/n猴王编号为：" + (s+k)); 运行结果：