约瑟夫问题 C++ 零基础完整教程

约瑟夫问题描述:n个人围成一圈,从第1个人开始报数,数到m的人出列;接着下一个人重新从1开始报数,不断重复,直到最后剩下1个人,求这个人最初的编号。 两种写法:

  1. 数组模拟(适合新手,直观好理解,推荐0基础先学这个)
  2. 数学公式法(效率极高,理解难度高一点)

方法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开始) 递推式:

(f(1)=0)(f(1)=0) f(k)=(f(k−1)+m) mod kf(k)=(f(k-1)+m) \bmod k

注意:公式下标从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基础知识点讲解

  1. #include <iostream>:输入输出头文件,cin cout 需要
  2. using namespace std;:标准命名空间,新手加上不用写std::cin
  3. bool 布尔类型:只有true(真)和false(假)
  4. % 取模运算:a%b 得到余数,用来实现环形循环
  5. 数组模拟:本质是一圈人挨个点名,数够m就踢出去。

练习任务

  1. 用数组模拟代码,n=10,m=2,预测结果,运行验证。
  2. 尝试修改代码,不打印出局信息,只输出最后幸存者。

1 条评论

  • @ 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基础看懂)

    1. #include <list>:使用STL链表必须引入这个头文件
    2. list<int>:一个存放int整数类型的双向链表
    3. push_back(x):在链表尾部添加元素x
    4. list<int>::iterator it:迭代器,相当于链表的“指针”,用来指向链表里面的元素
    5. *it:取迭代器指向位置的数据(就是人的编号)
    6. circle.erase(it):删除it指向的节点,返回删除位置的下一个迭代器
    7. 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