水仙花数----算法3

/**
 *
 * @author 东海陈光剑  2013-4-26下午1:00:36
 * flower2.java
 * chenguangjian iSword
 * Email：[e-mail]
 * Blog: http://blog.sina.com.cn/universsky11/
 *       http://blog.csdn.com/universsky
 *       http://blog.163.com/universsky@126/
 */

package iSword;

/**
 *
 * @author 东海陈光剑  2013-4-26下午1:00:36
 * flower2.java
 * chenguangjian iSword
 * Email：[e-mail]
 * Blog: http://blog.sina.com.cn/universsky11/
 *       http://blog.csdn.com/universsky
 *       http://blog.163.com/universsky@126/
 */


import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;

public class Test {

    public static void main(String[] args) {
        Test test = new Test(21);
        HashSet<BigInteger> set = new HashSet<BigInteger>();
        int s = test.MAX.divide(test.p(9)).intValue();
        for (int i = 0; i <= s; i++) {
            BigInteger temp = test.solve(i);
            if(temp != null) set.add(temp);
        }
        BigInteger[] result = new BigInteger[set.size()];
        set.toArray(result);
        Arrays.sort(result);
        for(BigInteger bi : result){
            System.out.println(bi);
        }
    }

    public Test(int size){
        this.size = size;
        int s = size < 10 ? 10 : size;
        for (int i = 0; i <= s; i++) {
            ht.put("n_" + i, new BigInteger(String.valueOf(i)));
        }
        for (int i = 0; i <= 10; i++) {
            ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(size));
        }
        MIN = n(10).pow(size - 1);
        MAX = n(10).pow(size).subtract(n(1));
    }

    private int size;

    private int[] array = new int[10];

    private int[] sumArray = new int[10];

    private BigInteger[] totalSum = new BigInteger[10];

    private int index = 0;

    private BigInteger ZERO = BigInteger.ZERO;

    private BigInteger MIN ;

    private BigInteger MAX;

    private Hashtable<String, BigInteger> ht = new Hashtable<String, BigInteger>();

    private BigInteger n(int i) {
        return ht.get("n_" + i);
    }

    private BigInteger p(int i) {
        return ht.get("p_" + i);
    }

    private boolean checkPersentArray() {
        BigInteger minVal = totalSum[index];
        BigInteger maxVal = totalSum[index].add(p(9 - index).multiply(
                n(size - sumArray[index])));
        if (minVal.compareTo(MAX) > 0) {
            return false;
        }
        if (maxVal.compareTo(MIN) < 0) {
            return false;
        }
        String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN
                .toString();
        String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX
                .toString();
        int[] sameCountArray = new int[10];
        for (int i = 0; i < size; i++) {
            char c;
            if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {
                sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;
            } else {
                break;
            }
        }
        for (int i = 0; i <= index; i++) {
            if (array[i] < sameCountArray[9 - i]) {
                return false;
            }
        }
        if (sumArray[index] == size) {
            String sumStr = totalSum[index].toString();
            BigInteger sum = ZERO;
            for (int i = 0; i < sumStr.length(); i++) {
                sum = sum.add(p(sumStr.charAt(i) - '0'));
            }
            return sum.compareTo(totalSum[index]) == 0;
        }
        return true;
    }

    private void setValue(int num) {
        array[index] = num;
        if (index == 0) {
            sumArray[index] = num;
            totalSum[index] = p(9 - index).multiply(n(num));
        } else {
            sumArray[index] = sumArray[index - 1] + num;
            totalSum[index] = totalSum[index - 1].add(p(9 - index).multiply(
                    n(num)));
        }
    }

    private boolean back() {
        if (array[index] == 0) {
            while (array[index] == 0) {
                if (index > 0) {
                    index--;
                } else {
                    return true;
                }
            }
        }
        if (index > 0) {
            setValue(array[index] - 1);
            return false;
        } else {
            return true;
        }
    }

    private BigInteger solve(int startValue) {
        index = 0;
        setValue(startValue);
        while (true) {
            if (checkPersentArray()) {
                if (sumArray[index] == size) {
                    return totalSum[index];
                }
                if (index != 9) {
                    index++;
                    setValue(size - sumArray[index - 1]);
                    continue;
                }
            }
            if (back()) {
                break;
            }
        }
        return null;
    }

}