C++算法实战：小孩报数问题（顺序循环队列实现）

问题描述

有若干个小孩围成一圈，从指定的第一个小孩开始报数，报到第w个时，该小孩出列，然后从下一个小孩开始报数，仍是报到w个出列，如此重复下去，直到所有的小孩都出列（总人数不足w个时将循环报数）。求小孩出列的顺序。

算法思路

为了模拟小孩循环报数的过程，我们可以使用顺序循环队列来存储所有小孩的信息。算法步骤如下：

初始化一个顺序循环队列，将所有小孩的名字入队。2. 从队首开始报数，每次报数计数器加一。3. 当计数器达到w时，将队首元素出队，并输出该小孩的名字。4. 否则，将队首元素出队，并将其重新入队到队尾。5. 重复步骤2-4，直到队列为空。

代码实现cpp#include <stdio.h>#include <malloc.h>#include <string.h>#define MaxSize 11#define N 10

typedef char ElemType;typedef struct // 顺序循环队列结点定义{ ElemType *name[MaxSize]; //小孩姓名 int front,rear; //队首和队尾指针} SqQueue;

void InitQueue(SqQueue *&q); //初始化队列；void DestroyQueue(SqQueue *&q); //销毁队列；bool QueueEmpty(SqQueue *q); //判定队列为空时返回true; 否则返回false;bool enQueue(SqQueue *&q,ElemType *e); // e 入队；成功入队返回true; 否则返回false;bool deQueue(SqQueue *&q,ElemType *&e); //出队，返回出队元素e，且成功出队返回true,否则返回false;

int main(){ ElemType *e; int n,i; SqQueue *q; InitQueue(q); scanf('%d',&n); while(1) { char *name=(char *)malloc(sizeof(char)*N); scanf('%s',name); if( (strcmp('-1',name)==0)||!enQueue(q,name)) break; } i=n-1; while(!QueueEmpty(q)) { deQueue(q,e); if(i-->0) enQueue(q,e); else { printf('%s ',e); i=n-1; free(e); } } DestroyQueue(q);}

void InitQueue(SqQueue *&q){ q = (SqQueue *)malloc(sizeof(SqQueue)); q->front = q->rear = 0;}

void DestroyQueue(SqQueue *&q){ free(q);}

bool QueueEmpty(SqQueue *q){ return q->front == q->rear;}

bool enQueue(SqQueue *&q, ElemType *e){ if ((q->rear + 1) % MaxSize == q->front) // 队列已满 return false; q->name[q->rear] = e; q->rear = (q->rear + 1) % MaxSize; return true;}

bool deQueue(SqQueue *&q, ElemType *&e){ if (q->front == q->rear) // 队列为空 return false; e = q->name[q->front]; q->front = (q->front + 1) % MaxSize; return true;}

输入样例

3Jenny Mike Lily Tom Yoyo -1

输出样例

LilyJennyYoyoMikeTom

总结

本文介绍了如何使用C++的顺序循环队列解决'小孩报数'问题。通过该算法，我们可以清晰地模拟循环报数的过程，并高效地找到出列顺序。该算法也体现了循环队列在解决实际问题中的应用价值。