秒懂约瑟夫环

秒懂约瑟夫环转自:https://blog.csdn.net/byn12345/article/details/79487253约瑟夫生者死者游戏约瑟夫游戏的大意:30个游客同乘一条船,因为严重超载,加上风浪大作,危险万分。因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入大海…

大家好,又见面了,我是你们的朋友全栈君。

转自:https://blog.csdn.net/byn12345/article/details/79487253

约瑟夫生者死者游戏

约瑟夫游戏的大意:30个游客同乘一条船,因为严重超载, 加上风浪大作,危险万分。因此船长告诉乘客,只有将全船 一半的旅客投入海中,其余人才能幸免于难。无奈,大家只 得同意这种办法,并议定30 个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入大海中,然后再从 他的下一个人数起,数到第9人,再将他投入大海中,如此 循环地进行,直到剩下 15 个游客为止。问:哪些位置是将 被扔下大海的位置? 

不失一般性,将 30 改为一个任意输入的正整数 n,而报数 上限(原为9)也为一个任选的正整数k

 

第一次看到这个题目,我首先想到的是用 链表 或者是 数组 来模拟,但是当我写完之后,与大神对答案,发现他的c语言代码是这么写的:

int ysfdg ( int sum, intvalue, intn)
{

    if ( n == 1 )
        return ( sum + value – 1 ) %sum;
    else
        return ( ysfdg ( sum-1, value,n-1 ) +value ) %sum;
}

7行。。。。。。再见(已经不能做朋友了吗。。。)

sum指的是总人数,value指的是每次最大报到的数值,n是第n次,该函数每次可以求出第n次扔海里的人的编号,( ysfdg指的是约瑟夫递归 ) 。

大神飘然而去,而我懵逼了一天,才明白了这段代码的意思。

 

举个栗子:

总人数sum为10人,从0开始,每报到4就把一人扔下去(value=4)。

初始情况为:

0   1   2   3   4   5   6   7   8   9

扔下去一个之后:

0   1   2        4   5   6   7   8   9

此时,这些编号已经不能组成一个环,但是可以看出4至2之间还是连着的(4 5 6 7 8 9 0 1 2),且下一次报数将从4开始。但是,之后的报数将总要考虑原编号3处的空位问题。

如何才能避免已经产生的空位对报数所造成的影响呢?

可以将剩下的9个连续的数组成一个新的环(将2、4连接),这样报数的时候就不用在意3的空位了。但是新产生的环的数字并非连续的,报数时不像之前那样好处理了(之前没人被扔海里时下一个报数的人的编号可以递推,即(当前编号+1)%sum ),无法不借助存储结构得知下一个应该报数的现存人员编号。

如何使新环上的编号能够递推来简化我们之后的处理呢?

可以建立一种有确定规则的映射,要求映射之后的数字可以递推,且可以将在新环中继续按原规则报数得到的结果逆推出在旧环中的对应数字。

方法:将它与  sum-1 个人组成的(0 ~ sum-1)环一 一映射。

比如之前的栗子,将剩余的 9 人与  9 人环(0~8)一 一映射。既然 3 被扔到海里之后,报数要从4开始 (4 其实在数值上等于最大报数值),那么就将4映射到0~8的新环中0的位置,也就是说在新环中从0开始报数即可,且新环中没有与3对应的数字,因此不必担心有空位的问题。从旧环的 4 开始报数等效于从新环中的 0 开始报数。

原始   0   1   2   3   4   5   6   7   8   9

旧环   0   1   2        4   5   6   7   8   9

新环   6   7   8        0   1   2   3   4   5

新环有这么一个优势:  相比于旧环中2与4之间在数学运算上的不连续性,新环8和0之间在对9取余的运算中是连续的,也就是说根本不需要单独费心设计用以记录并避开已产生的空位(如 编号3)的机制 ,新环的运算不受之前遗留结果的掣肘。同时只要能将新环与旧环的映射关系逆推出来,就能利用在新环中报数的结果退出之前旧环中的报数结果。

