约瑟夫问题——算法优化

在华为的OJ自学平台上有个约瑟夫问题，不过它不是原来意义上的约瑟夫问题，而是其变体，做了这个题之后，有一点关于算法优化的小想法，因此想写下来。

问题的描述如下：

 功能: 约瑟夫问题众所周知，原始的约瑟夫问题是这样的：有n个人，编号为1,2,..., n，站成一圈，

 每次第m个将会被处决，直到只剩下一个人。约瑟夫通过给出m来决定赦免其中的一个人。

 例如当n=6,m=5时，5,4,6,2,3将会被依次处决，而1将会幸免。

 假如有k个好人，和k个坏人，所有人站成一圈，前k个人是好人，后k个人是坏人，

 编写程序计算一个最小的m，使k个坏人都被处决，而不处决任何好人。

     

 输入: k 为正整数   

 输出: 

 返回: 最小的m，使k个坏人都被处决，而不处决任何好人。

一开始拿到这个题还真有点摸不着头脑，想来想去也不知如何下手，因为我在纸上随便试了几个数，感觉给定的k越大，所需的m&＃20540;就可能会呈指数幂增长，即使能做出来，提交后肯定会计算超时。

不过，先管不了那么多了，上网搜一搜看有没有现成的代码，符合这个题目的没找到，解原始约瑟夫问题的到是有一大堆，这里的一篇不错，就先拿去分析了一下代码。核心代码就是以下这段了：

//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(len>0){
if(a[i%n]>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(a[i%n]+" ");
a[i%n]=-1;
j=1;
i++;
len--;
}else{
i++;
j++;
}
}else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
i++;
}
}

这个算法的基本思路就是：先创建一个从1到n的递增数组，对数组进行遍历，找到要圈出的人，即计数器j为m的整数倍（j%m=0）,将其打印出来，标记为-1，计数器重新回到1，索引加一，数组长度-1（实际长度并未减）;若计时器j不是m的整数倍，则将计数器和索引i各自增1进入下一次循环。

由于采用数组，有一点不好的地方就是它的长度不可变，已经“删除”的数下次还会被判断，如果数组比较大，删除的数较多时，就会有大量无用的判断，因此决定采用用Java里的list试一试。为了不同实现方法的对比，将上面的核心算法提取为放方法，代码如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
*/
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");

//提示输入总人数
System.out.println("请输入做这个游戏的总人数：");
Scanner sca=new Scanner(System.in);
int n=sca.nextInt();
//提示输入要出圈的数值
System.out.println("请输入要出圈的数值：");
int k=sca.nextInt();
System.out.println("按出圈的次序输出序号：");
long time1=System.nanoTime();
test1(n,k);
long time2=System.nanoTime();
System.out.println("用时1："+(time2-time1));
test2(n,k);
long time3=System.nanoTime();
System.out.println("用时2："+(time3-time2));
} private static void test1(int n,int m){
//创建有m个值的数组
int[] a=new int[n];
//初始长度，以后出圈一个，长度就减一
int len=n;
//给数组赋值
for(int i=0;i a[i]=i+1;
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(len>0){
if(a[i%n]>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(a[i%n]+" ");
a[i%n]=-1;
j=1;
i++;
len--;
}else{
i++;
j++;
}
}else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
i++;
}
}
}
private static void test2(int n,int m){
//创建有m个值的数组
List list=new ArrayList();
//初始长度，以后出圈一个，长度就减一
//给数组赋值
for(int i=0;i list.add(i+1);
}
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(n>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(list.get(i%n)+" ");
list.remove(i%n);
j=1;
n--;
}else{
i++;
j++;
}
if(i>=n&&n>0)
i=i%n;
}
}
}

对于数据量比较少时，明显是数组占优势，因为list移除一个&＃20540;之后，后面的&＃20540;都会移动，但数据量大了后这个弱点就会被无效比较给抵消掉。

以下贴出将数组改为List的的核心算法：

//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(n>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(list.get(i%n)+" ");
list.remove(i%n);
j=1;
n--;
}else{
i++;
j++;
}
if(i>=n&&n>0)
i=i%n;
}相对于之前用数组，这里面少了个判断&＃20540;是否小于0 if 条件语句，不过加了两句

if(i>=n&&n>0)
i=i%n;当然，上面的list.get(i%n)也可以改为list.get(i)，除此之外，区别不大。以下还是贴出两者对比的完整代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
*/
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");

