T.11 · Слабые композиции, инварианты цикла и трассировка блок-схем

Подготовка к GRE для бакалавров. Локальные цели в рамках пересмотренного диапазона ETS; это оригинальное обучение, а не официальный тест или предиктор баллов.

Предварительные требования: биномиальные коэффициенты, дополнения и прослеживание присваиваний.

• Подсчёт неразличимых распределений при неотрицательных или положительных ограничениях
• Проследить блок-схему в порядке операторов с правильным поведением сброса
• Использовать инвариант цикла и меру прогресса для обоснования алгоритма

слабая композиция: упорядоченное распределение суммы на целые неотрицательные части.

инвариант цикла: свойство, сохраняемое до и после каждой итерации цикла.

Количество неотрицательных целых решений уравнения x₁+⋯+x_k=n равно C(n+k−1,k−1) при n≥0 и k≥1. Представьте n одинаковых звёзд, разделённых на k различных ящиков, с помощью k−1 перегородок; соседние перегородки и перегородки у краёв допускают нулевые значения. Ящики различимы, объекты — нет. Если бы подсчитывались различные токены, то каждому из них присваивалось бы значение независимо, что дало бы k^n до учёта других ограничений. Выбор модели зависит от того, чем являются объекты и получатели, а не от знакомства с биномиальным коэффициентом.

Для положительных распределений xᵢ≥1 положите zᵢ=xᵢ−1; оставшаяся сумма равна n−k, что даёт C(n−1,k−1) при n≥k. Более общие нижние границы xᵢ≥aᵢ обрабатываются вычитанием каждого aᵢ. Наличие хотя бы одного нуля является дополнением условия о положительности всех элементов: вычтите из общего числа неотрицательных решений C(n−1,k−1). Пересекающиеся случаи, такие как ровно две пустые коробки, требуют иного подсчёта; независимое вычитание случаев с пустыми коробками приводит к двойному подсчёту их пересечений.

Проследите блок-схему, выполняя операторы по одному, записывая переменные в таблицу. Различайте присваивание и математическую проверку равенства; правая часть присваивания использует старое значение до замены. Записывайте, какой веткой выполняется следующий шаг и какие переменные сбрасываются. Новый кандидат внешнего цикла может обнулить внутреннюю сумму, не обнуляя самого кандидата. Для процесса, добавляющего к S значения от 0 до ⟨1,3,5⟩, после m операций S=m², а следующее слагаемое равно 2m+1.

Инвариант цикла верен до и после каждой итерации. Инвариант квадратов сумм выполняется изначально при m=0 и сохраняется, так как m²+(2m+1)=(m+1)². Одного инварианта недостаточно для доказательства завершения. Чтобы проверить, является ли целое число N≥0 квадратом путём сложения нечётных чисел, пока S≥N, S возрастает неограниченно; эквивалентно, m увеличивается и должно достичь верхней границы, например N. В момент выхода равенство означает квадрат, а превышение — неквадрат. Распечатанное значение должно быть достигнуто на фактическом пути выполнения; одна лишь правдоподобная числовая закономерность не является трассировкой.

Распределите 11 одинаковых токенов среди 4 именованных ящиков. Число неотрицательных распределений равно C(14,3)=364; число строго положительных распределений равно C(10,3)=120. Следовательно, 244 распределений имеют хотя бы один пустой ящик. Для теста нечетной суммы при N=10, S progresses 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 равный нулю?

Разобранное решение

Положите $u=a-2$. Тогда $u+b+c=6$ имеет $\binom82=28$ неотрицательных решений. Требование положительности b и c и вычитание единицы из каждого дают общую сумму четыре в трёх неотрицательных переменных, подсчитываемую по формуле $\binom62=15$. Число дополнений равно $28-15=13$. Прямой подсчёт при b=0 даёт семь, при c=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 отвергается из-за превышения, а 16 принимается. Инвариант выполняется изначально и сохраняется, поскольку $m^2+(2m+1)=(m+1)^2$. Сумма возрастает неограниченно, поэтому со временем она достигнет или превысит N; например, при m=N это достаточно для положительного N. Для N=0 цикл пропускается, и выполняется равенство. Один лишь инвариант не устанавливает завершение.