2022-01-25

约瑟夫环问题（1）——粗暴的模拟

思路：模拟法，利用数组或者循环链表解决，需要学会掌握计数器方式，人动和数动。

数组：1.使用book数组来对应：是否出列，用于对已出列者不作为

            2.使用i来对应：依次点到的人，每个人都点，用于遍历每个人

            3.使用k来对应：每次从1报到m的循环中的报号数，用于得到哪个人要出列

            4.使用cnt（count）来对应：总共多少人是出列的，用于结束的条件

数组的代码：

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int main(void)
 5 {
 6     int n, m;//n为人数，m为第几个报数的出列
 7     cin >> n >> m;
 8     vector<int>book(n+1);//book数组判断出列与否
 9     int i = 0, k = 0, cnt = 0;//i为人数遍历，k为报数遍历，cnt为出列人数
10 
11     while (cnt != n)
12     {
13         i++;
14         if (i == n+1)
15             i = 1;
16         //如果到了末尾，那么就回到首位
17         if (book[i] == 0)
18         {
19             k++;
20             if (k == m)
21             {
22                 book[i] = 1;
23                 cout << i << ' ';
24                 cnt++;
25                 k = 0;//重新报数
26             }
27         }
28     }
29     return 0;
30 }

循环链表：更为直观地对应了围成圈的题意，掌握了循环链表的构建，链表中元素的删除。

关于node的构建：

struct node {
    int val;
    node* next;
    node(node* next_ = NULL)
    {
        next = next_;
    }//自动把next变成NULL，非常方便
};

关于循环链表的构建：

    node* head, * p, * r;
    head = new node;
    p = head;
    for (int i = 0;i < n;i++)
    {
        r = new node;
        r->val = i + 1;
        p->next = r;
        p = r;
    }
    p->next = head->next;

基础的构建链表知识加深记忆（需要三个node指针才可，一个为head——可以找到它的藏宝图，一个为p——替身狂魔，一个r——real的创造节点）

循环只需要最终把 “尾首相连”就好。

代码：

#include<iostream>
using namespace std;

struct node {
    int val;
    node* next;
    node(node* next_ = NULL)
    {
        next = next_;
    }
    //节点自动next变NULL
};

void display(node* head)
{
    node* p;
    p = head->next;
    while (p != NULL)
    {
        cout << (*p).val << ' ';
        p=p->next;
    }
}

int main(void)
{
    int n, m;
    cin >> n >> m;
    node* head, * p, * r;
    //牢记三指针
    head = new node;
    p = head;
    for (int i = 0;i < n;i++)
    {
        r = new node;
        r->val = i + 1;
        p->next = r;
        p = r;
    }
    if (m == 1)
    {
        display(head);
        return 0;
    }//特殊情况m=1时

    p->next = head->next;
    //链表构建——循环链表构建


    int cnt = 0;
    //报数计数
    p = head->next;
    //进入循环
    while (p != p->next)//当不止一个的时候
    {
        cnt++;
        if (cnt == m - 1)
        {
            cout << p->next->val << ' ';
            r = p->next;
            p->next = r->next;
            free(r);
            cnt = 0;
        }
        //链表节点删除的知识，需要两个指针进行删除活动
        p = p->next;//继续遍历
    }
    cout << endl << "the last one is " << p->val;
    return 0;
}