//提示输入总人数
System.out.println("请输入做这个游戏的总人数：");
Scanner sca=new Scanner(System.in);
int n=sca.nextInt();
//提示输入要出圈的数值
System.out.println("请输入要出圈的数值：");
int k=sca.nextInt();
System.out.println("按出圈的次序输出序号：");
long time1=System.nanoTime();
test1(n,k);
long time2=System.nanoTime();
System.out.println("用时1："+(time2-time1));
test2(n,k);
long time3=System.nanoTime();
System.out.println("用时2："+(time3-time2));
} private static void test1(int n,int m){
//创建有m个值的数组
int[] a=new int[n];
//初始长度，以后出圈一个，长度就减一
int len=n;
//给数组赋值
for(int i=0;i a[i]=i+1;
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(len>0){
if(a[i%n]>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(a[i%n]+" ");
a[i%n]=-1;
j=1;
i++;
len--;
}else{
i++;
j++;
}
}else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
i++;
}
}
}
private static void test2(int n,int m){
//创建有m个值的数组
List list=new ArrayList();
//初始长度，以后出圈一个，长度就减一
//给数组赋值
for(int i=0;i list.add(i+1);
}
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(n>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(list.get(i%n)+" ");
list.remove(i%n);
j=1;
n--;
}else{
i++;
j++;
}
if(i>=n&&n>0)
i=i%n;
}
}
}到了这里，我在想既然用了List链表，这里面就不用判断list里面的&＃20540;了，毕竟点到的都被移出了，其余的都是有用的。而我们的目的是找到第m个，把它移出，然后接着找下一个第m个， 因此，我为什么还要一次一次i&＃43;&＃43;、j&＃43;&＃43;呢，干嘛不一次i&＃43;=m-1，j&＃43;=m-1，这样不是一次性跳到了下一个m个么？
因此，代码稍作更改，速度几乎减半。以下为修改后的方法：

private static void test2(int n,int m){
//创建有m个值的数组
List list=new ArrayList();
//初始长度，以后出圈一个，长度就减一
//给数组赋值
for(int i=0;i list.add(i+1);
}
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(n>0){
if(j%m==0){//找到要出圈的人，并把圈中人数减一
System.out.print(list.get(i)+" ");
list.remove(i);
j=1;
n--;
}else{
i+=m-1;
j+=m-1;
}
if(i>=n&&n>0)
i=i%n;
}
}这个原始约瑟夫算法的优化就先到此了。接着就按题目的要求答题了。
题目的要求是前k个是好人，后k个是坏人，只处决坏人而不出决绝好人，因此这个方法里就不需打印移除的数了，同时while里的循环也不用循环整个数组了，只需循环数组长度的一半就行了，还有这个方法的返回类型就可以改为boolean类型了，移除数的时候，只要一遇到好人，提供的m&＃20540;就不满足条件，需要重新找m&＃20540;了。
（注：鉴于问题有变化，以上的参数需做更改了：原来的n换为k，链表长度为2k）
以下就是再次修改后的代码了：

private static boolean isFit(List list,int k){
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
int len=list.size();
int n=len/2;
while(len>n){
if(j%k==0){
int value=list.get(i);
if(value<=n)
return false;
list.remove(i);
j=1;
len--;
}else{
i+=k-1;
j+=k-1;
}
if(i>=len)
i=i%len;
}
return true;
}接下来就是要通过给定不同的k&＃20540;来找最小的m&＃20540;。找最小&＃20540;，最容易想到的就是对于给定的k&＃20540;，从1开始试，试到该方法返回true时即为所需的k&＃20540;。

于是程序的实现如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");

//提示输入总人数
System.out.println("请输入做这个游戏的好人数：");
Scanner sca=new Scanner(System.in);
int k=sca.nextInt();
//提示输入要出圈的数值
System.out.println("最小的m：");
boolean flag=false;
int c=0;//cycle
int m=1;
while(!flag){
List tmp=new ArrayList();
for(int j=0;j<2*k;j++){
tmp.add(j+1);
}
if(isFit(tmp,m)){
flag=true;
break;
}else{
m++;
}
c++;
}
System.out.print(m);
}
private static boolean isFit(List list,int k){
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
int len=list.size();
int n=len/2;
while(len>n){
if(j%k==0){//找到要出圈的人，并把圈中人数减一
int value=list.get(i);
if(value<=n)
return false;
list.remove(i);
j=1;
len--;
}else{
i+=k-1;
j+=k-1;
}
if(i>=len)
i=i%len;
}
return true;
}
} 这种找m的方法简直是太笨了，至少你可以给它划点范围啊，直接从m开始显然不明智。很明显，对于题目的要求时第一个要处决的是坏人，因此m的第一个尝试&＃20540;的取&＃20540;范围至少要在[k&＃43;1,2k]的范围之内啊，若果这个范围不合适，那就说明m得从大于2k（即至少绕一圈）的&＃20540;开始了。因此，我们可以对这个m取一个初略的范围限定，这样isFit方法的调用次数就再一次减半了。因此，可以对main方法里的代码稍作更改了，实现代码如下：

