Слабые композиции, инварианты цикла и трассировка блок-схем
Введено| 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 до учета других ограничений. Определяйте модель по тому, чем являются объекты и получатели, а не по знакомому виду биномиального коэффициента.
- Пройдите по блок-схеме в порядке утверждений с правильным поведением сброса.
How many ways put 11 identical tokens into 4 named boxes, allowing empty boxes?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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, что дает C(n−1,k−1) при n≥k. Более общие нижние границы 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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Проверьте условия
- Пройдите по блок-схеме по одному выполненному оператору за раз, записывая переменные в таблице. Различайте присваивание и математическую проверку равенства; правая часть присваивания использует старое значение до замены. Записывайте, какой ветвью выполняется следующий шаг и какие переменные сбрасываются. Новый кандидат внешнего цикла может обнулить внутреннюю сумму без сброса самого кандидата. Для процесса, добавляющего 1,3,5,… к S начиная с нуля, после m сложений S=m², а следующее слагаемое равно 2m+1.
- Используйте инвариант цикла и меру прогресса для обоснования алгоритма.
Распределите 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; столбцы суммы и следующего слагаемого нельзя путать.
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 ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Subtract the all-positive complement once: 364−120=244.
Применяйте формат задания
- Инвариант цикла верен до и после каждой итерации. Инвариант суммы квадратов верен изначально при m=0 и сохраняется, так как m²+(2m+1)=(m+1)². Сам по себе инвариант не доказывает завершение. Чтобы проверить, является ли целое число N≥0 квадратом, прибавляя нечетные числа до тех пор, пока S≥N, S растет неограниченно; эквивалентно, m увеличивается и должно достичь предела, такого как N. При выходе равенство означает квадрат, а превышение порога — неквадрат. Распечатанное значение должно быть достигнуто на фактическом пути выполнения; правдоподобная числовая закономерность сама по себе не является трассировкой.
- Используйте инвариант цикла и меру прогресса для обоснования алгоритма.
Одинаковые объекты и различные объекты используют разные модели. Хотя бы один пустой ящик — это не то же самое, что ровно один. В блок-схеме сохраняйте порядок обновления и сбрасывайте только те переменные, которые фактически сбрасываются на выполняемом пути.
Какой ответ подходит к данному случаю?
Подсчитать неразличимые распределения при неотрицательных или строгих положительных ограничениях
A preserved loop invariant alone proves that every execution of the loop terminates.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An infinite loop can preserve a property forever. Termination also needs a progress argument or decreasing well-founded measure.
Сохраняйте различия
- слабая композиция — Упорядоченное распределение общей величины на неотрицательные целочисленные части.
- инвариант цикла — Свойство, сохраняющееся до и после каждой итерации цикла.
- Подсчитайте неразличимые распределения с ограничениями на неотрицательность или строгую положительность.
- Пройдите по блок-схеме в порядке утверждений с правильным поведением сброса.
- Используйте инвариант цикла и меру прогресса для обоснования алгоритма.
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.