import java.math.BigInteger;
import java.util.Arrays;
import java.util.Date;
import java.util.HashMap;
/**
* java使用查表法+組合數學 求水仙花數
* @author [email protected]
* 水仙花數是指一個 n 位數 ( n≥3 ),它的每個位上的數字的 n 次幂之和等于它本身。(例如:1^3 + 5^3 + 3^3 = 153)
*/
public class FlowerNumber {
private HashMap<String, Long> libHashMap=new HashMap<String, Long>();
private Date startTime;
public void store2(int n){
for(int i=0;i<10;i++)
{
libHashMap.put(i+"", (long) Math.pow(i, n));
}
}
public void store(int n)
{
for(int i=0;i<10;i++)
{
//求i的n次方 值為count
long count=1;
for(int j=1;j<=n;j++)
{
count=count*i;
}
libHashMap.put(i+"", count);
}
}
//組合數學方法 機率
public void find2(int n)
{
int[] num=new int[n];
int i=0;
while(true)
{
if(i==(n-1))
{
isSXHS(num);
}else{
i++;
num[i]=num[i-1];
continue ;
}
while(i>=0 && num[i]==9)
{
i--;//回溯
}
if(i>=0)
{
num[i]++;
}else{
break;
}
}
}
private void isSXHS(int[] num) {
//必須得用大整數啊 如28116440335967
BigInteger bigInteger=BigInteger.valueOf(0);
for (int a : num) {
bigInteger=bigInteger.add(BigInteger.valueOf(libHashMap.get(String.valueOf(a))));
int [] tnum=new int[num.length];
String s=String.valueOf(bigInteger);
if(s.length()>num.length)
{
return ;
}
for(int i=0;i<s.length();i++)
{
tnum[i]=s.charAt(i)-'0';
}
Arrays.sort(tnum);
if(Arrays.equals(num, tnum) && s.length()==num.length)
{
System.out.println(bigInteger);
}
}
}
public void find(int n)
{
int minNumber=1;
int maxNumber=9;
for(int i=1;i<n;i++)
{
minNumber=minNumber*10;
maxNumber=maxNumber*10+9;
}
outer:for(int i=minNumber;i<=maxNumber;i++)
{
String iString=String.valueOf(i);
long total=0;
//1643=1+1296+256+81=1^4+6^4+4^4+3^4
for(int p=0;p<n;p++)
{
String key=String.valueOf(iString.charAt(p));
total=total+libHashMap.get(key);
if(total>i){
continue outer;
}
}
if(total==i)
{
long cha=new Date().getTime()-startTime.getTime();
System.out.println("I hava find one:======>>"+i+" 耗時:"+cha+"mm");
}
}
}
//輸入位數 n
public void findFlower(int n)
{
System.out.println("使用查表法+組合數學");
//水仙花數位n>=3以上
for(int i=3;i<=n;i++)
{
//i次方
this.store2(i);
this.find2(i);
}
System.out.println("使用查表法");
startTime=new Date();
for(int i=3;i<=n;i++)
{
this.store(i);
this.find(i);
}
}
public static void main(String[] args) {
FlowerNumber flowerNumber=new FlowerNumber();
flowerNumber.findFlower(7);
}
}