在给定范围内用特定数字写入的所有数字之和
我的目标是求出从4到666554的所有数字之和，其中只有4,5,6。
SUM = 4+5+6+44+45+46+54+55+56+64+65+66+.....................+666554.简单的方法是运行一个循环，并只添加由4、5和6组成的数字。
long long sum = 0;
for(int i=4;i <=666554;i++){
/*check if number contains only 4,5 and 6.
if condition is true then add the number to the sum*/
}但它似乎效率低下。检查数字是由4、5和6组成的，这需要时间。有没有办法提高效率。我尝试了很多，但没有新的方法，我有found.Please的帮助。
回答 5
Stack Overflow用户
发布于 2015-07-08 08:09:43
在基数3(数字值的数目)中实施计数器，例如0、1、2、10、11、12、20、21、22、100。然后将基-3数字转换为小数位数4、5、6 (0->4、1->5、2->6)，并添加到正在运行的总计中。重复到极限。
def compute_sum(digits, max_val):
def _next_val(cur_val):
for pos in range(len(cur_val)):
cur_val[pos]+=1
if cur_val[pos]<len(digits):
return
cur_val[pos]=0
cur_val.append(0)
def _get_val(cur_val):
digit_val=1
num_val=0
for x in cur_val:
num_val+=digits[x]*digit_val
digit_val*=10
return num_val
cur_val=[]
sum=0
while(True):
_next_val(cur_val)
num_val=_get_val(cur_val)
if num_val>max_val:
break
sum+=num_val
return sum
def main():
digits=[4,5,6]
max_val=666554
print(digits, max_val)
print(compute_sum(digits, max_val))Stack Overflow用户
发布于 2015-07-08 12:59:55
数学是好的，但并不是所有的问题都是微不足道的“可压缩的”，因此知道如何处理没有数学的问题是值得的。
在这个问题中，求和是微不足道的，困难在于第一眼就能有效地列举需要添加的数字。
“筛选”路径是一种可能性:递增地生成所有可能的数字，然后过滤掉那些不匹配的数字；但是，它也非常低效率(一般情况下)：
- 匹配的条件可能并不简单:在本例中，更简单的方法是将字符串转换为字符串(在除法和测试中相当重)，然后进行字符串匹配。
- 从每位数30%开始，过滤的比率并不坏，但是像吉英所说的那样，过滤的比例很低:对于一个4位数，它是1%，或者生成和检查100个数字，只得到其中的一个数字。
因此，我建议一种“代际”方法:只生成符合条件的数字(以及所有这些数字)。
我要指出，生成由4、5和6组成的所有数字就像计数(三元)：
- 从4点开始
- 45变成46 (提防结转)
- 66变成444 (极端结转)
让我们以Python作为生成器：
def generator():
def convert(array):
i = 0
for e in array:
i *= 10
i += e
return i
def increment(array):
result = []
carry = True
for e in array[::-1]:
if carry:
e += 1
carry = False
if e > 6:
e = 4
carry = True
result = [e,] + result
if carry:
result = [4,] + result
return result
array = [4]
while True:
num = convert(array)
if num > 666554: break
yield num
array = increment(array)其结果可以用sum(generator())打印。
$ time python example.py
409632209
python example.py 0.03s user 0.00s system 82% cpu 0.043 total和以下是C++中的相同内容。
Stack Overflow用户
发布于 2015-07-08 13:25:32
“从一个更简单的问题开始。”-Polya。
仅由数字4、5、6组成的n位数之和
正如余浩上面所解释的，存在3**n数，它们的平均对称性是eg。555555，所以之和是3**n * (10**n-1)*5/9。但是如果你没有注意到这一点，下面是你可以用另一种方法解决这个问题的方法。
这个问题有一个递归结构，所以让我们尝试一个递归解决方案。设g(n)是所有456位数的之和。然后我们得到了递推关系。
g(n) = (4+5+6)*10**(n-1)*3**(n-1) + 3*g(n-1)要查看这一点，请将和中的每个数字的第一个数字分开(例如。对于n=3，数百列)。这就给了第一个任期。第二个项是剩余数字之和，每个前缀为4、5、6，计数为g(n-1)。
如果仍不清楚，请写出n=2和，并将数十个单位与单位分开：
g(2) = 44+45+46 + 54+55+56 + 64+65+66
= (40+50+60)*3 + 3*(4+5+6)
= (4+5+6)*10*3 + 3*g(n-1)凉爽的。在这一点上，敏锐的读者可能要检查余浩的公式g(n)满足我们的递推关系。
为了解决OP的问题，从4到666666的456个数字之和为g(1) + g(2) + g(3) + g(4) + g(5) + g(6).在Python中，使用动态编程：
def sum456(n):
"""Find the sum of all numbers at most n digits which consist of 4,5,6 only"""
g = [0] * (n+1)
for i in range(1,n+1):
g[i] = 15*10**(i-1)*3**(i-1) + 3*g[i-1]
print(g) # show the array of partial solutions
return sum(g)对于n=6
>>> sum456(6)
[0, 15, 495, 14985, 449955, 13499865, 404999595]
418964910编辑:我注意到OP把他的和截断到666554，所以它不符合一般的模式。不会是最后几个条款了
>>> sum456(6) - (666555 + 666556 + 666564 + 666565 + 666566 + 666644 + 666645 + 666646 + 666654 + 666655 + 666656 + + 666664 + 666665 + 666666)
409632209https://stackoverflow.com/questions/31285547
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号