PKU1012解题

PKU1012解题

PKU1012题，让我费了几天的时间，才终于算是理出个头绪，真是杯具。看来以后的算法路还是相当曲折的，一道题弄个几天，那么多题，到我毕业时，也做了几百道了。

首先来翻译一下题目，锻炼下英语翻译能力：
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.
约瑟夫问题真是臭名昭著，notorious是臭名远扬的意思。我们先来熟悉一下规则：编号为1，2，3，.....n顺序排列的n个人，依次站成一个圈，提供一个数m,从第一个人开始报数，报到m的人要自杀，接下来从第m+1个人开始，从1开始继续报数，报到第m的人自杀，依次类推.....，直到还剩最后一个人，那这个人就可以存活下来了。约瑟夫太聪明了，他在报数前选了一个位置，结果最后只有他守到了最好，存活了下来。举个例子来说，假设n=6,m=5,自杀的顺序是4，6，2，3，而第一个人将会存活下来。

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.
假定这群人里有k个好人，有k个坏人，在这个圆圈里前k个是好人，后k个是坏人，要求你找到最小的m值，使得后k个人坏人自杀完了，才会轮到好人。

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.
输入包括单独的行，包含k值，最后一行是0，你可以假定k是在0到14之间的数。

Output
The output file will consist of separate lines containing m corresponding to k in the input file.
输出对应的m值

Sample Input
3
4
0

Sample Output
5
30

下一步就是解题了，这个题有多种方法求解，如链表法，数组法，递推法。我的程序是用链表法做的，先构建一个包含n个节点的循环链表，每个节点包括其序号，指向下个节点的指针，还有一个布尔变量，指示该节点是否已经被剔除；之后从当前节点（初始为头节点）开始搜索，跳过已被剔除的节点，找到第m－1个节点，如果第m-1个节点的序号在1～k间，将其布尔指示变量设为真，将第m个节点赋给当前节点，用刚才所述的方法继续搜索，而如果其序号大于k,那说明m值选取不当，将m加1，将所有为的布尔指示变量设为false，重新按上述方法进行搜索。

刚刚完全是用编程序的角度来描述解题思路，可能有些费解，如果更通俗一点讲，那就是找到一个报m的节点，那就判断m值是否可取，不可取，将m加1，重来，可取，继续搜，同时把报m的节点删除。我的实现代码如下：
#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct node
{
int no;
struct node* next;
}Node;

Node* head,*current;//头节点

int guys,mth,count_exec;//guys:好人或坏人的数目，count_exec:已经弄死了多少人，mth：隔多少人自杀一个

//建立链表
void build_list()
{
Node *s,*r;
head=(Node *)malloc(sizeof(Node));
head->no=1;
head->next=NULL;

r=head;

for(int i=2;i<=2*guys;i++)
{
s=(Node *)malloc(sizeof(Node));
s->no=i;
r->next=s;
r=s;
}
r->next=head;

total=2*guys;
current=head;
count_exec=0;
}

//删除自杀节点
int delete_node()
{
int temp;
Node *p,*s;
p=current;
for(int i=1;i<=mth-2;i++)
{
p=p->next;
}
s=p->next;
current=s->next;
temp=s->no;
p->next=current;
delete s;
total--;
return temp;
}

//释放内存
void del_list()
{
Node *p,*s;
p=current;
s=p;
for(int i=1;i<=total;i++)
{
s=p->next;
delete p;
p=s;
}
}

//处理主程序
int deal_list()
{
while(true)
{
int temp=delete_node();
if(temp<=guys)
{
mth++;
del_list();
build_list();
count_exec=0;
continue;
}
else
{
count_exec++;
}

if(count_exec==guys)
return mth;
}
}

//打印结果
void print_result()
{
cout<<mth<<endl;
}

int main()
{
while(cin>>guys,guys>0&&guys<14)
{
mth=guys+1;
build_list();
deal_list();
print_result();
del_list();
}
return 0;
}


数组法和链表法类似，为每一个数组元素增加一指示变量，循环求解，不难实现，不多说了。

说一下递推法，这是求解约瑟夫问题的数学解决方法，其简单而又复杂，简单是因其实现起来只有短短的几行，复杂是指它的理解起来很困难，我花了很长时间才弄明白是怎么回事，或许我的脑袋太笨了吧，嘿嘿，说一下大致思路，以设有n个人，以m报数：

