这可能是最快的自幂数算法

佚名 6年前 (2019-12-31) 算法 1740人围观抢沙发百度已收录

这可能是最快的自幂数算法

注意,了解的人可以直接拉到尾部看时间和代码
什么是自幂数
- 自幂数是指一个 n 位数，它的每个位上的数字的 n 次幂之和等于它本身。（例如：当n为3时，有1^3 + 5^3 + 3^3 = 153，153即是n为3时的一个自幂数）
- 自幂数包括：独身数、水仙花数、四叶玫瑰数、五角星数、六合数、北斗七星数、八仙数、九九重阳数、十全十美数
  ---摘自百度百科
如何计算自幂数
- 最近研究了一下水仙花数,完了之后就自然而然的优化成了计算自幂数的算法...
- 我的思路是,首先,如果要计算的是100-1000之间的水仙花数
  - 一个循环,从100-1000 (i=100; i<1000)
  - 每次循环先取出i的个位,十位,百位数
  - 将个位,十位,百位的三次方和i进行比较,相等则打印输出
  - 以下代码
```
for (var i = 100; i < 1000; i++) {
  var hundred = Math.floor(i / 100);
  var decade = Math.floor((i / 10) % 10);
  var single = i % 10;
  if (hundred * hundred * hundred + decade * decade * decade + single * single * single === i) {
  console.log(i); //153 370 371 407
  }
}
```
经过思考之后,代码改成了这个样子

for (var i = 100; i < 1000; i++) {
    var s = i + "";
    var hundred = +s[0];
    var decade = +s[1];
    var single = +s[2];
    if (Math.pow(hundred, 3) + Math.pow(decade, 3) + Math.pow(single, 3) === i) {
        console.log(i); //153 370 371 407
    }
}

然后发现上边定义变量的步骤完全是重复的,修改为

for (var i = 100; i < 10000; i++) {
    var s = i + "";
    var sum=0;
    for (var k = 0; k < 3; k++) {
        sum += Math.pow(s[k], 3)
    }
    if (sum === i) {
        console.log(i); //153 370 371 407
    }
}

以上代码可以优化为计算自幂数的算法

var max=3;//最大位数
var len=Math.pow(10, max);
for (var i = 100; i < len; i++) {
    var s = i + "";
    var sum=0;
    for (var k = 0; k < s.length; k++) {
        sum += Math.pow(s[k], s.length)
    }
    if (sum === i) {
        console.log(i); //153 370 371 407
    }
}

有没有发现有什么不同,除了上边的循环次数做了修改之外,就只是吧3修改成了s.length 这样是4位数的时候就会计算4个数的4次方,5个数...
因为我们可以肯定s[k]是一个数字,所以可以这样来获取这个字符串代表的值,比系统隐式转换的效率更高

var max=3;//最大位数
var len=Math.pow(10, max);
for (var i = 100; i < len; i++) {
    var s = i + "";
    var sum=0;
    for (var k = 0; k < s.length; k++) {
        sum += Math.pow(s[k] - '0', s.length)
    }
    if (sum === i) {
        console.log(i); //153 370 371 407
    }
}

到了这一步一个简单的自幂数算法就已经完成了,之后我又自己做了两次优化
第一版本是 eight1 (代码在下边)
第一次优化后的是eight2 具体是自己维护了一个代表当前数值的数组,而不再从数值中逐个转换,优化后速度提升了80%大概
第二次优化是最大的,就是提前吧几的几次方算好了,因为我发现实际运行中这个的计算次数是在是太多了....
优化后速度提升了数十倍
代码最初写的是java,后来因为发现js执行更快就改成了js

"Use strict";
function eight1(len) {
    var max = Math.pow(10, len);//初始化最大值
    var arr = [];//结果数组
    for (var j = 100; j < max; j++) {
        var s = j + "";
        var sum = 0;
        for (var k = 0; k < s.length; k++) {
            sum += Math.pow(s[k] - '0', s.length);
        }
        if (sum == j) {
            arr.push(j);
        }
    }
    console.log("eight1", arr);
}
function eight2(len) {
    var num = [];//num是我维护的数组
    //根据len初始化数组 len为6时 [0,0,1,0,0,0] 代表100
    for (let o = 0; o < len; o++) {
        if (o === 2) {
            num[o] = 1;
        } else {
            num[o] = 0;
        }
    }
    var cs = 3;//当前最大值是几位数
    var len = Math.pow(10, num.length) - 1;//循环次数
    var c;//本次计算了几位数
    var arr = [];//结果数组
    for (var j = 100; j < len; j++) {
        var t = 0;
        c = 0;
        num[t]++;
        //对数组进行+1操作,满10进1
        while (num[t] >= 10) {
            c++;
            num[t] = 0;
            t++;
            num[t]++;
        }
        if (c >= cs) {//如果本次到了比最大值更大的位数,则最大位数+1
            cs++;
        }
        var sum = 0;
        for (var k = 0; k < cs; k++) {
            sum += Math.pow(num[k], cs);
        }
        if (sum == j + 1) {
            arr.push(sum);
        }
    }
    console.log("eight2", arr);
}

function eight3(len) {
    var num = [];
    for (let o = 0; o < len; o++) {
        if (o === 2) {
            num[o] = 1;
        } else {
            num[o] = 0;
        }
    }
    var arr = [];
    var result = [];//提前把1-9 ^3 ~ 1-9 ^ len 的值给计算好,存放在数组中,然后使用时根据数组取值即可 
    for (var i = 0; i <= 9; i++) {
        result[i] = [];//因为是双层数组,所以这里做初始化
        for (var j = 3; j <= len; j++) {
            result[i][j] = Math.pow(i, j);//计算结果,赋值
        }
    }
    var cs = 3;
    var len = Math.pow(10, num.length) - 1;
    var c;
    for (var j = 100; j < len; j++) {
        var t = 0;
        c = 0;
        num[t]++;
        while (num[t] >= 10) {
            c++;
            num[t] = 0;
            t++;
            num[t]++;
        }
        if (c >= cs) {
            cs++;
        }
        var sum = 0;
        for (var k = 0; k < cs; k++) {
            sum += result[num[k]][cs];//这里直接取出结果行了,不需要计算
        }
        if (sum == j + 1) {
            console.log(sum);
            arr.push(sum);
        }
    }
    console.log("eight2_2", arr);
}
console.warn("eight1  start");
console.time();
eight1(6);
console.timeEnd();

console.warn("eight2  start");
console.time();
eight2(6);
console.timeEnd();

console.warn("eight3  start");
console.time();
eight3(6);
console.timeEnd();