12494


［条件］  
1.配列 ary はソートされている。  
2.N は ary の最大値以上

上記条件をみたすような **一般の ary、N に対し、**  
連続 i (> 0) 個の和が N 以下の組み合わせの総数の求めたいと考えています。  
どのように求めるのが **効率的** でしょうか？

例を示しますので、「下記の非効率な箇所」もしくは「より効率的な求め方」  
を教えて頂けたら、幸いです。

[code]

    N = 10
    
    ary = (1..N).to_a # 最大値がN以下の（ソートされた）配列の例
    size = ary.size
    
    cnt = size
    # 連続i（> 1）個取り出す
    i = 2
    i_sum = ary[0] + ary[1]
    sum = i_sum
    while sum <= N
      j = 0
      while sum <= N
        cnt += 1
        j += 1
        break if j > size - i
        # 再計算せず前の結果を利用
        sum = sum - ary[j - 1] + ary[i - 1 + j]
      end
      i += 1
      # 再計算せず前の結果を利用
      i_sum += ary[i - 1]
      sum = i_sum
    end
    p cnt
    
[/code]


CC BY-SA 3.0
2015-07-19T09:58:38.400
12480
2015-07-20T05:30:35.807
2015-07-19T16:22:56.893
5363
5363
question
ruby アルゴリズム
連続 i 個の和が N 以下の組み合わせの総数の求め方について


先頭を固定する方が素直な気がする。

[code]

    N = 10
    
    ary = (1..N).to_a # 最大値がN以下の（ソートされた）配列の例
    size = ary.size
    
    cnt = 0
    # 先頭をary[i]に固定する
    (0..size - 1).each{|i|
      j = i
      sum = ary[j]
      while sum <= N
        cnt += 1
        j += 1
        break if j > size - 1
        sum += ary[j]
      end
    }
    p cnt
    
[/code]


CC BY-SA 3.0
2015-07-19T16:46:35.247
12488
2015-07-19T16:46:35.247
5363
12480
answer


効率的に処理するなら、ループの回数を減らすことと、ループ内での処理を減らすことが効果的です。

今回の問題の場合、次の性質があることが分かります。

  * aryの要素は、1つずつなら全て要求を満たす（ので、数える必要はない）
  * aryの要素で、N/2以上の値のうち、最小値以外は、他の値との組み合わせはない

上記を考慮すると、次のような手順で効率的に求められると思います。

  1. カウント値を、argの要素数として初期化
  2. aryの後ろから前に辿りながら、合計がN以下になる組み合わせを列挙

自分はruby使いではないので、C#で、C#らしくないサンプルメソッドを示します。

[code]

    int Count2(List<int> ary, int N) {
        var c = ary.Count; // 初期値（1つずつとった場合を総カウント）
        for (int iEnd = ary.Count - 1; iEnd > 0; iEnd--) { // iEnd==0は不要
            if (ary[iEnd - 1] >= N / 2) continue; // 探索ポイントの１つ手前がN/2以上なら、合計はNを越えるので探索不要
            int sum = ary[iEnd]; // 合計の初期値を与えることで計算を削減
            for (int iBegin = iEnd - 1; iBegin >= 0; iBegin--) {
                if (s + ary[iBegin] > N) break;
                s += ary[iBegin];
                c++;
            }
        }
        return c;
    }
    
[/code]

私が気づいていない節約可能なポイントもあると思いますが、こういう考え方で処理効率は高められると思います。


CC BY-SA 3.0
2015-07-20T05:30:35.807
12494
2015-07-20T05:30:35.807
10588
12480
answer