约瑟夫环问题

题目链接：http://noi.openjudge.cn/ch0302/1748/

描述

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
 

输入

每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：

0 0
 

输出

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号

样例输入

6 2
12 4
8 3
0 0

样例输出

5
1
7

【分析】本题提供三种解题方法，一种是直接利用循环链表，对出局的猴子删除对应节点，注意创建循环链表时先对尾指针tail的指针域进行赋值再对插入节点的指针域赋值，因为空表时tail指向头结点，而头结点指针域为空，为了构造成循环链表，让最后一个节点总是指向首元结点，要先让头结点的指针域有所指向。该方法代码如下：

#include <stdio.h>
#include <stdlib.h> 

typedef struct Node {
	int data;
	struct Node * next;
}NODE, *PNODE;

int main() {
	int n,m;
	PNODE L = (NODE*)malloc(sizeof(NODE));
	L->next = NULL;
	while(1) {
		scanf("%d%d",&n,&m);
		if(!n || !m) break;
		PNODE tail = L;
		for(int i=1;i<=n;i++) { //建立1-n的循环链表 
			PNODE s = (NODE*)malloc(sizeof(NODE));
			s->data = i;
			tail->next = s; //先对尾结点的指针域赋值可以避免特判空表插入时指向首节点的操作 
			s->next = L->next;
			tail = tail->next;
		}
		PNODE p = L->next, q = tail; //指针一前一后 
		int cnt = 1;
		while(p!=q) {
			if(cnt==m) {	//有猴子出局就删除出局猴子的节点 
				q->next = p->next;
				free(p);
				p = q->next;
				cnt = 1;
			} else { //没有猴子出局，指针同时向前，报数加1 
				q = p;
				p = p->next;
				cnt++;
			}
		} 
//		L->next = q; 部分循环链表的题要求链表完整性 
		printf("%d\n",p->data);
		free(p);
		L->next = NULL;
	}
	free(L); 	//释放内存 
	return 0;
}

第二种方法是数组标记的方法，a[i]表示是第几只猴子，若为0说明该猴子出局，巧妙应用取余的方式使数组成环，循环截止条件是只剩一只猴子。代码如下：

#include <stdio.h>

int main() {
	int n,m;
	while(1) {
		scanf("%d%d",&n,&m);
		if(!n || !m) break; 
		int a[n];
		for(int i=0;i<n;i++)
			a[i] = i+1;	//a[i]表示是第几只猴子，若为0说明该猴子出局 
		int pos = 0, cnt = 1, sum = n; 
		while(sum>1) { //总数预留，不要直接对n操作 
			if(a[pos]) { //只对还未出局的猴子进行判断该回合是否出局 
				if(cnt==m) {
					a[pos] = 0; //出局猴子标记为0 
					cnt = 1;
					sum--;
				} else {
					cnt++;
				}
			} 
			pos = (pos+1) % n;	//数组成环的关键，无论猴子出没出局，都要遍历 
		}
		for(int i=0;i<n;i++)
			if(a[i])
				printf("%d\n",a[i]);
	}
	return 0;
}

第三种方法是数组模拟链表的方法，a[i]保存下标为i的下一个下标，若为-1说明该位置上的猴子淘汰，循环截止的条件是只剩一只猴子或者两指针指向的位置重合。整个过程是对下标的淘汰，最后表示成猴子需+1，建立位置的链接的方式和链表一样，代码如下：

#include <stdio.h>

int main() {
	int n,m;
	while(~scanf("%d%d",&n,&m)) {
		if(n==0 || m==0) break;
		int a[301] = {0};
		for(int i=0;i<n-1;i++)
			a[i] = i+1;	//a[i]保存的是下标为i的下一个猴子的下标，下标为n-1的元素保存的是0，即构成一个循环 
		int pos = 0, prior = n-1, cnt = 1, num = n;
		while(num>1) { //循环结束条件也可以是prior和pos重合 
			if(cnt!=m) { //报数没到m, prior和 pos指针都往前走一位 
				prior = pos; //prior接替pos的位置，一直跟在pos的后面
				pos = a[pos]; //a[i]保存的是下标为i的下一个猴子的下标
				cnt++; 
			} else { //pos所指的猴子出局 
				a[prior] = a[pos]; //重新建立连接关系，即a[prior]跳过出局猴子的下标(pos)，保存下一个猴子的下标,而本方法一直在强调a[pos]就是pos的后一个下标 
				a[pos] = -1; //出局的猴子位置标志为-1
				pos = a[prior]; //pos仍然在prior的前面一位 
				cnt = 1; 
				num--;
			}
		}
		printf("%d\n",pos+1);// 因为整个过程都是以猴子的位置做标识的，而数组下标是从0开始，猴子是从1开始，故结果要加1 
	}
	return 0;
}

以上三种做法在noi上都是可以通过的