[关闭]
@coder-pig 2019-05-31T06:06:07.000000Z 字数 4461 阅读 1137

小猪的数据结构辅助教程——2.5 经典例子:约瑟夫问题的解决

数据结构


约瑟夫问题的解析

关于问题的故事背景就不提了,我们直接说这个问题的内容吧:

一堆人,围成一个圈,然后规定一个数N,然后依次报数,当报数到N,这个人自杀,其他人鼓掌!啪啪啪,
接着又从1开始报数,报到N又自杀...以此类推,直到死剩最后一个人,那么游戏结束!

这就是问题,而我们用计算机模拟的话,用户输入:N(参与人数),M(第几个人死),结果返回最后一个人!
类似的问题有跳海问题,猴子选王等,下面我们就以N = 41和M = 3作为输入参数,使用不同的方法来
解决约瑟夫问题!


1.使用C语言的数组来解决

流程解析

这里我们用数组来模拟报数的流程,使用一个标记数组,1代表人没死,0代表已经死了!

  • Step 1:获取人数,第几个人死,初始化标记数组,将数组置为1
  • Step 2:使用一个变量last来统计剩下没死的人数 > 1作为循环条件
    1)判断标记数组中的元素是不是1,1代表没死,没死继续循环,这里很巧妙地用了这段代码:
    if(!tag[i%n])continue; 如果执行这个说明tag[i%n] == 0说明这B前面已经死了,而不直接
    用i,而是用i % n是因为,可能出现n少于m的情况!
    2)判断是否移动了m个人,是的话把这个人杀掉,就是数组对应下标设置为0,同时打印输出,
    统计人数的变量 -1;否则:判断是否移动m个人的变量++;
  • Step 3:使用循环链表遍历数组,找到不为0的元素,打印输出下标即可

代码实现:

  1. #include <stdio.h>
  2. int main()
  3. {
  4. //参数: n(人数),m(第m个人死),last(剩余的人数)
  5. int i,j,n,m,last;
  6. int tag[100];
  7. printf("输入参加的人数:\n");
  8. scanf("%d",&n);
  9. printf("输入每隔多少死一个人:\n");
  10. scanf("%d",&m);
  11. printf("\n准备报数!\n\n");
  12. //初始化数组
  13. for(i = 0;i < n;i++)
  14. {
  15. tag[i] = 1;
  16. }
  17. //开始报数
  18. j = 1;
  19. last = n;
  20. for(i = 0;last > 1;i++)
  21. {
  22. if(!tag[i%n])continue;
  23. if(j == m)
  24. {
  25. j = 1;
  26. tag[i%n] = 0;
  27. printf("第%d个人自杀了,大家快鼓掌!啪啪啪!\n",(i%n)+1);
  28. last--;
  29. }
  30. else j++;
  31. }
  32. for(i = 0;i < n;i++)if(tag[i])break;
  33. printf("第%d个人活下来了!\n",i+1);
  34. return 0;
  35. }

运行截图


2.使用循环链表来解决

上面使用数组来模拟报数,好像不太容易理解,要不我们用上一节学到的循环链表来嗨一下,
循环链表是一个环,我们只要把报到的结点删除掉,然后重新报数...最后剩下的结点就是没死
的那个了!下面我们写代码来实现下!
PS:代码还是蛮简单的,有不理解,可以自己画下图~

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. //定义循环链表的存储结构
  5. typedef struct LNode
  6. {
  7. int data; //数据域
  8. struct LNode *next; //指针域
  9. }LNode;
  10. typedef struct LNode *LinkList;
  11. //定义循环链表的初始化方法
  12. LinkList createList(int n)
  13. {
  14. printf("\n初始化循环链表\n\n");
  15. LinkList head,s,p;
  16. int i = 1;
  17. head = (LinkList)malloc(sizeof(LNode));
  18. p = head;
  19. if(n != 0)
  20. {
  21. while(i <= n)
  22. {
  23. s = (LinkList)malloc(sizeof(LNode));
  24. s ->data = i++; //为链表初始化,第一个结点值为1,第二个为2这样以此类推
  25. p ->next = s;
  26. p = s;
  27. }
  28. s->next = head->next;
  29. }
  30. free(head);
  31. return s->next;
  32. }
  33. int main()
  34. {
  35. int n,m,i;
  36. printf("输入参加的人数:\n");
  37. scanf("%d",&n);
  38. printf("输入每隔多少死一个人:\n");
  39. scanf("%d",&m);
  40. LinkList p = createList(n);
  41. LinkList temp;
  42. m %= n; //为了防止报数的人大于参与的人,求余可以理解为重头开始
  43. while(p != p ->next)
  44. {
  45. for(i = 1;i < m -1;i++)
  46. {
  47. p = p ->next;
  48. }
  49. printf("第%d个人自杀了\t",p ->next->data);
  50. //删除第m个结点
  51. temp = p ->next;
  52. p ->next = temp ->next;
  53. free(temp);
  54. p = p ->next;
  55. }
  56. printf("\n第%d个人活下来了!\n\n", p->data );
  57. return 0;
  58. }

运行截图


3.数学方法来解决

