從第一個(gè)人開(kāi)始報(bào)數(shù)(從1到3),凡報(bào)到3的人退出圈子,

有n個(gè)人圍成一圈，順序編號(hào)。從第一個(gè)人開(kāi)始報(bào)數(shù)(從1到3)，凡報(bào)到3的人退出圈子，

問(wèn)最后一個(gè)圈中的人的編號(hào)？

方法一：

算法分析：

1． 可以用一個(gè)數(shù)組保存n個(gè)人的編號(hào)，當(dāng)此人退出圈子時(shí)將編號(hào)變?yōu)?/span>0；

2． 用一個(gè)計(jì)數(shù)器i 模擬每個(gè)人的編號(hào)，如果此人已出圈（即編號(hào)為0），則跳過(guò)此人不計(jì)數(shù)，

否則進(jìn)行累加，當(dāng)報(bào)完一圈后將i置0，重新計(jì)數(shù)；

3． 用一個(gè)計(jì)數(shù)器k模擬報(bào)數(shù)，當(dāng)k==m 時(shí)，將k置0再?gòu)念^報(bào)數(shù)。

4． 用一個(gè)變量quit_num記錄出圈的人數(shù)，當(dāng)圈中只剩一個(gè)人時(shí)，即quit_num == n-1,停

止報(bào)數(shù)，輸出結(jié)果。

5． 對(duì)數(shù)組進(jìn)行搜索，查找編號(hào)不為零的人(留在圈中的人)，輸出他的編號(hào)。

流程圖：見(jiàn)下圖

開(kāi)始

給 p,k賦初值

m,

給所有的人編號(hào)

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

查找留在圈中的人

輸出結(jié)果

結(jié)束

流程圖

程序代碼：

#include "iostream.h"

#define nmax 200

void main()

{

int i = 0; //循環(huán)變量

int k = 0; //報(bào)數(shù)的計(jì)數(shù)器

int m = 0; //退出的人數(shù)

int n; //總?cè)藬?shù)

int num[nmax]; //保存所有人的編號(hào)

int *p = num; //初始化指針,使其指向num數(shù)組

cout<<"請(qǐng)輸入總?cè)藬?shù)(不大于200):";

cin>>n;

p=num;

//給所有的人編號(hào)為1到n

for(i=0;i

*(p+i)=i+1;

i=0;

k=0;

m=0;

//當(dāng)未退出人數(shù)大于1時(shí) 執(zhí)行循環(huán)

while(m

{

if(*(p+i)!=0) k++; //已經(jīng)出圈的人不參與報(bào)數(shù)

if(k==3)

{

*(p+i)=0; //退出圈子時(shí)將此人的編號(hào)置為0

k=0; //重新報(bào)數(shù)

m++;

}

i++;

if(i==n) i=0; //一圈報(bào)完后，再?gòu)念^循環(huán)

}

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

cout<<"最后流下的是"<<*p<<"號(hào)"<

}

方法二：

用鏈表，具體見(jiàn)程序及注釋?zhuān)?/span>

程序代碼：

#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));/*先分配一個(gè)*/

p->pos=1;

int n, i=0, num=3;

cout<<"請(qǐng)輸入總?cè)藬?shù):";

cin>>n;

for(i=2;i<=n;i++)/*再分配其它的,總共n個(gè)*/

{

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

p=p->next;

p->pos=i;

}

p->next=front;/*使之圍成一個(gè)圈*/

i=0;/*從頭開(kāi)始數(shù)*/

last=p=front;/*從頭開(kāi)始數(shù)*/

while(p->next!=p)/*當(dāng)p->next==p時(shí)就只剩一個(gè)了*/

{

i++;/*數(shù)數(shù)*/

if(i==3)/*數(shù)到3了,此退出*/

{

last->next=p->next;

free(p);

p=last;

i=0;

}

last=p;//last的作用是保存前一個(gè)link,如果是雙向鏈表,就不需要它了

p=p->next;//到下一個(gè)人

}

cout<<"最后流下的是"<pos<<"號(hào)"<最后剩下的一個(gè)人的位置

system("PAUSE");

return 0;

}