题目
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?
将一个数的所有数字的平方相加得到一个新的数，不断重复直到新的数已经出现过为止，这构成了一条数字链。
例如，
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
可见，任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是，从任意数开始，最终都会到达1或89。
有多少个小于一千万的数最终会到达89？
解题
这个链式的之前好有有个题目和这个差不多的，直接暴力很简单。
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=1s973ms static 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运行时间比较长
# coding=gbk import time as time from itertools import combinations def run(): MAX = 10000000 count = 0 for num in range(1,MAX): if is89(num): count+=1 print 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: break num = 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
题目给了一个这样的提示，只有我们知道中间的数，就一定能到89
最大值是9999999 ，nextnum = 9*9*7 = 567 ，可以定义一个568的数组来保存中间的计算结果能到达89的。
这里我只定义一个boolean数组Judge。先保存前一步的值numx， 若nextnum[numx] == 89 则，则Judge[numx] ==True
在以后我们可以先判断nextnum在Judge中是否是true，true就不用计算了。
当然如果定义一个矩阵，保存所有的计算中间值，这个比较复杂啊，对了，可以定义一个set，也很好判断是否存在。下面尝试一下。
下面run2（） 是定义boolean数组的，run3()是定义两个set的。
定义boolean数组的 对所有的值是否都能判断？ 这里就不知道了。所以才想起了定义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 定义一个长度是567的数组保存之前计算过程中的值 // 若以89结束定义为true 以后认为是true就可以直接认为是89结束了 static void run2(){ int MAX = 10000000; int count = 0; boolean Judge[] = new boolean[568]; for(int num =1;num<MAX;num++){ // 求下一个数 int numx = nextNum(num); // 下一个数是否计算过 if(Judge[numx]){ count+=1; }else{ while(true){ // 继续求下一个数 int tmp = nextNum(numx); // 计算过或者 遇到89的时候把之前的数更行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=0s944ms 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=1s973ms static 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=gbk import time as time def run2(): MAX = 10000000 count = 0 path=[] judge=[] for num in range(1,MAX): numx = next_num(num) if numx in path: count +=1 else: while True: judge.append(numx) numx = next_num(numx) if numx in path or numx == 89: count+=1 path +=judge judge=[] break if numx ==1: judge = [] break print count # 8581146 # running time= 165.453000069 s