|
丢手绢游戏规则： 有N(N<=1000)个小朋友玩丢手绢游戏，坐成一圈，从第一个小朋友开始数数，从1开始数，数到指定数字M的小朋友要出列，然后下一个小朋友继续从1开始数，依次类推，算出最后一个留下来的小朋友是谁？丢手绢问题又称为约瑟夫环，是一个计算机科学和数学中的问题。
模拟法 （1）由于对于每个小朋友只有出列和在列两种状态，因此可以用布尔型数组标记每个小朋友的状态，可用true表示出列，false表示在列。 （2）开始时每个小朋友都在列，所以数组初值全部赋为false。 （3）模拟整个丢手绢过程，直到只剩一个小朋友为止。 模拟丢手绢过程 #include <iostream> using namespace std; int main() { bool a[1001] = {0}; int n, m, i, f = 0, t = 0, s = 0; cin >> n >> m; while(f<n) { ++t; //逐个枚举圈中的所有位置 if (t > n) t = 1; //数组模拟环状，最后一个与第一个相连 if (!a[t]) s++; //第t个位置上有人则报数 if (s == m) //当前报的数是m { s = 0; //计数器清零 a[t] = true; //此处已出列，设置为true //cout<<t<<’\n’; //输出依次出列的序号 f++; //已出列人数+1 } } cout<<t;//最后一个出列 return 0; }
时间复杂度：O(n*m)，当n、m非常大时候，一定会超时。 空间复杂度：O(N)，N为人数的最大值，本示例为1000。 递推算法 问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数，求胜利者的编号。（为便于讨论，定义编号为0～n-1） 第一个人（编号为（m-1）mod n) 出列之后，剩下的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 令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果为f[n] 递推公式 f[1]=0; f=(f[i-1]+m) mod i; (i>1） 实际生活中编号从1开始，输出f[n]+1
#include <iostream> using namespace std; int main() { int n, m, s = 0; cin >> n >> m; for (int i = 2; i <= n; i++) s = (s + m) % i; cout << s + 1; return 0; } 时间复杂度：O(n)。 空间复杂度：O(1)。
| 
发表于 2022-1-22 11:13:33
置顶卡