请教两道算法问题

Question

package sean.home.test;import java.io.*;public class ShowSequence {
  
  public static void main(String[] args) {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
      System.out.print("Please input an integer which is between 0 and 10: ");
      try {
        int i = Integer.parseInt(in.readLine());
        showSequence(i);
        break;
      }
      catch (IOException io) {
        System.out.println("I/O Exception occurred. Program will exit.");
        break;
      }
      catch (NumberFormatException nfe) {
        System.out.println("NOTCIE: You need to input a number.");
      }
      catch (IllegalArgumentException iae) {
        System.out.println("NOTICE: Your input is outside range(0, 10).");
      }
    }
  }  static void showSequence(int a) {
    if (a<1||a>9) throw new IllegalArgumentException();
    int[] res = new int[a];
    for (int i = 0; i < a; i++) {
      res[i] = i + 1;
    }
    showSeq("", res);
  }  static void showSeq(String prefix, int[] ia) {
    String pref = prefix;
    if (ia.length == 1) {
      System.out.println(prefix+ia[0]);
      return;
    }
    for (int i = 0; i < ia.length; i++) {
      pref += ia[i];
      int[] temp = removeElem(i, ia);
      showSeq(pref, temp);
      pref = prefix;
    }
  }  static int[] removeElem(int at, int[] ia) {
    int iaLength = ia.length;
    if (iaLength == 1) return new int[0];
    int[] res = new int[iaLength - 1];
    for (int i = 0; i < at; i++) res[i] = ia[i];
    for (int i = at + 1; i < iaLength; i++) res[i-1] = ia[i];
    return res;
  }}

Answer 1

package sean.home.test;public class ShowPrime {
  
  static final long MAXVAL = 1000;
  
  public static void main(String[] args) {
    for (long l = 1; l < MAXVAL; l++) {
      if (isPrime(l)) System.out.println(l);
    }
  }
  
  static boolean isPrime(long n) {
    if (n<=1) return false;
    if (n==2) return true;
    if (n%2==0) return false;
    for (int i = 3; (i*i)<=n; i+=2) {
      if (n%i==0) return false;
    }
    return true;
  }
}

Answer 2

哇，丑石兄一定长得很英俊吧！！！
既然如此，也去
http://expert.csdn.net/Expert/topic/2885/2885176.xml?temp=4.108828E-02
看看吧，

Answer 3

//:AllOrder1.java
//计算正整数n的全排列，并打印；比如 n=3 打印出结果为：
//1,2,3
//1,3,2
//2,1,3
//2,3,1
//3,1,2
//3,2,1import java.util.*;
public class AllOrder1 {
public static ArrayList getAllOrder(int n) {
ArrayList al = new ArrayList();
if(1==n) {
al.add(new String[]{Integer.toString(1)});
return al;
} else {
al = getAllOrder(n-1);
ArrayList result=new ArrayList();
for(int i=0;i<al.size();i++) {
String[] arr = (String[])al.get(i);
for(int j=0;j<=arr.length;j++) {
//put 'n' in the int[n-1].
result.add(insert((String[])al.get(i), j, Integer.toString(n)));
}
}
return result;
}
} public static String[] insert(String[] arr, int pos, String n) {  //把n插入arr的所有空隙
String[] result=new String[arr.length+1];
for (int i=0;i<pos;i++) {
result[i]=arr[i];
}
result[pos]=n;
for (int j=pos+1;j<result.length;j++) {
result[j]=arr[j-1];
}
return result;
} public static void main(String[] args) {
int num=4;
ArrayList result = getAllOrder(num);
System.out.println("All result(" + result.size() + "组): ");

ArrayList all = new ArrayList();
for(int i=0;i<result.size();i++) {
String single = join((String[])result.get(i));
all.add(single);
} Object[] allStr = (Object[])(all.toArray());
Arrays.sort(allStr); for(int i=0;i<allStr.length;i++) {
System.out.println(split((String)allStr[i]));
} } public static String join(String[] arr) { //合并，用于排序:1,2,3->123
StringBuffer result=new StringBuffer("");
for(int i=0;i<arr.length;i++)
result.append(arr[i]);
return new String(result);
}

public static String split(String str) {  //拆分:123->1,2,3
StringBuffer result=new StringBuffer("");
for(int i=0;i<str.length();i++) {
result.append(str.substring(i, i+1));
if(i!=str.length()-1)
result.append(", ");
}
return new String(result);
}
}

Answer 4

用递归，ArrayList用来装需要排列组合的数，。若原数组只有一个元素，则结果只有一个——它自己把它加到set中即可；若原数组多于一个元素，则结果是从中取出一个元素，然后将剩下的元素排列组合，先前取出的元素加到每一个排列组合中即可。代码如下：
import java.util.*;public class Permutation {
  public static void main(String[] args) {
    int count =0;
    Permutation p = new Permutation();
    ArrayList sourceList = new ArrayList();
    //初始化要排列组合的数列
    for(int i=1; i<=2; i++) {
      sourceList.add(new Integer(i));
    }
    sourceList.add(new Integer(2));
    long t1 = System.currentTimeMillis();
    //所有结果将存储在一个HashSet对象中
    HashSet resultSet = p.permute(sourceList);
    long t2 = System.currentTimeMillis();
    Iterator rit = resultSet.iterator();
    while(rit.hasNext()) {
      System.out.println((ArrayList)rit.next());
      count++;
    }
    System.out.println(count);
    long t3 = System.currentTimeMillis();
    System.out.println("Permutation Time: " +(t2-t1));
    System.out.println("Total Time: " +(t3-t1));
  }  /*执行排列组合的具体方法：递归。若原数组只有一个元素，则结果只有一个——它自己
    把它加到set中即可；若原数组多于一个元素，则结果是从中取出一个元素，然后将剩下
    的元素排列组合，先前取出的元素加到每一个排列组合中即可*/
  public HashSet permute(ArrayList list) {
    HashSet set = new HashSet();
    if(list.size()==1) {
      set.add(list);
    }
    else if(list.size()>1) {
      for(int i=0; i<list.size(); i++) {
        Integer integer = (Integer)list.get(i);
        //克隆一个副本进行后续操作，以免原数组改变而影响下次循环。
        ArrayList cList = (ArrayList)list.clone();
        //将剩下的元素排列组合
        cList.remove(i);
        HashSet tempSet = permute(cList);
        Iterator it = tempSet.iterator();
        //把取出的元素与剩下元素的每一个排列组合相加
        while(it.hasNext()) {
          ArrayList tempList=(ArrayList)it.next();
          tempList.add(0,integer);
          set.add(tempList);
        }
      }
    }
    return set;
  }
}Java中没有局部对象的概念（只有局部引用），对象可以认为总是全局的，只要当没有任何引用再指向它时，JVM才会回收它。但本程序中必须要得到局部的对象才能使递归和循环不受影响，所以用clone()来实现。
因为排列组合不会涉及到数组内数值的改变，只是顺序改变罢了，所以浅层克隆就可以满足需求。