猴子选大王c++问题实现

猴子选大王是一个经典的问题，可以使用循环链表来实现。

具体实现步骤如下：

1. 定义节点结构体，包含一个成员变量表示当前猴子的编号，还有一个指向下一个猴子的指针。

struct Monkey {
    int num;
    Monkey* next;
};

2. 创建循环链表，可以使用循环语句创建，每个猴子的编号依次递增，并且每个猴子的next指针指向下一个猴子。

Monkey* createMonkeyList(int n) {
    Monkey* head = nullptr;
    Monkey* prev = nullptr;
    for (int i = 1; i <= n; i++) {
        Monkey* p = new Monkey();
        p->num = i;
        if (prev != nullptr) {
            prev->next = p;
        } else {
            head = p;
        }
        prev = p;
    }
    prev->next = head; // 链表尾部指向头部，形成循环链表
    return head;
}

3. 从第一个猴子开始数数，数到第m个猴子出列，然后从下一个猴子开始重新数数，重复以上步骤，直到只剩一个猴子为止。

int monkeyKing(int n, int m) {
    Monkey* head = createMonkeyList(n);
    int count = 1;
    Monkey* prev = nullptr;
    Monkey* cur = head;
    while (cur->next != cur) { // 只剩一个猴子时停止循环
        if (count == m) { // 数到第m个猴子，出列
            prev->next = cur->next;
            Monkey* tmp = cur;
            cur = cur->next;
            delete tmp;
            count = 1;
        } else {
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    int res = cur->num;
    delete cur;
    return res;
}

完整实现如下：

#include <iostream>

using namespace std;

struct Monkey {
    int num;
    Monkey* next;
};

Monkey* createMonkeyList(int n) {
    Monkey* head = nullptr;
    Monkey* prev = nullptr;
    for (int i = 1; i <= n; i++) {
        Monkey* p = new Monkey();
        p->num = i;
        if (prev != nullptr) {
            prev->next = p;
        } else {
            head = p;
        }
        prev = p;
    }
    prev->next = head; // 链表尾部指向头部，形成循环链表
    return head;
}

int monkeyKing(int n, int m) {
    Monkey* head = createMonkeyList(n);
    int count = 1;
    Monkey* prev = nullptr;
    Monkey* cur = head;
    while (cur->next != cur) { // 只剩一个猴子时停止循环
        if (count == m) { // 数到第m个猴子，出列
            prev->next = cur->next;
            Monkey* tmp = cur;
            cur = cur->next;
            delete tmp;
            count = 1;
        } else {
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    int res = cur->num;
    delete cur;
    return res;
}

int main() {
    int n = 10;
    int m = 3;
    int king = monkeyKing(n, m);
    cout << "The monkey king is " << king << endl;
    return 0;
}