DouKaku?beta

Comment detail

自然数の分割 (Nested Flatten) 
例えば(5,3)の場合、基数変換で[5,0,0]から[0,0,5]までの配列を生成後、合計が5のものだけ出力しています。
1
2
3
4
5
6
7
8
def divNat(n,m)
  ((n + 1)**(m - 1) * n).downto(0) {|i|
    w = sprintf("%0#{m}d",i.to_s(n + 1)).split(//).map {|j|j.to_i}
    p w if w.inject(0){|r,j|r += j} == n
  }
end

divNat(5,3)

divNat(n,m)で、n>9の場合エラーになります。 考え直さねば。

分解後の数字が2桁の場合の処理を簡潔に書く方法を思いつかなかったのと、スピードアップのために方針変更。 1桁目はnから0、2桁目は(n-1桁目)から0、...としました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def divNat(n, m, acc = [])
  if m == 1
    p acc << n
    return
  end
  n.downto(0) {|i|
    w = acc[0..-1]
    divNat(n-i,m-1, w << i)
  }
end

divNat(5,3)

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]