Loading...
墨滴

公子宇

2021/12/12  阅读:22  主题:自定义主题1

Josephus问题求解

Josephus问题求解

一、问题描述

(1) 实验题目

约瑟夫斯(Josephus)问题的一种描述是:编号为1,2,…,nn个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。

(2) 基本要求

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。

(3) 测试数据

n=77个人的密码依次为:3,1,7,2,4,8,4m初值为6(正确的出列顺序应为6,1,4,7,2,3,5

二、需求分析

(1) 程序所能达到的基本可能

  1. 本程序用来求出Josephus问题的出列顺序
  2. 程序运行后显示提示信息,引导用户输入n值,n个密码,m
  3. 用户输入完毕后,自动输出出列顺序

(2) 输入与输出的形式

  1. 输入数据:建立输入处理,输入n输入以及每个人的密码;m的初值。
  2. 输出形式:建立一个输出函数,输出正确的序列。

三、概要设计

(1) 链表节点类型定义

#define TypeDate int
typedef struct SlNode {
    int id;
    TypeDate data;
    struct SlNodenext;
} SlNode;

(2) 模块定义

SlNode* SlNode_create()// 创建链表模块
void SlNode_pop(SlNode *r,int k)// 出列模块

(3) 主程序调用关系

  1. 变量声明

    m, k, *h, *r

  2. 获取n

    n:队列人数

  3. 调用创建链表模块SlNode* SlNode_create();

  4. 获取m

    m:首次循环的人数

  5. 调用出列模块void SlNode_pop(SlNode *r,int k);

四、详细设计

(1) 全局变量声明和链表节点定义

int n;

#define TypeDate int

typedef struct SlNode {//循环链表
    int id;
    TypeDate data;
    struct SlNodenext;
} SlNode;

(2) 创建链表模块

SlNode* SlNode_create();

  1. 定义变量

    SlNode *h, *r, *p;

    int i = 0;

    h为该链表的头节点;r为链表的任意一个节点,用于创建节点;p为最后一个节点;

  2. 创建一个头节点h

  3. 循环获取输入

    1. 创建一个节点r
    2. 输入密码
    3. i赋给该节点的id
    4. r放置在头节点或之前节点的后面
  4. 把最后节点的指针指向首节点

    p->next = h->next;

  5. return h;

(3) 出列模块

void SlNode_pop(SlNode *r,int k);

  1. 前置准备

    int i,j;

    printf("\nOrder of departure: ");

  2. 利用一个嵌套循环来循环输出节点的id

    n个节点,外循环一共循环n

    1. 第一个节点就是目标节点,即r->id == 0

      if(k == 1)
      {
          printf("%d ",r->next->id);
          k = r->next->data;
          // 弹出目标节点
          r->next = r->next->next;
          for(int k=1;k<n;k++) r = r->next;
          r->next = r->next->next;
          r = r->next;
      }
      else
      {
          r = r->next;
          i--;
      }
    2. 第一个节点不是目标节点

      1. 遍历到目标节点的前一个节点

      2. 打印id

      3. 将目标节点的密码赋给k,这是下一轮循环的次数

      4. 把目标节点的next赋给上一个节点的next,以达到弹出目标节点的目的

      5. 要从下一个节点开始,所以将r移到r的下一个节点

        if(k != 1) r = r->next;

        k == 1,则报1的节点就是目标节点,此处要保证r必须为目标节点的上一个节点。

五、调试分析

(1) 算法编写思路

程序把围坐在一起的人看作一个循环链表,每个人的编号看作链表节点的id值,每个人的密码看作链表节点的data,并用头节点指向id值为1的节点,从而使调试比较方便。

(2) 算法的时空分析

  • 循环链表创建函数SlNode* SlNode_create();循环n次读入密码,运算次数为n,时间复杂度为O(n)。
  • 出列函数void SlNode_pop(SlNode *r,int k);,循环n次,每一次循环之中,又循环了k次,k为每个节点的data,时间复杂度为O(n^2^)。

六、使用说明

程序运行之后用户按提示先输入n值,之后逐个输入n个密码,最后输入m值,输入完毕之后,程序自动打印出列顺序

七、调试结果

第一组测试样例

  1. 输入

    Please input n: 7
    Please enter a password(1 of 7): 3
    Please enter a password(2 of 7): 1
    Please enter a password(3 of 7): 7
    Please enter a password(4 of 7): 2
    Please enter a password(5 of 7): 4
    Please enter a password(6 of 7): 8
    Please enter a password(7 of 7): 4
    Please input m for circulation: 6
  2. 输出

    Order of departure: 6 1 4 7 2 3 5 

第二组测试样例

  1. 输入

    Please input n: 5
    Please enter a password(1 of 5): 5
    Please enter a password(2 of 5): 4
    Please enter a password(3 of 5): 3
    Please enter a password(4 of 5): 2
    Please enter a password(5 of 5): 1
    Please input m for circulation: 1
  2. 输出

    Order of departure: 1 2 3 4 5 

八、 遇到的问题和解决方法

在编写代码时,我的问题主要出现在出列函数void SlNode_pop(SlNode *r,int k);这一块,总结如下:

(1) 输出的编号问题

  • 描述

    我最开始的思路是在循环的时候通过%运算来输出编号,但后来发现这样的运算总是会出现重复的编号

  • 解决办法

    将编号以id的形式在定义链表时就将其定义为链表的属性

(2) 当密码为1时

  • 描述

    由于我的出列算法的思路是r在目标节点的上一个节点,这样是为了方便弹出目标节点,但m == 1时,r就等于目标节点了

  • 解决办法

    r = r->next;改为判断语句if(k != 1) r = r->next;

(3) 当首个循环次数,即m == 1

  • 描述

    这是上一个问题的后续,因为r最开始的时候等于id == 1的节点,所以当m == 1时,该节点就是目标节点。

  • 解决办法

    r == hh为首节点),这保证了如果m == 1,r依旧是目标节点的上一个节点。之后再在外循环for(i=0;i<n;i++)内部增加:

    if(r->id == 0)//防止第一个节点就是目标节点
    {
        if(k == 1)
        {
            printf("%d ",r->next->id);
            k = r->next->data;
            // 弹出目标节点
            r->next = r->next->next;
            for(int k=1;k<n;k++) r = r->next;
            r->next = r->next->next;
            r = r->next;
        }
        else
        {
            r = r->next;
            i--;
        }
    }

    之后再把原先的代码加入到else{ }即可

九、实验收获与感想

  1. 通过这个实验,我对于链表,尤其是循环链表有了更深的理解。
  2. 而这次的实验也让我得到了不少教训,在编程时,尽量模块化,这样就不会出现一发而动全身的情况。我的很多问题就是模块不清晰产生的

十、附录

源程序文件清单:

  • Josephus.c

公子宇

2021/12/12  阅读:22  主题:自定义主题1

作者介绍

公子宇