|
约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。
约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 解法一：用循环链表实现代码语言：javascript复制#include
#include
typedef struct node
{
int data;
struct node *next;
}Node;
/**
* @功能 约瑟夫环
* @参数 total:总人数
* @参数 from:第一个报数的人
* @参数 count:出列者喊到的数
* @作者 zheng
* @更新 2013-12-5
*/
void JOSEPHUS(int total, int from, int count)
{
Node *p1, *head;
head = NULL;
int i;
// 建立循环链表
for(i = 1; i data = i;
if(NULL == head)
{
head = newNode;
}
else
{
p1->next = newNode;
}
p1 = newNode;
}
p1->next = head; // 尾节点连到头结点，使整个链表循环起来
p1 = head; // 使pcur指向头节点
// 把当前指针pcur移动到第一个报数的人
// 若从第一个人开始报数，这一段可要可不要
for(i = 1; i < from; i++)
{
p1 = p1->next;
}
Node *p2 = NULL;
// 循环地删除队列中报到count的结点
while(p1->next != p1)
{
for(i = 1; i < count; i++)
{
p2 = p1;
p1 = p1->next;
}
p2->next = p1->next;
printf("Delete number: %d\n", p1->data); // 打印所要删除结点的数据
free(p1); // 删除结点，从内存释放该结点占用的内存空间
p1 = p2->next; // p1指针指向新的结点p2->next，即原先的p1->next
}
printf("The last one is No.%d\n", p1->data);
}
int main()
{
int total, from, count;
scanf("%d%d%d", &total, &from, &count);
JOSEPHUS(total, from, count);
return 0;
}运行结果： 代码语言：javascript复制13 1 3
Delete number: 3
Delete number: 6
Delete number: 9
Delete number: 12
Delete number: 2
Delete number: 7
Delete number: 11
Delete number: 4
Delete number: 10
Delete number: 5
Delete number: 1
Delete number: 8
The last one is No.13解法二：数组实现思路：设数组a有n个变量，每个变量中初始放的标识数是1，表示这个人在队列里，若出列标识数就变为0。
现在计数器从1开始向后数，每报一个数即把累加器加1。这里累加器表示报数人数。累列到m时，报数的人要出列，标识数要变为0。下一个人从1开始重新报数。
报到最后一个人后，从第一个人开始继续报数。 代码语言：javascript复制#include
#include
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int flag[n + 1]; // 在队列里标记为1，出列标记为0
memset(flag, 0, sizeof(flag)); //把数组每个元素置0，在memory.h中声明
int i = 0;
int outCnt = 0; // 记录出列的人数
int numoff = 0; // 报数
// 默认都标记为1
for(i = 1; i n >> m;
cout > m;
int out = 0;
for(int i = 2; i |