从第一个人开始报数(从1到3),凡报到3的人退出圈子,

有n个人围成一圈，顺序编号。从第一个人开始报数(从1到3)，凡报到3的人退出圈子，

问最后一个圈中的人的编号？

方法一：

算法分析：

1． 可以用一个数组保存n个人的编号，当此人退出圈子时将编号变为0；

2． 用一个计数器i 模拟每个人的编号，如果此人已出圈（即编号为0），则跳过此人不计数，

否则进行累加，当报完一圈后将i置0，重新计数；

3． 用一个计数器k模拟报数，当k==m 时，将k置0再从头报数。

4． 用一个变量quit_num记录出圈的人数，当圈中只剩一个人时，即quit_num == n-1,停

止报数，输出结果。

5． 对数组进行搜索，查找编号不为零的人(留在圈中的人)，输出他的编号。

流程图：见下图

开始

给 p,k赋初值

m,

给所有的人编号

m < n – 1?

Y

N

*(p+i) != 0?

Y

k++

N

k == m?

Y

*(p+i)=0

m ++

k = 0

N

N

i==n?

Y

i=0

查找留在圈中的人

输出结果

结束

流程图

程序代码：

#include "iostream.h"

#define nmax 200

void main()

{

int i = 0; //循环变量

int k = 0; //报数的计数器

int m = 0; //退出的人数

int n; //总人数

int num[nmax]; //保存所有人的编号

int *p = num; //初始化指针,使其指向num数组

cout<<"请输入总人数(不大于200):";

cin>>n;

p=num;

//给所有的人编号为1到n

for(i=0;i

*(p+i)=i+1;

i=0;

k=0;

m=0;

//当未退出人数大于1时 执行循环

while(m

{

if(*(p+i)!=0) k++; //已经出圈的人不参与报数

if(k==3)

{

*(p+i)=0; //退出圈子时将此人的编号置为0

k=0; //重新报数

m++;

}

i++;

if(i==n) i=0; //一圈报完后，再从头循环

}

while(*p==0) p++; //查找留在圈中的人

cout<<"最后流下的是"<<*p<<"号"<

}

方法二：

用链表，具体见程序及注释：

程序代码：

#include

#include

#include

typedef struct _link

{

struct _link * next;

int pos;

}link;

int main(int argc, char *argv[])

{

link *front, *p, *last;

p=front=(link *)malloc(sizeof(link));/*先分配一个*/

p->pos=1;

int n, i=0, num=3;

cout<<"请输入总人数:";

cin>>n;

for(i=2;i<=n;i++)/*再分配其它的,总共n个*/

{

p->next=(link *)malloc(sizeof(link));

p=p->next;

p->pos=i;

}

p->next=front;/*使之围成一个圈*/

i=0;/*从头开始数*/

last=p=front;/*从头开始数*/

while(p->next!=p)/*当p->next==p时就只剩一个了*/

{

i++;/*数数*/

if(i==3)/*数到3了,此退出*/

{

last->next=p->next;

free(p);

p=last;

i=0;

}

last=p;//last的作用是保存前一个link,如果是双向链表,就不需要它了

p=p->next;//到下一个人

}

cout<<"最后流下的是"<pos<<"号"<最后剩下的一个人的位置

system("PAUSE");

return 0;

}