约瑟夫环:用户输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,直至最后一个元素并输出该元素的值。

一、循环链表:建立一个有N个元素的循环链表,然后从链表头开始遍历并记数,如果计数值为M,则输出并删除该元素,继续循环(其实是N-1次),当当前元素与下一元素相同时退出循环。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h> typedef struct temp
{
int data;
struct temp *next;
}Node; void JosephRing(int n, int m)
{
//建立约瑟夫环
int i;
Node *head, *p1, *p2; assert(n > 0 && m > 0);
head = (Node *)malloc(sizeof(Node));
head->data = 1; p1 = head;
for (i = 2; i <= n; i++)
{
p2 = (Node *)malloc(sizeof(Node));
p2->data = i;
p1->next = p2;
p1 = p2;
}
p1->next = head;//首尾相连 //循环计数,输出并删除
p2 = head;
while (p2 != p2->next)
{
i = m;
while (--i)
{
p1 = p2;
p2 = p2->next;
} printf("%d ", p2->data);
p1->next = p2->next;
free(p2);
p2 = p1->next;
}
printf("%d\n", p2->data);
free(p2);
}

二、取余操作:令f(n,m)表示n个人玩游戏报m退出最终结果,递推公式:
  f(1)=0;
  f(n,m)=[f(n-1,m)+m]%n; (n>1)
有了这个公式,我们要做的就是从1~n顺序算出f(n,m)的数值。因为实际生活中编号总是从1开始,我们输出f(n,m)+1。

int Josephus(int n, int m)
{
int i, s = 0;
assert(n > 0 && m > 0);
for (i = 2; i <= n; i++)
s = (s+m)%i;
return s+1;
}

详细分析见:何海涛-圆圈中最后剩下的数字

三、验证程序

int main()
{
int n, m;
scanf("%d%d", &n, &m);
JosephRing(n, m);
printf("%d\n", Josephus(n, m));
return 0;
}
05-12 05:58