如何得到所有的“水仙花数”？

你这性能确实也太低了，可能是BigInteger导致的，如果直接使用long将能够提升很多，当数字大到一定程度的时候再选择使用BigInteger，不知道你需要计算到多少位？

按你这种毫不剪枝的暴力搜索的算法，把long范围内算完都几乎不可能。。更不要说BigInteger了。。
我给你稍微优化了一下，创建了一个乘方表，就不需要每次去pow了，另外使用long，速度相对快一点。
测试了一下，得到146511208可以从你的四分多降低到二十几秒。 public static void main(String[] args) {
long[][] table = createTable();
for (long number = 0; number < Long.MAX_VALUE; number++) {
if (isNarcissisticNumber(number, table)) {
System.out.println(getTime() + "\t" + number);
}
}
}

public static boolean isNarcissisticNumber(long number, long[][] table) {
long sum = 0;
char[] digits = String.valueOf(number).toCharArray();
int len = digits.length;
for (char digit : digits) {
sum += table[(int)(digit - 48)][len];
if (sum < 0) return false;
}

return sum == number;
}

public static long[][] createTable() {
long[][] table = new long[10][20];
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
table[i][j] = (long)Math.pow(i, j);
}
}
return table;
}

public static String getTime() {
return new Date().toString();
}

