1

このアルゴリズムの正式な名前があり、これを解決するためのエレガントな方法は何でしょうか。問題は、たとえば、配列が与えられた[3, 6, 2]場合、、、、、で始まるすべての数値を出力すると、000次の数値は「キャリーオーバー」して、になり、そして。車の走行距離計に似ていますが、代わりにもう一方の端の桁を大きくしても問題ありません。は2桁目の最大数です。は3桁目の最大数です。したがって、プログラムは最後の番号として出力する必要があります。10020030001011062362

私は以下の解決策を思いついたが、それはあまりにも厄介に見える。それで、私はエレガントな解決策があるかどうか疑問に思います、そしてこの問題と解決策は実際にそれを解決するための正式な名前と既知のエレガントな解決策を持っていますか？

再帰は実際には可能ですが、再帰がすべての数値の配列を返す場合、入力配列に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

特定の言語を念頭に置いていますか？Python には、このような問題をかなり単純にするrange()方法があります。はとrange(n)の間のすべての数値のリストを返すので、 を返します。簡単なグーグル検索で、Rubyを使用して同様の効果を作成できることがわかりました (ただし、これは少しハックのように思えます)。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

代わりに文字列連結を使用することもできましたが、 s とs を"{}{}".format()組み合わせているため、型エラーを回避したかったことに注意してくださいstrint

于 2013-02-13T08:09:16.373 に答える
0

混合基数 (または混合基数) の位置番号システムがあります。よく知られた例 - 時 - 分 - 秒。単純なサイクルですべての値を確認できます。基数の部分積を事前に計算し、整数除算と剰余演算を使用してすべての桁を分離します。

10 進数の例: 76543 の 4 桁目を抽出するには、(76543 div 1000) mod 10 を使用します。

動作する Delphi コード

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 に答える