Question

C++约瑟夫环问题，题目要求输出最后一个人的编号，并且要允许多组数据的输入和输出

例如，输入是
6 2
12 4
8 3
0 0

输出应为
5
1
7

求帮忙，谢谢！

Answer 1

//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdlib.h"
#include <iostream>
using namespace std;
int main(void){
int i,j,k,M,S,x,*p;
while(1){
cout << "Please input M(int M>0) & S(int S>0)...\n";
if(cin >> M >> S,M==0 && S==0)
break;
if(M>0 && S>0 ){
if(p=new int[M],p){
for(i=0;i<M;p[i]=1+i++);
for(x=M-1,k=j=i=0;k<M;i<x ? i++ : i=0)
if(p[i]!=0 && ++j==S){
p[i]=j=0;
k++;
}
cout << "The last one is the No." << (i ? i : M) << endl;
delete [M]p;
}
else{
cout << "Application memory failure...";
exit(0);
}
}
else cout << "Error,redo: ";
}
cout << endl;
return 0;
}

Answer 2

#include <iostream>
using namespace std;

int n,m,ans;

int main()
{
while (scanf("%d%d",&n,&m))
{
ans=0; if (n+m==0) return 0;
for (int i=1;i<=n;i++) ans=(ans+m)%i;
printf("%d\n",ans%n+1);
}
}

追问

你这个代码不对。。。

追答

你给的三个样例都通过了啊，可以给出问题的数据吗？

我简单的解释一下这给代码吧。(先定义一下人的位置从0开始标号)
这样考虑，一开始有n个人站成一圈，从第一个人开始报数，报到m的人出列。
接下去相当于有n-1个人站成一圈，从第m+1个人开始报数，到m的出列，这是一个子问题，只不过每个人的位置从i变到了 (i+m)%n，设f[n]表示n个人报数是出去的人的标号，那么就有f[n]=(f[n-1]+m)%n。
然后f[n]其实不用存，我给出的代码中用ans代替了

追问

能具体解释一下为什么是(i+m)%n吗 你这个是对的我就是不知道为什么。。。

追答

可以换一种理解方式
首先，n个人围成了一个环，定义环的第一个人标号为0，接着为 1，2，3...n-1
这样的话第 i 个人后m位的人的标号就是 (i+m)%n，比如说n=5第3个人后4位的人的标号就是(3+4)%5=2
f[n]表示n个人报数的话最后一个走出的人位于第一个报数的人后几位
考虑如何从f[n]推出f[n+1]
n+1个人报数第一轮首先会走出标号为m-1的人，接着就变成了n个人报数，而这时我已经知道了n个人报数，最后一个走出的人是第一个报数的人后f[n]位，而m-1出列后，第一个报数的人是第m个人，所以我立马就知道了n+1个人报数，最后一个人是位于第m个人后f[n]为的人。
得到 f[n+1]=(f[n]+m)%(n+1)即f[n]=(f[n-1]+m)%n

Answer 3

#include<stdio.h>
int main(void)
{
int a[1000];
int n,m,i,j=0,t;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
a[i]=i;
while(1)
{
for(i=1;i<=n;i++)
{
if(a[i]) {j++;printf("(%2d) ",a[i]);}
if(j%m==0&&a[i]!=0)
{
printf(" %2d\n",a[i]);
t=a[i];
a[i]=0;
}
}
if(j==m*n)
{
printf("最后胜利的人是：%d号\n",t);
break;
}
}
}

Answer 4

你这个是简单的吧？等下我电脑网络好了给你写一个。