choose.java

来自「java xml开发指南（初学者推荐）Java Xml 编程指南书籍源码」· Java 代码 · 共 63 行

package MyNa.utils;

import java.math.BigInteger;
import java.util.*;
public class Choose extends Cache {

/*
choose(n,k)=0, if(k>n or k<0)
           =1, if(n==k or k==0)
            choose(n-1,k)+choose(n-1,k-1) otherwise
*/


public BigInteger biV(int n){  // big-integer value conversion
  return BigInteger.valueOf(n);
}


public BigInteger choose1(int n, int k)
        throws ArithmeticException{ // traditional recursive answer.
  if(n<k || k<0)return biV(0);
  if(n==k || k==0)return biV(1);
  return choose1(n-1,k).add(choose1(n-1,k-1));
}


public BigInteger choose(int n,int k)
      throws ArithmeticException{
  BigInteger biN=biV(n); BigInteger biK=biV(k); 
  BigInteger R=(BigInteger)get(biN,biK);
  if(null!=R)return R;
  if(n<k || k<0)R=biV(0);
  else if(n==k || k==0)R= biV(1);
  else R= choose(n-1,k).add(choose(n-1,k-1));
  return (BigInteger)put(biN,biK,R);
}

private static Cache instance=null; // the one and only class instance
private static int clients=0;       // how many are asking us?

protected void init(){super.init();}  // e.g., register, init logger
 
public static synchronized Cache getInstance(){ 
  if(null==instance)instance=new Choose();
  clients++;
  return instance;
}

public static synchronized int freeInstance(){ 
  if(null==instance)return 0;
  clients--;
  if(clients==0)close(); // all gone, and the cache with it.
  return clients;
}

public static synchronized boolean close(){ 
  clients=0;instance=null;
  return true;
}


}