プログラマ専用SNS ミクプラ

こんばんは。
尺取り法について質問があり、投稿させていただきました。

尺取り法は、累積和と似た考え方で、配列内を一つ前を動かし、一つ後ろを前に動かしと繰り返していくことまではわかりました。
今回、苦戦している問題は、配列がない状態での尺取り法の使い方です。
ネットや本で調べたところ、あるコードがもう少しでわかりそうなところまで来ています。
これが、そのコードです。

コード:

#include<iostream>
using namespace std;

int main(){
  int n;
  while(1){
    cin >> n;
    if(n == 0)break;
    int s,t,cnt,sum;
    s = 1;
    t = 2;
    sum = 3;
    cnt = 0;
    while(1){

      if(s > n)break;
      else if(sum < n || s == t)sum += ++t;
      else if(sum > n)sum -= s++;
      else if(sum == n){cnt++;sum -= s++;}
    }
    cout << cnt << endl;
  }
  return 0;
}

（http://winfield95.hatenablog.com/entry/ ... 1319890701　　９５さんのコードを引用しました）
質問は、どうしてs,t,sumはそれぞれ１，２，３という数値が代入されているのでしょうか？
ここがわかれば、かなり道は開けてくると思います。皆様のお力をお借りしてもよろしいでしょうか。
よろしくお願いします。
以下は、このコードの問題です。
問題：http://judge.u-aizu.ac.jp/onlinejudge/d ... sp?id=2197

問題文です。

あなたは数か月に渡る受験戦争を勝ち抜き，晴れてICPC大学に入学することができた．入学手続きの日，大学のキャンパス内では熱狂的なサークルの勧誘活動が行われており，あなたは大量のパンフレットを受け取って帰ってきた．部屋に戻ってきたあなたは受け取ったパンフレットの中から気になる一枚を見つけた．そのパンフレットは大学の広報部から渡されたものだった．

パンフレットには以下のような問題が記されていた．

和が N となるような，連続する2つ以上の正の整数の組み合わせは，何組存在するでしょうか？例えば， 9 は 2+3+4 と 4+5 の 2通りの組み合わせがあります．
この問題の答えが気になったあなたは，プログラムを書いてその答えを調べることにした．したがって，あなたの仕事は，入力として与えられる正の整数 N に対して，問題の答えを出力するプログラムを書くことである．

s : 最小の正の整数
t : sの次の正の整数(2つ以上の正の整数の組み合わせを探したいので)
sum : s以上t以下の正の整数の和

だと思います。

きょうさんが書きました:質問は、どうしてs,t,sumはそれぞれ１，２，３という数値が代入されているのでしょうか？

入力が 9 のとき、2+3+4 と 4+5 をどうやって求めるかを素直に考えるとわかります。

まず、1 で始まって連続するものを試します。
1 + 2 = 3。だめだ。
1 + 2 + 3 = 6。だめだ。
1 + 2 + 3 + 4 = 10。だめだ。9 を超えた。
1から始まるのは無理。
次は 2 で始まるものを試してみよう。先頭の 1 を引いて
2 + 3 + 4 = 9。あたり。
次は 3 で始まるものを試してみよう。先頭の 2 を引いて
3 + 4 = 7。だめだ。
3 + 4 + 5 = 12。だめだ。9 を超えた。
次は 4 で始まるものを試してみよう。先頭の 3 を引いて
4 + 5 = 9。あたり。
次は 5 で始まるものを試してみよう。先頭の 4 を引いて
5 = 5。s と t が等しいのは足し算していないからだめだ。
5 + 6 = 11。だめだ。9 を超えた。
次は 6 で始まるものを試してみよう。先頭の 5 を引いて
6 = 6。s と t が等しいのは足し算していないからだめだ。
6 + 7 = 13。だめだ。9 を超えた。
こうして、先頭が 9 を超えるまで繰り返して終了。

このアルゴリズムは 1 + 2 = 3 から始めます。

きょうさんが書きました:尺取り法は、累積和と似た考え方で、配列内を一つ前を動かし、一つ後ろを前に動かしと繰り返していくことまではわかりました。
今回、苦戦している問題は、配列がない状態での尺取り法の使い方です。

今回の問題では、正の整数が順番に格納されている仮想的な配列に対して操作を行う、と考えられます。

みけCATさん

なるほど！シュミレーションをすることで、わかりました。仮想的な配列を使っているわけですね！

かずまさん

サンプルでシュミレーションをすることで、理解が得られますね。

お二人様、本当にありがとうございます。しっかりと理解することができました。仮想的な配列を使用し、シュミレーションを行うということを忘れずに、今後もやっていきます。

プログラマ専用SNS ミクプラ

尺取り法について質問です。

尺取り法について質問です。

Re: 尺取り法について質問です。

Re: 尺取り法について質問です。

Re: 尺取り法について質問です。

Re: 尺取り法について質問です。