1

各正の整数 n には 2^(n−1) 個の異なる構成があります。リストにある特定の番号のみを持つ構成の番号が必要な場合：

例えば4の合成は

4
3 1
1 3
2 2
2 1 1
1 2 1
1 1 2
1 1 1 1

しかし、1と2しかない4の構成の数が必要な場合、異なる構成のNUMBERをどのように計算できますか?

2 2
2 1 1
1 2 1
1 1 2
1 1 1 1

編集: ここでは数字を計算する Haskell コードですが、数字 70 の暗記を追加しても時間がかかりすぎると思います

main :: IO ()
main = do
     putStrLn "Enter the integer number"
     num' <- getLine
     let num = read num' :: Int
     putStr ""
     let result= composition num
     let len=length result
     print len
      --print result

composition 0 = [[]]
composition n = [x:rest | x <- [1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000],x<=n ,rest <- composition (n-x)]
4

1 に答える 1

1

動的計画法を使用して、必要な構成の数を計算できます。あなたの例の再帰関係の例:

 P(4, [1,2]) = P(3, [1,2])  + P(2, [1,2])

これP(N, [list])は、リストから N を作成するバリアントの数です。

数式を一般化して、トップダウンのメモ化またはボトムアップのテーブル フィル DP を使用して、結果をすばやく見つけるようにしてください。

Delphi の例:

var
  A: TArray<Integer>;
  Mem: TArray<Int64>;
  N, i: Integer;

  function Calc(N: Integer): Int64;
  var
    i: Integer;
  begin
    if Mem[N] >= 0 then
      Exit(Mem[N]);

    i := 0;
    Result := 0;
    while A[i] <= N do begin
      Result := Result + Calc(N - A[i]);
      Inc(i);
    end;
    Mem[N] := Result;
  end;

begin
  //should be sorted
  //-1 - sentinel value to stop
  A := TArray<Integer>.Create(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
    70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, -1);
  for N := 10 to 64 do begin
    SetLength(Mem, N + 1);
    for i := 1 to N do
      Mem[i] := -1; //not initialized yet
    Mem[0] := 1;
    Memo1.Lines.Add(Format('%d   %d', [N, Calc(N)]));
  end;
于 2016-08-22T15:57:02.260 に答える