Question

C 语言中关于猴子选大王的代码

问题描述：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照从1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。基本要求：（1）利用单循环链表结构模拟此过程；（2）输入数据：输入m,n m,n 为整数，n<m（3）按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。先谢谢各位高手了！

Answer 1

注释写得很清楚 相信你能看懂 #include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct Node
{
int data;//存储猴子编号
struct Node *next;
}*List;

/* 用链表来得出大王的序号 */
int LinkedList(int num_monkey,int number);

/* 用顺序表来得出大王的序号 */
int SequenceList(int num_monkey,int number);

/* 创建循环单链表 */
List CreateList(int n);

void main()
{
int m, n, way, king;
printf("请输入猴子个数:");
scanf("%d", &n);
printf("请输入要报的数:");
scanf("%d", &m);

while (1)
{
printf("\n请选择解决问题的方法:\n");
printf("1.单链表\n");
printf("2.顺序表\n");
scanf("%d", &way);

if (way == 1)
{
king = LinkedList(n,m);
break;
}
else if (way == 2)
{
king = SequenceList(n,m);
break;
}
else
{
printf("输入不合法!\n");
}
}
printf("%d号猴子是大王\n", king);
}

/* 创建循环单链表 */
List CreateList(int n)
{
int i;
List head, p;
head = (List)malloc(sizeof(struct Node));
head->next = head;
for (i = 1; i < n; ++i)
{
p = (List)malloc(sizeof(struct Node));
p->next = head->next;
head->next = p;
}
p = head;
for (i = 0; i < n; ++i)
{
p->data = i+1;
p = p->next;
}
return head;
}

/* 用链表来得出大王的序号 */
int LinkedList(int num_monkey,int number)
{
int i,j;
List head = CreateList(num_monkey);
List tail = head;//用来存储最后一个节点的地址
List out,p;//out指向要淘汰的节点,p指向其前一个节点

/* 让tail指向最后一个节点 */
for (i = 1; i < num_monkey; i++)
{
tail = tail->next;
}

/* 淘汰的猴子个数比总个数少1，报数一轮就淘汰一个猴子，所以需要报数的轮数比
猴子总个数少1*/
for( i = 1; i < num_monkey; i++ )
{
p = tail;
/* 让p指向要淘汰的猴子的前一个 */
for ( j = 1; j < number; j++ )
{
p = p->next;
}
out = p->next;
/* 如果最后一个猴子被淘汰就更新尾节点 */
if (out == tail)
{
tail = p;
}
p->next = out->next;
printf("猴子%d淘汰\n", out->data);
free(out);//删除被淘汰猴子的节点
}
return p->data;
}

/* 用顺序表来得出大王的序号 */
int SequenceList(int num_monkey,int number)
{
/* 用来表示个猴子的信息，如果猴子出局就存储0，否则存储1。第一个元素不使用 */
int monkey[MAXSIZE];
/* 用来表示出局的猴子的序号 */
int out = 1;
/* 用来表示当前猴子的个数 */
int num_now = num_monkey;
int i,j;
for (i = 0; i < num_monkey+1; i++)
{ /* 开始将每个元素置1 */
monkey[i] = 1;
}

/* 报数次数比猴子个数少一 */
for (i = 1; i < num_monkey; i++)
{
out = 1;
/* 报数整个过程 */
for (j = 0; j < number; j++)
{
/* 如果序号数大于猴子个数，表示循环了一圈，那么去掉那个圈数 */
if (out > num_monkey)
out -= num_monkey;

/* 之前已经出局的猴子不参加报数 */
while(monkey[out] == 0)
{
out ++;
/* 如果序号数大于猴子个数，表示循环了一圈，那么去掉那个圈数 */
if (out > num_monkey)
out -= num_monkey;
}
out++;

}
out--;//报完数后out应该是被淘汰的猴子的下一个，所以要向前移动

monkey[out] = 0;
printf("猴子%d淘汰\n",out);

}
while(monkey[out] == 0)
{
out ++;
/* 如果序号数大于猴子个数，表示循环了一圈，那么去掉那个圈数 */
if (out > num_monkey)
out -= num_monkey;
}
return out;
}

Answer 2

main()
{
void left(int *p, int n);
int i, num[100], n;
printf("How many monkey?");
scanf("%d",&n);
for(i=0;i<n;i++)
num[i]=i+1;
left(num, n);
for(i=0;i<n;i++)
if(num[i]!=0)
printf("No.which left last is :%d",num[i]);
}

void left(int *p, int n)
{
int i=0, out=0, count=0;
while(out<n-1)
{
if(*(p+i)!=0)
count++;
if(count==3)
{
*(p+i)=0;
count=0;
out++;
}
i++;
if(i==n)
i++;
}
}