0
1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
4679307774
32164049650
32164049651
40028394225
42678290603
44708635679
49388550606
82693916578
94204591914
28116440335967
4338281769391370
4338281769391371
21897142587612075
35641594208964132
35875699062250035
1517841543307505039
3289582984443187032
4498128791164624869
4929273885928088826
63105425988599693916
128468643043731391252
449177399146038697307
21887696841122916288858
27879694893054074471405
27907865009977052567814
28361281321319229463398
35452590104031691935943
174088005938065293023722
188451485447897896036875
239313664430041569350093
1550475334214501539088894
1553242162893771850669378
3706907995955475988644380
3706907995955475988644381
4422095118095899619457938
121204998563613372405438066
121270696006801314328439376
128851796696487777842012787
174650464499531377631639254
177265453171792792366489765
14607640612971980372614873089
19008174136254279995012734740
19008174136254279995012734741
23866716435523975980390369295
1145037275765491025924292050346
1927890457142960697580636236639
2309092682616190307509695338915
17333509997782249308725103962772
186709961001538790100634132976990
186709961001538790100634132976991
1122763285329372541592822900204593
12639369517103790328947807201478392
12679937780272278566303885594196922
1219167219625434121569735803609966019
12815792078366059955099770545296129367
115132219018763992565095597973971522400
115132219018763992565095597973971522401
把上面这些数加入到String数组中，十进制的水仙花数一共才88个，循环打印出来即可。

    public static final SimpleDateFormat SDF = new SimpleDateFormat("yyyy-MM--dd HH:mm:ss.SSS");
    public static final BigInteger EndPoint = new BigInteger("115132219018763992565095597973971522402");
    private static final BigInteger Poison = new BigInteger("-1");
    private static class CompareThread extends Thread{
        private BlockingQueue<BigInteger> numbers;
        public CompareThread(BlockingQueue<BigInteger> queue){
            numbers=queue;
        }
        public void run(){
            BigInteger number = BigInteger.ZERO;
            try {
                while((number=numbers.take())!=Poison){
                    if(isNarcissisticNumber(number)){
                        System.out.println(SDF.format(new Date()) + "\t" + number);
                    }
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * 判断一个数是否为水仙花数：一个N位整数，其各位数字的N次方的和等于该数本身
     *
     * @param number
     * @return 当输入的参数为水仙花数时返回true，否则返回false
     */
    public static boolean isNarcissisticNumber(final BigInteger number) {
        BigInteger sum = BigInteger.ZERO; // 各位数字的N次方的和
        char[] digitArray = number.toString(10).toCharArray(); // 各位数字的数组
        for (char digit : digitArray) {
            switch (digit){
                case '0': continue;
                case '1': sum = sum.add(BigInteger.ONE);break;
                default:
                    sum = sum.add(BigInteger.valueOf(digit - '0').pow(digitArray.length));
            }        }
        return sum.compareTo(number)==0;
    }
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<BigInteger> queue = new LinkedBlockingQueue<BigInteger>(1000);
        CompareThread[] pool = new CompareThread[Runtime.getRuntime().availableProcessors()];
        for(int i=0;i<pool.length;i++){
            pool[i]= new CompareThread(queue);
            pool[i].setPriority(Thread.MIN_PRIORITY);
            pool[i].start();
        }
        System.out.println("水仙花数列表");
        new CompareThread(queue).start();
        for(BigInteger number = BigInteger.ZERO;number.compareTo(EndPoint)<=0;number=number.add(BigInteger.ONE)){
            queue.put(number);
        }
    }

去掉第51行的代码 “ new CompareThread(queue).start(); ”，忘了删除了。

常量表是最好的算法。
我优化了一下我写的那个多线程的算法，提高了一下效率：
public static final SimpleDateFormat SDF = new SimpleDateFormat("yyyy-MM--dd HH:mm:ss.SSS");
    public static final BigInteger EndPoint = new BigInteger("115132219018763992565095597973971522402");
    private static final BigInteger Poison = new BigInteger("-1");
    private static class CompareThread extends Thread{
        private BlockingQueue<BigInteger> numbers;
        public CompareThread(BlockingQueue<BigInteger> queue){
            numbers=queue;
        }
        public void run(){
            BigInteger number = BigInteger.ZERO;
            try {
                while((number=numbers.take())!=Poison){
                    if(isNarcissisticNumber(number)){
                        System.out.println(SDF.format(new Date()) + "\t" + number);
                    }
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    private static final BigInteger[][] Powers = new BigInteger[40][10];
    static{
        for(int i=0;i<40;i++){
            for(int j=0;j<10;j++){
                Powers[i][j] = BigInteger.valueOf(j).pow(i);
            }
        }
    }
    public static boolean isNarcissisticNumber(final BigInteger number) {
        BigInteger sum = BigInteger.ZERO; // 各位数字的N次方的和
        char[] digitArray = number.toString(10).toCharArray(); // 各位数字的数组
        for (char digit : digitArray) {
            sum = sum.add(Powers[digitArray.length][digit-'0']);
        }
        return sum.compareTo(number)==0;
    }
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<BigInteger> queue = new LinkedBlockingQueue<BigInteger>(1000);
        CompareThread[] pool = new CompareThread[Runtime.getRuntime().availableProcessors()];
        for(int i=0;i<pool.length;i++){
            pool[i]= new CompareThread(queue);
            pool[i].setPriority(Thread.MIN_PRIORITY);
            pool[i].start();
        }
        System.out.println("水仙花数列表");
        for(BigInteger number = BigInteger.ZERO;number.compareTo(EndPoint)<=0;number=number.add(BigInteger.ONE)){
            queue.put(number);
        }
    }

public static void main(String[] args) {
  for(int i=100;i<=999;i++) {
   int g,s,b;
   b=i/100;
   s=(i-b*100)/10;
   g=i-b*100-s*10;
   if(i==g*g*g+s*s*s+b*b*b) {
    System.out.println(i);
   }
  }
}

楼上论文知网下载：http://www.cnki.net/KCMS/detail/detail.aspx?QueryID=0&CurRec=1&recid=&filename=LQSZ200206006&dbname=CJFD9902&dbcode=CJFQ&pr=&urlid=&yx=&v=MzA4MzN5cm5VYjNOS1R6WWRMRzRIdFBNcVk5RllvUjhlWDFMdXhZUzdEaDFUM3FUcldNMUZyQ1VSTDZmWWVScUY=

-- 心血来潮，写一段， 60 这个数字是这么来的。。呵呵。
declare @len int ;
set @len = 3
while ( POWER(10.0/9 , @len) / 10 < @len)
begin
print @len
set @len = @len + 1 ;
end 3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

实际上你那个乘方表只需要 long[9][n]就可以了，0的n次幂总是0，可以从1开始计算

实际上你那个乘方表只需要 long[9][n]就可以了，0的n次幂总是0，可以从1开始计算
0写进去只是为了方便程序逻辑，不然每次还要去判断是不是0，而且取下标时还要减1。
本来楼主这方法就慢得行不通，只能说能快一点就快一点了。

要证明存在最大的水仙花数其实也简单，对于长度为N的水仙花数K而言，
一方面有
K=a[1]*10^0+a[2]*10^1+...+a[N]*10^(N-1)>=a[N]*10^(N-1)>=10^(N-1) ........(1)
另一方面有
K=a[1]^N+a[2]^N+...+a[N]^N<=N*(9^N)=9N*9^(N-1) .......................(2)比较(1)式和(2)就可以知道，都是关于N的指数函数，一个是以9为底，一个是以10为底，虽然(2)还有9N的倍数加成，但是当N足够大的时候还是比不上(1)的。
实际上，要(1)>(2)，其实就是
10^(N-1)>9N*9^(N-1)
=>(10/9)^(N-1)>9N
画一下函数图像就可以知道，y=(10/9)^x是一条向上弯曲的指数函数曲线，y=9*x是一条倾斜向上的直线，所以y=(10/9)^x迟早会追上并超过y=9*x这个函数的，而且一旦超过就再也不会回来了。假设这个交叉点的x值为A，则当N>A时(1)永远大于(2)，也就不存在位数超过A的水仙花数了

不知道你用的什么机器几十秒就搞定了我跑了6分多钟也就到这儿。。
Fri Jun 27 11:53:38 HKT 2014 0
Fri Jun 27 11:53:38 HKT 2014 1
Fri Jun 27 11:53:38 HKT 2014 2
Fri Jun 27 11:53:38 HKT 2014 3
Fri Jun 27 11:53:38 HKT 2014 4
Fri Jun 27 11:53:38 HKT 2014 5
Fri Jun 27 11:53:38 HKT 2014 6
Fri Jun 27 11:53:38 HKT 2014 7
Fri Jun 27 11:53:38 HKT 2014 8
Fri Jun 27 11:53:38 HKT 2014 9
Fri Jun 27 11:53:38 HKT 2014 153
Fri Jun 27 11:53:38 HKT 2014 370
Fri Jun 27 11:53:38 HKT 2014 371
Fri Jun 27 11:53:38 HKT 2014 407
Fri Jun 27 11:53:38 HKT 2014 1634
Fri Jun 27 11:53:38 HKT 2014 8208
Fri Jun 27 11:53:38 HKT 2014 9474
Fri Jun 27 11:53:38 HKT 2014 54748
Fri Jun 27 11:53:38 HKT 2014 92727
Fri Jun 27 11:53:38 HKT 2014 93084
Fri Jun 27 11:53:38 HKT 2014 548834
Fri Jun 27 11:53:38 HKT 2014 1741725
Fri Jun 27 11:53:39 HKT 2014 4210818
Fri Jun 27 11:53:39 HKT 2014 9800817
Fri Jun 27 11:53:39 HKT 2014 9926315
Fri Jun 27 11:53:40 HKT 2014 24678050
Fri Jun 27 11:53:40 HKT 2014 24678051
Fri Jun 27 11:53:45 HKT 2014 88593477
Fri Jun 27 11:53:49 HKT 2014 146511208
Fri Jun 27 11:54:13 HKT 2014 472335975
Fri Jun 27 11:54:17 HKT 2014 534494836
Fri Jun 27 11:54:46 HKT 2014 912985153
Fri Jun 27 11:59:57 HKT 2014 4679307774

不知道你用的什么机器几十秒就搞定了我跑了6分多钟也就到这儿。。
Fri Jun 27 11:53:38 HKT 2014 0
Fri Jun 27 11:53:38 HKT 2014 1
Fri Jun 27 11:53:38 HKT 2014 2
Fri Jun 27 11:53:38 HKT 2014 3
Fri Jun 27 11:53:38 HKT 2014 4
Fri Jun 27 11:53:38 HKT 2014 5
Fri Jun 27 11:53:38 HKT 2014 6
Fri Jun 27 11:53:38 HKT 2014 7
Fri Jun 27 11:53:38 HKT 2014 8
Fri Jun 27 11:53:38 HKT 2014 9
Fri Jun 27 11:53:38 HKT 2014 153
Fri Jun 27 11:53:38 HKT 2014 370
Fri Jun 27 11:53:38 HKT 2014 371
Fri Jun 27 11:53:38 HKT 2014 407
Fri Jun 27 11:53:38 HKT 2014 1634
Fri Jun 27 11:53:38 HKT 2014 8208
Fri Jun 27 11:53:38 HKT 2014 9474
Fri Jun 27 11:53:38 HKT 2014 54748
Fri Jun 27 11:53:38 HKT 2014 92727
Fri Jun 27 11:53:38 HKT 2014 93084
Fri Jun 27 11:53:38 HKT 2014 548834
Fri Jun 27 11:53:38 HKT 2014 1741725
Fri Jun 27 11:53:39 HKT 2014 4210818
Fri Jun 27 11:53:39 HKT 2014 9800817
Fri Jun 27 11:53:39 HKT 2014 9926315
Fri Jun 27 11:53:40 HKT 2014 24678050
Fri Jun 27 11:53:40 HKT 2014 24678051
Fri Jun 27 11:53:45 HKT 2014 88593477
Fri Jun 27 11:53:49 HKT 2014 146511208
Fri Jun 27 11:54:13 HKT 2014 472335975
Fri Jun 27 11:54:17 HKT 2014 534494836
Fri Jun 27 11:54:46 HKT 2014 912985153
Fri Jun 27 11:59:57 HKT 2014 4679307774
我说的是跑到146511208用时几十秒，我可没说跑完long

不知道你用的什么机器几十秒就搞定了我跑了6分多钟也就到这儿。。
Fri Jun 27 11:53:38 HKT 2014 0
Fri Jun 27 11:53:38 HKT 2014 1
Fri Jun 27 11:53:38 HKT 2014 2
Fri Jun 27 11:53:38 HKT 2014 3
Fri Jun 27 11:53:38 HKT 2014 4
Fri Jun 27 11:53:38 HKT 2014 5
Fri Jun 27 11:53:38 HKT 2014 6
Fri Jun 27 11:53:38 HKT 2014 7
Fri Jun 27 11:53:38 HKT 2014 8
Fri Jun 27 11:53:38 HKT 2014 9
Fri Jun 27 11:53:38 HKT 2014 153
Fri Jun 27 11:53:38 HKT 2014 370
Fri Jun 27 11:53:38 HKT 2014 371
Fri Jun 27 11:53:38 HKT 2014 407
Fri Jun 27 11:53:38 HKT 2014 1634
Fri Jun 27 11:53:38 HKT 2014 8208
Fri Jun 27 11:53:38 HKT 2014 9474
Fri Jun 27 11:53:38 HKT 2014 54748
Fri Jun 27 11:53:38 HKT 2014 92727
Fri Jun 27 11:53:38 HKT 2014 93084
Fri Jun 27 11:53:38 HKT 2014 548834
Fri Jun 27 11:53:38 HKT 2014 1741725
Fri Jun 27 11:53:39 HKT 2014 4210818
Fri Jun 27 11:53:39 HKT 2014 9800817
Fri Jun 27 11:53:39 HKT 2014 9926315
Fri Jun 27 11:53:40 HKT 2014 24678050
Fri Jun 27 11:53:40 HKT 2014 24678051
Fri Jun 27 11:53:45 HKT 2014 88593477
Fri Jun 27 11:53:49 HKT 2014 146511208
Fri Jun 27 11:54:13 HKT 2014 472335975
Fri Jun 27 11:54:17 HKT 2014 534494836
Fri Jun 27 11:54:46 HKT 2014 912985153
Fri Jun 27 11:59:57 HKT 2014 4679307774
我说的是跑到146511208用时几十秒，我可没说跑完long
眼花。。

最快的算法，恐怕是做一个数组递归
每次减去个位的pow(n,digits),加上pow(n+1,digits)
他们的差还可以写个inline函数来搞定
还有就是位数数量级不对直接continue掉

算法的问题，可以参看http://bbs.csdn.net/topics/360185693，@litaoye的C#程序计算21位秒杀，39位也只需5~6秒。

大部分都是JAVA的，怎么木有c++或者C语言的

调试易

如何得到所有的“水仙花数”？

解决方案 »