猴子选大王

1.需求分析：

根据问题描述可知，该问题中m个猴子围坐在一起形成首尾相接的环，因此可用循环链表解决。从第n个猴子开始出列相当于从链表中删除一个结点。该程序主要有三个模块组成，建立单链表，报数利用do-while循环实现猴子的出列，最终剩下的猴子即猴王。具体步骤如下：

第一步 首先创建循环链表。

第二步 向单链表中填入猴子的编号

第二步 找第一个开始报数的猴子。

第三步 数到n让这个猴子出列。

第四步 接着开始报数，重复第三步

2.概要设计（流程图）

开始

定义结构体，变量

建立循环单链表

在循环链表填入数据

猴子数数Count++

Count= = n-1？

释放第n个猴子

指针q指向第n+1个节点q=q->next

否

q->next= =q?

是

猴王就是第q-〉data 个猴子

结束

3.详细设计：

#include

#include

struct Node

{

int data

struct Node *next

}

int main()

{

struct Node *head, *s, *q, *t

int n, m, count=0, i

printf("input the number m:")

scanf("%d",&m)

printf(" input the number n:")

scanf("%d",&n)

for(i=0i<i++)>

{

s=(struct Node *)malloc(sizeof(struct Node))

s->data=i+1

s->next=NULL

if(i= =0)

{

head=s

q=head

}

else

{

q->next=s

q=q->next

}

}

q->next=head

printf("before:")

q=head

while(q->next!=head)

{

printf("%d ",q->data)

q=q->next

}

printf("%d ",q->data)

q=head

printf(" ")

do {

count++

if(count= =n-1)

{

t=q->next

q->next=t->next

count=0

printf("%d ", t->data)

free(t)

}

q=q->next

}

while(q->next!=q)

printf(" the king is: %d ",q->data)

}

4.测试数据：

1）input the number m:20

input the number n:5

before:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

5 10 15 20 6 12 18 4 13 1 9 19 11 3 17 16 2 8 14

the king is: 7

2）input the number m:9

input the number n:11

before:1 2 3 4 5 6 7 8 9

2 5 9 7 8 4 1 3

the king is: 6

3）input the number m:10

input the number n:5

before:1 2 3 4 5 6 7 8 9 10

5 10 6 2 9 8 1 4 7

the king is: 3

一群猴子要选新猴王。新猴王的选择方法是：让M只候选猴子围成一圈，从某位置起顺序编号为1~M号。从第1号开始报数，每轮从1报到N，凡报到N的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

请输入猴子的数量m 11

请输入要排除第几个猴子n 3

7

常规做法又两种，一种是数组，一种是链表，（数学方法不考虑）。对于数组方法测试了两种思路，第一种是生成一个键为1-M的关联数组，值为true，退出的键值为false；另一种是值为1-M的数值数组，退出的unset；结果是使用unset效率更高些。链表是用数组模拟的链表，生成键为1-M的关联数组，值为下一位的键值，最后一位的值为1。退出了就把上一位和下一位链接起来。测试表明，使用链表的速度快于数组。

#include <iostream>

using namespace std

template <class datatype>class LinkList

template <class datatype>

class Node

{

friend class LinkList<datatype>//友元类

private:

datatype data//计猴子号

Node<datatype>*next

}

template <class datatype>

class LinkList

{

public:

LinkList()

void monkey(int m) //建立有m个元素的单链表

datatype Get(int a) //取单链表中第i个结点的元素值

datatype Delete(int n)//在单链表中删除第n个结点

private:

Node<datatype>*head,*tail //单链表的结构指针

}

template <class datatype>

LinkList<datatype>:: LinkList( )

{head=new Node<datatype>head->next=NULL}

template <class datatype>

void LinkList<datatype>::monkey(int m)

{

int i//整型变量i，用于计数

Node<datatype>*p,*q//声明结构指针

p=new Node<datatype>//为p分配空间

p->data=1//初始化p结点data域为1

p->next=NULL//初始化p结点next域为空

head=p//链表头指针head赋值为p

q=p //q赋值为p

for (i=2i<=mi++) //用循环结构构造链表

{

p=new Node<datatype>//为p配内存空间

p->data=i //初始化p结点data域为i,表示猴子号

q->next=p//将p点加到链表尾部

q=p //让指向链表尾部结点

p->next=NULL//链表尾部为空

}

tail=q//链表尾

tail->next=head//链表尾部指向链表头，形成循环链表

}

template <class datatype>

datatype LinkList<datatype>::Delete(int n)

{

Node<datatype>*p,*q

int j=0

q=tail//指向循环链表尾部

cout<<"被删除的猴子号码依次为："<<endl

while (q!=q->next) //剩余结点数不为1，则继续循环

{

p=q->next//p赋值给下一个相邻结点

j++

if(j%n==0)

{

cout<<p->data<<ends

q->next=p->next//删除此结点

delete p//释放空间

p=NULL

}

else q=p//q指向相邻的下一个结点p

}

cout<<endl

head=q//head指向结点q,q为链表中剩余的一个结点

return head->data

}

template <class datatype>

datatype LinkList<datatype>::Get(int a)

{

Node<datatype>*p

int j//计数器

p=head->next j=1 //或p=head j=0

while (p &&j<a)

{

p=p->next //工作指针p后移

j++

}

if (!p) throw "a值不合法"

else return p->data

}

void main()

{

int m,n

LinkList<int>mon

cout<<"请输入猴子的总数："<<endl

cin>>m

cout<<"请输入要删除猴子的所报的数："<<endl

cin>>n

mon.monkey(m)

mon.Delete(n)

cout<<"猴王是："<<mon.Get(1)<<"号"<<endl

}

---