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。
以一千万以下的数字n开始，有多少个n会到达89？
算法一：常规方法，从2~10000000逐个判断，同时统计结果
#include<stdio.h> #define N 10000000 int fun(int n)
{
int t, sum;
sum = ;
while(n) {
t = n % ;
sum += t * t;
n /= ;
}
return sum;
} void solve(void)
{
int i, sum, t;
sum = ;
for(i = ; i < N; i++) {
t = fun(i);
while() {
if(t == ) {
sum++;
break;
} else if(t == ) {
break;
} else {
t = fun(t);
}
}
}
printf("%d\n",sum);
} int main(void)
{
solve();
return ;
}
算法二（优化）：使用一个bool型数组，保存每次结果，由于最大的中间数为9999999产生的：9^2*7 = 567，所以bool型数组的大小开到600足够
#include <stdio.h>
#include <stdbool.h> #define N 10000000 bool a[] = {false}; int fun(int n)
{
int t, sum;
sum = ;
while(n) {
t = n % ;
sum += t * t;
n /= ;
}
return sum;
} void solve(void)
{
int i, sum, t, temp;
sum = ;
for(i = ; i < N; i++) {
t = fun(i);
temp = t;
if(a[temp]) {
sum++;
} else {
while() {
t = fun(t);
if(a[t] || t == ) {
a[temp] = true;
sum++;
break;
} else if(t == ) {
break;
} else {
}
}
}
}
printf("%d\n",sum);
} int main(void)
{
solve();
return ;
}
Answer: | 8581146 |