c/c++编程题之猴子选大王（数组、链表两种方法）

题目描述

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

输入

输入在一行中给一个正整数N（<=1000）。

输出

在一行中输出当选猴王的编号。

样例输入

样例输出

AC代码如下：

#include "iostream"
using namespace std;

int main(int argc, char* argv[])
{
	int count=0,num,i;
	int a[1010],n;
	cin>>n;
	num=n;//记录未退出的猴子数
	for (i=1;i<=n;i++)
	{
		a[i]=1;//每个猴子标记为1，表示该猴子未退出
	}
	while(num!=1)//当只有一猴子时，退出循环
	{
		for (i=1;i<=n;i++)
		{
			if (a[i]==1)
			{
				count++;
			}
			if (count==3)
			{
				a[i]=0;  //
				num--;   //退出一只猴子
				count=0;
			}
		}
	}
	for (i=1;i<=n;i++)
	{
		if (a[i]==1)//输出最后剩下的那只猴子，猴王
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

链表实现：

#include <iostream>
#include <stdio.h> 
using namespace std;

struct node{
	int data;
	int last;
	int next;
};

struct node a[1100];

int main(int argc, char** argv) {
	int n;
	while(scanf("%d",&n)==1)
	{
		for(int i=2;i<n;i++)
		{
			a[i].data=i;  a[i].last=i-1;  a[i].next=i+1;
		}
		a[1].data=1; a[1].last=n;   a[1].next=2;
		a[n].data=n; a[n].last=n-1; a[n].next=1;
		
		int num=1;       //记录报数次数 
		int count=1;     //记录当前猴子的序号 
		while(a[count].next!=a[count].data)
		{
			if(num%3==0)
			{
				a[a[count].last].next=a[count].next;
				a[a[count].next].last=a[count].last;
				
			}
			num++;
			count=a[count].next;
		}
		printf("%d\n",a[count].data);
	}
	
	return 0;
}