关于jos环,使用递推公式简化问题和代码,关键在于找到正确的递推公式,可使用一个例子来寻找。
(数学能力较差,只好打个表找规律了)
为方便取余运算,将编号1---n的下标表示为0--(n-1) 举例n=11,m=3,即11个人报数,报到3的人出列
下标 0 1 2 3 4 5 6 7 8 9 10
序号 1 2 3 4 5 6 8 9 10 11
一, 4 5 6 8 9 10 11 1 2
二, 7 8 9 10 11 1 2 4 5
三, 10 11 1 2 4 5 8
四, 2 4 5 7 8 10 11
五, 8 10 11 2 4
六, 11 2 4 8
七, 8 11 2
八, 2 8
九, 2
十, 7
推到最后可知存活者为7号(红色标记),对应下标(此下标应为最原始所对应的)为6,(实际上无论n,m为何值最后存活的人下标均为0)。
观察红色标记,可发现从第一行开始,每一次7对应的下标都往前推了三位(在自己所在的那一行推);
由此从上至下7对应的下标 6->3->0->6->3->0->3->0->1->1->0;
现在要做的就是从右开始往左边推出最原始的下标,再加一就是存活者序号;
推出过程即将当前坐标向右平移三位,不难发现此时推倒时应对应上一行的人数推倒~-~;
公式: (当前下标+m)%(当前所在行对应的上一行的人数);
还以11-3为例: (0+3)%2=1--> (1+3)%3=1-->(1+3)%4=0-->(0+3)%5=3......(省略).....(3+3)%11=6;得出最终下标,加一为序号7;
代码rx:
using namespace std;
int jos(int n,int m)
{
int i,k=0;
for (i=2;i<=n;i++)
k=(k+m)%i;
return k+1;
}
int main()
{
int n,m;
while (cin>>n>>m)
cout<<jos(n,m)<<endl;
return 0;
}
当然也可通过设变量为字母找到此规律-.-;