数据结构 - 约瑟夫问题链表法

作者: 主教主

什么是约瑟夫问题?

约瑟夫问题:n个人围成一圈,初始编号从1~n排列,从约定编号为x的人开始报数,数到第m个人出圈,接着又从1开始报数,报到第m个数的人又退出圈,以此类推,最后圈内只剩下一个人,这个人就是赢家,求出赢家的编号。

是不是有点点复杂,其实该问题归结为模拟类型的算法题,根据题目要求模拟即可。

环形链表

image
1、先创建一个环形链表来存放元素:

2、然后一边遍历链表一遍删除,直到链表只剩下一个节点,这里就不全部演示了
image

那么,通过前面对环形链表的了解,以你的智慧应该会轻松解决简单的约瑟夫问题了。

不妨们加大难度,设有编号为1,2,3,…,n(n>0)个人按顺时针顺序围坐一圈,没人手持一个随机产生的密码(正整数)。现从第k个人开始顺时针的方向以1开始报数,报数的上限第一个人持有的密码m,报到m的人出列,然后将出列的人所持有的密码作为新的m值,从下一个人开始重新从1开始报数,如此下去,直到最后一个人出列为止,要求设计一个程序模拟此过程,并输出他们的列编号序列

问题分析

很显然这是一个线性结构,可以用线性表来表示。进行的主要操作是报数、出列,这个相当于对线性表进行删除操作,因此宜用用链表存储结构,每个节点表示一个人。n个人围城一圈循环报数,则利用单循环链表存储结构更容易解决问题。
因此,
第一步需要创建单循环链表,每个节点存储节点序号和密码,密码随机生成(1-10)
第二步实现循环删除操作,将密码作为每次循环的步长(这里指的是距离)
第三步实现打印操作(跟随第二步操作)

程序设计

/*单循环链表的存储结构*/
typedef struct
{
    int num;//序号
    int pwd;//密码
    struct Joseph *next;

}Joseph;

输入设计

在一行中输入总人数和第几个人开始报数

输入设计

首先输出每个人的编号以及持有的密码,其次输出出列的编号次序,最后输出幸存者。

基本操作

创建链表Joseph* creatList(Joseph* head,int n);
输出每个人的序号以及密码: void printList(Joseph* head,int n);
初始从第k个人开始报数,输出出列次序: void outList(Joseph *head,int k);

程序代码

include <stdio.h>
include <stdlib.h>
include <math.h>
include <malloc.h>
/*约瑟夫环问题
*单循环链表的创建
*打印单循环链表
*循环淘汰m,最后留下幸存者
*/
typedef struct
{
    int num;
    int pwd;
    struct Joseph *next;

}Joseph;
Joseph* creatList(Joseph* head,int n)
{
    int i;
    Joseph *p,*q;
    q = head;
    q->num = 1;
    q->pwd = rand()%10+1;


    for(i = 2;i<=n;i++)              //尾插法
    {
        p = (Joseph*)malloc(sizeof(Joseph));
        p->num = i;
        p->pwd = rand()%10+1;
        q->next = p;
        q = p;

    }
    p->next = head;

}
void printList(Joseph* head,int n)
{
    int i;
    Joseph *list;
    list = head;
    for(i = 0;i<n;i++)
    {
        printf("第%d位的密码是%d\n",list->num,list->pwd);
        list = list->next;
    }

}
void outList(Joseph *head,int k)
{
    Joseph *p,*q;
    q = (Joseph*)malloc(sizeof(Joseph));
    p = head;
    int m;


    for(int i = 1;i<k;i++)              //找第k个节点,作为开始
    {
        q = p;
        p = p->next;
    }

    m = head->pwd;                       //第k个节点的密码作为步长(这里指的是距离)
    while(p!=q)                          //当留下最后一个节点时p = q
    {
        for(int i = 1;i<m;i++)
        {
            q = p;
            p = p->next;
        }
        m = p->pwd;
        printf("%d ",p->num);
        q->next = p->next;
        free(p);
        p = q->next;
    }
    printf("\n幸存者:%d",q->num);
    free(p);


}



