问计算整数范围之间的零数

EN

重新检查问题

下面是Ruby中的一个简单解决方案，它检查间隔m，n中的每个整数，确定标准基数10位置系统中其数字的字符串，并计数出现的0位数：

def brute_force(m, n)
  if m > n
    return 0
  end
  z = 0
  m.upto(n) do |k|
    z += k.to_s.count('0')
  end
  z
end

如果您在交互式Ruby shell中运行它，您将得到

irb> brute_force(1,100)
=> 11

这很好。但是，使用问题中示例中的间隔界限

m = 1234567890
n = 2345678901

你会意识到这需要相当长的时间。在我的机器上它确实需要超过几秒钟，我不得不取消到目前为止。

所以真正的问题不仅是想出正确的零计数，而且要比上面的蛮力解更快。

复杂性:运行时

该蛮力解需要执行n-m+1次搜索基数10字符串的数字k，它的长度是地板(log_10(K))+1，所以它不会超过

O(n (log(n)+1))

字符串数字访问。这个慢例子的n值大约为10^9。

降低复杂度

容一鸣的回答是第一次尝试降低问题的复杂性。

如果计算关于区间m，n的零点数的函数是F(m，n)，则它具有以下性质

F(m，n) = F(1，n) - F(1，m-1)

因此，只要寻找一个最有可能更简单的函数G，就足够了

G(n) = F(1，n)。

除法与征服

给出函数G的封闭公式并不是那么容易。例如，间隔1,1000包含192个零，但间隔1001,2000包含300个零，因为在第一个区间中，像k= 99这样的大小写将对应于第二个区间中的k= 1099，这将产生另一个零数字来计数。k=7将显示为1007，产生两个零。

我们可以尝试的是用更简单的问题实例的解决方案来表达某些问题实例的解决方案。这种策略在计算机科学中被称为分而治之。如果在某种复杂程度上，可以解决问题实例，并且可以从较简单问题的解决中推断出更复杂问题的解决方案，则该方法是可行的。这自然会导致递归公式。

例如，我们可以为G的一个受限版本制定一个解决方案，它只适用于某些论点。我们称它为g，定义为9，99,999等，对于这些参数，它将等于G。它可以使用这个递归函数来计算：

# zeros for 1..n, where n = (10^k)-1: 0, 9, 99, 999, ..
def g(n)
  if n <= 9
    return 0
  end
  n2 = (n - 9) / 10
  return 10 * g(n2) + n2
end

请注意，这个函数比蛮力方法要快得多:要计算间隔1，10^9-1中的零，这与问题中的m相当，它只需要9次调用，其复杂性是

O(log(n))

请再次注意，这个g不是为任意n定义的，只对n= (10^k)-1定义。

G-的推导

它首先找到函数h(n)的递归定义，如果十进制表示有前导零，则h(N)在从1到n= (10^k) -1的数字中计数零。

示例: h(999)计算数字表示的零位数：

• 001..009
• 010.099
• 100..999

结果是h(999) = 297。

使用k=楼层(log10(n+1))，k2 =k-1，n2 = (10^k2) -1= (n-9)/10，则函数h是

h(n) =9 k2 + h( n2 ) + h( n2 ) +n2=9 k2 + 10 h(n2) +n2

初始条件h( 0 ) =0。它允许将g表示为

g(n) =9 k2 + h(n2) + g(n2)

与初始条件g( 0 ) =0。

根据这两个定义，我们也可以将h和g之间的差异d定义为递归函数：

d(n) = h(n) - g(n) = h( n2 ) - g( n2 ) +n2= d(n2) +n2

初始条件d( 0 ) =0。尝试一些例子可以得到一个几何级数，例如d(9999) = d( 999 ) + 999 = d( 99 ) + 99 + 999 = d(9) +9+ 999 =0+9+ 99 +999= (10^0)-1 + (10^1)-1 + (10^2)-1 + (10^3)-1 = (10^4 - 1)/(10-1) - 4。

d(n) = n/9 -k

这允许我们仅用g来表示g：

g(n) =9 k2 + h( n2 ) + g( n2 ) =9 k2 + g(n2) + d(n2) + g(n2) =9 k2 +9d(N2)+10g(N2)=9 k2 +n2-9 k2 +10g(N2)=10g(N2)+n2

G的推导

使用上述定义并命名表示法q_k、q_k2、.、q2、q1的k位，我们首先将h扩展为H：

H(q_k q_k2..q_1) = q_k k2 + h( n2 ) +r (k2-kr) + H(q_kr..q_1) +n2

以初始条件H( q_1 ) =0表示q_1 <= 9。

请注意附加的定义r= q_kr..q_1。要理解为什么需要它，请看示例H(901)，其中对H的下一个级别调用是H(1)，这意味着数字字符串长度从k=3缩减到kr=1，需要用r (k2-kr)零位数进行额外填充。

使用此方法，我们还可以将g扩展到G：

G(q_k q_k2..q_1) = (q_k-1) k2 + h(n2) + k2 +r (k2-kr) + H(q_kr..q_1) + g(n2)

以初始条件G( q_1 ) =0表示q_1 <= 9。

注意:很可能在上面g的情况下，可以简化上面的表达式。例如，试图用G来表示G，而不使用H和H。我将来可能会这样做。以上已足以实现快速的零计算。

测试结果

recursive(1234567890, 2345678901) =
  987654304
expected:
  987654304
success

有关详细信息，请参阅来源和日志。

更新:我根据竞赛中更详细的问题描述更改了源和日志(允许0作为输入，处理无效的输入，第二个更大的例子)。

你可以用标准方法求m = 1，M-1和n= 1，N，然后M，N=n。

标准方法很容易获得：计数零。