网站做2微码,是网站推广的案例,wordpress 备份工具怎么使用,丹江口网站建设约瑟夫问题重述#xff1a;
在计算机编程的算法中#xff0c;类似问题又称为约瑟夫环
约瑟夫环#xff1a;N个人围成一圈#xff0c;从第一个开始报数#xff0c;第M个将被杀掉#xff0c;最后剩下一个#xff0c;其余人都将被杀掉。
例如N6#xff0c;M5#xff0…约瑟夫问题重述
在计算机编程的算法中类似问题又称为约瑟夫环
约瑟夫环N个人围成一圈从第一个开始报数第M个将被杀掉最后剩下一个其余人都将被杀掉。
例如N6M5被杀掉的顺序是546231。
如图所示 2.约瑟夫问题递归法计算原理 2.1 内容设FN,M为最后存活者的位置位置从0开始则有
FNMFN-1MM%N
2.2 证明数学归纳法
· 当n1时f(1,m)0因为编号从0开始且只有一个人胜利者编号显然为0。 当n2时序列为0,1若m为奇数则胜利者编号为1若m为偶数则胜利者编号为0易有f(2,m)m%2(0m)%2[f(1,m)m]%2结论成立。
· 假设当ni-1时结论成立即对于序列0,1,2,...,i-2而言最后的胜利者编号为f(i-1,m)。 当ni时序列为0,1,2,...,i-1。设第一轮的淘汰者编号为k若m%i0则ki-1否则km%i-1则序列可表示为0,1,2,...,k-1,k,k1,...,i-1。第一轮淘汰k余下的序列x为k1,...,i-1,0,1,...,k-1问题规模变为i-1。 因为由归纳假设当ni-1时对于序列x:0,1,2,...,f(i-1,m),...,i-2胜利者编号为f(i-1,m)。
由于x(xk1)%i故f(i,m)[f(i-1,m)k1]%i。当m%i0时k1i[f(i-1,m)k1]%i[f(i-1,m)i]%if(i-1,m)%i0f(i-1,m)%im%i[f(i-1,m)m]%i当m%i!0时k1m%i[f(i-1,m)k1]%i[f(i-1,m)m%i]%i[f(i-1,m)m]%i。故当ni时结论成立。
· 综上命题成立。
3.设计对象问题
3.1问题重述
假设你正在游玩约瑟夫游戏从你开始报数游戏规则与课上讲述一致现在你想确保你是最后一个出列的玩家如果由你设置m即每报几个数出列一人你应该如何设置m来确保自己的胜利
3.2问题分析
FNMFN-1MM%N设“我”的编号为S总人数为N每次第M个人被杀掉S,N为已知量M是待确定量最终目标在保证FNM S S的条件下确定M在确保时间复杂度计算的开销等因素下尽量进行优化的选取。
3.3问题求解
F(N , M) (F(N-1M)M) mod N (1)
F(N , M) 0; ( 2 )
思路1枚举法
1.实现枚举m运用公式计算F(N,M) , 找到满足条件的m;
2.复杂度O(n*m)
3.优点 思路简单枚举足够多就能找到全部解且容易。
4.缺点用while()枚举当大到一定程度终结。无法确定是否能找到m以及m要枚举多大。 思路2设计法
实现
F(1,M) 0;
F(2,M) (M)%2 0;
F(3,M) (M%2 M)%3 0 ;
...
F(N,M) (M%2 M%3 M%4 ...M%N)%N 0;
令 M N!则满足条件。
2.复杂度O(N)
3.优点 复杂度低
4.缺点当N过大时m数据值过大。
6.优化
1.操作
双指针删因子法缩小m规模。
试图在不改变复杂度条件下删除公共因子以减小m的数据规模。
复杂度 O(N);缺陷降低规模效果不明显依旧只能处理小范围数据进一步优化方法1用string进行大数计算方法2用Python方法3n小则用法2n大用法1但是依旧具有m不确定是否能找到的不稳定性。
只需在原有基础上修改为大数模式在此除了方法三外不做具体实现。
