21位水仙花数的求解

wuchangjian2021-11-03 04:51:01编程学习

题目要求:

水仙花数(Narcissistic number),它是指一个 n 位数(n≥3 ),它的每个数位上的数字的 n 次幂之和,等于它本身(例如:13 + 53+ 33 = 153)。现给出位数 n ,试求出所有满足条件的水仙花数。


听起来是不是很简单?!
我循环遍历所有数字,对每数字每一位进行处理,加起来判断一下不就完了么,还有什么难度?就这?!
那么就来看看计算量有多恐怖吧。


public class Main {

	public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        long starttime = System.currentTimeMillis();
        fun(n);
        System.out.println("运行时间:" + (System.currentTimeMillis() - starttime) + " ms");
    }

    public static void fun(int n) {
        int start = 1, end = 10;
        for (int i = 1; i < n; i++) {
            start *= 10;
            end *= 10;
        }
        getNarcissisticNumbersWithin(start, end);
    }

    public static void getNarcissisticNumbersWithin(int start, int end) {
        for (int i = start; i <= end; i++) {
            if (isNarcissistic(i)) {
                System.out.println(i);
            }
        }
    }

    public static boolean isNarcissistic(int number) {
        int D = getDigit(number);
        int sum = getSum(number, D);
        return sum == number;
    }

    public static int getDigit(int number) {
        int digit = 1;
        while ((number /= 10) > 0) {
            digit++;
        }
        return digit;
    }

    public static int getSum(int number, int D) {
        int sum = 0;
        for (int i = 0; i < D; i++) {
            sum += Math.pow((number % 10), D);
            number /= 10;
        }
        return sum;
    }
}

代码很简单,就是对按照水仙花数的定义,遍历数字每一位,判断是否符合要求,是则输入,不是则继续循环操作。
下面我放了几张不同位数的计算量。
在这里插入图片描述
这是 6 位水仙花数,运行花了 177 ms,还挺快^_^ 。
在这里插入图片描述
这是 7 位的水仙花数,运行花了 2044 ms,也不是很慢嘛!
在这里插入图片描述
这是 8 位的水仙花数,比刚才多了 1 位,花了23249 ms 。。

可以明显的看到,随着位数的增加,运行耗费的时间也以十倍以上的关系不断增大,这还没有考虑到后续 int 类型数据溢出的情况,不过算到了后面,哪怕是 long 型,也得溢出。

所以要计算21位的水仙花数,我们采用 Java 的 BigInteger 进行大数处理,但这并不能实际解决问题,所以我们需要对算法进行优化。


关键点:弱化水仙花数的数值与水仙花数中每一个数字数位的关系,侧重于每个数字在水仙花数数值中出现的次数。
因此我们可以这么来处理:
1. 写一个函数 calcu_21() 计算 0–9 的 21 次方的大数,并用 base[10] 保存
2. 写一个函数 a[10] 对应保存 0–9 十个数字分别出现的次数
3. 写一个函数 f ,负责搜索遍历所有的情况,需要用到递归
4. 最后写一个测试函数 test ,检验是否为水仙花数

public class ex2 {

    //每个数字21次方

    public static BigInteger[] base = new BigInteger[10];

    public static BigInteger calcu_21(int n) {
        BigInteger a = BigInteger.ONE;
        for (int i = 0; i < 21; i++) {
            a = a.multiply(BigInteger.valueOf(n));
        }
        return a;
    }

    public static void test(int[] a) {
        BigInteger bn = BigInteger.ZERO;
        for (int i = 0; i < a.length; i++) {
            bn = bn.add(base[i].multiply(BigInteger.valueOf(a[i])));
        }
        String s = bn.toString();
        if (s.length() != 21) {
            return;
        }
        int[] b = new int[10];
        for (int i = 0; i < s.length(); i++) {
            b[s.charAt(i) - '0']++;
        }
        for (int i = 0; i < 10; i++) {
            if (a[i] != b[i]) {
                return;
            }
        }
        System.out.println(bn);
    }

    /*
     *处理第 k 个,还有 sum 个名额
     *
     */
    public static void f(int[] a, int k, int sum) {
        if (sum == 0) {
            test(a);
            return;
        }
        if (k == a.length - 1) {
            a[k] = sum;
            f(a, k + 1, 0);
            return;
        }
        for (int i = 0; i <= sum; i++) {
            a[k] = i;
            f(a, k + 1, sum - i);
            a[k] = 0;
        }
    }

    public static void main(String[] args) {
        long starttime = System.currentTimeMillis();
        for (int i = 0; i < base.length; i++) {
            base[i] = calcu_21(i);
        }
        //每个数字出现几次
        int[] a = new int[10];
        f(a, 0, 21);
        System.out.println("运行时间:" + (System.currentTimeMillis() - starttime) + " ms");
    }
}

最后程序运行截图放出来
在这里插入图片描述
计算21水仙花数只花了不到 10s
nice (**)

相关文章

什么是304不锈钢?

什么是304不锈钢? 304...

(i++)(i--)

for(i=0;i<=9;i++)代表 循环从第0...

20 Flowable容器

BPMN2.0中的容器由事件子流程、事物、子流程、泳池和泳池五部分组成。其中的事件子流程...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。