纠正：java代码求1^1+2^2+3^3+4^4+5^5+……20^20...n^n大数运算的和

刺骨的言语ヽ痛彻心扉 2021-09-07 06:08 235阅读 0赞

应博友需求代码实现n的n次方的和：

正常加到16已经超出long型了，所以肯定不能直接用基本数据类型计算。用string显然问题很多：到处在强转、效率低下、繁琐的无用逻辑等（用String写的博客不仅抄的一样，还都是错的?），所以采用List<Integer>来保存每一位值才是最好的（List<Long>也可以，双倍内存提升10%的效率）。

**由于多数博客鱼龙混杂，本博客如果让你非常满意或解决了大家的根本性问题，希望多多支持在右边点赞和回复一下，举手之劳方便大家。**

public static void main(String[] args) {
            int number = 15;
            System.out.println("数组保存结果：" + getResult(number));
    
            //16会超出long的值就无法对比验证了
            if (number > 15) {
                System.out.println("直接结算结果：超出long值，无法计算");
                return;
            }
            long result = 0;
            for (int i = 1; i <= number; i++) {
                if (number <= 13) {//太大Math会引用科学计数法导致丢失精度
                    result += Math.pow(i, i);
                } else {
                    long cache = i;
                    for (int j = 1; j < i; j++) {
                        cache *= i;
                    }
                    result += cache;
                }
            }
            System.out.println("直接计算结果：" + result);
        }
    
        /**
         * 求n的n次方的和
         *
         * @param initialNumber 任意正整数（由于次方的数据量很大时间复杂度很高，所以请小于1000）
         */
        private static String getResult(int initialNumber) {
            ArrayList<Integer> result = new ArrayList<>();
            for (int i = 1; i <= initialNumber; i++) {
                List<Integer> power = getPower(i);
                //取最大for循环
                int count = power.size() > result.size() ? power.size() : result.size();
                for (int j = 0; j < count; j++) {//将result和power相加
                    if (j >= power.size()) {//加完了
                        break;
                    }
                    if (j >= result.size()) {
                        result.add(power.get(j));
                        continue;
                    }
                    result.set(j, result.get(j) + power.get(j));//两者相加
                }
    
                fastFormatList(result);
            }
            formatList(result);//最后再来一遍
            StringBuilder builder = new StringBuilder();
            for (int i = result.size() - 1; i >= 0; i--) {//由高位到低位按正常顺序打印
                builder.append((int) result.get(i));
            }
            return builder.toString();
        }
    
        /**
         * 获得n的n次方
         *
         * @return 返回对应次方的值，如：a的a次方是123456则倒序返回[6,5,4,3,2,1]
         */
        private static List<Integer> getPower(int n) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(n);
            for (int i = 1; i < n; i++) {//默认add了number，循环number-1次
                for (int j = 0; j < list.size(); j++) {
                    int item = list.get(j);
                    list.set(j, item * n);//先乘好
                }
                fastFormatList(list);//再进行格式化进位操作
            }
            return list;
        }
    
        /**
         * 快速格式化list
         * 减少进位次数，只有累积到一定值才会进位
         * {@link #formatList}
         */
        private static void fastFormatList(List<Integer> list) {
            for (int item : list) {
                if (item > 100_000) {
                    formatList(list);
                    return;
                }
            }
        }
    
        /**
         * 对每一位超过10都进行进位操作，如：[21,22]进位成[1,4,2]
         */
        private static void formatList(List<Integer> list) {
            for (int i = 0; i < list.size(); i++) {//从低位开始往高位进
                int item = list.get(i);
                int itemNext = item / 10;
                if (itemNext > 0) {
                    list.set(i, item % 10);//舍去10以上进到下一位
                    //进位
                    if (i < list.size() - 1) {
                        int item1 = list.get(i + 1);
                        list.set(i + 1, item1 + itemNext);//进到下一位
                    } else {
                        //最后一位进位的话需要重新add
                        list.add(itemNext);
                    }
                }
            }
        }

当然也可以递归实现，但在已知遍历次数的情况下，递归并不怎么友好，代码多了、效率也没变高、还浪费了内存。发一下主要实现

private static String recursiveResult(int initialNumber) {
            List<Integer> result = recursive(initialNumber);
            formatList(result);//最后再来一遍
            StringBuilder builder = new StringBuilder();
            for (int i = result.size() - 1; i >= 0; i--) {//由高位到低位打印
                builder.append((int) result.get(i));
            }
            return builder.toString();
        }
    
        private static List<Integer> recursive(int initialNumber) {
            if (initialNumber == 1) {
                ArrayList<Integer> listReturn = new ArrayList<>();
                listReturn.add(1);
                return listReturn;
            }
            List<Integer> result = recursive(initialNumber - 1);
            List<Integer> power = getPower(initialNumber);
            //取最大for循环
            int count = power.size() > result.size() ? power.size() : result.size();
            for (int j = 0; j < count; j++) {//将result和power相加
                if (j >= power.size()) {//加完了
                    break;
                }
                if (j >= result.size()) {
                    result.add(power.get(j));
                    continue;
                }
                result.set(j, result.get(j) + power.get(j));//两者相加
            }
            fastFormatList(result);
            return result;
        }

转载请注明出处：王能的博客：[https://blog.csdn.net/weimingjue/article/details/101760480][https_blog.csdn.net_weimingjue_article_details_101760480]

[https_blog.csdn.net_weimingjue_article_details_101760480]: https://blog.csdn.net/weimingjue/article/details/101760480