1

我想知道这个算法是否有正式名称，以及解决这个问题的优雅方法是什么：问题是——给定一个数组，比如说，打印出所有以, , ,[3, 6, 2]开头的数字，然后下一个数字将“结转”并成为，然后。它就像汽车的里程表，只是增加另一端的数字就可以了。是第二个数字的最大数字。是第三个数字的最大数字。所以程序应该打印出最后一个数字。00010020030001011062362

我想出了下面的解决方案，但它看起来太乱了。所以我想知道是否有一个优雅的解决方案，这个问题和解决方案实际上是否有一个正式的名称和一个已知的优雅解决方案来解决它？

递归实际上是可能的，但我认为如果递归返回一个包含所有数字的数组，如果输入数组中有 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])
4

3 回答 3

1

在我看来，递归更简单。使函数采用数字最大值列表和包含到目前为止计算的数字的后缀。如果列表为空。后缀是要打印的数字。否则，从列表中剥离最后一个最大值并迭代，递归调用自己。我不知道鲁比。这是一个（经过测试的）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])
于 2013-02-13T05:46:08.137 回答
0

有混合基（或混合基数）位置数字系统。众所周知的例子 - 小时-分钟-秒。您可以通过简单的循环遍历所有值。预先计算基数的部分乘积，并使用整数除法和模运算来隔离每个数字。

十进制示例：要提取 76543 的第四位，我们使用 (76543 div 1000) mod 10。

工作德尔福代码

var
  A, Products: TDynIntegerArray;
  Len, i, j: Integer;
  s: string;
begin
  A := TDynIntegerArray.Create(3, 4, 2);
  Len := Length(A);
  SetLength(Products, Len);
  Products[Len - 1] := 1;
  for i := Len - 2 downto 0  do
    Products[i] := Products[i + 1] * (A[i + 1] + 1); //partial products
  for i := 0 to Products[0] * (A[0] + 1) - 1 do begin // overall count of "numbers"
    s := '';
    for j := 0 to Len - 1 do
      s := s + IntToStr((i div Products[j]) mod (A[j] + 1));
    Memo1.Lines.Add(s); // output string
  end;

Output: 000 001 002 010 011 012 020 021 022 030 031 032 040 041 042 100 101 102 110 111 112 120 121 122 130 131 132 140 141 142 200 201 202 210 211 212 220 221 222 230 231 232 240 241 242 300 301 302 310 311 312 320 321 322 330 331 332 340 341 342

于 2013-02-13T06:57:55.977 回答
0

您有特定的语言吗？Python 有一种range()方法可以使此类问题变得相当简单。返回和range(n)之间的所有数字的列表，因此返回。一些简单的谷歌搜索告诉我，可以在 Ruby中使用类似的效果创建（尽管这看起来有点 hackish）。0n-1range(3)[0, 1, 2](0..n-1)

使用range()，然后我将采用动态编程方法来存储我看到的数字的所有可能前缀（从没有前缀开始）。我将遍历每个最大数字，计算所有可能的有效数字，然后将它们与有效前缀组合，从而生成一个新的有效前缀列表，该列表比前一个列表长 1 位。一旦我的“前缀”与所需的数字一样长，我就完成了。

例如，给定[1, 2, 3]，首先我生成[0, 1]（最大为 1 的所有有效数字）。接下来我生成[0, 1, 2]（所有有效数字最多为 2），然后将它们与我的可能前缀列表 ( [0, 1]) 结合以生成[00, 01, 02, 10, 11, 12]. 现在这是我的新前缀列表，我会重复，直到我查看了所有最大值。所有这些都不需要递归。我也觉得这个解决方案在概念上和查看代码上都更容易理解。

这是一个 Python 实现：

def printNumbers(maxNums):
    possibleNums = [""] #start with empty prefix

    for digit in maxNums: #start with the first digit then work back
        possibleSuffixes = range(digit + 1) #+1 to allow us to capture the number itself

        newNums = [] #this will hold the new list of possible numbers
        for prefix in possibleNums: #looking at each prefix
            for suffix in possibleSuffixes: #looking at each suffix
                newNums.append("{}{}".format(prefix, suffix)) #join them
        possibleNums = newNums

    for num in possibleNums: #for each number
        print num

请注意，"{}{}".format()我可以使用字符串连接而不是使用字符串连接，但是由于我将strs 和ints 组合在一起，因此我想避免任何类型错误

于 2013-02-13T08:09:16.373 回答