- C++
约瑟夫问题 C++
- @ 2026-10-1 9:38:37
约瑟夫问题 C++ 零基础完整教程
约瑟夫问题描述:n个人围成一圈,从第1个人开始报数,数到m的人出列;接着下一个人重新从1开始报数,不断重复,直到最后剩下1个人,求这个人最初的编号。 两种写法:
- 数组模拟(适合新手,直观好理解,推荐0基础先学这个)
- 数学公式法(效率极高,理解难度高一点)
方法1:数组模拟(推荐零基础)
思路:用数组标记每个人是否还在圈内。循环报数,数到m就标记出局,直到只剩1个人。
#include <iostream>
using namespace std;
int main()
{
// n:总人数,m:报数上限
int n, m;
cout << "请输入总人数n:";
cin >> n;
cout << "请输入数到第几个人出局m:";
cin >> m;
// 数组,true表示人还在圈里,false代表已经出局
bool people[1000] = {true};
// 初始化所有人都在场,编号从1~n
for(int i = 1; i <= n; i++)
{
people[i] = true;
}
int remain = n; // 剩余还在圈里的人数
int idx = 0; // 当前遍历到哪个人
// 只要剩下的人大于1,继续循环淘汰
while(remain > 1)
{
idx++; // 走到下一个人
// 如果走到末尾,回到开头,形成环形
if(idx > n)
{
idx = 1;
}
// 如果这个人还没有出局
if(people[idx] == true)
{
m--; // 报一次数,计数减1
if(m == 0)
{
// 数到m,这个人出局
people[idx] = false;
remain--; // 剩余人数-1
m = 原来的m; // 重置报数,下次从1开始数
// 这里m要恢复,比如m=3,淘汰完下一轮重新数1,2,3
cout << idx << " 号出局" << endl;
}
}
}
// 循环结束,找唯一还在圈内的人
for(int i = 1; i <= n; i++)
{
if(people[i] == true)
{
cout << "最后存活的编号:" << i << endl;
}
}
return 0;
}
缺陷说明:数组大小固定,人数很大时不推荐;优点是完全可视化,能打印每一轮谁出局,新手最容易看懂。
测试示例
输入:
请输入总人数n:5
请输入数到第几个人出局m:3
运行输出:
3 号出局
1 号出局
5 号出局
2 号出局
最后存活的编号:4
5个人,数3淘汰,结果就是4号。
方法2:数学递推公式(约瑟夫公式,高性能)
公式定义:
设 f(k) 代表k个人的时候,幸存者的下标(从0开始)
递推式:
注意:公式下标从0开始,最后结果+1转为题目里1开始的编号。
#include <iostream>
using namespace std;
int main()
{
int n, m;
cout << "请输入总人数n:";
cin >> n;
cout << "请输入数到第几个人出局m:";
cin >> m;
int res = 0; // \(f(1)=0\),只有1个人时下标0
// 从2个人一直递推到n个人
for(int i = 2; i <= n; i++)
{
res = (res + m) % i;
}
// 公式得到的是0起始下标,+1转为1开始编号
cout << "最后存活编号:" << res + 1 << endl;
return 0;
}
✅优点:速度极快!n上百万都能秒算,不需要数组 ❌缺点:不能打印淘汰过程,纯数学推导,看不到中间过程。
测试:n=5,m=3,输出4,和上面模拟结果一致。
0基础知识点讲解
#include <iostream>:输入输出头文件,cincout需要using namespace std;:标准命名空间,新手加上不用写std::cinbool布尔类型:只有true(真)和false(假)%取模运算:a%b得到余数,用来实现环形循环- 数组模拟:本质是一圈人挨个点名,数够m就踢出去。
练习任务
- 用数组模拟代码,n=10,m=2,预测结果,运行验证。
- 尝试修改代码,不打印出局信息,只输出最后幸存者。
1 条评论
-
admin SU @ 2026-10-1 9:38:50已修改
约瑟夫问题 C++ list 链表实现(零基础,完整注释)
使用 STL 的
std::list双向链表模拟环形报数。 链表优势:删除元素很快,不用移动大量数据;适合理解“从圈子里移除一个人”。 注意:list 不是环形容器,我们手动循环迭代器模拟环。#include <iostream> // STL链表头文件 #include <list> using namespace std; int main() { int n, m; cout << "请输入总人数n:"; cin >> n; cout << "请输入数到第几个人出局m:"; cin >> m; // 定义链表,存放人的编号 1,2,3...n list<int> circle; // 把所有人加入链表 for(int i = 1; i <= n; i++) { circle.push_back(i); } // 创建迭代器 it,指向链表第一个元素 list<int>::iterator it = circle.begin(); // 当圈里人数大于1,继续淘汰 while(circle.size() > 1) { // 需要数 m-1 次:因为当前it已经是第1个,移动m-1次到达要删除的人 for(int i = 1; i < m; i++) { it++; // 迭代器往后走一位 // 如果走到链表末尾,回到开头,模拟环形 if(it == circle.end()) { it = circle.begin(); } } // it 现在指向要出局的人 cout << *it << " 号出局" << endl; // erase删除迭代器指向元素,并且返回下一个有效的迭代器 it = circle.erase(it); // 如果删除后迭代器到末尾,重置到开头(环形) if(it == circle.end()) { it = circle.begin(); } } // 链表只剩最后一个元素,就是幸存者 cout << "最后存活的编号:" << *circle.begin() << endl; return 0; }核心知识点讲解(0基础看懂)
#include <list>:使用STL链表必须引入这个头文件list<int>:一个存放int整数类型的双向链表push_back(x):在链表尾部添加元素xlist<int>::iterator it:迭代器,相当于链表的“指针”,用来指向链表里面的元素*it:取迭代器指向位置的数据(就是人的编号)circle.erase(it):删除it指向的节点,返回删除位置的下一个迭代器circle.end():代表链表末尾的“哨兵位置”,不是真实元素;走到end就要回到begin()实现环形
测试样例
输入:
请输入总人数n:5 请输入数到第几个人出局m:3输出:
3 号出局 1 号出局 5 号出局 2 号出局 最后存活的编号:4对比三种写法
写法 优点 缺点 适用场景 数组模拟 最简单好理解 删除元素麻烦,人多效率低 初学理解过程 list链表 删除快,贴合“出圈”模型 迭代器容易踩坑 数据量中等,需要打印淘汰顺序 数学公式 速度最快,n极大也没问题 看不到中间淘汰过程 只需要最后答案,竞赛 坑提醒:为什么循环移动
m-1次而不是 m 次? 迭代器it本身已经指向当前报数的第1个人,所以只要往后移动 m-1 次,就到达第m个人。C++ list 约瑟夫环(精简版,只输出幸存者,带注释)
#include <iostream> #include <list> using namespace std; int main() { int n, m; cout << "总人数n:"; cin >> n; cout << "数到m出局:"; cin >> m; list<int> circle; // 把编号1~n放入链表 for(int i = 1; i <= n; i++) { circle.push_back(i); } list<int>::iterator it = circle.begin(); // 剩下超过1个人就继续淘汰 while(circle.size() > 1) { // 当前it是第1个,移动m-1次到达要删除的人 for(int i = 1; i < m; i++) { it++; // 到链表尾部,回到头部,模拟环形 if(it == circle.end()) it = circle.begin(); } // 删除当前迭代器指向元素,it接收删除后的下一个位置 it = circle.erase(it); // 如果删完到末尾,重置到开头 if(it == circle.end()) it = circle.begin(); } // 输出最后剩下的编号 cout << "幸存者编号:" << *circle.begin() << endl; return 0; }测试
输入:
总人数n:5 数到m出局:3输出:
幸存者编号:4
- 1