GRE Subject Test · GRE Mathematics · 주제 26
3:02
T.11 · 약한 구성, 루프 불변량 및 플로우차트 추종
이 단위는 음이 아닌 또는 양의 제약 조건 하에서 구별 불가능한 할당 개수를 세며, 문장의 순서에 따라 플로우 차트를 추적하여 올바른 초기화를 수행하고, 사용합니다…
영어 내레이션 · 영어 + 중국어 자막 burned-in
학부 GRE 준비. 검토된 ETS 범위 내의 로컬 목표; 이는 공식 시험이나 점수 예측기가 아닌 독자적 교육 과정입니다.
선행 지식: 이항 계수, 보수 및 할당 추적.
약분해(weak composition): 전체를 비음수 정수 부분으로 나눈 순서 있는 할당.
루프 불변량(loop invariant): 루프의 각 반복 전후에 유지되는 성질.
| English | 한국어 |
|---|---|
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | 약한 합성 분할 |
| loop invariant/luːp ɪnˈveərɪənt/ | 루프 불변량 |
The number of nonnegative integer solutions of x₁+⋯+x_k=n is C(n+k−1,k−1), for n≥0 and k≥1. Represent n identical stars separated into k named boxes by k−1 bars; adjacent bars and end bars allow zero entries. Boxes are distinguishable, objects are not. Counting distinct tokens would instead assign each token independently, giving k^n before other constraints. Decide the model from what the objects and recipients represent, not from a familiar-looking binomial coefficient.
For positive allocations x_i≥1, put z_i=x_i−1; the remaining total is n−k, giving C(n−1,k−1) when n≥k. More general lower bounds x_i≥a_i are handled by subtracting each a_i. At least one zero is the complement of every entry positive: subtract C(n−1,k−1) from the nonnegative total. Overlapping cases such as exactly two empty boxes need a different count; subtracting each empty-box case independently double-counts their intersections.
흐름도를 한 번에 실행되는 문장 단위로 추적하며 변수를 표에 기록한다. 할당과 수학적 등식 검사를 구분해야 하며, 할당의 우변은 치환되기 전의 이전 값을 사용한다. 다음에 실행될 분기가 무엇인지와 어떤 변수가 초기화되는지 기록한다. 새로운 외부 루프 후보는 내부 합을 초기화할 수 있으나 후보 자체는 초기화되지 않을 수 있다. S에 1,3,5,…를 0부터 추가하는 과정이 m회 수행된 후 S=m²이 되며, 다음 추가할 값은 2m+1이다.
루프 불변식은 각 반복 전후로 참이어야 합니다. 제곱합 불변식은 m=0에서 초기에 성립하며, m²+(2m+1)=(m+1)²이기 때문에 보존됩니다. 불변식만으로는 종료를 증명할 수 없습니다. 정수 N≥0가 제곱수인지 odd numbers를 더해서 S≥N이 될 때까지 테스트하려면, S는 무한히 커집니다; 즉, m은 N과 같은 상한값에 도달해야 합니다. 탈출 시 equality는 제곱수임을, overshoot는 비제곱수임을 의미합니다. 출력된 값은 실제 실행 경로에서 도달되어야 하며, 단순한 수학적 패턴만으로 트레이스가 될 수는 없습니다.
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이며, 합계 열과 다음에 더할 수 열은 혼동해서는 안 됩니다.
동일한 객체와 상이한 객체는 서로 다른 모델을 사용합니다. 적어도 하나의 빈 상자는 정확히 하나의 상자와 동일하지 않습니다. 흐름도에서는 업데이트 순서를 유지하고, 실행된 경로가 실제로 리셋하는 변수만 리셋하십시오.
$a+b+c=8$의 비음수 해를 $a\ge2$로 세십시오. 그중에서 $b,c\ge1$을 갖는 것은 몇 개인가요? 첫 번째 집합에서 b나 c 중 하나가 0 이상인 것은 몇 개인가요?
$u=a-2$을 대입하십시오. 그러면 $u+b+c=6$에는 $\binom82=28$개의 비음수 해가 있습니다. b, c를 양수로 요구하여 각각 1씩 빼면 총 네 개의 해가 세 가지 비음수 변수에서 생성되는데, 이는 $\binom62=15$로 세어집니다. 보수의 개수는 $28-15=13$입니다. 직접 b=0은 일곱 개, c=0은 일곱 개를 주며, 둘 다 0인 경우는 두 번 세어지므로 총 $7+7-1=13$개입니다.
N=15 및 N=16에 대해 이 알고리즘을 추적하라: S=0, k=1로 초기화합니다; S<N이면 S=S+k를 실행한 후 k=k+2를 실행하고, S=N인지 보고합니다. 불변량을 제시하고, 정수 $N\ge0$에 대한 종료를 정당화하시오.
m회 반복 후, $S=m^2$과 $k=2m+1$입니다. 트레이스 쌍 (S,k)은 $(0,1),(1,3),(4,5),(9,7),(16,9)$입니다. 따라서 15는 overshoot에 의해 거절되고 16는 수락됩니다. 불변식은 초기에 성립하며, $m^2+(2m+1)=(m+1)^2$이기 때문에 보존됩니다. 합은 무한히 커지므로 결국 N에 도달하거나 초과합니다; 예를 들어 N이 양수이면 m=N이면 충분합니다. N=0일 경우 루프는 생략되고 equality가 성립합니다. 불변식만으로는 종료를 확립할 수 없습니다.
즉시 체크 기능 exercises를 통해 단계별로 진행하세요.