題目

Square digit chains

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 →?1?→?1
85 →?89?→ 145 → 42 → 20 → 4 → 16 → 37 → 58 →?89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

---

平方數(shù)字鏈

將一個(gè)數(shù)的所有數(shù)字的平方相加得到一個(gè)新的數(shù)，不斷重復(fù)直到新的數(shù)已經(jīng)出現(xiàn)過為止，這構(gòu)成了一條數(shù)字鏈。

例如，

44 → 32 → 13 → 10 →?1?→?1
85 →?89?→ 145 → 42 → 20 → 4 → 16 → 37 → 58 →?89

可見，任何一個(gè)到達(dá)1或89的數(shù)字鏈都會(huì)陷入無盡的循環(huán)。更令人驚奇的是，從任意數(shù)開始，最終都會(huì)到達(dá)1或89。

有多少個(gè)小于一千萬的數(shù)最終會(huì)到達(dá)89？

解題

這個(gè)鏈?zhǔn)降闹昂糜杏袀€(gè)題目和這個(gè)差不多的，直接暴力很簡(jiǎn)單。

JAVA

package Level3;public class PE092{static void run(){int MAX = 10000000;int count = 0;for(int num=1;num<=MAX;num++){int numx = num;if(is89(numx))count +=1;}System.out.println(count);} // 8581146 // running time=1s973msstatic boolean is89(int num){int next_num = num;while(true){if(next_num == 89) break;if(next_num == 1) break;next_num = nextNum(next_num);}if(next_num ==89)return true;return false;}static int nextNum(int num){int next_num = 0;while(num!=0){int tmp = num%10;next_num += tmp*tmp;num/=10;}return next_num;}public static void main(String[] args) {long t0 = System.currentTimeMillis();run();long t1 = System.currentTimeMillis();long t = t1 - t0;System.out.println("running time="+t/1000+"s"+t%1000+"ms");} }

?Python運(yùn)行時(shí)間比較長(zhǎng)

# coding=gbkimport time as time from itertools import combinations def run():MAX = 10000000count = 0for num in range(1,MAX):if is89(num):count+=1print count # 8581146 # running time= 305.638000011 s def next_num(num):return sum([a*a for a in map(int ,str(num))])def is89(num):while True:if num == 89 or num == 1:breaknum = next_num(num)if num == 89:return True return False t0 = time.time() run() t1 = time.time() print "running time=",(t1-t0),"s"

85 →?89?→ 145 → 42 → 20 → 4 → 16 → 37 → 58 →?89

題目給了一個(gè)這樣的提示，只有我們知道中間的數(shù)，就一定能到89

最大值是9999999 ，nextnum = 9*9*7 = 567 ，可以定義一個(gè)568的數(shù)組來保存中間的計(jì)算結(jié)果能到達(dá)89的。

這里我只定義一個(gè)boolean數(shù)組Judge。先保存前一步的值numx， 若nextnum[numx] == 89 則，則Judge[numx] ==True

在以后我們可以先判斷nextnum在Judge中是否是true，true就不用計(jì)算了。

當(dāng)然如果定義一個(gè)矩陣，保存所有的計(jì)算中間值，這個(gè)比較復(fù)雜啊，對(duì)了，可以定義一個(gè)set，也很好判斷是否存在。下面嘗試一下。

下面run2（） 是定義boolean數(shù)組的，run3()是定義兩個(gè)set的。

定義boolean數(shù)組的 ?對(duì)所有的值是否都能判斷？ 這里就不知道了。所以才想起了定義set的

package Level3;import java.util.TreeSet;public class PE092{static void run3(){int MAX = 10000000;int count =0;TreeSet<Integer> path = new TreeSet<Integer>();TreeSet<Integer> judge = new TreeSet<Integer>();for(int num =2;num<MAX;num++){int numx = nextNum(num);if(path.contains(numx)){count +=1;}else{while(true){judge.add(numx);numx = nextNum(numx);if(path.contains(numx) || numx==89){path.addAll(judge);judge.clear();count +=1;break;}if(numx == 1){judge.clear();break;}}}}System.out.println(count);} // 8581146 // running time=0s953ms// 9*9*7 = 567 定義一個(gè)長(zhǎng)度是567的數(shù)組保存之前計(jì)算過程中的值 // 若以89結(jié)束定義為true 以后認(rèn)為是true就可以直接認(rèn)為是89結(jié)束了static void run2(){int MAX = 10000000;int count = 0;boolean Judge[] = new boolean[568];for(int num =1;num<MAX;num++){// 求下一個(gè)數(shù)int numx = nextNum(num);// 下一個(gè)數(shù)是否計(jì)算過if(Judge[numx]){count+=1;}else{ while(true){// 繼續(xù)求下一個(gè)數(shù) int tmp = nextNum(numx);// 計(jì)算過或者 遇到89的時(shí)候把之前的數(shù)更行Judge[numx] if(Judge[tmp] || tmp==89){count+=1;Judge[numx] = true;break;}if(tmp ==1) break;numx = tmp;}}}System.out.println(count);} // 8581146 // running time=0s944msstatic void run(){int MAX = 10000000;int count = 0;for(int num=1;num<=MAX;num++){int numx = num;if(is89(numx))count +=1;}System.out.println(count);} // 8581146 // running time=1s973msstatic boolean is89(int num){int next_num = num;while(true){if(next_num == 89) break;if(next_num == 1) break;next_num = nextNum(next_num);}if(next_num ==89)return true;return false;}static int nextNum(int num){int next_num = 0;while(num!=0){int tmp = num%10;next_num += tmp*tmp;num/=10;}return next_num;}public static void main(String[] args) {long t0 = System.currentTimeMillis();run2();long t1 = System.currentTimeMillis();long t = t1 - t0;System.out.println("running time="+t/1000+"s"+t%1000+"ms");} }

Python

# coding=gbkimport time as time def run2():MAX = 10000000count = 0 path=[]judge=[]for num in range(1,MAX):numx = next_num(num)if numx in path:count +=1else:while True:judge.append(numx)numx = next_num(numx)if numx in path or numx == 89:count+=1path +=judgejudge=[]breakif numx ==1:judge = []breakprint count # 8581146 # running time= 165.453000069 s

?

總結(jié)

以上是生活随笔為你收集整理的Project Euler 92：Square digit chains 平方数字链的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。