约瑟夫问题的三种解法

约瑟夫环问题即设有n个人坐成一个圈，从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人再次出列，如此循环，知道 所有人都出列为止，最后按照出列顺序输出

约瑟夫环问题的三种方法，

利用数组问题解决：

#include

#include

#pragma warning (disable:4996)

int main(void)

{

printf("请输入总数：\n");

int m;

scanf("%d", &m);

printf("请输入间隔数：\n");

int n;

scanf("%d", &n);

int *a = (int *)malloc(sizeof(int)*m);

int count = 0;

for (int i = 0; i < m; i++)

{

a[i] = i + 1;

}

for (int k = 0; k < m; k++)

{

int l = 0;

while (l < n)

{

l++;

count++;

if (a[(count - 1) % m] == 0)//一旦这个这个数为0，l--，继续寻找

{

l--;

}

}

printf("%d-->", a[(count - 1) % m]);

a[(count - 1) % m] = 0;//每输出一个数，就进行清除，此处为假删除

}

}

用循环链表解决，建立一个循环链表，每删除一个数据，节点释放，此处为真删除

#include "stdio.h"

#include "stdlib.h"

#include "malloc.h"

#include "math.h"

#pragma warning (disable:4996)

#define LEN sizeof(struct linklist)

typedef struct linklist

{

int num;

struct linklist *next;

}list;

struct linklist * create_list(int n)// 建立一个存储n个数据的循环链表

{

#include "stdio.h"

#include "stdlib.h"

#include "malloc.h"

#include "math.h"

#pragma warning (disable:4996)

#define LEN sizeof(struct linklist)

typedef struct linklist

{

int num;

struct linklist *next;

}list;

struct linklist * create_list(int n)// 建立一个存储n个数据的循环链表

{

list *head;

list *p1, *p2; //首先建立循环链表

head = (struct linklist *)malloc(LEN);//头结点的创立

p2 = head;//将p2指针赋初值

p2->next = NULL;

p1 = NULL;

int i;

if (head == NULL)

{

printf("创建链表失败");

return NULL;

}

for (i = 0; i < n; i++) //创立一个n个数据的循环链表

{

p1 = (struct linklist *)malloc(LEN);

p1->num = i + 1;

p2->next = p1;

p2 = p1;

p1->next = NULL;

}

p1->next = head->next;// 将最后一个节点的数据指向第一个节点

return head;

}

void josephus(struct linklist *head, int n, int m)

{

list *p1, *p2;

p1 = head->next;

p2 = NULL;

list *temp;

int i, j;

if (head == NULL)

{

printf("传输数据有误");

return;

}

for (i = 0; i < n; i++)

{

for (j = 1; j < m; j++)

{

p2 = p1;

p1 = p1->next;

}

printf("%d---->", p1->num);

temp = p1;

p2->next = temp->next;//删除这个节点

p1 = temp->next;

free(temp);

}

}

void main()

{

int n, m;

list *head;

printf("请输入多少人参与杀人游戏");

scanf("%d", &n);

printf("请输入每几个人死去一个");

scanf("%d", &m);

head = create_list(n);

josephus(head, n, m);

}

数学方法实现，最简单的方法当然是求出递推关系式，然后直接编程，非常容易。

#include

#pragma warning (disable:4996)

int main(void)

{

int n, m, i, s = 0;

printf("N M = ");

scanf("%d%d", &n, &m);

for (i = 2; i <= n; i++)

s = (s + m) % i;

printf("The winner is %d\n", s);

return 0;

}

/*这是一个递推关系式，最后一个人编号假设为X，如果从n-1个人中的编号可以求出n个，那么便可以依次类推。

假设第m个人被杀 则

重新编号

m m+1 m+2 ......n-2 n-1 0 ...... m-2

0 1 2 ........n-2-m n-1-m n-1-m-2... n-2

X

假设幸存者在n-1队列中编号为X

那么可以知道在n编号中的X为 X+m, 举例 X=2，那么m+2为队列n中的编号

由于X+m可能会越界，所以（X+m）% n。

本例假设m其实不小于n也没有关系，因为 （X + m) % n = (X + m')%n,其中 m'+k*n = m,k为整数。

本文来源：https://www.2haoxitong.net/k/doc/77db183a65ce05087732132a.html