含有n个数字的圆圈中每次删除第m个元素，求最后剩下的数字，给出程序

含有n个数字的圆圈中每次删除第m个元素，求最后剩下的数字，给出程序

int JohnsonRing(int length, int seg)
{
int arr[100];
int i, k, n;


for(i=0; i arr[i] = 0;
}

i = 0;
k = 1;
n = length;
while(n > 1) {
if(arr[i] == 1){
i = (i + 1) % length;
continue;
}
if(k == seg){
arr[i] = 1;
n--;
printf("%d\n", i+1);
i = (i + 1) % length;
k = 1;
}
else{
k++;
i = (i + 1) % length;
}
}

for(i=0; i return i+1;
}

void main()
{
int remain;
int m, n;
m = 6;
n = 3;
printf("出局顺序 :\n");
remain = JohnsonRing(m, n);
printf("最后的剩余者 : %d\n", remain);
}

这是典型的数学问题：约瑟夫环问题，使用迭代求解，不要模拟，否则n很大时将会耗时很长。这里不再解释算法具体证明过程。
注意，这里的第m个是从上一次结束之后的位置开始计算，第一次从第一个数开始。
#include
int main(){
int n,m,i,w,num[10000];//这个num数组中存放你的n个数，大小请酌情设定
while(scanf("%d%d",&n,&m),n){//输入n和m，输入n=0结束
for(i=0;ifor(w=0,i=2;i<=n;++i)w=(w+m)%i;
printf("%d\n",num[w]);
}
}

#include
int main()
{
const int n=100;////////////////////////n个数字
int m=30;//////////////////////////第m个元素
int a[n];
for(int j=0;j a[j]=j+1;
int k=1;
int i=-1;
while(1)
{

for(int j=0;j {
i=(i+1)%n;
if(a[i]!=0)
j++;
}
if(k==n)
break;
a[i]=0;
k++;
}
cout<<”最后一个数字是“< return 0;
}

Actually, although this is a so traditional problem, I was always to lazy to think about this or even to search for the answer.(What a shame...). Finally, by google I found the elegant solution for it.
The keys are:
1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n
2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th element instead of 0, so the answer is (f(n-1, m)+k+1)%n
3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n.
finally, f(1, m) = 0;
Now this is a O(n) solution.
int joseph(int n, int m) {
int fn=0;
for (int i=2; i<=n; i++) {
fn = (fn+m)%i; }
return fn;
}
微软100题给出的解法

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息