poj1012 Joseph 解题报告

Joseph

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30

题目描述：就是2k个人围成一圈 。 每次报数 报到M的人出局 1 - k是好人 k+1 - 2*k 是坏人 。 M 是多少的时候保证坏人都出局之后好人一个都没有出局

解题思路：对于这个约瑟夫问题，要求的就是把后K个一个个出局，而前K个都没有一个出局的，说明了前K就都没有变，后面变对题目是没有影响的，所以对于N就可以变，当出局一个，N就减少一个，i相对应减一，对于i大于N的，要进行数据处理，让这些数循环起来，一直找到最小符合条件的M

相应的C++代码如下

#include<iostream>
usingnamespacestd;

intmain()
{
intk;
while(cin>>k)
{
if(k==0)
break;
for(intm=k+1;;m++)
{
intn=2*k;
intstate=0;
inti=0;
while(n>k)
{
i+=m;
i=i%n;
if(i>k||i==0)
{
if(i==0)
i=n-1;
else
i--;
n--;
}
else
{
state=1;
break;
}
}
if(state==0)
{
cout<<m<<endl;
break;
}
}
}
return0;
}

但交的时候是超时了 ，在网站搜了一下，得到了一个非常精简的代码，由于k是小于14的，所以就可以直接用数组都弄出来，避免了每次都要去求而花费太多的时间。也理解了用打表来解决超时问题，但要是我那个代码可以改改，求出前面14的全部满足条件的数存在一个数组里，然后直接用就可以了额，当然也可以把那些数直接赋值给数组，代码如下：

#include<stdio.h>

inta[15]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720};
intmain()
{
intk;
while(scanf("%d",&k)==1)
{
if(k==0)
break;
printf("%d/n",a[k]);
}
return0;
}