c语言课程设计：选出一位幸运人士，一定要用递归算法！要源代码，流程图，和算法描述！

Question

一次大型派对的最后节目是选出一位幸运人士，该人将获得派对组织者准备的一个钻石戒指。而选择幸运人士的办法是让所有人员一字排列，然后从左至右点数，凡是奇数号的全部剔除。对于剩下的人员，又从左至右点数，逢奇数号就剔除。如此不断递归下去，直到只剩一人为止。此人即为幸运之人。请设计一个递归算法计算幸运之人所在的位置，并分析该算法的时间效率。

Answer 1

这道题做ACM题目的时候做过，当时使用数组做的，最后因为效率太低通过不了。

G Josephus Problem
Time Limit:1000MS Memory Limit:65535K

题型: 编程题 语言: 无限制

描述
Josephus Problem is an ancient problem named for Flavius Josephus. There are people standing in a circle waiting to be executed. The counting out begins at the
first point in the circle and proceeds around the circle in a fixed direction. In each step, one person is skipped and the next person is executed. The elimination
proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

For example, if there are 10 people in the circle, the executed order is 2, 4, 6, 8, 10, 3, 7, 1, 9. So the 5th person survives.

Now we define a function J(n) to be the survivor’s number when there are n person in the circle, and J^2(n)=J(J(n)), for instance J^2(10)=J(J(10))=J(5)=3,
and J^3(n)=J(J(J(n))), and so on. Could you calculate J^m(n)?

输入格式
The input consists of a number of cases.
Each case contains integers n and m. 0<n, m<=10^9
The input is terminated by a case with m=n=0

输出格式
For each case, print the number J^m(n)

输入样例
10 2
10 1
20 1
0 0

输出样例
3
5
9

Provider
admin
#include<stdio.h>
#include<malloc.h>
#include<math.h>

int J(int number,int * circle)

{
int i,length=number;

for(i=0;i<number;i++)
{
circle[i]=i+1;

}

while(length>1)
{
if(length%2==0)
{
for(i=0;i<length;i++)
{

circle[i]=circle[i*2];

}
length=length/2;
continue;

}
if(length%2==1)
{
circle[0]=circle[length-1];
for(i=1;i<length;i++)
{

circle[i]=circle[(i-1)*2];

}
length=length/2+1;
continue;

}

}

return circle[0];
}

int main()
{

int n,m,i,*circle;

circle=(int*)malloc(n*sizeof(int));
while(1){
{
scanf("%d%d",&n,&m);
}while(n<0||m<0||m>10);
if(n==0&&m==0)
break;
for(i=0;i<m;i++)
{
n=J(n,circle);

}
printf("%d\n",n);

}

return 0;
}