秒懂约瑟夫环

秒懂约瑟夫环转自: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)
blank

相关推荐

  • Python websocket_php需要编译吗

    Python websocket_php需要编译吗这里很坑爹………地址换了….网上到处都是旧的github地址….更郁闷的是旧地址的代码在centos等各个linux都能编译通过,但是到了mac就郁闷了,各种报错…..坑爹来的然后很多人说hs没在维护了,那是因为他们看到的是旧的git代码地址….囧…..搞死我了,我还真以为他不更新了,看到git项目,3年没更新了,心都凉了……各种找错误各种…

  • yourphp常用标签

    yourphp常用标签

  • C# 中List与json字符串的相互转换「建议收藏」

    C# 中List与json字符串的相互转换「建议收藏」将list转换成json字符串List<HingeType>hinges=[{id:1,name:hingeOne},{id:2,name:hingeTwo},···];StringhingeString=Newtonsoft.Json.JsonConvert.SerializeObject(hinges);将json字符串转换成listList<HingeType>hingeList=Newtonsoft.Json.JsonConvert.Deseria

    2022年10月17日
  • 怎么新建pytest的ini文件_qt读写配置文件

    怎么新建pytest的ini文件_qt读写配置文件前言pytest配置文件可以改变pytest的运行方式,它是一个固定的文件pytest.ini文件,读取配置信息,按指定的方式去运行查看pytest.ini的配置选项pytest-h找到以下

  • Java3大框架学习,今年最受欢迎的后端框架

    Java3大框架学习,今年最受欢迎的后端框架作为20多年来最流行的编程语言,Java拥有一整套后端框架,但它们的可靠性和多功能性差异很大。当今最流行的Java后端框架是:SpringFramework Struts HibernateJava后端框架的比较:框架 优势 弱点 SpringFramework 1.许多现成的组件对Web应用程序有帮助2.DI和IoC创建灵活的配置3.易于暴露RESTful服务 1.许多依赖2.丰富的选择可能导致混乱3.学习曲线,因为它可以做很多..

  • 初识业务架构图_管理架构图

    初识业务架构图_管理架构图文章目录什么是业务架构图?业务架构图规范宏观微观设计步骤分层分模块分功能实例什么是业务架构图?是将用户需求进行宏观系统抽象进行描述和展示,是表达业务层级和关系的工具,目的是将简单的业务逻辑简单化,降低理解难度,这个图是给用户和各级领导看的。业务架构图规范宏观1.宏观:横向:并列结构,级别是相同的;纵向:要有分层的思想,整体上有层次感,上层是依赖于下层的,越底层的,越是基础服务,同时也更为重要;对称:要讲究对称美,尽可能地功能结构分配均匀;虚线框:多个模块,逻辑上可以归为一块时可以使用虚线

    2022年10月11日

发表回复

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

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