欧拉计划 发表于 2016-9-14 23:41:44

题目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 发表于 2017-8-30 14:30:47

用广度优先搜索或者A*搜索可以解，问题是要求20位的话，花的时间会非常长。
我算了一下10位的，大概10秒多一点。每多一位要差不多5倍的时间。
这样算20位的话至少需要97656250秒，也就是计算机要跑3年。。。
我的天啊，应该能找到更好的方法来求解吧。
from collections import deque
def euler164(length=20):
        count = 0
        quee = deque(['1','2','3','4','5','6','7','8','9'])
        while quee:
                q = quee.popleft()
                tt = 0
                for i in range(min(len(q),2)):
                        tt += int(q[-1-i])
                if tt > 9: continue
                for j in range(10-tt):
                        if len(q)+1 == length:
                                count += 1
                                #print(q+str(j), count)
                                continue
                        else:
                                quee.appendleft(q+str(j))
        return count
print(euler164(10))
# 3                165
# 4                990
# 5                5445
# 6                27588
# 7                146586
# 8                783057
# 9                4129851
# 10                21838806

guosl 发表于 2020-5-9 21:04:19

本帖最后由 guosl 于 2020-12-2 19:29 编辑

答案：378158756814587
应用递推即可。
#include <iostream>
using namespace std;

long long f;

int main(void)
{
for (int i = 1; i <= 9; ++i) //枚举首位数
    f = 1;
for (int n = 2; n <= 20; ++n) //数字的位数
{
    for (int m1 = 0; m1 <= 9; ++m1) //枚举最后一位
    {
      for (int m2 = 0; m2 <= 9; ++m2)//枚举最后二位
      {
      int k = m1 + m2;
      if (k > 9)
          break;
      for (int m3 = 0; m3 <= 9 - k; ++m3)////枚举最后三位
          f += f;
      }
    }
}
long long nCount = 0;
for (int m1 = 0; m1 <= 9; ++m1) //求和
{
    for (int m2 = 0; m2 <= 9; ++m2)
      nCount += f;
}
cout << nCount << endl;
return 0;
}

瓦屋青衣 发表于 2021-4-1 14:38:28

import time
import math

timeStart = time.time()

n = 20

dic = {}
lis = [(i ,j) for i in range(10) for j in range(10) if i+j <= 9]
for tp in lis:
    dic[(3, *tp)] = 9-sum(tp)
for x in range(4, 1+20):
    for tp in lis:
      for y in range(10-sum(tp)):
            dic[(x, *tp)] = dic.setdefault((x, *tp), 0) + dic[(x-1, y, tp)]
#

ans = sum(dic[(n, *tp)] for tp in lis)

print(ans)

print(f'time used: {time.time() - timeStart: .3f} s')
页: [1]
查看完整版本: 题目164：任意三个相邻数字位之和不超过给定值的数字