题目164：任意三个相邻数字位之和不超过给定值的数字

欧拉计划

Numbers for which no three consecutive digits have a sum greater than a given value

How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a sum greater than 9?

题目：

请问，存在多少个位数为 20（没有前导 0），并且任意三个相邻数位之和不超过 9 的数字？

jerryxjr1220

用广度优先搜索或者A*搜索可以解，问题是要求20位的话，花的时间会非常长。
我算了一下10位的，大概10秒多一点。每多一位要差不多5倍的时间。
这样算20位的话至少需要97656250秒，也就是计算机要跑3年。。。
我的天啊，应该能找到更好的方法来求解吧。

1. from collections import deque
   
2. def euler164(length=20):
   
3.         count = 0
   
4.         quee = deque(['1','2','3','4','5','6','7','8','9'])
   
5.         while quee:
   
6.                 q = quee.popleft()
   
7.                 tt = 0
   
8.                 for i in range(min(len(q),2)):
   
9.                         tt += int(q[-1-i])
   
10.                 if tt > 9: continue
    
11.                 for j in range(10-tt):
    
12.                         if len(q)+1 == length:
    
13.                                 count += 1
    
14.                                 #print(q+str(j), count)
    
15.                                 continue
    
16.                         else:
    
17.                                 quee.appendleft(q+str(j))
    
18.         return count
    
19. print(euler164(10))
    
20. # 3                165
    
21. # 4                990
    
22. # 5                5445
    
23. # 6                27588
    
24. # 7                146586
    
25. # 8                783057
    
26. # 9                4129851
    
27. # 10                21838806

复制代码

guosl

答案：378158756814587
应用递推即可。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. long long f[21][10][10];
   
5. 
   
6. int main(void)
   
7. {
   
8.   for (int i = 1; i <= 9; ++i) //枚举首位数
   
9.     f[1][i][0] = 1;
   
10.   for (int n = 2; n <= 20; ++n) //数字的位数
    
11.   {
    
12.     for (int m1 = 0; m1 <= 9; ++m1) //枚举最后一位
    
13.     {
    
14.       for (int m2 = 0; m2 <= 9; ++m2)//枚举最后二位
    
15.       {
    
16.         int k = m1 + m2;
    
17.         if (k > 9)
    
18.           break;
    
19.         for (int m3 = 0; m3 <= 9 - k; ++m3)////枚举最后三位
    
20.           f[n][m1][m2] += f[n - 1][m2][m3];
    
21.       }
    
22.     }
    
23.   }
    
24.   long long nCount = 0;
    
25.   for (int m1 = 0; m1 <= 9; ++m1) //求和
    
26.   {
    
27.     for (int m2 = 0; m2 <= 9; ++m2)
    
28.       nCount += f[20][m1][m2];
    
29.   }
    
30.   cout << nCount << endl;
    
31.   return 0;
    
32. }
    

复制代码

瓦屋青衣

1. import time
   
2. import math
   
3. 
   
4. timeStart = time.time()
   
5. 
   
6. n = 20
   
7. 
   
8. dic = {}
   
9. lis = [(i ,j) for i in range(10) for j in range(10) if i+j <= 9]
   
10. for tp in lis:
    
11.     dic[(3, *tp)] = 9-sum(tp)
    
12. for x in range(4, 1+20):
    
13.     for tp in lis:
    
14.         for y in range(10-sum(tp)):
    
15.             dic[(x, *tp)] = dic.setdefault((x, *tp), 0) + dic[(x-1, y, tp[0])]
    
16. #[print(k, v) for k, v in dic.items()]
    
17. 
    
18. ans = sum(dic[(n, *tp)] for tp in lis)
    
19. 
    
20. print(ans)
    
21. 
    
22. print(f'time used: {time.time() - timeStart: .3f} s')

复制代码