题目92：考察具有有趣性质的平方数链,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2016-8-11 23:14:50

题目92：考察具有有趣性质的平方数链

本帖最后由永恒的蓝色梦想于 2020-6-5 14:24 编辑

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?

题目：

通过将一个数各位的平方不断相加，直到遇到已经出现过的数字，可以形成一个数字链。

例如：
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

因此任何到达 1 或 89 的数字链都会陷入无限循环。令人惊奇的是，以任何数字开始，最终都会到达 1 或 89。

以一千万以下的数字 n 开始，有多少个 n 会到达 89？

迷雾少年 发表于 2016-8-31 16:48:19

结果12587445
#include <iostream>
#include <vector>
#include <algorithm>
using namespacestd;
/*
返回一个数字各位数平方相加后的数
*/
int get(int num)
{
int sum=0;
int t = num;
while(num)
{
sum+= (num%10)*(num%10);
num/=10;
}
return sum;
}
int main()
{
//限制从1KW
vector<int> result;
int j = 0;
int sum=0;//统计有89的数字
for (int i =1;i<=10000000;i++)
{
j=i;
int value = 0;

//获取这个数字各位数平方和
while(1)
{

value = get(j);
if(value==89) sum++;
if(result.end()==find(result.begin(),result.end(),value))
{
//没找到到了
result.push_back(value);
j=value;

}else
{
//找到退出
result.push_back(value);
break;

}

}
//输出结果

//std::cout<<i<<":";
for (int m=0;m<result.size();m++)
{
//std::cout<<result<<" ";
}
//std::cout<<endl;
result.clear();

}
std::cout<<"结果"<<sum<<endl;
return 0;
}

QingXin 发表于 2016-9-18 23:31:59

10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在运行过程中一旦碰到字典中的数，马上将1或89作为结果反馈。这样，可以加速运算过程。代码如下，结果为8581146。
def get_sum(x):
number_list = []
while x:
   x,temp = divmod(x,10)
   number_list.insert(0,temp)
return sum()

num_dict = {}

for i in range(1,600):
s = i
while s != 1 and s != 89:
   if num_dict.get(s,0):
         s = num_dict
         break
   s = get_sum(s)
num_dict = s

count_89 = 0
for i in range(1,10000001):
s = get_sum(i)
if num_dict == 89:
   count_89+=1

print(count_89)

jerryxjr1220 发表于 2016-10-18 11:51:14

QingXin 发表于 2016-9-18 23:31
10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在 ...

8581146

楼上的方法比我好，我只是暴力求解，花了1分多钟。
def chain(n):
i = n
while True:
s = 0
while True:
s += (i%10)**2
i = int(i/10)
if i == 0:
break
i = s
if i == 89:
return True
elif i == 1:
return False
else:
pass

count = 0
for i in range(2,10000000):
if chain(i):
count += 1
print count

愤怒的大头菇 发表于 2016-11-23 10:17:51

def Loop(x,count=0):
while x!=1 and x!=89:
   for each in str(x):
         count += int(each)**2
   x = count
   count = 0
if x ==89:
   return True
if x == 1:
   return False
total = 0
for i in range(1,10000000):
if Loop(i,count=0):
   total += 1
print(total)
结果：8581146

芒果加黄桃 发表于 2017-3-6 16:53:04

# encoding:utf-8
# 具有有趣性质的平方数链
from time import time
N = 10000000
flag = * (N + 1)
def getNums(n):
while (n != 1 and n != 89):
   if flag == 1:
         return 1
   elif flag == 89:
         return 89
   sums = 0
   for x in str(n):
         sums += (int(x)) ** 2
   n = sums
return n

def euler092(N):
for n in range(1, N):
   t = getNums(n)
   # print(n,t)
   if t == 1:
         flag = 1
   else:
         flag = 89
print(len())

if __name__ == '__main__':
start = time()
euler092(N)
print('cost %.6f sec' % (time() - start))

永恒的蓝色梦想 发表于 2019-7-22 11:07:04

本帖最后由永恒的蓝色梦想于 2021-2-12 20:49 编辑

借鉴3L思路
C++ 265ms#include<iostream>

constexpr unsigned char arrive_at(unsigned int x)noexcept {
constexpr unsigned char squares[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
static unsigned char cache + 1] = { = 1, = 89};
unsigned int temp;
unsigned short res = 0;

while (x) {
   temp = x;
   x /= 10;
   res += squares;
}

if (cache) {
   return cache;
}

return cache = arrive_at(res);
}

int main() {
using namespace std;
ios::sync_with_stdio(false);

unsigned int count = 0, num;

for (num = 1; num < 10000000; num++) {
   count += arrive_at(num) == 89;
}

cout << count << endl;
return 0;
}

永恒的蓝色梦想 发表于 2020-6-19 15:41:00

本帖最后由永恒的蓝色梦想于 2020-6-25 19:57 编辑

QingXin 发表于 2016-9-18 23:31
10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在 ...

把 get_sum 函数改为def get_sum(x):
result = 0

while x:
x,temp = divmod(x,10)
result += temp * temp

return result会更好。

QingXin 发表于 2020-6-25 13:00:04

永恒的蓝色梦想发表于 2020-6-19 15:41
把 get_sum 函数改为会更好。

嗯嗯，谢谢指正！确实，建一个列表占用了时间，这个列表没必要建立的。版主的代码里面应该写result += temp**2 ？太匆忙忘记了吧

永恒的蓝色梦想 发表于 2020-6-25 19:57:22

QingXin 发表于 2020-6-25 13:00
嗯嗯，谢谢指正！确实，建一个列表占用了时间，这个列表没必要建立的。版主的代码里面应该写result...

确实是{:10_258:}写错了

debuggerzh 发表于 2020-8-21 10:15:21

8581146

Process returned 0 (0x0) execution time : 0.514 s
Press any key to continue.
递归+记忆化搜索
#include<iostream>
using namespace std;

const int M = 1e7;
int e = {0};

int square_sum(int x){
int res = 0;
int x0 = x;
if (e)return e;

while(x){
int t = x % 10;
res += t*t;
x /= 10;
}

if (res == 1 || res == 89) return e = res;
return e = square_sum(res);
}

int main(){
int cnt = 0;

for (int i = 1;i < M;i++){
square_sum(i);
if (e == 89) cnt++;
}
cout << cnt << endl;
return 0;
}

guosl 发表于 2022-1-17 13:56:20

/*
答案：8581146
耗时：0.314319秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;

int v1 = { 1,10,13,32,44 };
int v89 = { 4,16,20,37,42,58,85,89,145 };
int S = { 0,1,4,9,16,25,36,49,64,81 };

int main(void)
{
double t = omp_get_wtime();
int nCount = 0;
#pragma omp parallel for shared(v1,v89,S) reduction(+:nCount)
for (int n = 1; n <= 10000000; ++n)
{
int k = n;
bool bFind = false;
while (true)
{
   int nSum = 0;
   while (k != 0)
   {
   nSum += S;
   k /= 10;
   }
   if (binary_search(v1, v1 + 5, nSum))
   break;
   if (binary_search(v89, v89 + 9, nSum))
   {
   bFind = true;
   break;
   }
   k = nSum;
}
if (bFind)
   ++nCount;
}
t = omp_get_wtime() - t;
cout << nCount << endl << t << endl;
return 0;
}

页: [1]

鱼C论坛's Archiver

题目92：考察具有有趣性质的平方数链