以下是新环与旧环中下一个要人扔海里的人位置:

 

旧环   0   1   2        4   5   6   7   8   9

                                             ^

新环   6   7   8        0   1   2   3   4   5

                                             ^

如何由新环中的 3 得到旧环中的 7 呢。其实可以简单地逆推回去 : 新环是由  (旧环中编号-最大报数值)%旧总人数  得到的,所以逆推时可以由 ( 新环中的数字 + 最大报数值 )% 旧总人数 取得。即 old_number = ( new_number + value ) % old_sum.

  如 : ( 3 + 4 ) % 10 =7 .

也就是说在,原序列( sum ) 中第二次被扔入海中编号可以由新序列( sum – 1) 第一次扔海里的编号通过特定的逆推运算得出。

而新序列 (sum -1)也是(从0开始)连续的,它的第二次被扔入海中的编号由可以由(sum – 2)的第一次扔入海里的编号通过特定的逆推运算得出,并且它的第二次被扔入海中的编号又与原序列中的第三次被扔入海里的编号是有对应关系的。

也求是说有以下推出关系:

(sum-2)环的第1次出环编号 >>>(sum-1)环的第2次出环编号 >>>(sum)环的第3次出环编号

即 在以 k 为出环报数值的约瑟夫环中, m人环中的第n次出环编号可以由 (m-1) 人环中的第 (n-1) 次出环编号通过特定运算推出。

幸运的是,第一次出环的编号是可以直接求出的,也就是说,对于任意次出环的编号,我们可以将之一直降到第一次出环的编号问题,再一  一 递推而出。

注意 以下图示中的环数字排列都是顺序的,且从编号0开始。

秒懂约瑟夫环

由图知,10人环中最后入海的是4号,现由其在1人环中的对应编号0来求解。

 秒懂约瑟夫环                                                                                                                         

通过以上运算,其实我们已经求出分别位于9个环中九个特定次数的结果,只不过我们需要的是10人环的结果罢了。

这种方法既可以写成递归也可以写成循环,它对于求特定次数的出环编号效率较高。

递归就比较好写了,出口即是当次数为1时。

实际编号是从1开始,而不是0,输出时要注意转换。

借此就可以看懂那个大神的代码了。

以下是三种约瑟夫环解法(数组,链表,递归)的c语言代码,作者水平不高,将就看看吧 ╮(╯_╰)╭:

 

