用数学方法解约瑟夫环

2024-06-11 14:08
文章标签 约瑟夫 数学方法

本文主要是介绍用数学方法解约瑟夫环,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

5.5.4  用数学方法解约瑟夫环

原文:http://book.51cto.com/art/201403/433941.htm


上面编写的解约瑟夫环的程序模拟了整个报数的过程,程序运行时间还可以接受,很快就可以出计算结果。可是,当参与的总人数N及出列值M非常大时,其运算速度就慢下来。例如,当N的值有上百万,M的值为几万时,到最后虽然只剩2个人,也需要循环几万次(M的数量)才能确定2个人中下一个出列的序号。显然,在这个程序的执行过程中,很多步骤都是进行重复无用的循环。


那么,能不能设计出更有效率的程序呢?


办法当然有。其中,在约瑟夫环中,只是需要求出最后的一个出列者最初的序号,而不必要去模拟整个报数的过程。因此,为了追求效率,可以考虑从数学角度进行推算,找出规律然后再编写程序即可。


为了讨论方便,先根据原意将问题用数学语言进行描述。


问题:将编号为0~(N–1)这N个人进行圆形排列,按顺时针从0开始报数,报到M–1的人退出圆形队列,剩下的人继续从0开始报数,不断重复。求最后出列者最初在圆形队列中的编号。


下面首先列出0~(N–1)这N个人的原始编号如下:




根据前面曾经推导的过程可知,第一个出列人的编号一定是(M–1)%n。例如,在41个人中,若报到3的人出列,则第一个出列人的编号一定是(3–1)%41=2,注意这里的编号是从0开始的,因此编号2实际对应以1为起点中的编号3。根据前面的描述,m的前一个元素(M–1)已经出列,则出列1人后的列表如下:




根据规则,当有人出列之后,下一个位置的人又从0开始报数,则以上列表可调整为以下形式(即以M位置开始,N–1之后再接上0、1、2……,形成环状):




按上面排列的顺序重新进行编号,可得到下面的对应关系:
 



即,将出列1人后的数据重新组织成了0~(N–2)共N–1个人的列表,继续求n–1个参与人员,按报数到M–1即出列,求解最后一个出列者最初在圆形队列中的编号。


看出什么规律没有?对了,通过一次处理,将问题的规模缩小了。即,对于N个人报数的问题,可以分解为先求解(N–1)个人报数的子问题;而对于(N–1)个人报数的子问题,又可分解为先求[(N–1)–1]人个报数的子问题,……。


问题中的规模最小时是什么情况?就是只有1个人时(N=1),报数到(M–1)的人出列,这时最后出列的是谁?当然只有编号为0这个人。因此,可设有以下函数:
 



那么,当N=2,报数到(M–1)的人出列,最后出列的人是谁?应该是只有一个人报数时得到的最后出列的序号加上M,因为报到M-1的人已出列,只有2个人,则另一个出列的就是最后出列者,可用公式表示为以下形式:
 



通过上面的算式计算时,F(2)的结果可能会超过N值(人数的总数)。例如,设N=2,M=3(即2个人,报数到2时就出列),则按上式计算得到的值是:
 



一共只有2人参与,编号为3的人显然没有。怎么办?由于是环状报数,因此当两个人报完数之后,又从编号为0的人开始接着报数。根据这个原理,即可对求得的值与总人数N进行模运算,即:
 


5.5.4  用数学方法解约瑟夫环(2)

即,N=2,M=3(即有2个人,报数到3–1的人出列)时,循环报数最后一个出列的人的编号为1(编号从0开始)。我们来推算一下,如下所示,当编号为0、1的两个人循环报数时,编号为0的人报的数为0和2,当报到2(M–1)时,编号0出列,最后剩下编号为1的人,所以编号为1的人最后出列。

根据上面的推导过程,可以很容易推导出,当N=3时的公式:

同理,也可以推导出参与人数为N时,最后出列人员编号的公式:

其实,这就是一个递推公式,公式包含以下两个式子:

有了这个递推公式,再来设计程序就很简单了,可以用递归的方法来设计程序,具体代码如下:
 

 
  1. #include <stdio.h> 
  2. int main(void)  
  3. {  
  4.     int n,m,i,s=0;  
  5.     printf ("输入参与人数N和出列位置M的值 = ");  
  6.     scanf("%d%d",&n,&m);  
  7.       
  8.     printf ("最后出列的人最初位置是 %d\n",josephus(n,m));  
  9.     getch();  
  10.     return 0 ;  
  11. }  
  12.  
  13. int josephus(int n,int m)  
  14. {  
  15.     if(n==1)  
  16.         return 0;  
  17.     else  
  18.         return (josephus(n-1,m)+m)%n;  
  19. }  

