我想知道这个算法是否有一个正式的名称,解决这个问题的优雅方法是什么:问题是——给定一个数组,比如说,[3, 6, 2]
,打印出所有以000
、100
、200
、300
开头的数字,然后下一个数字将“进位” over"并变为 010
,然后是 110
。它就像汽车的里程表,只是增加另一端的数字就可以了。 6
是第二个数字的最大数字。 2
是第三个数字的最大数字。所以程序应该打印出 362
作为最后一个数字。
我想出了下面的解决方案,但它看起来太乱了。所以我想知道是否有一个优雅的解决方案,这个问题和解决方案是否真的有一个正式的名称和一个已知的优雅解决方案来解决它?
递归实际上是可能的,但我认为如果递归返回所有数字的数组,如果输入数组中有 10 或 15 个数字,算法将无法处理它,因为生成的数组可以增长呈指数增长,它会变得非常大并占用大量内存。
# In Ruby
def print_all_numbers(arr_ranges)
arr = arr_ranges.map { 0 } # convert it to [0, 0, 0]
while (true)
incrementer_index = 0
puts arr.join
arr[incrementer_index] += 1
while arr[incrementer_index] > arr_ranges[incrementer_index]
arr[incrementer_index] = 0
incrementer_index += 1
return if incrementer_index >= arr.length
arr[incrementer_index] += 1
end
end
end
print_all_numbers([3, 6, 2])
最佳答案
在我看来,递归更简单。使函数采用数字最大值列表和包含到目前为止计算的数字的后缀。如果列表为空。后缀是要打印的数字。否则,从列表中剥离最后一个最大值并迭代,递归地调用自己。我不知道 ruby 。这是一个(经过测试的)Python 解决方案:
#!/usr/bin/python
def printNumbers(digitMaxima, suffix=''):
if len(digitMaxima) == 0:
print suffix
return
thisDigitMaximum = digitMaxima[-1]
remainingDigitMaxima = digitMaxima[:-1]
for d in range(0, thisDigitMaximum+1):
digitAsString = '%d' % d
printNumbers(remainingDigitMaxima, digitAsString + suffix)
printNumbers([3, 6, 2])
关于递增数组中每个位置的数字的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14846937/