21位水仙花数（算法优化版）

 题目要求：

一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
例如：
当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时，92727满足条件。
实际上，对N的每个取值，可能有多个数字满足条件。
程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。

如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。


 解题思路：

     21位数的每一位数的21次方相加仍等于他本身，这属于大数处理的范畴，所以必须用BigInteger函数来处理，如果是9位数以内的水仙花数可以考虑用爆破来枚举，但21位就要考虑重复的数字了。所以解题主要分三步。

1.写一个函数计算0--9的21次方的大数，并用num[10]保存

2.写一个函数次数[10]保存0--9数字分别出现的次数

3，没有输入，未知的情况，当然要考虑写一个搜索函数，遍历所有的情况咯，所以写一个递归函数

4.最后是计算函数了。。。


输入代码：

/*
 * 21位水仙花数
 */
import java.math.BigInteger;
public class Main 
{

	public static void main(String[] args) 
	{
      BigInteger [] num={Fn(0),Fn(1),Fn(2),Fn(3),Fn(4),Fn(5),Fn(6),Fn(7),Fn(8),Fn(9)};//定义一个数组存贮每个数字的21次方
      
      int [] cishu=new int [10];//定义一个数组存贮每个数字在21位数中出现的次数
      
      fun(num,cishu,0,0);
      
      
	}

	/*
	 * 求n的21次方
	 */
	public  static BigInteger Fn(int n) 
	{
		
	  BigInteger sum=BigInteger.ONE;
	  for(int i=0;i<21;i++)
	  {
		  sum=sum.multiply(BigInteger.valueOf(n));
	  }
		return sum;
	}
	
	//m表示当前处理的是数组cishu的第几位
	//n表示21位的名额已经甩掉了多少
	public static void fun(BigInteger[] num, int[] cishu, int m, int n) 
	{
		if(m==9)
		{
			cishu[9]=21-n;
			jisuan(num,cishu);
			return ;
		}
		
		//对当前位置所有可能进行枚举
		for(int i=0;i<21-n;i++)
		{
			cishu[m]=i;
			fun(num,cishu,m+1,n+i);
		}
		
	}

	public static void jisuan(BigInteger[] num, int[] cishu) 
	{
	  BigInteger ss=BigInteger.ZERO;
	  for(int i=0;i<10;i++)
	  {
		  ss=ss.add(num[i].multiply(BigInteger.valueOf(cishu[i])));
	  }
		
	  String str=""+ss;
	  
	  if(str.length()!=21)
	  {
		  return ;
	  }
	  
	  int []cishu2=new int [10];
	  
	  //确认和中各数字各出现多少次
	  
	  for(int i=0;i<21;i++)
	  {
	    cishu2[str.charAt(i)-'0']++;
	  }
	  
	  //测试数组cishu和数组cishu2是否完全匹配
	  
	  for(int i=0;i<10;i++)
	  {
		  if(cishu[i]!=cishu2[i])
		  {
			  return ;
		  }
	  }
	  
	  //完全匹配，打印结果
	  System.out.println(str);
	}

}