הרכבות חלשות, אינווריאנטים של לולאות ועקיבת תרשים זרימה
הוצג| 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 פסי们; פסים סמוכים ופסי קצה מאפשרים ערכים אפס. הקופסאות נבדלות, האובייקטים לא. ספירת טוקנים נבדלים הייתה במקום זאת מ assigning כל טוקן באופן עצמאי, תוך מתן 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. ברגע היציאה, שוויון מוכיח ריבוע וחריגה מוכיחה שאינו ריבוע. ערך מודפץ חייב להיות מושג בדרך ביצוע בפועל; דפוס מספרי סביר לבדו אינו עקיבה.
- השתמש באינבריאנט מחזור ובמדד התקדמות כדי להצדיק אלגוריתם.
אובייקטים זהים ואובייקטים נבדלים משתמשים בדגמים שונים. לפחות קופסה ריקה אחת אינה זהה למדויק אחת. במפה זרימה, שמור על סדר העדכון והחל רק משתנים שהמסלול המבוצע בפועל מאפס.
איזו תשובה מתאימה למקרה זה?
ספור הקצאות בלתי מובחנות עם מגבלות אי-שליליות או חיוביות
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.