包含给定数字的数字是多少？(How many numbers are there that include a given digit?)

包含给定数字的数字是多少？(How many numbers are there that include a given digit?)

我们有3位数字（100-999）。 有多少这样的数字至少有一个数字“2”存在？

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

Let's have 3 digit number (100-999). How many such numbers with at least one digit "2" exist?

How to make algorithm for that? Or math function?

最满意答案

包含 - 排除原则

有多少个3位数字作为第一个数字（ 2xx ）有2 ？ 那是对的 - 100 。 并作为第二个数字（ x2x ）？ 100 ！ 而作为第三个（ xx2 ） - 相同的数字。 好的，现在我们有300号码，但我们忘记了22x表格中的数字，我们将它们计算两次。 现在我们需要减去22x ， 2x2和x22数量。 现在我们有270个，但我们忘记了222 ，我们添加了三次，减去了三次，我们需要再次添加它： 271 。 该解释是包含 - 排除原则的示例。

但这不是结束，我们需要减去所有0xx数字，其中2为数字。 类似方法： 271 - 10 - 10 + 1 = 252 。

动态编程

好吧，如果您不喜欢以前的方法，还有另一种方法。 让我们计算函数F(i, has2) ，其中i - 是数字的数字长度， has2布尔值，如果数字包含2 ，则等于false ，否则等于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

Inclusion-exclusion principle

How many 3-digit numbers have 2 as the first digit (2xx)? That's right - 100. And as the second digit (x2x)? 100! And as the third (xx2) - the same number. Ok, now we have 300 numbers, but we forgot about numbers in the form 22x, we count them twice. Now we need to subtract the amount of 22x, 2x2 and x22 numbers. Now we have 270 of them, but we forgot about number 222, we added it three times, and subtracted three times, we need to add it again: 271. This explanation is an example of inclusion-exclusion principle.

But that's not the end, we need to subtract all 0xx numbers having 2 as a digit. Similar approach: 271 - 10 - 10 + 1 = 252.

Dynamic programming

Ok, if you don't like the previous method, there is another one. Let's count the function F(i, has2), where i - is the digit length of the number, has2 boolean value that is equal to true if digits contain 2, otherwise it equals to false. The recurrence relation is the following:

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

The answer is F(3, true).

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