水仙花数的帖子不让回了，满3次了，只好发个新帖解决思路

水仙花数的帖子不让回了，满3次了，只好发个新帖
又加强了一下提前剪枝，目前效率已经不错了，计算全部88个水仙花数，一共不到1分钟，只有1没有算出来，所以是87个。
算39位的大概5-6秒吧！

C# code

1. 22. 33. 44. 55. 66. 77. 88. 99. 15310. 37011. 37112. 40713. 163414. 820815. 947416. 5474817. 9272718. 9308419. 54883420. 174172521. 421081822. 980081723. 992631524. 2467805025. 2467805126. 8859347727. 14651120828. 47233597529. 53449483630. 91298515331. 467930777432. 3216404965033. 3216404965134. 4002839422535. 4267829060336. 4470863567937. 4938855060638. 8269391657839. 9420459191440. 2811644033596741. 433828176939137042. 433828176939137143. 2189714258761207544. 3564159420896413245. 3587569906225003546. 151784154330750503947. 328958298444318703248. 449812879116462486949. 492927388592808882650. 6310542598859969391651. 12846864304373139125252. 44917739914603869730753. 2188769684112291628885854. 2787969489305407447140555. 2790786500997705256781456. 2836128132131922946339857. 3545259010403169193594358. 17408800593806529302372259. 18845148544789789603687560. 23931366443004156935009361. 155047533421450153908889462. 155324216289377185066937863. 370690799595547598864438064. 370690799595547598864438165. 442209511809589961945793866. 12120499856361337240543806667. 12127069600680131432843937668. 12885179669648777784201278769. 17465046449953137763163925470. 17726545317179279236648976571. 1460764061297198037261487308972. 1900817413625427999501273474073. 1900817413625427999501273474174. 2386671643552397598039036929575. 114503727576549102592429205034676. 192789045714296069758063623663977. 230909268261619030750969533891578. 1733350999778224930872510396277279. 18670996100153879010063413297699080. 18670996100153879010063413297699181. 112276328532937254159282290020459382. 1263936951710379032894780720147839283. 1267993778027227856630388559419692284. 121916721962543412156973580360996601985. 1281579207836605995509977054529612936786. 11513221901876399256509559797397152240087. 115132219018763992565095597973971522401

C# code

using System;using System.Numerics;namespace CSharpTest{    class Program    {        private static BigInteger[] PowerOf10;        private static BigInteger[,] PreTable;        private static BigInteger[,] PreTable2;        private static int[,] PreTable3;        private static int[] Selected = new int[10];        private static int Length;        private static int Count = 0;        public static void Main()        {            DateTime begin = DateTime.Now;            for (int i = 1; i < 40; i++)            {                InitPre(i);                Search(9, 0, i);            }            Console.WriteLine(DateTime.Now - begin);        }        private static void InitPre(int n)        {            PowerOf10 = new BigInteger[n + 1];            PowerOf10[0] = 1;            Length = n;            for (int i = 1; i <= n; i++)                PowerOf10[i] = PowerOf10[i - 1] * 10;                        PreTable = new BigInteger[10, n + 1];            PreTable2 = new BigInteger[10, n + 1];            PreTable3 = new int[10, n + 1];            for (int i = 0; i < 10; i++)            {                for (int j = 0; j <= n; j++)                {                    PreTable[i, j] = BigInteger.Pow(i, n) * j;                    PreTable2[i, j] = PowerOf10[Length - 1] - PreTable[i, j];                    for (int k = n; k >= 0; k--)                    {                        if (PowerOf10[k] < PreTable[i, j])                        {                            PreTable3[i, j] = k;                            break;                        }                    }                }            }        }        private static bool PreCheck(int currentIndex, BigInteger sum, int remainCount)        {            if (sum < PreTable[currentIndex, remainCount])                return true;            BigInteger max = sum + PreTable[currentIndex, remainCount];            max /= PowerOf10[PreTable3[currentIndex, remainCount]];            sum /= PowerOf10[PreTable3[currentIndex, remainCount]];            while (max != sum)            {                max /= 10;                sum /= 10;            }            if (max == 0)                return true;            int[] counter = GetCounter(max);            for (int i = 9; i > currentIndex; i--)                if (counter[i] > Selected[i])                    return false;            for (int i = 0; i <= currentIndex; i++)                remainCount -= counter[i];            return remainCount >= 0;        }        private static void Search(int currentIndex, BigInteger sum, int remainCount)        {            if (sum >= PowerOf10[Length])                return;            if (remainCount == 0)            {                if (sum > PowerOf10[Length - 1] && Check(sum))                {                    Count++;                    Console.WriteLine("{0}. {1}", Count, sum);                }                return;            }            if (!PreCheck(currentIndex, sum, remainCount))                return;            if (sum < PreTable2[currentIndex, remainCount])                return;            if (currentIndex == 0)            {                Selected[0] = remainCount;                Search(-1, sum, 0);            }            else            {                for (int i = 0; i <= remainCount; i++)                {                    Selected[currentIndex] = i;                    Search(currentIndex - 1, sum + PreTable[currentIndex, i], remainCount - i);                }            }            Selected[currentIndex] = 0;        }        private static bool Check(BigInteger sum)        {            int[] counter = GetCounter(sum);            for (int i = 0; i < 10; i++)            {                if (Selected[i] != counter[i])                    return false;            }            return true;        }        public static int[] GetCounter(BigInteger value)        {            int[] counter = new int[10];            char[] sumChar = value.ToString().ToCharArray();            for (int i = 0; i < sumChar.Length; i++)                counter[sumChar[i] - '0']++;            return counter;        }    }} 
 

