小明学约瑟夫问题得到很大的帮助

约瑟夫问题
描述

小明最近在学些约瑟夫问题，与是他给他的奶牛们每头牛一个数字，让它们站成一排，从第一头开始，让每头牛写上

参考GPT

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n; // 输入牛的数量

    std::vector<int> cows(n); // 存储每头牛的数字
    for (int i = 0; i < n; ++i) {
        std::cin >> cows[i];
    }

    int rounds = 0; // 轮数计数
    int current = 0; // 当前写数字的牛的索引

    while (true) {
        bool wroteNumber = false; // 记录本轮是否有牛写了数字

        // 从当前位置开始，按照规则找到下一个可以写数字的牛
        for (int i = 1; i <= n; ++i) {
            int nextCow = (current + i) % n; // 计算下一个位置
            if (cows[nextCow] == 0) {
                cows[nextCow] = n - i + 1; // 写数字
                wroteNumber = true;
                current = nextCow; // 更新当前位置
                break;
            }
        }

        if (!wroteNumber) {
            break; // 如果没有牛写数字，退出循环
        }

        ++rounds;
    }

    std::cout << rounds << std::endl; // 输出所需轮数

    return 0;
}

#include <iostream>
#include <vector>

int josephus(int n, int k) {
    std::vector<int> cows(n);
    for (int i = 0; i < n; i++) {
        cows[i] = i + 1;
    }

    int current = 0;
    int count = 0;
    int rounds = 0;

    while (count < n) {
        if (cows[current] != 0) {
            count++;
            if (count % k == 0) {
                cows[current] = 0;
                count = 0;
            }
        }
        current = (current + 1) % n;
        if (current == 0) {
            rounds++;
        }
    }

    return rounds;
}

int main() {
    int n = 10; // 奶牛的数量
    int k = 3; // 每轮跳过的数字个数
    int rounds = josephus(n, k);
    std::cout << "最少需要 " << rounds << " 轮才能完成写数字的过程。" << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

int josephus(int n, int k) {
    std::vector<int> cows(n);
    for (int i = 0; i < n; i++) {
        cows[i] = i + 1;
    }

    int current = 0;
    int count = 0;
    int rounds = 0;

    while (count < n) {
        if (cows[current] != 0) {
            count++;
            if (count % k == 0) {
                cows[current] = 0;
                count = 0;
            }
        }
        current = (current + 1) % n;
        if (current == 0) {
            rounds++;
        }
    }

    return rounds;
}

int main() {
    int n = 10; // 奶牛的数量
    int k = 3; // 每轮跳过的数字个数
    int rounds = josephus(n, k);
    std::cout << "最少需要 " << rounds << " 轮才能完成写数字的过程。" << std::endl;
    return 0;
}

【以下回答由 GPT 生成】

约瑟夫问题的具体描述是：有n个人围成一圈，从第一个人开始，报数1、2、3，报到3的人出局，然后再从下一个人开始继续报数，直到剩下最后一个人为止。现在要求根据给定的n和出局的规则，找到最后剩下的那个人的编号。

解决方案： 可以使用循环链表来模拟这个问题。首先，创建一个n节点的循环链表，并按照顺序编号为1到n。

然后，通过循环遍历链表，每次遍历到第m个节点的时候，将该节点从链表中删除。删除节点的具体操作是将该节点的前一个节点的next指针指向该节点的下一个节点，然后释放该节点的内存。

重复上述操作，直到链表中只剩下一个节点为止，此时这个节点的编号就是最后剩下的那个人的编号。

下面是一个用C++实现的示例代码：

#include <iostream>

struct Node {
    int data;
    Node* next;
};

int josephus(int n, int m) {
    Node* head = new Node();
    Node* curr = head;

    // 创建循环链表
    for (int i = 1; i <= n; i++) {
        Node* newNode = new Node();
        newNode->data = i;
        curr->next = newNode;
        curr = curr->next;
    }
    curr->next = head->next;

    // 开始约瑟夫问题
    curr = head;
    while (curr->next != curr) {
        // 找到需要删除的节点
        for (int i = 1; i < m; i++) {
            curr = curr->next;
        }
        // 删除节点
        Node* deletedNode = curr->next;
        curr->next = deletedNode->next;
        delete deletedNode;
    }

    // 返回最后剩下的节点编号
    return curr->data;
}

int main() {
    int n, m;
    std::cout << "请输入总人数n和报数的规则m：" << std::endl;
    std::cin >> n >> m;
    std::cout << "最后剩下的人的编号是：" << josephus(n, m) << std::endl;
    return 0;
}

使用这个代码可以求解任意n和m的约瑟夫问题。假设输入n=5，m=3，输出结果为4，表示在1,2,3,4,5号人中，按照报数规则每次报到3的人会被淘汰，最后剩下的是4号人。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/681212
• 这篇博客也不错, 你可以看下已存入数组中的数据值已经按由小到大的顺序存放，现从键盘输入一个数据，把它插入到数组中，要求插入新数据以后，数组数据仍然保持有序。请编写一个程序实现上述功能。
• 您还可以看一下 韦语洋（Lccee）老师的一机一码加密、被破解自动销毁随时授权回收升级系列视频课程课程中的 课程介绍：能学到什么（必看内容）小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 如何按逆顺序输出一个多位数各个位上的数字？中的 如果只是为了倒序输出而不需要知道具体的数位的数字，那么还有一种更简洁的方法： 部分也许能够解决你的问题。