开发者社区 问答 正文

类似约瑟夫问题c++

已解决

沃瑟夫问题
有 n 个人排成一圈,从 1 到 n 编号。从第一个人开始依次报数(第一个人报的数是 1,下一个人报的数是 2...,当前这个人报的数字等于前面那个人报的数字加一),报数一共进行 n 轮,对于第 i (1<=i<=n) 轮,数到 i^2 的人出列,下一个人继续从 1 开始报数。结束的时候所有人都会出列。
请依次输出每一轮出列的人的编号。

输入格式
第一行一个整数 n
输出格式
输出一行,包含 n 个数,表示每一轮出列的人的编号

样例输入

10
样例输出

1 5 6 8 9 10 2 3 4 7
数据规模
对于 100% 的数据,保证 1≤n≤5000。

展开
收起
算精通 2023-07-20 22:11:07 208 分享 版权
4 条回答
写回答
取消 提交回答
  • 北京阿里云ACE会长
    采纳回答

    可以使用模拟的方法来解决。由于需要一轮一轮地计算出列的人的编号,可以使用一个循环来遍历每一轮,然后在每一轮中模拟报数的过程,找到需要出列的人并将其从列表中删除。

    具体来说,我们可以使用一个列表 people 存储当前还在圈子里的人的编号。然后,我们在每一轮中遍历 people 列表,模拟报数的过程。当报数等于 i^2 时,我们就将该人从列表中删除,并将其编号添加到结果列表 result 中。最后,我们将剩余的人重新组成一个新的列表,准备进行下一轮的报数。

    以下是一个 Python 实现的示例代码:

    python
    Copy
    n = int(input())

    初始化人数列表

    people = list(range(1, n+1))

    初始化结果列表

    result = []

    依次进行 n 轮报数

    for i in range(1, n+1):

    # 初始化报数和出列的计数器
    count = 0
    removed = 0
    
    # 初始化新的人数列表
    new_people = []
    
    # 遍历当前的人数列表
    for j in range(len(people)):
        # 进行报数
        count += 1
    
        # 如果报数等于 i^2,则将该人出列,并将其编号添加到结果列表中
        if count == i**2:
            result.append(people[j])
            removed += 1
        # 否则将该人添加到新的人数列表中
        else:
            new_people.append(people[j])
    
    # 更新人数列表
    people = new_people
    
    # 如果所有人都已经出列,则退出循环
    if removed == n:
        break
    

    输出结果

    print(' '.join(map(str, result)))
    在这个代码中,我们首先初始化人数列表 people 和结果列表 result。然后,我们使用一个循环来遍历每一轮报数,并在每一轮中模拟报数的过程。在每一轮中,我们遍历当前的人数列表 people,逐个进行报数。如果报数等于 i^2,则将该人出列,并将其编号添加到结果列表 result 中;否则将该人添加到新的人数列表 new_people 中。

    在每一轮结束后,我们更新人数列表 people 为新的人数列表 new_people。如果所有人都已经出列,则退出循环。最后,我们将结果列表 result 转换为字符串,并使用空格分隔,输出到标准输出。

    对于你提供的示例输入,上述代码将输出以下结果:

    basic
    Copy
    1 5 6 8 9 10 2 3 4 7

    2023-07-20 22:24:01
    赞同 1 展开评论
  • 沃瑟夫问题是一个经典的约瑟夫问题的变种。解决这个问题的一种常用方法是使用循环链表的思想来模拟报数和出列的过程

    2023-07-23 21:15:28
    赞同 展开评论
  • 根据沃瑟夫问题的规则,我们可以使用循环队列来模拟报数和出列的过程。具体实现步骤如下:

    1. 创建一个长度为 n 的数组来表示 n 个人的编号。
    2. 创建一个变量 count,并初始化为 0,用于记录当前报到的数字。
    3. 创建一个变量 step,并初始化为 1,用于表示每一轮报数的步长。
    4. 创建一个变量 index,并初始化为 0,表示当前报数的人在数组中的索引。
    5. 进行 n 轮报数和出列的循环,每一轮的结束条件是数组中剩余的人数大于 1。
      • 在每一轮中,先将当前报数的人的编号置为 0,表示该人已出列。
      • 然后根据当前报到的数字计算下一个报数的人的索引。
      • 如果当前报到的数字等于该轮的平方数 (i^2),则将下一个报数的人的索引向后移动一个位置。
      • 更新 count 的值,即下一个报到的数字。
    6. 最后遍历数组,输出剩余未出列的人的编号。

    以下是实现该算法的示例代码:

    n = int(input())  # 输入 n
    
    # 创建编号数组
    people = [i+1 for i in range(n)]
    
    count = 0
    step = 1
    index = 0
    
    while len(people) > 1:
        count += 1
        if count == step * step:
            people[index] = 0
            count = 0
            index += 1
            while index < n and people[index] == 0:
                index += 1
            step += 1
        index %= n
    
    result = [x for x in people if x != 0]
    print(' '.join(map(str, result)))
    

    该算法的时间复杂度为 O(n^2),可以满足数据规模要求。输入示例的输出结果应为:1 5 6 8 9 10 2 3 4 7。

    2023-07-21 09:01:39
    赞同 展开评论
  • 下面是一个在 C++ 中解决沃瑟夫问题的示例代码:

    #include <iostream>
    #include <vector>
    
    std::vector<int> josephus(int n) {
        std::vector<int> people(n);  // 创建一个长度为 n 的 vector,存储每个人的编号
    
        for (int i = 0; i < n; i++) {
            people[i] = i + 1;  // 初始化每个人的编号
        }
    
        std::vector<int> result;  // 存储出列的人的编号
    
        int i = 0;  // 当前报数的人的索引
    
        for (int round = 1; round <= n; round++) {
            int target = round * round;  // 目标数字
            int count = 0;  // 当前报的数字
    
            while (count < target) {
                if (people[i] != 0) {  // 如果当前人还没有出列
                    count++;
    
                    if (count == target) {  // 数到目标数字时,将该人出列
                        result.push_back(people[i]);
                        people[i] = 0;  // 将其置为0,表示已出列
                    }
                }
    
                i = (i + 1) % n;  // 更新索引,循环报数
            }
        }
    
        return result;
    }
    
    int main() {
        int n;
        std::cin >> n;  // 输入 n
    
        std::vector<int> output = josephus(n);
    
        for (int i = 0; i < n; i++) {
            std::cout << output[i] << " ";  // 输出每一轮出列的人的编号
        }
    
        return 0;
    }
    

    这段代码使用了一个 vector people 来存储 n 个人的编号,并依次进行 n 轮报数。在每一轮中,根据规则找到应该出列的人,并将其编号添加到结果 vector result 中。最后,我们遍历输出结果 vector 中的元素,即每一轮出列的人的编号。

    例如,对于输入样例 10,得到的输出为 1 5 6 8 9 10 2 3 4 7

    2023-07-20 22:29:21
    赞同 展开评论
问答分类:
C++
问答标签:
问答地址: