這可能是最快的自冪數演算法

• 注意,了解的人可以直接拉到尾部看時間和代碼
• 什么是自冪數
  • 自冪數是指一個 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();

• 可以吧代碼拷貝走,自己跑一下試試
• 下面是我在自己電腦上跑的速度對比 10次的平均值
• 單位 ms
• 8位以上的除了eight3其他的沒有跑,eight3也只跑了一次

• 還有一些細節并沒有優化到位,畢竟只是練習,有大神發現了歡迎指正

標籤：其他

上一篇：PAT乙級1001

下一篇：【自考】資料結構第三章，陣列，期末不掛科指南，第5篇