Question

C++猴子选大王问题

M只猴子选大王
M只猴子选大王，方法：所有猴子按1……M编号围成一圈，从第一个开始按顺序1，2，3报数，报到3的退出，如此循环，直到最后一只，那只就是猴王。

Answer 1

花了一点时间思考才写出来的。由于采用遍历数组作为while循环的条件表达式,所以开销较大,应该可以优化的.
程序代码：
<script>
//假设7个猴子围成一圈.将7个猴子存储在一个数组中
var arr=new Array(7);
arr[0]=1;
arr[1]=2;
arr[2]=3;
arr[3]=4;
arr[4]=5;
arr[5]=6;
arr[6]=7;
//数组最大下标
var arrlen=arr.length-1;
//检测数组是否还剩一个不为0的元素值,0表示该猴子已退出
function remainOne()
{
var count=0;
for(i=0;i<arr.length;i++)
{
if(arr[i]!=0)
{
count++;
}
}
if(count==1)
{
return false;
}else{
return true;
}
}var k=0;
var m=0; //m为数组的动态下标
//不断循环数猴子一直数到剩下一个为止
while(remainOne())
{
if(arr[m]!=0)
{
++k;
}
//当k=3时表示数到第三只猴子,则该猴子退出
if(k==3)
{
//将k重置为0,重新开始数
k=0;
//该位置的猴子退出
arr[m]=0;
}
m++;
//如果m超出了最大的数组下标,则从最小下标重新开始
if(m>arrlen)
{
m=0;
}
}
for(i=0;i<arr.length;i++)
{
if(arr[i]!=0)
{
alert("猴王是："+arr[i]);
}
}
</script>

Answer 2

/*23:00-23:16-23:21*/
#include <stdio.h>
#include <stdlib.h>
struct node {int no;<br> struct node *next;<br> };
struct node *creatlink(int n)
{int i;<br> struct node *h,*p;<br> if(n<=0) h=NULL;<br> else {h=(struct node *)malloc(sizeof(struct node));<br> h->no=1;h->next=h;<br> for(i=n;i>=2;i--)<br> {p=(struct node *)malloc(sizeof(*p));<br> p->no=i;p->next=h->next;<br> h->next=p;<br> }
}
return h;
}
struct node *dellink(struct node *h,int c)
{int k=1;<br> struct node *p;<br> if(h==NULL||c<=0) return NULL;<br> else<br> {while(h->next!=h)<br> {while(k+1!=c){h=h->next;k++;}
p=h->next;
h->next=p->next;
free(p);
h=h->next;k=1;
}
}
return h;
}void main()
{int number,count;<br> struct node *head;<br> printf("\nHow many monkeys[>0]?: ");<br> scanf("%d",&number);<br> head=creatlink(number);<br> printf("\nHow to count[interval>0]?: ");<br> scanf("%d",&count);<br> head=dellink(head,count);<br> if(head==NULL)<br> printf("\nNo solution!");<br> else printf("\nThe %dth monkey is king.",head->no);<br> }

Answer 3

一个简单的单链表循环的问题，我这里正好有一个示例。原题是一群人围成一群，数到3的人出去，应该和你的题一摸一样吧。#include<iostream>
#include<conio.h>
#include<iomanip>
using namespace std;
typedef struct Lnode{
int data;
struct Lnode *next;
}LNode,*LinkList; void CreatList(LinkList &L,int n);
void Show(LinkList L);
void ShowList(LinkList L); void main(int argc, _TCHAR* argv[]){
int number;
LinkList L;
cout<<"多少个人围成的圈子:";
cin>>number;
CreatList(L,number);
cout<<"原圈子的样子:"<<endl;
ShowList(L);
Show(L);
getch();
} void CreatList(LinkList &L,int n){
LinkList pc,p;
int num=1;
while(num<=n){
if(num==1){
L=new LNode;
L->data=1;
L->next=L;
pc=L;
}else{
p=new LNode;
p->data=num;
p->next=pc->next;
pc->next=p;
pc=p;
}
num++;
}
} void ShowList(LinkList L){
LinkList p=L;
while(p->next!=L){
cout<<p->data<<setw(3);
p=p->next;
}
cout<<p->data<<endl;
}
void Show(LinkList L){
LinkList pc=L;
LinkList pr;
int count=1;
for(;pc->next!=pc;count++){
if(count%3==0){
pr->next=pc->next;
if(pc==L)
L=pc->next;
delete pc;
pc=pr->next;
ShowList(L); }else{
pr=pc;
pc=pc->next;
}
}
cout<<"最后留在圈子里的人的号码是: "<<pc->data<<endl;
}