1

首先，这不是一个家庭作业问题。我正在通过一些组合问题来解决算法问题，我真的只需要开始解决这个问题。

我最初的想法是声明一个大小为 17 的数组来初始化它并运行一个循环来查找一个数字的出现，比如使用简单的搜索“5”。但是该解决方案看起来乏味且丑陋。

  1. 关于如何表示一个大数字（10 ^ 16）的任何想法？
  2. 有没有简单的组合公式/算法来解决这类问题？

谢谢。

4

2 回答 2

1

假设您的意思是 0 <= l < 10^16（不是 <= 10^16），则此范围内的所有整数都有 10 位数字（允许前导 0）。在这个范围内总共有 10^16 个值。我会把问题写成：

带数字n = 10^16 - 不带数字n的数字。

那么有多少种方法可以不选择n代替 1 呢？9种方式。我们有多少种方法可以不在 10 或 1 的位置上加上“n”？9*9。按照这个逻辑，有 9^16 种方法可以不将n放入 16 个可能的插槽中的任何一个。

所以你的答案是 10^16 - 9^16。

如果您实际上的意思是 0 <= l <= 16，则该范围只有一个数字，即 10^16。这个数字的前导数字是 1，所以如果n = 1，你正好有 10^16 - 9^16 + 1 个值，其中包含 1。如果 n != 1 则前面的答案成立。

于 2013-07-23T06:09:46.583 回答
0

让：

G(m)是包含数字的值的i数量0<=i<=10^mn!=0

正如前面的答案所说，当 时n!=0，答案是：

G(m) = 10^m - 9^m

所以，G(16) = 10,000,000,000,000,000 - 1,853,020,188,851,841 = 8,126,979,811,148,159

当 时n=0，有两种可能的方式来看待它。

1) 只计算第一个非零数字之后的数字 2) 计算所有m数字，即使数字以多位0数字开头

对于第二种情况，那么答案 whenn=0与 when 相同n!=0。

F(m)是包含数字的值的i数量0<=i<=10^mn=0

对于第一种情况，答案稍微复杂一些。在一个m数字中，第一个数字不是 0，但其余m-1数字可以是任何数字。因此，G(m-1)在那些m-1' digits can contain a zero. Since there are 9 (non zero) possibilities for the leading digit,F(m) = 9*G(m-1)` 定义的数字中。

让H(m,n)是值的数量i，其中0<=i<=10^m包含数字n

然后：

H(m,n) = G(m)如果n!=0，9*G(m-1)如果n=0

在哪里

G(m) = 10^m - 9^m

因此，H(16,n) = 8,126,979,811,148,159如果n!=0和H(16,0) = 7,146,979,811,148,159

于 2013-07-25T16:46:26.310 回答