将n个人从为开始排序：
0 1 2 3 4 5 ....... n-1
剔除第m%n-1个人（他报m,这一点需要注意，如果m%n==0的话，是指第n-1个人)，将剩下的人列出来：
m%n m%n+1 m%n+2 .... n-1 0 1 ....(总共n-1个），好，将这几个的序号依次变为：
0 1 2 3 4 5 ..... n-2
呵呵，应该可以看得出来了吧，下一步我们就是从这n-1个人的序列里找到要剔除的序号，显示其序号是m%(n-1)-1个人(同样需注意m%(n-1)==0的情况)，将其剔除，将剩下的人列出：
m%(n-1) m%(n-1)+1 m%(n-1)+2 ... n-2 0 1 ...(总共n-2个）,我们采用同样的方法，变为：
0 1 2 3 4 5 .... n-3
...............................
..........................
..................
依次类推，直到还剩一个人。用这种方法，我们不仅可以找到最后一个人的序号，还可以把自杀的序列找出来。试想一下：如果当前我们知道有i个人的自杀序列，我们只需要将依某种规则把它们对应到i+1个人的队列中去，得到他们在i+1个人中序号，加上m%(i+1)-1，那不就是自杀序列了吗? 关键一点是我们该如何对应呢？
设变换前的序列为k k+1 k+2 k+3 ... i-1 0 1 2 ... 变换后的序列为0 1 2 3 4 .... i-1
设x为变换后的某一序号，它在变换前的序列中的序号为(x+k)%(i+1), 其中k又可以通过m%(i+1)得到 你看是不是？

有了以上思路，我们就可以编写算法程序，将自杀序列顺序输出了：
#include<iostream>
#define MAX 10000
int a[MAX];
using namespace std;

int main()
{
int guys,mth,i,j,k;
while(cin>>guys>>mth,guys)
{
a[0]=0;
for(i=1;i<guys;i++)
{
if(mth%(i+1)==0)
a[i]=i;
else
a[i]=mth%(i+1)-1;

k=mth%(i+1);

for(j=0;j<i;j++)
a[j]=(a[j]+k)%(i+1);
}

for(i=guys-1;i>=0;i--)
cout<<a[i]+1<<" ";
cout<<endl;
}
return 0;
}

用以上的递推方法，可以解决PKU1012题了，算法程序如下：
#include<iostream>
#define MAX 14
int a[2*MAX];
using namespace std;

int main()
{
int guys,mth,i,j,k;
bool stop;
while(cin>>guys,guys>0&&guys<MAX)
{
mth=guys+1;
while(true)
{
stop=false;
a[0]=0;
for(i=1;i<2*guys;i++)
{
if(mth%(i+1)==0)
a[i]=i;
else
a[i]=mth%(i+1)-1;

k=mth%(i+1);

for(j=0;j<i;j++)
a[j]=(a[j]+k)%(i+1);
}

for(j=0;j<guys;j++)
if(a[j]+1>guys)
{
stop=true;
break;
}

if(stop)
{
mth++;
continue;
}
else
{
cout<<mth<<endl;
break;
}
}
}

return 0;
}

呵呵，弄了一大堆，费了一大堆工夫，编译也通过了，将几个测试用例输入，也正确了，那应该行了吧，拿到PKU Judge on Line上，TLE!!!运行超时，杯具，又重新运行我的程序，输入13，嘿嘿，半天也没有出来，难怪(注：上述两种方法都没AC，都TLE了）。

在网上搜了一下，找到一个网页http://www.cnblogs.com/lotus3x/articles/1240935.html，源程序如下：
#include <iostream>
#define MAXK 14
using namespace std;

bool check(int n, int k)
{
int all = n * 2, w = k % all;

for (int i = 1; i < n; i++)
{
all--;
if (--w < 0)
w = all;
w = (w + k) % all;
if (w <= n && w > 0)
return false;
}
return true;
}

int main()
{
int m[MAXK];
int i, j, k;

for (i = 1; i < MAXK; i++)
for (j = i + 1; ; j += (j % i == 0) ? i + 1 : 1)
if (check(i, j))
{
m[i] = j;
break;
}
while (cin>>k,k>0&&k<MAXK)
cout<<m[k]<<endl;
return 0;
}

弄到PKU Judge on line上，AC了，对上述程序的Check函数百思不得其解，分析了好久，Check函数对于本题是行得能的，可对于一般情况下的约瑟夫问题就不行了，如果将j设为0～i+1间，结果就是错误了，不知道那位网友的思路是不是仅仅针对此题的。

另外，发现一个很怪的现象，因为觉得此题一下把所有的情况都计算了，觉得没有必要，就小改动了下：
#include<iostream>
using namespace std;

bool check(int n,int k)
{
int all=n*2,w=k%all;

for(int i=1;i<n;i++)
{
all--;
if(--w<0)
w=all;
w=(w+k)%all;
if(w<=n&&w>0)
return false;
}
return true;
}
int main()
{
int guys,j;
while(cin>>guys,guys>0&&guys<14)
{
for(j=guys+1;;j+=(j%guys==0)?guys+1:1)
if(check(guys,j))
{
cout<<j<<endl;
break;
}
}
return 0;
}

按理说，应该可以通过的，可惜，又是TLE，我真的讶异了！

好了，下面不说PKU1012题了，我们看一下约瑟夫问题，约瑟夫问题有很多变种：诸如：

1）不从第一个开始，从第P个开始，那最后剩下的是哪一个？

2）输入m,n,k，输入第k个人是第几个自杀的？

3）给定m和最后一个自杀的编号，问最小的报数n?