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

Question

我们有3位数字(100-999).有多少这样的数字至少有一个数字"2"存在？

如何制作算法呢？还是数学函数？

Answer 1

包含 - 排除原则

有多少个3位数字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