public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");

//提示输入总人数
System.out.println("请输入做这个游戏的好人数：");
Scanner sca=new Scanner(System.in);
int k=sca.nextInt();
//提示输入要出圈的数值
System.out.println("最小的m：");
boolean flag=false;
int c=0;//cycle
int m=0;
while(!flag){
for(int i=(2*c+1)*k+1;i<=2*k*(c+1);i++){
List tmp=new ArrayList();
for(int j=0;j<2*k;j++){
tmp.add(j+1);
}
if(isFit(tmp,i)){
flag=true;
m=i;
break;
}
}
c++;
}
System.out.print(m);
}

这段代码里加了一个c（即圈数），指的时从1输到m时绕好坏人围成圈的圈数。m的取&＃20540;就被限定在[2k*c&＃43;k&＃43;1,2k*c&＃43;2k]范围内。

终于，代码提交后顺利通过自学平台提供的测试用例。

写到这里，代码基本上达到了目的，不过，这个算法的优化并没有结束，因为当k的&＃20540;达到14时，计算出m的结果就得好几分钟了。

完整实现代码如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");

//提示输入总人数
System.out.println("请输入做这个游戏的好人数：");
Scanner sca=new Scanner(System.in);
int k=sca.nextInt();
//提示输入要出圈的数值
System.out.println("最小的m：");
List list=new ArrayList();
for(int i=0;i<2*k;i++){
list.add(i+1);
}
boolean flag=false;
int c=0;//cycle
int m=0;
while(!flag){
for(int i=(2*c+1)*k+1;i<=2*k*(c+1);i++){
List tmp=new ArrayList();
for(int j=0;j<2*k;j++){
tmp.add(j+1);
}
if(isFit(tmp,i)){
flag=true;
m=i;
break;
}
}
c++;
}
System.out.print(m);
} private static boolean isFit(List list,int k){
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
int len=list.size();
int n=len/2;
while(len>n){
if(j%k==0){//找到要出圈的人，并把圈中人数减一
int value=list.get(i);
if(value<=n)
return false;
list.remove(i);
j=1;
len--;
}else{
i+=k-1;
j+=k-1;
}
if(i>=len)
i=i%len;
}
return true;
}
}

目前，我个人的思路有两个：

其一是每次循环都要建立一个List数组，这里可以考虑在循环外面建立一个list后，在循环里通过java提供的复制函数来复制，这应该比每次新建list要快；

其二是继续压缩m的取&＃20540;范围，上面只提到第一次处决一个坏人时的m范围，处决第二个坏人也是有范围限制的，因此可以从这里入手。

思路就说到这里，具体实现就不细说了，读者如果有兴趣可以自己尝试着去完善！(*^__^*) 嘻嘻……

附OJ自学平台里的demo实现源码：

import java.util.ArrayList;
import java.util.List;
public final class Demo {
/*
功能: 约瑟夫问题众所周知，原始的约瑟夫问题是这样的：有n个人，编号为1,2,..., n，站成一圈，
每次第m个将会被处决，直到只剩下一个人。约瑟夫通过给出m来决定赦免其中的一个人。
例如当n=6,m=5时，5,4,6,2,3将会被依次处决，而1将会幸免。
假如有k个好人，和k个坏人，所有人站成一圈，前k个人是好人，后k个人是坏人，
编写程序计算一个最小的m，使k个坏人都被处决，而不处决任何好人。
输入: k 为正整数
输出:
返回: 最小的m，使k个坏人都被处决，而不处决任何好人。
*/
public static int getMinimumM(int K)
{
boolean flag=false;
int c=0;//cycle
int m=0;
while(!flag){
for(int i=(2*c+1)*K+1;i<=2*K*(c+1);i++){
List tmp=new ArrayList();
for(int j=0;j<2*K;j++){
tmp.add(j+1);
}
if(isFit(tmp,i)){
flag=true;
m=i;
break;
}
}
c++;
}
return m;
}
private static boolean isFit(List list,int k){
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
int len=list.size();
int n=len/2;
while(len>n){
if(j%k==0){
int value=list.get(i);
if(value<=n)
return false;
list.remove(i);
j=1;
len--;
}else{
i+=k-1;
j+=k-1;
}
if(i>=len)
i=i%len;
}
return true;
}
}

约瑟夫问题——算法优化,布布扣,bubuko.com