C++ 约瑟夫环问题案例详解

 更新时间:2021年8月15日 00:00  点击:2999

在牛客网上做到一道题,是约瑟夫环的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫环问题的解释,下一篇再写题目:

##1.首先,我们先来了解一下什么是约瑟夫环问题:
讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后kill所有人。
于是约瑟夫建议:每次由其他两人一起kill一个人,而被kill的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在kill了除了他和剩余那个人之外的最后一人,他劝服了另外一个没死的人投降了罗马。

我们这个规则是这么定的:
在一间房间总共有n个人(下标0~n-1),只能有最后一个人活命。

按照如下规则去排除人:

所有人围成一圈顺时针报数,每次报到q的人将被排除掉被排除掉的人将从房间内被移走然后从被kill掉的下一个人重新报数,继续报q,再清除,直到剩余一人

你要做的是:当你在这一群人之间时,你必须选择一个位置以使得你变成那剩余的最后一人,也就是活下来。

##2.这就是约瑟夫环问题,接下来我们说个特例初步了解下这种问题的求解思路:

特例:2,当q = 2时候,是一个特例,能快速求解
特例还分两种

###1.思路:注意这里的前提是n = 2^k(也就是2的幂次个人,其他数另外讨论)

如果只有2个人,显然剩余的为1号

如果有4个人,第一轮除掉2,4,剩下1,3,3死,留下1

如果是8个人,先除去2,4,6,8,之后3,7,剩下1,5,除去5,又剩下1了

定义J(n)为n个人构成的约瑟夫环最后结果,则有j(2^k) = 1

J(n) = 2^k – 2^k-1 = 2^k-1     				n=2^k

J(n) = 2^k-1 – 2^k-2 = 2^k-2    			n=2^k-1

………

J(2^2) = 2^2 – 2^1 = 2^1 					n=2^2

递推得到如上结果,起始我们仔细分析也就是每次除去一半的元素,然后剩余的一半继续重复之前的策略,再除去一半。(可想到递归)

结合:J(2) = 1 我知道两个数,从1开始,肯定是2先死,剩下1.

得到:j(2^k) = 1

###2.but当n 不等于 2^k时候,比如9,11这种:

n 不等于 2^k时,就不存在这样的easy的规律了,重新分析:

假设n = 9,这时候如图下:

这里写图片描述

能看出来,我们干掉第一个人也就是2,之后就只剩下8个人了,又回到J(2^k)上了,这时候我们需要的是找到当前的1号元素。
见图下:

这里写图片描述

这时候,我们从3号开始,就成了另外一个规模小1的约瑟夫问题(恰好为2^k的特例)。
这时候,我们可以把3号看成新的约瑟夫问题中的1号位置:
J(8) = J(2^3) = 1,也就是说这里的1代表的就是上一个问题中的3号

So:J(9) = 3
答案为3号

####同理可知所有的非2^k的数都是这样:
假设n = 2^k + t,t可以随意取,比如1,2,3…….

假设n = 11,这时候n = 2^3 + 3,也就是说t = 3,所以开始剔除元素直到其成为2^k问题的约瑟夫问题。
So,我们在剔除了t(3)个元素之后(分别是2,4,6),此时我们定格在2t+1(7)处,并且将2t+1(7)作为新的一号,而且这时候的约瑟夫环只剩下23,也就是J(23 + 3) = 2*3 + 1 = 7,答案为7

总结一下这个规律:
J(2^k + t) = 2t+1

##3.说完了特例,现在说说q 不等于2的情况下:

当q ≠ 2:

我们假定:

  • n — n人构成的约瑟夫环
  • q — 每次移除第q个人
    约定:
  • Jq(n)表示n人构成的约瑟夫环,每次移除第q个人的解
  • n个人的编号从0开始至n-1

我们沿用之前特例的思想:能不能由Jq(n+1)的问题缩小成为J(n)的问题(这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案),Jq(n)是在Jq(n+1)基础上移除一个人之后的解。也就是说,我们能由Jq(n)得到Jq(n+1)。

规律:Jq(n+1) = ( Jq(n) + q ) / (n+1)
详细推导过程见这篇博文

大致是如下这样:

0 1 2 3 4 5 ......  n-1       总共n人
设第q个人也就是下标为q-1的那位,kill:

