欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

士兵队列训练问题:某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的

程序员文章站 2022-06-18 10:06:19
题目描述:某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数。。。,以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。输入:本题有多个测试数据组,第一行为组数N,接着为N行新兵人数,新兵人数不超过5000。输出:共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空...

题目描述:
某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数。。。,以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
输入:
本题有多个测试数据组,第一行为组数N,接着为N行新兵人数,新兵人数不超过5000。

输出:
共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。

样例输入:
2
20
40
样例输出:
1 7 19
1 19 37

思路:利用两个队列实现,q1队列用来从一至二报数,非2的进入q2,;q2用来从一至三报数,非3的进入队列q1,直至两个队列中任意一个队列元素数小于等于3。其中用到bool变量来决定哪个队列元素出队,哪个队列元素如队。需要注意的是每次一个队列出队完成后都要重新初始化,否则将会有你意想不到的错误(本人亲测)。一下就是具体的源码:

#include <iostream>
#define MAXSIZE 5001
using namespace std;

typedef struct queue
{
    int data[MAXSIZE];
    int front;
    int rear;
    int capacity;
}Queue;
void InitQueue(Queue *q)
{
    q->front=0;
    q->rear=0;
    q->capacity=0;
}
void EnterQueue(Queue *q,int &data)
{
    if(MAXSIZE!=q->rear)
    {
        q->data[++q->rear]=data;
        q->capacity++;
    }
}
int OuterQueue(Queue *q)
{
    int data;
    if(q->front!=q->rear)
    {
        data=q->data[++q->front];
        q->capacity--;
    }
    return data;
}
int main()
{
    int N,m,data,m1,m2;
    Queue q1,q2;
    cin>>N;
    while(N--)
    {
        InitQueue(&q1);
        InitQueue(&q2);
        bool isq1=true;
        cin>>m;
        for(int i=1;i<=m;i++)
            EnterQueue(&q1,i);
        while(q1.capacity>3||q2.capacity>3)
        {
            if(isq1)
            {
                m1=q1.capacity;
                for(int i=1;i<=m1;i++)
                {
                    if(i%2!=0)
                    {
                        data=OuterQueue(&q1);
                        EnterQueue(&q2,data);
                    }
                    else
                        OuterQueue(&q1);
                }
                isq1=false;
                InitQueue(&q1);
            }
            else
            {
                m2=q2.capacity;
                for(int i=1;i<=m2;i++)
                {
                    if(i%3!=0)
                    {
                        data=OuterQueue(&q2);
                        EnterQueue(&q1,data);
                    }
                    else
                        OuterQueue(&q2);
                }
                isq1=true;
                InitQueue(&q2);
            }
        }
        if(isq1)
        {
            cout<<q1.data[1];
            for(int i=2;i<=q1.capacity;i++)
                cout<<" "<<q1.data[i];
            cout<<endl;
        }
        else
        {
            cout<<q2.data[1];
            for(int i=2;i<=q2.capacity;i++)
                cout<<" "<<q2.data[i];
            cout<<endl;
        }
    }
    return 0;
}

本文地址:https://blog.csdn.net/T13629119629/article/details/109270769

相关标签: c++ 队列 算法