[cpp] view plain copy

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #define FAIL 0  
  4. #define SUCCESS 1  
  5.   
  6. typedef struct gamenode  
  7. {  
  8.     int number;  
  9.     struct gamenode* next;  
  10.  } node;  
  11.   
  12. //读入初值  
  13. int getvalue(int* sum,int* count,int* alive)  
  14. {  
  15.     printf(“请输入要参与约瑟夫生存游戏的人数:(人数>0)\n”);  
  16.     while(1)  
  17.     {  
  18.         scanf(“%d”,sum);  
  19.         if(*sum>0)  
  20.         break;  
  21.         printf(“输入无效,请重新输入。\n”);  
  22.     };  
  23.     printf(“请输入能报到的最大数字:(1<=数字)\n”);  
  24.     while(1)  
  25.     {  
  26.         scanf(“%d”,count);  
  27.         if(*count>=1)  
  28.         break;  
  29.         printf(“输入无效,请重新输入。\n”);  
  30.     };  
  31.     printf(“请输入要求最后存活的人数:(0<=人数<=%d)\n”,*sum);  
  32.     while(1)  
  33.     {  
  34.         scanf(“%d”,alive);  
  35.         if(*alive>=0&&*alive<=*sum)  
  36.         break;  
  37.         printf(“输入无效,请重新输入。\n”);  
  38.     };  
  39.     return SUCCESS;  
  40. }  
  41.   
  42. //数组解法  
  43. int ysfsz(int n,int k,int s)  
  44. {  
  45.     int i=0,*p=NULL,sum=n-k,j=1,o=0,pr=0;  
  46.     if ((p=(int*)malloc(sizeof(int)*n))==NULL)  
  47.     {  
  48.     printf(“FAIL!\n”);  
  49.     return FAIL;  
  50.     }  
  51.     for(i=0;i<n;i++)  
  52.     {  
  53.         p[i]=1;  
  54.     }  
  55.     i=0;  
  56.     while(1)  
  57.     {  
  58.         if (sum==0)  
  59.         break;  
  60.         if (j==s&&p[i]==1)  
  61.         {     
  62.             p[i]=0;  
  63.             j=1;  
  64.             –sum;  
  65.         }  
  66.         else if(p[i]==1)  
  67.         {     
  68.         j++;  
  69.         }  
  70.         i++;  
  71.         i=i%n;      
  72.     }  
  73.     printf(“\n生存下来的人的位置是:”);  
  74.     for(i=0;i<n;i++)  
  75.     {  
  76.         if(p[i]==1)  
  77.         printf(“%d “,i+1);  
  78.     }  
  79.     printf(“\n”);  
  80.     printf(“\n扔海里的位置是:”);  
  81.     for(i=0;i<n;i++)  
  82.     {  
  83.         if(p[i]==0)  
  84.         printf(“%d “,i+1);  
  85.     }  
  86.     printf(“\n”);  
  87.     free(p);  
  88.     return SUCCESS;  
  89. }  
  90.   
  91. //链表解法  
  92. int ysflb(int n,int k,int s)  
  93. {  
  94.     node *h=NULL,*p=NULL,*q=NULL;  
  95.     int i=0;  
  96.     if ((h=(node*)malloc(sizeof(node)*n))==NULL)  
  97.     {  
  98.     printf(“FAIL!\n”);  
  99.     return FAIL;  
  100.     }  
  101.     h->number=1;  
  102.     h->next=h;  
  103.     q=h;  
  104.     for(i=1;i<n;i++)  
  105.     {  
  106.         if ((p=(node*)malloc(sizeof(node)*n))==NULL)  
  107.         {  
  108.         printf(“FAIL!\n”);  
  109.         exit (-1);  
  110.         }  
  111.         else  
  112.         {      
  113.             p->next=NULL;  
  114.             p->number=i+1;  
  115.             q->next=p;  
  116.             q=q->next;  
  117.         }  
  118.     }  
  119.     q->next=h;  
  120.     p=h;  
  121.     i=1;  
  122.     k=n-k;  
  123.     while(k>0)  
  124.     {  
  125.         if(i==s)  
  126.         {  
  127.             if(p!=p->next)  
  128.             {  
  129.                 q->next=p->next;  
  130.                 printf(“%d号已被扔进海里。\n”,p->number);  
  131.                 free(p);  
  132.                 p=q->next;  
  133.             }  
  134.             else  
  135.             {  
  136.                 printf(“%d号已被扔进海里。\n”,p->number);  
  137.                 p=q=h=NULL;  
  138.             }  
  139.             –k;  
  140.         }  
  141.         else  
  142.         {  
  143.             p=p->next;  
  144.             q=q->next;  
  145.         }  
  146.         ++i;  
  147.         if(i>=s+1)  
  148.         i=1;  
  149.     }  
  150.     if(p!=NULL)  
  151.     {  
  152.         printf(“幸存下来的人有:”);  
  153.         h=p;  
  154.         p=p->next;  
  155.         while(p!=h)  
  156.         {  
  157.             q=p->next;  
  158.             printf(“%d “,p->number);  
  159.             free(p);  
  160.             p=q;  
  161.         }  
  162.         printf(“%d “,h->number);  
  163.         free(h);  
  164.     }  
  165.     else  
  166.     printf(“全部扔海里去了。\n”);  
  167.     return SUCCESS;  
  168. }  
  169.   
  170. //递归解法  
  171. int ysfdg(int sum,int value,int n)  
  172. {  
  173.     if(n==1)  
  174.         return (sum+value-1)%sum;  
  175.     else  
  176.         return (ysfdg(sum-1,value,n-1)+value)%sum;  
  177. }  
  178.   
  179. //主函数  
  180. int main(void)  
  181. {  
  182.     int sum=0,count=0,alive=0,i=0;  
  183.       
  184.     //读入总人数,报数值,存活人数  
  185.     getvalue(&sum,&count,&alive);  
  186.       
  187.     /*————————————————————*/      
  188.       
  189.     //1.约瑟夫环的数组解法  
  190.     //ysfsz(sum,alive,count);  
  191.       
  192.     //2.约瑟夫环的链表解法  
  193.     //ysflb(sum,alive,count);  
  194.   
  195.     //3. 约瑟夫环递归解法  
  196.     for(i=1;i<=sum-alive;i++)  
  197.         printf(“第%2d个被扔海里人的编号:%2d\n”,i,ysfdg(sum,count,i)+1);  
  198.           
  199.     return 0;  
  200. }  
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136059.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Eclipse中代码字体背景变红/变黄/变绿

    Eclipse中代码字体背景变红/变黄/变绿如图所示:运行之后,突然这样。到底是什么原因导致的呢?:经过查找资料可知:因为Eclipse中有覆盖代码功能(绿色表示代码被执行到,红色表示代码没有被执行到,黄色表示代码部分执行到)怎么解决这个问题:Remove All Sessions就是点击下图红色框中的部分。                            或者点击window–&gt;Show view –&gt; Other …

  • html静态页面代码_静态网页设计代码

    html静态页面代码_静态网页设计代码这个例子我们做一个游戏静态页面,自动跳转到我们想要玩的游戏或者视频等网站大家也可以根绝我的代码,适当修改一些信息,但是套用我的这个模板请注释下来自我这,我也是初学者,辛辛苦苦写了几个小时,尊重下劳动成果先看效果图:我以张杰为背景图,里面是各种网站跳转,比如我点击:冰火人,他就会跳转到4399的冰火人游戏界面。ok,上代码,我觉得比较简单,就没注释,希望能看懂:<!DOCTYPEhtml><html><headlang=”en”><metacha

  • 大数据技术,Spark核心技术之运行原理

    大数据技术,Spark核心技术之运行原理

  • PyCharm的几个使用技巧(持续更新)[通俗易懂]

    PyCharm的几个使用技巧(持续更新)[通俗易懂]目录引言1、轻松加注释2、让代码自动缩进3、快速自定义文件4、一键全局格式化5、轻松查找与替换6、关闭波浪线引言PyCharm是个十分强大的Python编辑器,笔者在日常的工作中学到了很多该IDE的使用技巧,有的是从别人那里学到的,有的是自己学习的。you  以下将介绍几个简单的PyCharm使用技巧。以windows系统中的PyCharm使用为例。1、轻松加注释多行注释:CTRL+/…

  • idea如何打包war包_idea怎么导入war包

    idea如何打包war包_idea怎么导入war包本文分四个步骤进行讲述步骤一、打开ProjectStructure步骤二、增加打包配置(包括项目、打包类型、导出路径等等)步骤三、修改war包配置步骤四、打包步骤一、打开ProjectStructure打开idea开发工具,在File下找到ProjectStructure…(注意:低版本的idea在Nevigate目录下找)步骤二、增加打包配置(包括项目、打包类型、导出路径等…

  • IIS http 500 内部服务器错误 (解决方案)「建议收藏」

    IIS http 500 内部服务器错误 (解决方案)「建议收藏」 第一步:“开始”->“设置”->“控制面板”->“管理工具”->“组件服务”中,“控制台根目录”->“组件服务”->“计算机”->“我的电脑”->“COM+应用程序”中,有一个“IISOut-Of-ProcessPooled”鼠标右键“属性”–“标识”–把“此用户”调整为“交互式用户–目前已登录的用户”。然后“确定”,再鼠标右键“属性”–“启动”.第二步:“开始”->“管理工具”-

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号