弱成分分解、ループ不変量およびフローチャートトレース
導入済み| English | 意味 |
|---|---|
| loop invariant/luːp ɪnˈveərɪənt/ | ループ不変量 |
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | 弱組合分割 |
解答前に考えるべきこと
- 名付けられた箱に同一トークンを割り当てることと、異なるトークンに順序付きの受領者を選ぶことは異なる。計数モデルのわずかな変化が答えを大幅に変えることがある。
- 目標：非負または正の制約条件下での区別できない配分数を数える。
関係性を読む
- x₁+⋯+x_k=n の非負整数解の個数は C(n+k−1,k−1) であり、n≥0 かつ k≥1 である。n個の同一の星をk個の名前付き箱に分ける際、k−1本のバーで区切る。隣接するバーや端のバーはゼロの成分を許容する。箱は区別可能だが、物体は区別できない。もし区別可能なトークンを数えるのであれば、各トークンに独立に割り当てを行い、他の制約がある前に k^n となる。モデルは familiar な二項係数の形ではなく、対象物と受け手それぞれが何を表しているかによって決定されるべきである。
- 正しいリセット挙動を持って、文書順にフローチャートをトレースする。
How many ways put 11 identical tokens into 4 named boxes, allowing empty boxes?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
There are 11 stars and 3 bars. Choose the 3 bar positions among 14 positions: C(14,3)=364.
定義ルールを使う
- 正の配分 x_i≥1 については、z_i=x_i−1 と置くと、残りの総和は n−k となり、n≥k のとき C(n−1,k−1) となる。より一般的な下限 x_i≥a_i は、各 a_i を引くことで扱える。「少なくとも一つがゼロである」ことは「すべての成分が正である」ことの補集合であるため、非負の全配置数から C(n−1,k−1) を引く。完全に空の箱がちょうど2つあるような重なり合うケースは別の数え方をする必要がある。各空の箱のケースを独立に引くと、それらの共通部分の二重カウントが生じる。
- ループ不変量と進行 measure を用いてアルゴリズムを正当化する。
Starting from S=0, add successive odd numbers 1,3,5,… until S≥10. What is S at exit?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
The successive sums are 1,4,9,16. The first sum at least 10 is 16, so the test overshoots rather than declaring 10 square.
条件を確認する
- 実行された各文を順を追ってフローチャートをトレースし、表に変数を記録する。代入と数学的な等号テストを区別すること；代入の右辺では置換前の古い値を用いる。次に実行される分支とリセットされる変数を記録すること。新しい外側ループの候補は内側の和をリセットしても、候補自体はリセットしないことがある。プロセスが zero から S に 1,3,5,… を加算する場合、m回の加算後 S=m² となり、次の加算項は 2m+1 となる。
- ループ不変量と進行 measure を用いてアルゴリズムを正当化する。
11 個の同一のトークンを 4 個の名前付き箱に分配する。非負の配分数は C(14,3)=364、全正の配分数は C(10,3)=120 である。したがって、少なくとも1つの空箱を含む配分数は 244 である。N=10 の奇数和テストにおいて、S は 0,1,4,9,16 へ進み、超えて 10 を却下する。N=9 の場合、3回の加算後に S=9 で終了する。次の加算対象は 1,3,5,7,9 であり、和と次の加算対象の列は混同してはならない。
Of the 364 nonnegative allocations of 11 tokens to 4 boxes, 120 have every box positive. The count with at least one empty box is ____.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Subtract the all-positive complement once: 364−120=244.
タスク形式を適用する
- ループ不変式は各反復の前後で真となる。平方和不変式は initially m=0 で成立し、m²+(2m+1)=(m+1)² であるため維持される。不変式だけでは終端性を証明できない。整数 N≥0 が平方数かどうかを奇数の和 S≥N になるまで足してテストする場合、S は無制限に増加する；同様に m も増加し、N のような境界値に達しなければならない。出口では等号が平方数を示し、超過が非平方数を示す。印刷された値は実際の実行パス上で到達されなければならない；単なる妥当な数値パターンだけではトレースにはならない。
- ループ不変量と進行 measure を用いてアルゴリズムを正当化する。
同一物体と固有物体は異なるモデルを用いる。少なくとも一つの空箱は「ちょうど一つ」の物とは同じではない。フローチャートでは更新順序を保持し、実行されたパスが実際にリセットする変数のみをリセットする。
Which answer fits this case?
Count indistinguishable allocations with nonnegative or positive constraints
A preserved loop invariant alone proves that every execution of the loop terminates.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
An infinite loop can preserve a property forever. Termination also needs a progress argument or decreasing well-founded measure.
区別を保つ
- 弱い composition — 合計を非負整数部分への順次割り当て。
- ループ不変式 — ループの各反復の前後で維持される性質。
- 非負または正の制約付き区別不可能な割り当てを数える。
- 正しいリセット挙動を持って、文書順にフローチャートをトレースする。
- ループ不変量と進行 measure を用いてアルゴリズムを正当化する。
Match each term with its precise meaning in this lesson.
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
The order follows the stated process; check each stage before the next.