约瑟夫环问题，也称圆桌问题，解决的方案很多，在此，给出三种解决方案，双向循环链表，静态链表和公式法
题目描述
编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一
开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。
输入
第一行输入两个整数，依次表示人数n和初始化密码m，以空格间隔。
第二行依次输入n个整数，分别表示n个人的密码，以空格间隔。
输出
按出列次序输出每个人的编号，以空格间隔。
输入
7 20
3 1 7 2 4 8 4
输出
6 1 4 7 2 3 5
双向循环链表
思想十分简单，就是建立一个双向链表来存储数据结构体，然后一直遍历，当遍历到指定位置，改变密码值，然后删除该结点，如此循环，直到仅剩一个结点时，退出循环
下面是主要函数的流程图：
源码如下（注释已加）
//双向循环链表解决约瑟夫环问题
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data; //手持密码值
int num; //编号
struct node *prev;
struct node *next;
}Jose_node;
//debug打印链表
void print_list(Jose_node *head,int n){
Jose_node *p = head;
while(n--){
printf("data = %d,num = %d \n",p->data,p->num);
p = p->next;
getchar();
}
}
//创建链表
Jose_node *Creatlist(){
Jose_node *head = (Jose_node*)malloc(sizeof(Jose_node));
head->data = 0;
head->next = head;
head->prev = head;
return head;
}
//链表输入
int Insertlist(Jose_node *head){
int sum,pwd;
Jose_node *p = head;
scanf("%d %d",&sum,&pwd);
int n = sum;
//在头后开始插入结点，所以结点 编号 为 2
int num = 2;
//头的编号为1
head->num = 1;
//插入结点
while(sum--){
Jose_node *q = (Jose_node*)malloc(sizeof(Jose_node));
scanf("%d",&p->data);
q->num = num;
num++;
q->next = head;
head->prev = q;
p->next = q;
q->prev = p;
p = p->next;
}
//释放空结点
p = head->prev;
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
//打印链表
/* print_list(head,n); */
//返回密码值
return pwd;
}
//约瑟夫环
void Josephus(Jose_node *head,int pwd){
int n = 1;
Jose_node *p = NULL;
while(head){
//与密码相同
if(n == pwd){
printf("%d ",head->num);
//结束
if(head->next == head){
printf("\n");
free(head);
break;
}
//重置密码
pwd = head->data;
//释放结点
p = head;
head = head->next;
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
//从 1 开始
n = 1;
}else{
//继续游戏
head = head->next;
n++;
}
}
}
int main()
{
//创建链表
Jose_node *head = Creatlist();
//添加数据
int pwd = Insertlist(head);
//约瑟夫环
Josephus(head,pwd);
return 0;
}
运行结果：
静态链表法
这个就更加简单了，只需要将数据存入链表中，然后每当一个人出局时，对其进行标识，初始化步数，继续进行遍历，快越界时，初始化下标即可
//静态链表解决约瑟夫环问题
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
int num;
}Jose_node;
int main()
{
int sum,pwd;
scanf("%d %d",&sum,&pwd);
Jose_node *head = (Jose_node *)malloc(sizeof(Jose_node)*(sum+1));
//循环输入数据
for(int i = 1;i <= sum;i++){
scanf("%d",&head[i].data);
head[i].num = i;
}
//下标
int h = 1;
//步数
int steps = 1;
int flag = 0;
while(1){
//越界
if(h > sum){
h = 1;
continue;
}
//已被删除
if(head[h].num == -1){
h++;
continue;
}
//当到达这个点
if(steps == pwd){
printf("%d ",head[h].num);
//人已经全部离开
flag++;
if(flag == sum){
break;
}
//标识已离开
pwd = head[h].data;
head[h].num = -1;
//步数初始化
steps = 1;
//下标继续向后
h++;
continue;
}
h++;
steps++;
}
printf("\n");
return 0;
}
具体运行结果同上面的运行结果
公式法
这个就是一个奥数推导题目，推导过程 没有细看 看了没懂，以后有机会学习一下，最终的公式十分简单
以下转载于这个博客
题目：
n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
#include <stdio.h>
int main()
{
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 ("\nThe winner is %d\n", s+1);
}