剩下n-1个人,如下:
q q+1 q+2 ...... n-2  n-1   0  1  2   ......  q-2     (这里是除去q-1这位兄台的剩余n-1人)

这时,又来重复我们的老套路:将新的被kill的后一个人作为新的0号,于是新的如下:
0  1  2   ......     ..........     ........  n-2

其实就是从q开始,到之前最大数n-1,每个数都减去q,从0开始之后接着n-1这个新的值每次往后加1,直到加到n-1(这个下标)
举个例子:

J4(9) :
0 1 2 3 4 5 6 7 8    消去3-->    0 1 2 4 5 6 7 8( 0 1 2)
				  对应的新值:	      0 1 2 3 4  5 6 7

其中:q=4,从3之后第一个数4开始:每个数5-q=1,6-q=2,7-q=3,8-q=4,因为是个环,0-q=-4,1-q=-3 ....直到加到n-1=7 

这就相当于一个限定范围内的数的相对位置,-1代表的是最后一个元素,也就是之前的8
(-2就代表7,-3代表6,-4代表5.....-9代表0,从后面开始数过来第9位)

大致过程如图下:

这里写图片描述

那么我们知道是这么得到的新的队列,那么也很容易知道怎么反推了:
反观如上的变化情况,都是减去一个q,所以:
变回去的公式如下:old = (new + q) % n
这里的old和new指的是下标,n指的是总共有多少人

知道了怎么推出之前的下标,那么也就可以一步步递推回去得到开始的队列或者从小推到大得到最后剩余的结果。

##最后再做一道实际点的例子,求J2(4):
J2(1) = 0
J2(2) = (J2(1) + 2) % 2 = 0
J2(3) = (J2(2) + 2) % 3 = 2
J2(4) = (J2(3) + 2) % 4 = 0

这样一步步求就能得到所有的给出n和q条件的答案了。

#include<iostream>
#include<stdio.h>
using namespace std;

int yuesefu(int n,int m){
        if(n == 1){
                return 0; //这里返回下标,从0开始,只有一个元素就是剩余的元素0
        }
        else{
                return (yuesefu(n-1,m) + m) % n; //我们传入的n是总共多少个数
        }
}
int main(void){
        int a,b;
        cin>>a>>b;
        cout<<yuesefu(a,b)<<endl;

		//或者,直接循环迭代,求出来的result如上
		int result = 0;
        for(int i = 2;i <= a;i++){
                result = (result+b) %i;
        }
        cout<<"result = "<<result<<endl;
        return 0;
}

##总结:
在遇上包含特殊的出队规则相关的题目时,应该联想到是否是约瑟夫环问题,方便求解。
此文章重新整理在约瑟夫环问题详解里了,修改了之前写过程中存在的一些错误,并添加了一些新的推导过程,谢谢指出错误之处.

到此这篇关于C++ 约瑟夫环问题案例详解的文章就介绍到这了,更多相关C++ 约瑟夫环问题内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

[!--infotagslink--]

相关文章

  • C++ STL标准库std::vector的使用详解

    vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
  • C++中取余运算的实现

    这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
  • 详解C++ string常用截取字符串方法

    这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
  • C++调用C#的DLL程序实现方法

    本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
  • C++中四种加密算法之AES源代码

    本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
  • C++ 整数拆分方法详解

    整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
  • C++中 Sort函数详细解析

    这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
  • C++万能库头文件在vs中的安装步骤(图文)

    这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
  • 详解C++ bitset用法

    这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
  • C++ Eigen库计算矩阵特征值及特征向量

    这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
  • 浅谈C++中的string 类型占几个字节

    本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
  • C++ pair的用法实例详解

    这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
  • C++中的循环引用

    虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
  • C++实现递归函数的方法

    在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25
  • VSCode C++多文件编译的简单使用方法

    这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
  • C++如何删除map容器中指定值的元素详解

    map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
  • C++随机点名生成器实例代码(老师们的福音!)

    这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
  • C++实现数字转换为十六进制字符串的方法

    这篇文章主要介绍了C++实现数字转换为十六进制字符串的方法,涉及C++操作数字与字符串转换的相关技巧,需要的朋友可以参考下...2020-04-25
  • C++中cin的用法详细

    这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
  • 基于C++中常见编译错误的总结详解

    本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25