c++算法问题（围圈，数数退出）

Question

有n只猴子，按顺时针方向围成一圈选大王（编号从1到n），从第1号开始报数，一直数到m，数到m的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入n，m后，输出最后猴王的编号。

怎么做？
越具体越好。。。THX

Answer 1

约瑟夫问题(一)
这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。这个是愿意。

现在的衍生问题

就是说有n个人围成一圈，然后说从任意指定的一个
人那里为起点，以m个人为单位，每转m个人第m个人被杀死。当起始人也就是所谓的
第1个人是最后被杀死的，这个m就是为所求，满足这样就叫joseph问题。

然后带一个超叼的递归实现

#include<iostream.h>
#include<stdlib.h>
void make(int *base,int n,int pos,int c,int m)//参数的意义。base数组名，n数组长度。pos跑格的一个东西。c计算次数的。m每次跑路的长度。
{
int j=0;
cout<<"NO. "<<++c<<" 第"<<pos+1<<"位出列"<<endl;//输出
base[pos]=0;//踢掉
if(c==n)return; //出口
while(j-m)if(base[pos=(pos+1)%n])j++;//递归点 ,每次数到几这个3就改到几
make(base,n,pos,c,m);//递归
}
int main()
{
int n,m,c=0,pos;//从N开始数,则把pos改为N-1就行了.
cout<<"请输入总人数"<<endl;
cin>>n;
cout<<"请输入要隔几个人:"<<endl;
cin>>m;
int *base=new int[n];
for(int i=0;i<n;i++)base[i]=1;
pos=m-1;
make(base,n,pos,c,m);
delete[]base;
system("PAUSE");
return 0;
}

参考资料：http://blog.csdn.net/tw7613781/archive/2007/03/13/1528312.aspx

Answer 2

#include<iostream.h>

void main()
{
int m,n,i,j,k,p;

cout<<"请输入猴子个数："<<endl;
cin>>n;
cout<<"请输入编号："<<endl;
cin>>m;
int *a=new int[n];

for(i=0;i<n;i++)
a[i]=i+1;
cout<<"共有"<<n<<"只猴子，";
j=1;
p=1;
while(n>1)
{
if(j%m==0)
{
for(k=p;k<n;k++)
a[k-1]=a[k];
n--;
p--;
}
j++;
p++;
if(p>n)
p=1;
}
cout<<"数到第"<<m<<"个下去，剩下的是第"<<a[0]<<"号";
}本回答被提问者采纳

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#define MAX 100000
typedef struct node
{
int data;
struct node *next;
}Node;
typedef Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
clock_t start, stop;

void init(List *L) //initilize the list L
{
*L=(Node*)malloc(sizeof(Node));
(*L)->data=-1;
(*L)->next=NULL;
}

void insert(Position p,int x){// insert the elemnet x after the position of p
PtrToNode q,r;
q=(Node*)malloc(sizeof(Node));
q->data=x;
r=p->next;
q->next=r;
p->next=q;
}

void delect(Position p){// delect the element after p
PtrToNode tmp;
tmp=p->next;
p->next=tmp->next;
free(tmp);
}

void MakeList(List *L,int n){//make the list
int i;
Position p=L;
for(i=1;i<=n;i++){
insert(p,i);
p=p->next;
}
}

void main()
{
int i,j,n,m;
Position p,q,r;
List L;
double duration;
while(scanf("%d%d",&n,&m)!=EOF){//input the number to slect
if(n>MAX){
printf("The number is too large!\n");
continue;
}
init(&L);//initilze the list
MakeList(L,n);//make the list
start = clock();
q=p=L->next;// p and q are the first position of the list
for(i=0;i<n;i++){

for(j=1;j<m-1;j++){//find the porper position of p
p=p->next;
if(p==NULL)p=q;
}
r=p->next; // r is the position of the element we select
if(r==NULL)r=q;

if(i!=n-1)printf("No%d: %d\n", i+1, r->data);//print the element
else printf("Last No is: %d\n",r->data);

if(p->next==NULL){
delect(L);
q=L->next;//delect the position of p->next
}
else delect(p);
p=p->next;
if(p==NULL)p=q;
}
stop = clock();
duration = ((double)(stop - start))/CLK_TCK;
printf("The time is %f\n",duration);
}
}
这个给出运算所需的时间。当n=100000时，时间大部分都是花在输出，但是一共17s左右