精华内容
下载资源
问答
  • 猴子选大王--约瑟夫问题浅析 猴子选大王--约瑟夫问题浅析  猴子选大王问题是一个十分经典的算法问题,这个问题是这样的:一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1...

    猴子选大王--约瑟夫问题浅析

    猴子选大王--约瑟夫问题浅析

      猴子选大王问题是一个十分经典的算法问题,这个问题是这样的:一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。

      这个问题要解决起来并不难,但求解的方法很多;题目的变化形式也很多,而我们统称这类问题为约瑟夫问题。这类题目基本的描述为:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。下面我们先来分析一下解决这类问题的几个步骤。

      (1)由于对于每个人只有死和活两种状态,因此可以用布朗型数组标记每个人的状态,可用true表示死,false表示活。

      (2)开始时每个人都是活的,所以数组初值全部赋为false。

      (3)模拟杀人过程,直到所有人都被杀死为止。

     

      题目中N个人围成一圈,因而启发我们用一个循环的链来表示,可以使用数组结构来构成一个循环链表。结构中有两个成员,其一为指向下一个人的指针,以构成环形的链;其二为该人是否被杀死的标记,为1表示还存活。从第一个人开始对还存活的人进行计数,每数到M时,将结构中的标记改为0,表示该人已被杀死。这样循环计数直到有15个人被杀死为止。

      但是,无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),当n,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程。因此如果要追求效率,就要打破常规,实施一点数学策略。

     

      

    为了讨论方便,先把问题稍微改变一下,并不影响原意:

    问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。

    我们知道第一个人(编号一定是(m-1)) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m mod n的人开始):

    k k+1 k+2 ... n-2,n-1,0,1,2,... k-2

    并且从k开始报0。

    我们把他们的编号做一下转换:

    k --> 0

    k+1 --> 1

    k+2 --> 2

    ...

    ...

    k-2 --> n-2

    变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'=(x+k) mod n

    如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

    令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

    递推公式

    f[1]=0;

    f[i]=(f[i-1]+m) mod i; (i>1)

    有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1

    由于是逐级递推,不需要保存每个f,程序也是异常简单:

     

     1 package com.jredu100.ch4.test;
     2 
     3 import java.util.Scanner;
     4 /**
     5  * 约瑟夫问题
     6  * @author ymyBlogs
     7  *
     8  */
     9 public class Test11 {
    10 
    11     public static void main(String[] args) {
    12         // TODO Auto-generated method stub
    13         int s=0;
    14         int M=3;
    15         Scanner sc=new Scanner(System.in);
    16         System.out.println("请输入人数:");
    17         int n=sc.nextInt();
    18         for(int i=2;i<=n;i++){  //注:此处第一个i=1或者2 都不影响结果 因为i=1时输出的编号为零 零带入公式不影响结果
    19             s=(s+M)%i;
    20         }
    21         System.out.println("最终位置为:");
    22         System.out.println(s+1);
    23     }
    24 
    25 }

     

    这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题了。可见,适当地运用数学策略,不仅可以让编程变得简单,而且往往会成倍地提高算法执行效率。

    转自 博客园https://www.cnblogs.com/ymyBlogs/p/8638082.html

    如有侵权请联系删除

    展开全文
  • 经典C题目猴子选大王,即约瑟夫环,是一个经典的问题,此为模拟法实现。
  • 约瑟夫环 猴子选大王

    2009-10-13 21:12:45
    C语言,数据结构作业 约瑟夫环 猴子选大王
  • 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。 输入 输入两个整数n和m,1<=m<=n<=100。 输出 输出猴王...

    题目描述
    n只猴子围坐成一个圈,按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。
    输入
    输入两个整数n和m,1<=m<=n<=100。
    输出
    输出猴王的编号
    样例输入
    8 3
    样例输出
    7
    代码:

    #include<stdio.h>
    #include<stdlib.h>
    int main()
    {
        int n,m,s=0,i;
        scanf("%d%d",&n,&m);
        for(i=2;i<=n;i++)
        s=(s+m)%i;
        printf("%d",s+1);
        return 0;
    }
    
    

    此类约瑟夫环问题均可以用公式
    如本题中的 s=s(s+m)%i
    ,此类问题求最后留下来的,不用模拟中间过程,与杀人游戏不同,杀人游戏需要模拟中间过程,不需要最后结果。
    推导过程
    F(n,m)=k 表示n个人 ,报数间隔为m的约瑟夫环中,最终胜出者的是从头开始数得第k个人,而且1<k<n。总人数 和 报数间隔确定的话,最终胜出者相对于队头(开始报数者)的位置也就确定了。
    对于F(n+1,m),从头开始数m,一个人出局。出局后,就变成F(n,m)。 所以,再往后数k,就是最终胜出者。所以,对于F(n+1,m),最终胜出者就是从头开始数的第m+k个人。
    由于 k的范围(0<k<n),所以再往后数k个人时,不会受到第一人出局的人的影响。

    即F(n+1,m)=(F(n,m)+m)%(n+1)

    展开全文
  • 猴子选大王-约瑟夫环

    千次阅读 2014-04-07 21:53:40
    jobdu-1188:约瑟夫环-ac 猴子选大王,如此经典的问题

    jobdu-1188:约瑟夫环-ac

    猴子选大王,如此经典的问题

    //jobdu-1188:约瑟夫环-ac
    #include 
       
        
    #include 
        
         
    using namespace std;
    int n,p;
    vector
         
           v;
    vector
          
           ::iterator	it;
    vector
           
            ::iterator tmp; void f_next(vector
            
             & v,vector
             
              ::iterator& it){ //让迭代器指向数组中下一个 if(it==v.end()-1) it=v.begin(); else it++; } int main( ) { bool mark; while(cin>>n>>p){ mark=false; v.clear(); for(int i=0;i
              
             
            
           
          
         
        
       

     

    展开全文
  • Python 猴子选大王约瑟夫环)算法

    千次阅读 2019-03-17 11:51:56
    def KingElect(totalNum, startNum, intervalNum): ... 猴子选大王 totalNum:猴子总数 tartNum:开始序号 intervalNum:间隔数 ''' monkeyList = [] out_order = 0 #出列计数 current_index = 0 #报数...
    def KingElect(totalNum, startNum, intervalNum):
        '''
        猴子选大王
        totalNum:猴子总数
        tartNum:开始序号
        intervalNum:间隔数
        '''
        monkeyList = []
        out_order = 0  #出列计数
        current_index = 0 #报数序列
        monkeyId = startNum  # 初始编号
        for i in range(totalNum):
            # 生成初始队列
            # 例 KingElect(7, 2, 3)
            # range(7) : i = 0 -> 6
            # i=0 monkeyId = 2  monkeyList=[2]
            # i=1 monkeyId = 3  monkeyList=[2,3]
            # i=2 monkeyId = 4  monkeyList=[2,3,4]
            # i=3 monkeyId = 5  monkeyList=[2,3,4,5]
            # i=4 monkeyId = 6  monkeyList=[2,3,4,5,6]
            # i=5 monkeyId = 7  monkeyList=[2,3,4,5,6,7]
            # i=6 monkeyId = 8 8 = 7 +1 monkeyId = 1  monkeyList=[2,3,4,5,6,7,1]
            if monkeyId == totalNum + 1:
                monkeyId = 1
            monkeyList.append(monkeyId)
            monkeyId += 1
        # print(monkeyList,end='  ')
        while(len(monkeyList) > 1):
            out_order     += 1
            current_index += 1
            if(current_index > len(monkeyList)):
                current_index = 1
            if(out_order == intervalNum):
                out = monkeyList.pop(current_index-1)
                # print('%d  %d Out' % (out,out))
                out_order = 0
                # print(monkeyList,end='  ')
                current_index -= 1
            else:
                pass
                # print('%d-'%(monkeyList[current_index - 1]),end='')
        print(monkeyList[0],'Gain the elect')
    if __name__=='__main__':
        KingElect(7, 2, 3)

     

    测试结果
    执行过程
    展开全文
  • 利用猴子选大王约瑟夫问题进行探究,用多种方式进行完成 迅速 简洁
  • 猴子选大王问题(约瑟夫环

    千次阅读 多人点赞 2014-06-03 19:12:08
    猴子选大王问题(约瑟夫环
  • //猴子选大王 function yuesefu($n,$m) { $r=0; for($i=2; $i&lt;=$n; $i++) { $r=($r+$m)%$i; } return $r+1; } echo yuesefu(10,3)."是猴王"; // 每个猴子出列后,剩下的猴子又组成了...
  • 一群猴子一共TOTAL只,需要选出一个猴王,于是它们站成一圈,约定从1开始报数,报到NUMBER时就出局一只猴子,接着继续从1开始报数。直到剩下一只猴子的时候,它就是猴王。 输入 TOTAL:猴子总数 NUMBER:出局的报...
  • 这个问题其实是一个特例,将其中的100和14换成变量 n 和 m ,就是约瑟夫环问题。 思路: 利用链表来解决,每一只猴子的标号存入到链表的一个节点中,将这些节点组成一个链表。为了让它围成一个圈,编程的时候需要...
  • 猴子选大王问题: 一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1到m的顺序围坐一圈, 从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子大王...
  • 猴子选大王 一群猴子新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。...
  • //(约瑟夫环猴子选大王 // 思路:一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去...,如此不停的进行下去,直到最后只剩下...
  • PTA 猴子选大王约瑟夫环问题)

    千次阅读 2020-02-21 15:50:38
    一群猴子新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。如此不断循环,...
  • 环形链表,猴子选大王,数到几出去,从几开始数,由用户输入决定
  • 问题:  设编号为1,2,…,n的n个人围坐一圈(每个人有一个密码(正整数)),约定编号为k(1<=k<...以此类推,直到所有人全部出列,计算出列顺序? 解决思路:  循环链表 ... 3 * 设编号为1,2,…,n的n个人围坐一...
  • c++实验1:猴子选大王约瑟夫环

    千次阅读 2019-03-12 23:09:45
    7-6 猴子选大王 (20 分) 一群猴子新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始...
  • 猴子选大王 【问题描述】要从n只猴子中选出一位大王。它们决定使用下面的方法: n只猴子围成一圈,从1到n顺序编号。从第q只猴子开始,从1到m报数,凡报到m的猴子退出竞选,下一次又从退出的那只猴子的下一只开始从1...
  • // 函数king:猴子选大王 // 参数:a-猴子数组n-1个猴子分别占据下标为~n-1的位置,n-数组长度 // 返回值:新猴王的下标序号 int king(int a[], int n); int main() { int n, a[1000], i; // 定义变量及数组,n-...
  • 猴子选大王 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status 有m个猴子围成一圈,按顺时针编号,分别为1到m。现打算从中选出一个大王。经...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 958
精华内容 383
关键字:

猴子选大王约瑟夫环