n个人围成圈,依次编号为1,2,..,n,现在从1号开始依次报数,当报到m时,报m的人退出,下一个人重新从1报起,循环下去,问最后剩下那个人的编号是多少?
递归法
参见百度百科:Josephus(约瑟夫)问题的数学方法
递推式:
将这些人的编号用对总人数取模所得余数代替(即原编号减一),其中 Fn 表示n个人的环,最后剩下的那个人的编号。
由这个递推式不难写出相应代码:
/* 约瑟夫环问题 */
# include <stdio.h>
int main()
{
int m, n, i, s;
while (~scanf("%d%d", &m, &n))
{
s = 0; // F1 = 0;
for (i = 2; i <= n; ++i)
s = (s + m) % i;
printf("%d\n", s+1); // 原问题的编号是从1开始的
}
return 0;
}
上述代码的复杂度为O(n)。
模拟法
采用循环链表进行模拟题目描述的过程,退出通过删除节点表示;
使用链表模拟时,维护一个充当报数角色的变量 i ,每当 i 等于 m 时,重置 i 为 1;
循环终止的条件是只剩余一个节点(p->next = p),或者已经删除了 n-1 个节点;
由于每次删除一个节点需要报够 m 次数(遍历 m 个节点),一共要删除 n-1 个数,所以链表模拟的复杂度为O(m*n)。
/* 约瑟夫环问题——链表模拟*/
# include <stdio.h>
# include <stdlib.h>
typedef struct node
{
int id;
struct node* next;
} node;
int main()
{
int m, n, i;
node *p, *q, *head;
while (~scanf("%d%d", &m, &n))
{
// 创建含 n 个节点的循环链表,初始化编号
head = (node *)malloc(sizeof(node));
head->id = 1;
q = head;
for (i = 2; i <= n; ++i)
{
p = (node *)malloc(sizeof(node));
p->id = i;
q->next = p;
q = p;
}
q->next = head;
// 模拟退出过程
i = 1;
p = head;
while (p->next != p)
{
q = p;
p = p->next;
++i;
if (i == m) //delete(p); i = 1;
{
q->next = p->next;
free(p);
p = q->next;
i = 1;
}
}
// 打印剩余节点的编号
printf("%d\n", p->id);
free(p);
}
return 0;
}
扩展
当最先报数的那个人编号不是 1 时,对于递归法,需要对结果进行调整,对于链表只需要将循环起点的 head 改成相应编号的指针;
当报数前去掉一个编号为 k 的人,并从 k+1 开始报数时,可以认为从某个人报起,到编号为 k 时,刚好为 m ,因此去掉了这个人,这样对应上述递归方法的结果为:(s+1) + (m-k),并将这个结果的范围调整到 [1, n] 内。