[解决办法]
LZ可以讲下计算n位水仙花数的思路吗？
[解决办法]
LZ 果然 V5 迅猛
吾等五体投地
[解决办法]
支持楼上，附上算法思想就更赞了
[解决办法]
汗死 都木有听说过
[解决办法]
我承认我吃惊了。。那个只有88个的结论违反我的直觉，我总觉得应该有无限个才对。。
很感兴趣只有有限个的证明
另外想到一个问题：如果不是10进制，是N进制，有没有一个N可以让这个进制下有无限个水仙花数
[解决办法]
我什么都不知道，但我知道LZ一定很牛逼
[解决办法]
支持LZ，不过要是写上一些注释或者写一下算法思想就更好了。
[解决办法]
理论上，最大的水仙花数不超过34位。
[解决办法]
楼主把算法思想讲一下呗！！！
[解决办法]
楼主的算法也是在通过枚举结果是由哪些i^n之和组成。在Search的for循环中直接枚举9^n,8^n....的个数，并将选取的个数记录在select中用于与最后得到的结果比对。各个数出现的次数与选取的次数一致就说明找到一个解。sum记录当前已经枚举了的结果。在枚举过程中遇到明显不可能是结果的组合提前返回。 不过我没明白precheck中的第一个if是为什么。还望楼主出来指点。
[解决办法]
牛人也
[解决办法]
能讲一下思路不？谢谢
[解决办法]
我根据我的理解改成了java版的，写了注释。
有错误的，或可以优化的地方欢迎交流分享。

Java code

