脚本宝典收集整理的这篇文章主要介绍了约瑟夫问题的数学解(C++),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
@R_147_@R_512_2621@4@一般的解法即用循环模拟报数,但是此这样的方法@R_218_1304@为O(mn),m为报的数,n为人数,在规模较大时旺旺效率并不好,我们可以用数学方法来讲问题进行简化,用O(n)的复杂度解决问题
初始的约瑟夫问题设为F(n),我们假设从第0人开始报数,第一个出去的人即第m-1个人,淘汰一人之后我们可以看作是一个n-1人的约瑟夫问题,但是其初始报数位置并不是从头开始,而是从第m%n处开始,我们可以将序号平移,将m%n处的人移动到第一位,便可以变成一n-1人的约瑟夫环F(n-1),则F(n-1)中编号为k的人刚才的序号为(k+m)%n,
即F(n)[(k+m)%n]=F(n-1)[k]
类似的,我们反过来看,当只有一个人时
F(1)=0
这个人即为最后胜利的人,那么这个人在上一次报数中所在的位置为
F(2)=(F(1)+m)%n
F(3)=(F(2)+m)%n
...
F(n)=(F(n-1)+m)%
即为此人最开始的编号
c++实现如下
#include<iostream>
using namespace std;
int main(int argc, char** argv) {
int n,k;
cin>>n>>k;
int r;
r=0;
for(int i=1;i<=n;i++){
r=(r+k)%i;
}
cout<<r+1<<endl;
}
以上是脚本宝典为你收集整理的约瑟夫问题的数学解(C++)全部内容,希望文章能够帮你解决约瑟夫问题的数学解(C++)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。