약한 합성, 루프 불변량 및 흐름도 추적
도입됨| 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개의 막대로 표현하며, 인접한 막대나 끝막대는 빈 상자(0개)를 허용한다. 상자는 식별 가능하지만 물체는 식별 불가능하다. 각 토큰을 독립적으로 배정한다면 개수는 k^n이 되며, 이는 다른 제약 조건을 고려하기 전의 경우이다. 물체와 수혜자가 무엇을 나타내는지에 따라 모델을 결정해야 하며, 보기에 친숙한 이항계수만으로 결정해서는 안 된다.
- 올바른 초기화 동작과 함께 스테이트먼트 순서에 따라 흐름도를 추적하십시오.
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)를 뺀다. 정확히 두 개의 빈 상자가 있는 것과 같은 겹치는 사례는 다른 개수를 요구하며, 각 빈 상자 사례를 독립적으로 빼면 교집합이 이중으로 세게 된다.
- 루프 불변식과 진전 측정값을 사용하여 알고리즘을 정당화하십시오.
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.
조건 확인
- 변수를 표에 기록하며 스테이트먼트 하나씩 흐름도를 추적하십시오. 할당을 수학 등호 테스트와 구분하십시오. 할당의 우변은 교체되기 전의 이전 값을 사용합니다. 다음에 실행될 가지와 어떤 변수가 초기화되는지 기록하십시오. 새로운 외부 루프 후보가 내부 합계를 초기화할 수 있으나 후보 자체는 초기화되지 않을 수 있습니다. S에 1,3,5,…을 0부터 더하는 프로세스에서, m번 더한 후 S=m²이며, 다음 더하는 수는 2m+1입니다.
- 루프 불변식과 진전 측정값을 사용하여 알고리즘을 정당화하십시오.
11개의 동일한 토큰을 4개의 이름이 붙은 상자에 나눕니다. 비음 할당의 개수는 C(14,3)=364이고, 모든 값이 양수인 할당의 개수는 C(10,3)=120입니다. 따라서 244개의 할당은 최소 하나의 빈 상자를 포함합니다. N=10인 기수 합 테스트에서 S는 0,1,4,9,16까지 진행하지만, 초과하여 10를 거절합니다. N=9인 경우 세 번의 덧셈 후 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.
문제 형식 적용하기
- 루프 불변식은 각 반복 전후로 참이어야 합니다. 제곱합 불변식은 m=0에서 초기에 성립하며, m²+(2m+1)=(m+1)²이므로 유지됩니다. 불변식만으로는 종료를 증명할 수 없습니다. 정수 N≥0가 제곱수인지 확인하기 위해 홀수를 더하여 S≥N이 될 때까지 반복하면, S는 무한히 커집니다; 이는 동등하게 m이 증가하여 N과 같은 상한값에 도달해야 함을 의미합니다. 종료 시 등호는 제곱수임을, 오버슈트는 비제곱수임을 나타냅니다. 출력된 값은 실제 실행 경로상에서 도달되어야 하며, 단순한 plausible numerical pattern만으로 trace를 구성할 수 없습니다.
- 루프 불변식과 진전 측정값을 사용하여 알고리즘을 정당화하십시오.
동일한 객체와 상이한 객체는 서로 다른 모델을 사용합니다. 적어도 하나의 빈 상자는 정확히 하나의 상자와 동일하지 않습니다. 흐름도에서는 업데이트 순서를 유지하고, 실행된 경로가 실제로 리셋하는 변수만 리셋하십시오.
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.
구분을 유지하기
- 약한 분할(weak composition) — 전체를 음이 아닌 정수 부분으로 순서 있게 할당하는 것.
- 루프 불변식(loop invariant) — 루프의 각 반복 전후로 유지되는 속성.
- 음이 아닌 또는 양의 제약 조건이 있는 구별 불가능한 할당의 개수를 세십시오.
- 올바른 초기화 동작과 함께 스테이트먼트 순서에 따라 흐름도를 추적하십시오.
- 루프 불변식과 진전 측정값을 사용하여 알고리즘을 정당화하십시오.
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.