c：约瑟夫问题

21、若干人围成一组（如7个人，编号分别为1-7），从1开始报数，凡报到5或5的倍数（亦可选择其它基数）的那个人即从此小组中退出（出局）；同时，这一报数过程继续进行，问最后一个留在小组中的那一个人的编号。试通过程序来模拟这一过程，并求出最终留下来的那个人的编号（此问题称为约瑟夫问题）。

解题思路：
就用7个同学的例子来看
报完第1轮会踢出一个同学
然后在原报数的基础上继续
会有数个轮回
直到最后只剩下一位同学
同学有编号
一开始是有序的
但从中踢出同学后就变的无序了
我一开始没有思路
然后想到了一个解决办法
我可以用循环链表
既符合它的无序删除
又可以轮回
我的代码在这里：

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct yue)

//定义一个结构体，date记录编号，num记录报道的数据
struct yue{
    int date;
    int num;
    struct yue *next;
};

int n;//n记录节点个数

//定义创建结构体的函数
struct yue *creat(int l){//参数l传递初始人数
    struct yue *head;
    struct yue *p1,*p2;
    n=0;
    p1=p2=malloc(LEN);
    while(1){
        n++;
        if(n==1)//节点数为1，此时记录头节点数据
            head=p1;       
        else//节点数不为1，则把p1所指的节点连接到表尾
            p2->next=p1;
        if(n==l){//创建一个循环链表            
            p1->next=head;
            p1->date=n;
            break;
        }
        p1->date=n;
        p2=p1;//p2移到表尾
        p1=malloc(LEN);
    }
    return head;
}

//定义删除功能的函数
struct yue *del(struct yue *p1,struct yue *p2){
    p2->next=p1->next;//p1是要删除的数据的指针，p2是他的前一指针
    printf("编号为 %d 的同学退出\t退出前报数：%d\t",p1->date,p1->num);
    printf("还剩 %d 个同学\n",--n);
}

int main(){
    int l,m,i=1;
    printf("输入同学个数：");
    scanf("%d",&l);
    printf("输入基数：");
    scanf("%d",&m);
    struct yue *p1,*p2;
    p1=creat(l);
    p1->num=i;
    if(m==1)//基数为1时可以直观确定，首轮最后一个同学将会留下来
        printf("最终留下来的同学编号为：%d\n",l);
    else{//基数不为1的情况如下
        while(n>1){
            //printf("编号 %d 报数 %d\n",p1->date,p1->num);//这一语句可以显示每个同学报的数字
            p1->next->num=++i;//确定下一个同学报的数字
            if((p1->next->num)%m==0){//判断是否出局
                del(p1->next,p1);
                p1->next->num=++i;//已出局的同学的下一同学将不会被检索，因为基数大于1时不会有相邻的同学出局
            }
            p2=p1;//p2记录出局的前一位同学,方便最后统计
            p1=p1->next;
        }
        printf("最终留下来的同学编号为：%d\n",p1->date);
    }
  
    return 0;
}

运行测试在这里：

详细步骤：

c：约瑟夫问题

原文：https://www.cnblogs.com/danl/p/13463881.html