网站有哪几种类型,外发加工费会计分录,地名公共服务网站建设,深圳光明区目录 1. 问题
2. 思路
3. 代码
4. 运行 1. 问题 本题即为典型的约瑟夫问题#xff0c;通过递推公式倒推出问题的解。原始问题是从n个人中每隔m个数踢出一个人#xff0c;原始问题变成从n-1个人中每隔m个数踢出一个人……
示例 1#xff1a;
输入: n 5, m 3
输出: 3…目录 1. 问题
2. 思路
3. 代码
4. 运行 1. 问题 本题即为典型的约瑟夫问题通过递推公式倒推出问题的解。原始问题是从n个人中每隔m个数踢出一个人原始问题变成从n-1个人中每隔m个数踢出一个人……
示例 1
输入: n 5, m 3
输出: 3示例 2
输入: n 10, m 17
输出: 22. 思路 第一行表示每个人的下标现在要从11个人中删除报数为3的人从图中可以可看出最后7是胜利者。分析其中的规律
第一轮中11个人中胜利者7的角标是6
第二轮中10个人中胜利者7的角标是3
第三轮中9个人中胜利者7的角标是0
第四轮中8个人中胜利者7的角标是6
第五轮中7个人中胜利者7的角标是3
第六轮中6个人中胜利者7的角标是0
第七轮中5个人中胜利者7的角标是3
第八轮中4个人中胜利者7的角标是0
第九轮中3个人中胜利者7的角标是1
第十轮中2个人中胜利者7的角标是1
第十一轮中1个人中胜利者7的角标是0 从第十一轮中倒推到第一轮
从第十一轮中推出第十轮的角标数f(2,3) (f(1,3) m) % 2 (03) % 2 1
从第十轮中推出第九轮的角标数f(3,3) (f(2,3) m) % 3 (13) % 3 1
从第九轮中推出第八轮的角标数f(4,3) (f(3,3) m) % 4 (13) % 4 0
懒得写了……. 结论从n个人中每隔m删除一人递推公式为 f(n,m) (f(n-1,m)m) % n
3. 代码
#include iostream
using namespace std;class Solution {
public:// n表示多少个人m表示随机数int LastRemaining_Solution(int n, int m){// 特殊输入if (n 0 || m 0) return -1;// 递推公式计算int res 0;for (int i 1; i n; i){res (res m) % i;cout res endl;}return res;}
};
int main()
{int n 11;int m 3;Solution solution;solution.LastRemaining_Solution(n, m);return 0;
}4. 运行