import java.math.BigInteger;/** * 水仙花数：N位整数，它等于各位上的数字的N次方之和，例如有一个N位数字，a1a2a3a4.....aN = a1^N +a2^N+......aN^N *  * 算法原理： 注意：以下 sum 为各位上的数字的N次方之和 sum_a为集合a中的数的sum *  * 对于任意的N位数字，定义形如315，351，513等这样的数字都属于“1出现1次，3出现1次，5出现1次”的集合a * 明显可以看出“包含在集合a中的数的sum都相同”，即sum_a="1^N（位数）*T1(1出现的次数)+3^N*T3+5^N*T5"， * 观察得，如果集合a包含水仙花数，则该水仙花数=水仙花数的sum（水仙花数定义）=sum_a（充要条件）。 * 可以随便举个反例215,512，125在集合b中，但b的sum_a=134明显不属于集合b，所以b不是包含水仙花数的集合 * 总结：将寻找水仙花数，转换为寻找包含水仙花数的集合，从而减少判断的次数。 *  * 结束条件：（楼主在这里进行了优化） 首先不是一次选完，而是从0到N个9，0到N个8...这样选，总数由remainCount控制 设当前情况为集合a * 1.如果当sum_a大于最大数即10^N-1，矛盾 2.因最小的数字为10^(N - * 1)，注意到，如果选某数时sum_a小于最小值，则后面的情况不用讨论了。 * 例如3位数，已选1个3选2，发现sum_a最大为=3^3*1+2^3*2=43<100，可以断定不用选2,1,0了； * （当前情况能表示的最大数：比如说3位数我选了1个9，8的情况选完了不行，现在开始选7，最大数就是977不可能是987） * 3.判断sum_a和当前情况能表示的最大数首部相同部分中某数出现的次数是否比已经选择的集合中该数出现的次数多 * 设sum_a=99900当前情况能表示的最大数为99988，则当前情况的数肯定在这之间即999XX，而当前情况9已经选了且只选了1次，则矛盾。 * 4.同上：相同部分中还没选的数 的出现次数比剩余的总数还多 例如相同部分为789111,1还没选而且只剩2个数没选了，则矛盾 * 5.当选完所有数时如果sum_a属于集合a，则sum_a为水仙花数。 *  */public class NarcissisticNumber {    /**     * 记录10的0~N次方     */    private static BigInteger[] PowerOf10;    /**     * 记录0到9中任意数字i的N次方乘以i出现的次数j的结果（i^N*j）     */    private static BigInteger[][] PreTable;    /**     * 记录可能为水仙花数的下限与PreTable中对应数的差     */    // private static BigInteger[][] PreTable2; 没什么用，变量定多了不容易理解    /**     * 记录离PreTable中对应数最近的10的k次方     */    private static int[][] PreTable3;    /**     * 记录0到9中每个数出现的次数     */    private static int[] Selected = new int[10];    /**     * 记录水仙花数的位数     */    private static int Length;    /**     * 记录水仙花数出现的个数     */    private static int Count = 0;    /**     * 记录当前的进制     */    private static int NumberSystem = 10;    public static void main(String[] args) {        long time = System.nanoTime();        // for (int i = 1; i < 40; i++) {        NarcissisticNumber narcissisticNumber = new NarcissisticNumber(39);        narcissisticNumber.show();        // }        time = System.nanoTime() - time;        System.out.println("time:\t" + time / 1000000000.0 + "s");    }    // 初始化计算时使用的数据结构，这也是提高效率的地方    /**     * @param n     *            水仙花数的位数     */    public NarcissisticNumber(int n) {        PowerOf10 = new BigInteger[n + 1];        PowerOf10[0] = BigInteger.ONE;        Length = n;            for (int i = 1; i <= n; i++){            PowerOf10[i] = PowerOf10[i - 1].multiply(BigInteger.TEN);        }            PreTable = new BigInteger[NumberSystem][n + 1];        // PreTable2 = new BigInteger[NumberSystem][n + 1];        PreTable3 = new int[NumberSystem][n + 1];            for (int i = 0; i < NumberSystem; i++) {            for (int j = 0; j <= n; j++) {                PreTable[i][j] = new BigInteger(new Integer(i).toString()).pow(                        n).multiply(new BigInteger(new Integer(j).toString()));                // PreTable2[i][j] = PowerOf10[Length - 1]                // .subtract(PreTable[i][j]);                    for (int k = n; k >= 0; k--) {                    if (PowerOf10[k].compareTo(PreTable[i][j]) < 0) {                        PreTable3[i][j] = k;                        break;                    }                }            }        }    }    private void show() {        Search(NumberSystem - 1, BigInteger.ZERO, Length);    }    /**     * @param currentIndex     *            记录当前正在选择的数字(0~9)     * @param sum     *            记录当前值（如选了3个9、2个8 就是9^N*3+8^N*2）     * @param remainCount     *            记录还可选择多少数     */    private static void Search(int currentIndex, BigInteger sum, int remainCount) {        if (sum.compareTo(PowerOf10[Length]) >= 0)// 见结束条件1        {            return;        }            if (remainCount == 0) {// 没数可选时            if (sum.compareTo(PowerOf10[Length - 1]) > 0 && Check(sum)) {// 见结束条件5                Count++;                System.out.print(Count + " ");                System.out.println(sum);            }            return;        }            if (!PreCheck(currentIndex, sum, remainCount))// 见结束条件3,4            return;            if (sum.add(PreTable[currentIndex][remainCount]).compareTo(                PowerOf10[Length - 1]) < 0)// 见结束条件2            return;            if (currentIndex == 0) {// 选到0这个数时的处理            Selected[0] = remainCount;            Search(-1, sum, 0);        } else {            for (int i = 0; i <= remainCount; i++) {// 穷举所选数可能出现的情况                Selected[currentIndex] = i;                Search(currentIndex - 1, sum.add(PreTable[currentIndex][i]),                        remainCount - i);            }        }        // 到这里说明所选数currentIndex的所有情况都遍历了        Selected[currentIndex] = 0;    }    /**     * @param currentIndex     *            记录当前正在选择的数字(0~9)     * @param sum     *            记录当前值（如选了3个9、2个8 就是9^N*3+8^N*2）     * @param remainCount     *            记录还可选择多少数     * @return 如果当前值符合条件返回true     */    private static Boolean PreCheck(int currentIndex, BigInteger sum,            int remainCount) {        if (sum.compareTo(PreTable[currentIndex][remainCount]) < 0)// 判断当前值是否小于PreTable中对应元素的值            return true;// 说明还有很多数没选            BigInteger max = sum.add(PreTable[currentIndex][remainCount]);// 当前情况的最大值        max = max.divide(PowerOf10[PreTable3[currentIndex][remainCount]]);// 取前面一部分比较        sum = sum.divide(PowerOf10[PreTable3[currentIndex][remainCount]]);            while (!max.equals(sum)) {// 检验sum和max首部是否有相同的部分            max = max.divide(BigInteger.TEN);            sum = sum.divide(BigInteger.TEN);        }            if (max.equals(BigInteger.ZERO))// 无相同部分            return true;            int[] counter = GetCounter(max);            for (int i = 9; i > currentIndex; i--)            if (counter[i] > Selected[i])// 见结束条件3                return false;            for (int i = 0; i <= currentIndex; i++)            remainCount -= counter[i];            return remainCount >= 0;// 见结束条件4    }    /**     * @param sum     *            记录当前值（如选了3个9、2个8 就是9^N*3+8^N*2）     * @return 如果sum存在于所选集合中返回true     */    private static Boolean Check(BigInteger sum) {        int[] counter = GetCounter(sum);            for (int i = 0; i < NumberSystem; i++) {            if (Selected[i] != counter[i])                return false;        }            return true;    }    /**     * @param value     *            需要检验的数     * @return 返回value中0到9出现的次数的集合     */    public static int[] GetCounter(BigInteger value) {        int[] counter = new int[NumberSystem];        char[] sumChar = value.toString().toCharArray();        for (int i = 0; i < sumChar.length; i++)            counter[sumChar[i] - '0']++;        return counter;    }} 
 
[解决办法]
Java code
if (sum.compareTo(PowerOf10[Length - 1]) > 0 && Check(sum)) {// 见结束条件5                Count++;                System.out.print(Count + " ");                System.out.println(sum);            }
[解决办法]
楼主·  真的。说实话。  在菜鸟的眼里 你就是神奇的存在、  我也想成为神奇啊！
[解决办法]
学习啊，还不知道水仙花是什么题目呢，呵呵
[解决办法]
探讨

LZ 果然 V5 迅猛
吾等五体投地

[解决办法]
我没明白precheck中的第一个if是为什么?盛请lz说说当时是怎麽想到这一句的？？ 

 

查看更多 下一篇