包含给定数字的数字有多少？

Question

让我们有 3 位数字 (100-999)。有多少这样的数字至少有一位数字“2”？

如何为此制定算法？还是数学函数？

Answer 1

包容-排除原则

有多少个三位数字的第一位是

2

(

2xx

)？没错-

100

。作为第二个数字（

x2x

）？

100

！和第三个 (

xx2

) - 相同的数字。好的，现在我们有了

300

数字，但是我们忘记了

22x

形式的数字，我们数了两次。现在我们需要减去

22x

、

2x2

和

x22

数的数量。现在我们有

270

个，但是我们忘记了

222

这个数字，我们加了三次，减了三次，我们需要再加一次：

271

。这个解释是包含 - 排除原则的一个例子。

但这还没有结束，我们需要减去所有以

0xx

为数字的

2

数。类似的做法：

271 - 10 - 10 + 1 = 252

。

动态规划

好吧，如果你不喜欢前面的方法，还有一个。让我们计算函数

F(i, has2)

，其中

i

- 是数字的数字长度，如果数字包含

has2

，则

true

布尔值等于

2

，否则等于

false

。递归关系如下：

 F(1, false) = 8, F(1, true) = 1
 F(i, true) = F(i-1, true) * 10 + F(i-1, false) 
 F(i, false) = F(i-1, false) * 9

答案是

F(3, true)

。

 F(2, true) = 10 + 8 = 18
 F(2, false) = 8 * 9 = 72
 F(3, true) = 18 * 10 + 72 = 252      

Answer 2

使用 python 的快速'n'dirty 是：

n  = [x for x in range(100,999) if '2' in str(x)] 

print("There are " + str(len(n)) + " numbers between 100 and 999 containing at least one '2'")
print(n)

将其放入 https://pyfiddle.io/ 进行测试。

Answer 3

考虑我们没有面对给定集合

[0, 10^n]

中指定数字的概率。很明显我们可以推导为

0.9^n

，那么相反的概率是

P = 1 - 0.9^n

• 对于

  n = 1

  ：

  P = 0.1

  ;
• 对于

  n = 2

  ：

  P = 0.19

  ;
• 对于

  n = 3

  ：

  P = 0.271

  .

以下公式可以帮助定义这个集合中有多少个数字包含某个给定数字：

N = P * 10^n,

在你的情况下

n = 3

。 同样在您的情况下，我们应该减去集合

[0, 100]

中此类值的数量。这给了我们

N = N(3) - N(2) = 271 - 19 = 252.

没有循环，没有递归，纯数学。