int main()
{
    Joseph *joseph;
    joseph = (Joseph*)malloc(sizeof(Joseph));
    int n;
    printf("输入总人数:");
    scanf("%d",&n);

    creatList(joseph,n);
    printList(joseph,n);

    int k;
    printf("输入从第几个人开始报数:");
    scanf("%d",&k);

    outList(joseph,k);


    return 0;
}

约瑟夫问题:一行代码就解决了 ————转载

原文创作:主教主

原文链接:https://www.cnblogs.com/zhujiaozhu/p/15388058.html

更多推荐

更多
  • Azure数据工程指南-二十四、数据治理的权限 创建 azure 预览帐户,探索 azure 预览,探索词汇表,浏览资产,以编程方式使用预览,摘要,管理凭证和访问,创建扫描, 许多组织需要建立数据治理流程、标准和方法,并且已经能够使用内部 SQL Server 工具(如 Master
    Apache CN

  • Azure数据工程指南-二十二、Synapse 分析工作区 创建 Synapse 分析工作区,使用 Spark 探索样本数据,用 SQL 查询数据,用 SQL 创建外部表,摘要, 微软 Azure 数据平台的众多新增功能已经围绕许多类似的产品及其在现代 Azure 数据平台中的用途产生了兴奋和困
    Apache CN

  • Azure数据工程指南-二十三、数据块中的机器学习 创建 MLflow 实验,安装 MLflow 库,创建笔记本,选择性测井,自动记录,摘要, 寻求利用机器学习(ML)和人工智能能力的组织和开发人员花费大量时间构建 ML 模型,并寻求一种方法来简化他们的机器学习开发生命周期,以跟踪实验,
    Apache CN

  • Azure数据工程指南-二十一、将 Apache Spark 的 GraphFrame API 用于图形分析 安装 JAR 库,加载新数据表,将数据加载到数据块笔记本中,用顶点和边构建一个图,查询图表,寻找有图案的图案,用 PageRank 发现重要性,探索入度和出度度量,摘要,进行广度优先搜索,查找连接的组件, 图形技术使用户能够以图形的形式
    Apache CN

  • Azure数据工程指南-20 二十、部署 SQL 数据库先决条件,创建 Visual Studio SQL 数据库项目,安装 Visual Studio GitHub 扩展,导入 AdventureWorks 数据库,连接到 GitHub Repo 源代码控制,将
    Apache CN

  • Azure数据工程指南-十九、部署数据工厂更改 先决条件,创建 DevOps 持续集成构建管道,创建 DevOps 持续部署发布渠道,验证部署的数据工厂资源,摘要,Azure PowerShell 任务停止触发器,ARM 模板部署任务,Azure PowerShell 任务启动触发器
    Apache CN

  • Azure数据工程指南-十八、用于 Cosmos DB 的 Azure Synapse 链接 创建一个 Azure Cosmos DB 帐户,启用 Azure Synapse 链接,创建一个 Cosmos DB 容器和数据库,将数据导入 Azure Cosmos DB,在 Azure Synapse Analytics 中创建
    Apache CN

  • Azure数据工程指南-十六、流分析异常检测 先决条件,创建流分析输入和输出,创建实时电源 BI 仪表板,监控实时电源 BI 流,摘要,创建 Azure 流分析作业,创建物联网中心,创建 Power BI 服务,下载设备模拟器,添加流输入,添加流输出,编写流分析查询,启动流分析作业
    Apache CN

  • Azure数据工程指南-十七、使用 Apache Spark 的实时物联网分析 先决条件,创建物联网中心,创建数据块集群,安装 Maven 库,创建笔记本并运行结构化流查询,摘要,配置笔记本连接,开始结构化流,启动物联网设备模拟器,显示实时流数据,创建 Spark SQL 表,将流写入增量表, 实时物联网分析、高级
    Apache CN

  • Azure数据工程指南-十五、DeltaLake 为什么是酸性 DeltaLake,先决条件,创建并插入 DeltaLake,更新 DeltaLake,从 DeltaLake 删除,浏览增量日志,摘要,插入,更新,删除, 在使用 Azure Data Lake Storage Gen2
    Apache CN

  • 近期文章

    更多
    文章目录

      推荐作者

      更多