上面讲述的两种解决约瑟夫问题的方法都是模拟一个报数的流程,对付一些小的数据量
还可以,但是假如我们输入的数据量很大的时候,就会显得很笨重,我们需要使用一些
数学策略来解决这个问题,有这样一个递推公式:
f[ 1 ]=0;
f[ i ]=(f[ i-1 ]+m)%i; (i>1)

而我们根据上面这个递推公式,写出如下代码:

实现代码

  1. #include <stdio.h>
  2. int main()
  3. {
  4. int n, m, i, s=0;
  5. printf ("N M = ");
  6. scanf("%d%d", &n, &m);
  7. for (i=2; i<=n; i++)s=(s+m)%i;
  8. printf ("最后一个剩下的人: %d\n", s+1);
  9. return 0;
  10. }

运行截图

卧槽,这是何等的卧槽,就for(i=2; i<=n; i++)s=(s+m)%i; 这样一个东西就得出结果了?
我选择死亡....
好吧,又一次体会到数学的流弊之处,果然玩算法的数学必须得好,笔者的数学太屎,推导不出
k' = (k + m)%i这条公式...这里贴下网上别人的解释吧:


4.约瑟夫问题的增强版

题目
假如现在是不固定报数,而是每人次优一个密码,从第一个持有密码的人开始,把他作为
报数的M值,从第一个数开始报数,当报数到M时候,报数的人出列,拿出他的密码,把密码
作为报数的M值,接着依次下去..直到全部人出列,游戏结束!

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX_SIZE 100
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK 1
  7. #define ERROR 0
  8. //定义循环链表的存储结构
  9. typedef int Status;
  10. typedef struct LNode
  11. {
  12. int id; //第几个人
  13. int pawd; //密码
  14. struct LNode *next; //指针域
  15. }LNode;
  16. typedef struct LNode *LinkList;
  17. //1.定义一个创建结点的方法
  18. LNode *GetNode(int pid,int ppawd)
  19. {
  20. LinkList p;
  21. p = (LinkList)malloc(sizeof(LNode));
  22. if(!p)return ERROR;
  23. p ->id = pid;
  24. p ->pawd = ppawd;
  25. p ->next = NULL;
  26. return p;
  27. }
  28. //2.创建循环单链表
  29. Status ListCreate(LinkList L,int n)
  30. {
  31. int i,ppawd;
  32. LinkList p,q;
  33. for(i = 1;i <= n;i++)
  34. {
  35. printf("请输入第%d个人持有的密码:",i);
  36. scanf("%d",&ppawd);
  37. p = GetNode(i,ppawd);
  38. if(L == NULL)
  39. {
  40. L = q = p;
  41. q ->next = L;
  42. }else{
  43. p ->next = q ->next;
  44. q ->next = q;
  45. q = p;
  46. }
  47. }
  48. printf("完成单向循环链表的创建!\n");
  49. return OK;
  50. }
  51. //3.判断循环单链表是否为空
  52. Status ListEmpty(LinkList L)
  53. {
  54. if(!L)return TRUE;
  55. return FALSE;
  56. }
  57. //4.打印循环链表当前的所有元素
  58. void ListPrint(LinkList L)
  59. {
  60. LinkList p = L;
  61. if(ListEmpty(L))return;
  62. do{
  63. printf("第%d个人的密码为:%d\n",p ->id,p ->pawd);
  64. p = p ->next;
  65. }while(p != L);
  66. getchar();
  67. }
  68. //5.开始游戏
  69. void StartGame(LinkList L,int startpawd)
  70. {
  71. int i,isFlag = 1;
  72. LinkList p,q,r;
  73. p = q = L;
  74. //让p指向尾部结点,为删除做准备
  75. while(p ->next != L)p = p ->next;
  76. while(isFlag)
  77. {
  78. for(i = 1;i < startpawd;i++)
  79. {
  80. p = q;
  81. q = q ->next;
  82. }
  83. if(p == q)isFlag = 0;
  84. r = q; //删除q指向的结点,有人出列
  85. p ->next = q ->next;
  86. q = q->next;
  87. startpawd = q ->pawd;
  88. printf("第%d个人出列,他手持的密码是:%d\n",r ->id,r ->pawd);
  89. free(r);
  90. }
  91. L = NULL;
  92. getchar();
  93. }
  94. int main()
  95. {
  96. int n, m;
  97. LinkList L = NULL;
  98. while(1)
  99. {
  100. printf("请输入人数n(最多%d个): ", MAX_SIZE);
  101. scanf("%d", &n);
  102. printf("和初始密码m: ");
  103. scanf("%d", &m);
  104. if (n > MAX_SIZE)
  105. {
  106. printf("人数太多,请重新输入!\n");
  107. continue;
  108. }
  109. else
  110. break;
  111. }
  112. ListCreate(L,n);
  113. printf("\n------------ 循环链表原始打印 -------------\n");
  114. ListPrint(L);
  115. printf("\n-------------删除出队情况打印 -------------\n");
  116. StartGame(L, m);
  117. return 0;
  118. }

运行截图


5.本节代码下载

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu1.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu2.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu3.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu4.c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注