1。问题介绍
我想找出具有一定位数的单调递增数字的个数。 k
的单调递增数字数字可以写成
n = a_0 a_1 ... a_k-1
哪里a_i <= a_(i+1)
对于所有 i in range(0, k)
.一个更具体的例子是 123
或 12234489
.我正在尝试创建这样的函数
increasing(2) = 45
increasing(3) = 165
increasing(4) = 495
increasing(5) = 1287
increasing(6) = 3003
因为有45个两位数递增的数,11, 12, ..., 22, 23, ..., 88, 89, 99
.等等。
我认为这是使用递归的好机会。我试图编写一个代码来执行此操作,但是结果有问题。我的伪代码是这样的
2。伪代码
- 以数字
[1, 2, ..., 9]
开头遍历这些数字。增加length
一个。 - 遍历数字
[i, ..., 9]
其中last_digit
是上一次递归的数字。 - 如果
length = number of digits wanted
加一到total
和return
否则重复上述步骤。
3。代码
global total
total = 0
nums = range(1, 10)
def num_increasing(digits, last_digit = 1, length = 0):
global total
# If the length of the number is equal to the number of digits return
if digits == length:
total += 1
return
possible_digits = nums[last_digit-1::]
for i in possible_digits:
last_digit = i
num_increasing(digits, last_digit, length + 1)
return total
if __name__ == '__main__':
num_increasing(6)
print total
4。问题:
我的伪代码是否可以正确找到这些数字?如何正确使用递归来解决这个问题?
我不会要求找出我的代码中的错误,但是非常有必要提供一些指针或有效的代码示例。
最佳答案
这可以用封闭形式计算。
我们有 8 个单位的预算,我们可以将其分配给每个数字或分配给“剩余”。分配了 n
个预算单位的数字比它前面的数字大 n
;对于第一个数字,如果我们在那里分配 n
个预算单位,它的值为 n+1
。剩余预算无济于事。
预算分配与单调递增的数字是一一对应的,因为每个预算分配产生一个单调递增的数字,每个单调递增的数字都有对应的预算分配。因此,长度为k
的单调递增数的个数就是将8个单位的预算分配给k+1
个桶的方法数,每个数字一个桶,一个桶剩饭剩菜。
由经典stars and bars结果,这是 (8 + k) 选择 8
,或 (8+k)!/(8!k!)
:
def monotone_number_count(k):
total = 1
for i in xrange(k+1, k+9):
total *= i
for i in xrange(1, 9):
total //= i
return total
对于单调递减的数字,可以应用相同的想法。这次我们有 9 个预算单位,因为我们的数字可以从 9 下降到 0,而不是从 1 开始上升到 9。一个分配了 n
预算单位的数字是 n
低于前一位;对于第一个数字,n
个预算单位赋予它值 9-n
。需要注意的是,这会将 0000
计为一个四位数,对于 k
的其他值也类似,因此我们必须显式地取消计数,使结果 ((9 + k) 选择 9) - 1
:
def monotonely_decreasing_number_count(k):
total = 1
for i in xrange(k+1, k+10):
total *= i
for i in xrange(1, 10):
total //= i
total -= 1
return total
关于python - 单调递增数的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37031296/