约瑟夫环问题的一种描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人手持一个密码(正整数)。一开始任选一个整数作为报数上限值,从第一人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将它的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去直到所有人全部出列为止。

特别说明:代码仅供学习参考,不允许用来应付作业。

#include <cstdio>

struct node { //0. 定义结构体,即单链表结构
	int value, index; //1. 链表内容物有两个值,value用来存密码,index用来存下标
	node *next; //2. 单链表下一个节点的位置
};

node* input(int n) { //5. input函数的功能是读入数据,构建链表,并返回尾节点
	node* first = new node(); //6. 新建一个节点,作为链表的头节点
	node* temp = first; //7. 用temp指针指向头节点,来构建链表
	for (int i = 1; i < n; ++i) { //8. 循环n-1次,可以产生n-1个节点
		scanf("%d", &temp->value); //9. 读入密码,存在temp指针位置
		temp->index = i; //10. 定义该节点的下标为i
		temp->next = new node(); //11. 新建一个节点,并让temp指针的下一个位置指向该节点
		temp = temp->next; //12. 将temp指针向后移动
	}
	scanf("%d", &temp->value); //13. 读入最后一个节点的密码
	temp->index = n; //14. 定义其下表为n
	temp->next = first; //15. 尾节点的下一个位置指向头节点,使单链表变成无空节点的循环单链表
	return temp; //16. 返回尾节点
}

void output(node* previous, int count, int m) { //18. output函数的功能是通过前一个节点,判断当前节点是否为输出的答案,其中count用来统计当前是第几个数,m是当前密码
	node* temp = previous->next; //19. 用temp指针指向当前节点
	if (previous == temp) { //20. 如果前一个节点等于当前节点,说明链表中只剩下一个节点,直接输出
		printf("%d\n", previous->index); //21. 输出最后一个节点的下标
		delete(previous); //22. 释放最后一个节点
		return; //23. 终止递归
	}
	if (count == m) { //24. 如果count等于m,说明当前节点就是要输出的节点
		printf("%d ", temp->index); //25. 输出当前节点的下标
		previous->next = temp->next; //26. 前一个节点的下一个位置指向当前节点的下一个位置,作用相当于从链表中删除当前节点
		m = temp->value; //27. 更新m的值为当前节点的密码
		delete(temp); //28. 释放当前节点
		output(previous, 1, m); //29. 进入下一层递归,因为当前节点已经被删除,所以下一个节点的前一个节点,依然为当前节点的前一个节点
	} else output(previous->next, count + 1, m); //30. 如果当前节点不是要输出的节点,则进入下一层递归
	return;
}

int main() {
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF) { //3. 读入n,m
		node* last = input(n); //4. 执行input函数,并得到链表的尾节点
		output(last, 1, m); //17. 执行output函数,进入递归,输出约瑟夫环,并释放链表
	}
	return 0;
}
转载保留版权:http://haipz.com/blog/i/6101 - 海胖博客