假设您的输入n有k位数字,而开头的数字是d.
然后,我们考虑所有具有最多k-1位数的数字以及一些(可能是全部)具有恰好k位数的数字.
对于最多具有k-1位数字的数字,我们可以允许前置零,然后将数字视为恰好具有k位数字,其中一些数字具有前置零.由于有10个数字,因此其中有10个q(k-1),并且由于除了"9"之外还有9个数字,因此其中有9个q(k-1)没有9,因此有10个q(k-1)- 9个q(k-1)确实有9.
现在我们需要考虑恰好具有k位数字的数字.假设开头的数字是d.那么,前置数字在1 d-1之间的所有k位数字的集合也有10个^(k-1)- 9^(k-1)成员,至少有一个9.
如果d是9,那么剩下的就很容易了,只需计算所有k位数字,其前面的9最多为n.
如果d小于9,则在n上循环,删除开头数字.
例如,n = 234,因此d = 2,k = 3
2-数字:102 - 92 = 100 - 81 = 19.这些是:9、19、29、39、49、59、69、79、89、90、91、92、93、94、95、96、97、98、99.
3-前置数字在11之间的数字:其中有1个,这意味着另外19个(上面列表中的每个elt,加上100).
回归:对于n = 34重复上面的操作(我们删除了前面的2).
我不知道c#,所以这是Ruby代码,您可以将其视为伪代码.
def f(n)
# n = input
# k = num digits
# d = leading digit
# confirm input >= 0 & answer basic 1-digit questions directly
return -1 if n < 0 # invalid input
return 0 if n < 9
return 1 if n == 9
# calculate k (num digits) and d (leading digit)
k = Math.log10(n).to_i + 1
d = n / 10 ** (k-1)
# Start with all k-1-digit numbers
ans = 10 ** (k-1) - 9 ** (k-1)
# Next, multiply this by d to account for leading digits 0 through d-1
ans *= d
# Next, handle the leading digit differently depending on whether or not it's a 9.
if d == 9
ans += n - (9 * 10 ** (k-1) - 1)
else
ans += f(n - d * (10 ** (k-1)))
end
return ans
end
...这是n最多100的输出.
1.upto(99) do |n|
puts "#{n}, #{f(n)}"
end
1, 0
2, 0
3, 0
4, 0
5, 0
6, 0
7, 0
8, 0
9, 1
10, 1
11, 1
12, 1
13, 1
14, 1
15, 1
16, 1
17, 1
18, 1
19, 2
20, 2
21, 2
22, 2
23, 2
24, 2
25, 2
26, 2
27, 2
28, 2
29, 3
30, 3
31, 3
32, 3
33, 3
34, 3
35, 3
36, 3
37, 3
38, 3
39, 4
40, 4
41, 4
42, 4
43, 4
44, 4
45, 4
46, 4
47, 4
48, 4
49, 5
50, 5
51, 5
52, 5
53, 5
54, 5
55, 5
56, 5
57, 5
58, 5
59, 6
60, 6
61, 6
62, 6
63, 6
64, 6
65, 6
66, 6
67, 6
68, 6
69, 7
70, 7
71, 7
72, 7
73, 7
74, 7
75, 7
76, 7
77, 7
78, 7
79, 8
80, 8
81, 8
82, 8
83, 8
84, 8
85, 8
86, 8
87, 8
88, 8
89, 9
90, 10
91, 11
92, 12
93, 13
94, 14
95, 15
96, 16
97, 17
98, 18
99, 19
..最后,OP的例子:
> f(3950)
=> 1035