在以上代码中,定义了一个递归函数josephus(),然后在主函数中调用这个函数进行   运算。

编译执行以上程序,输入N和M的值,可以很快得到最后出列人的编号,输入N=8,M=3,得到的结果如图5-19所示(注意编号是从0开始)。
 

使用递归函数会占用计算机较多的内存,当递归层次太深时可能导致程序不能执行,因此,也可以将程序直接编写为以下的递推形式:
 

 
  1. #include <stdio.h> 
  2. int main(void)  
  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++)  
  8.         s=(s+m)%i;  
  9.     printf ("最后出列的人最初位置是 %d\n",s);  
  10.     getch();  
  11.     return 0 ;  
  12. }  

这段代码执行的结果与递归程序执行结果完全相同。

可以看出,经过一些数学推导,最后总结出规律简化程序,将几十行的代码缩减到几行。更主要的是,程序执行的效率得到大大的提升,省去了很多重复的循环,既使求解的N和M值很大,也不会成为问题

这篇关于用数学方法解约瑟夫环的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1051386

相关文章

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

PHP约瑟夫环问题

#循环 function circle($arr,$idx,$k){for($i=0;$i<$idx;$i++){$tmp = array_shift($arr);array_push($arr,$tmp);}$j = 1;while(count($arr) > 0){$tmp = array_shift($arr);if($j++%$k == 0){echo $tmp."\n";}else{a

约瑟夫问题(多解)——POJ 3750

对应POJ题目:点击打开链接 小孩报数问题 Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u Submit Status Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,

约瑟夫问题的五种实现方法

一、队列 #include <stdio.h>#include <queue>using namespace std;queue<int> q;int n, m, cnt, out, a[101]; //a[i]=0表示在圈里 int main(){scanf("%d %d", &n, &m);for(int i=1; i<=n; i++){q.push(i);}while(!q

理解 约瑟夫环

总结了个小经验,有时候光靠看是看不出什么端倪来的,还必须得动下笔,比划比划也许就那么简单 #include <stdio.h> #include <stdlib.h> typedef struct Node {  int data;  struct Node *next; }Node;   Node *CreatList(int n)    //创建一个含n个人的循环链表 { int i;

约瑟夫环和一元多项式

约瑟夫环 一、问题描述     假设有 n 个人围成一圈,从第一个人开始报数,报数到 m 的人将被淘汰出圈,然后从下一个人开始继续从 1 报数,如此重复,直到最后只剩下一个人。求最后剩下的这个人的编号。 二、问题分析 可以使用循环链表来模拟这个过程。 1.创建一个包含 n 个节点的循环链表,每个节点代表一个人,节点中存储这个人的编号。 2.从第一个节点开始报数,每报到 m,就将对应

第十八题(约瑟夫环问题)

第18 题: 题目:n 个数字(0,1,…,n-1)形成一个圆圈,从数字0 开始, 每次从这个圆圈中删除第m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数 字)。 当一个数字删除后,从被删除数字的下一个继续删除第m 个数字。 求出在这个圆圈中剩下的最后一个数字。 这道题网上讲解的很多,主要有两种方法: 第一种,采用循环链表实现,建立一个有n个节点的循环链表,然后从链表头开

【C/C++】约瑟夫环问题

目录 题目描述输入描述输出描述 示例题解 题目描述 n个人(0,1,2,3,4…n-1),围成一圈,从编号为k的人开始报数,报数报到m的人出队(报数是1,2,…m这样报的)。下次从出队的人之后开始重新报数,循环往复,当队伍中只剩最后一个人的时候,那个人就是大王。现在,给定n,k,m, 请你求出大王的编号。 输入描述 输入一行包含三个整数n,k,m 1<=n<=100,1<=

桟和队列--约瑟夫问题

Time Limit: 1000MS Memory limit: 65536K 题目描述 n个人想玩残酷的死亡游戏,游戏规则如下: n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。 请输出最后一个人的编号。 输入 输入n和m值。 输出 输出胜利者的编号。 示例输入 5 3

约瑟夫问题:有n个人围成一圈,顺序报数(1~3),报到3退出

【描述】 有n个人围成一圈,顺序排号,从第一个人开始报数(从1~3报数),凡报到3的人退出圈子,问最后留下的人原来排在第几号。 【C语言】 #include<stdio.h>int main() {int num[50];int *p;int i, k, m, n;scanf("%d", &n);p = num;for (i = 0; i < n; i++)*(p + i) = i +