التكوينات الضعيفة، ثوابت الحلقة وتتبع المخطط الانسيابي
مُقدَّم| 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 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. عند الخروج، يعني التساوي أنه مربع، ويعني التجاوز أنه ليس مربعاً. يجب الوصول إلى قيمة مطبوعة عبر مسار تنفيذ فعلي؛ نمط رقمي معقول وحده ليس مساراً.
- استخدم ثوابت الحلقة ومقياس التقدم لتبرير خوارزمية.
الأشياء المتطابقة والأشياء المتميزة تستخدم نماذج مختلفة. وجود صندوق فارغ واحد على الأقل ليس نفس وجود صندوق فارغ واحد بالضبط. في المخطط الانسيابي، حافظ على ترتيب التحديث وأعد ضبط المتغيرات فقط التي يعيد المسار المنفذ فعليًا ضبطها.
أي إجابة تتناسب مع هذه الحالة؟
حساب التوزيعات التي لا يمكن تمييزها مع قيود غير سالبة أو موجبة ⟦number⟧
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.