在给定范围内使用特定数字写入的所有数字的总和

Question

我的目标是找到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组成需要时间.有没有办法提高效率.我已经尝试了很多,但没有找到新的方法.请帮助.

Answer 1

对于1位数字,请注意

4 + 5 + 6 == 5 * 3

对于2位数字:

(44 + 45 + 46) + (54 + 55 + 56) + (64 + 65 + 66)
== 45 * 3 + 55 * 3 + 65 * 3
== 55 * 9

等等.

在一般情况下,n-digits数字,有3 ^ň的其中包括4,5,6只是,他们的平均价值是完全5...5(n位).使用代码,它们的总和是('5' * n).to_i * 3 ** n(Ruby)或int('5' * n) * 3 ** n(Python).

您计算最多6位数字,然后减去666555to 的总和666666.

PS:对于小数字666554,使用模式匹配足够快.(例子)

Answer 2

在基数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))

Answer 3

数学是好的,但并非所有的问题都是"可压缩的",所以知道如何在没有数学的情况下处理它们是值得的.

在这个问题中,求和是微不足道的,难以有效地枚举需要添加的数字,乍一看.

"过滤"路径是一种可能性:逐步生成所有可能的数字,并过滤掉那些不匹配的数字; 但它的效率也很低(一般来说):

• 条件可能不容易匹配:在这种情况下,更简单的方法是转换为字符串(在分区和测试上相当繁重),然后是字符串匹配
• gen-ys评论说,过滤的比例并不是太差,但它的扩展速度非常差:对于4位数字,它是1%,或生成并检查100个数字只得到1他们

因此,我建议采用"世代"方法:只生成符合条件的数字(以及所有数字).

我会注意到,生成由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++相同.