Java教程

2022.1.25#约瑟夫环问题(1)——粗暴的模拟

本文主要是介绍2022.1.25#约瑟夫环问题(1)——粗暴的模拟,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
}

 

这篇关于2022.1.25#约瑟夫环问题(1)——粗暴的模拟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!