אלגוריתמים
הוצג| English | משמעות |
|---|---|
| algorithm/ˈælɡərɪθəm/ | אלגוריתם |
| flowchart/ˈfləʊtʃɑːt/ | תרשים זרימה |
| pseudocode/ˈsuːdəʊkəʊd/ | 伪代码 |
| tracing/ˈtreɪsɪŋ/ | עקיבה |
| binary search/ˈbaɪnəri sɜːtʃ/ | חיפוש בינארי |
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
| efficiency/ɪˈfɪʃənsi/ | יעילות |
ציין אילו קלטים הפרוצדורה חייבת לעבד
- אלגוריתם מתאר שלבים חד-משמעים למשימה. פרוצדורה הפותרת משימה סופית מצוינת חייבת להסתיים ולהחזיר תוצאה נכונה לכל קלט מותר.
- מעקב מוצלח על קלט אחד מראה את המקרה ההוא, אך אינו הוכחה לכל הקלטים. מקרי גבול וקלטים ריקים עלולים לחשוף שגיאות שמדגם טיפוסי לא מגלה.
איזה מהתכונות הבאות חיוניות כדי שהסדרת צעדים תהיה אלגוריתם? בחר את כל האפשרויות הרלוונטיות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
שלב פתרון למשימה סופית המצוינת דורש צעדים חד-משמעיים, תוצאות נכונות וסיום על כניסות מותרות. פסאודוקוד ומפות זרימה הם ייצוגים, ואינם תנאי לשימוש בשפת תכנות ספציפית.
ייצג בחירות ועדכונים בצורה ברורה
- תרשים זרימה משתמש במערכת החלטה (יהלום), תהליך (מלבן), קלט/פלט (מקבילית) ותחילת/סיום (טרמינל), המחוברים על ידי חצים זרימה ממוסמים.
- פסאודוקוד מתאר את השלבים ללא הצורך בשפת יישום ספציפית. הגדר משמעות האצלת משתנים, נקודת התחלת אינדקס, גבולי מחזור ותנאי ענפים לפני ביצוע מעקב.
התאם כל צורת במבנה זרימה למשמעות שלה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
השתמש בריבועי תהליך, יהלום החלטה וקצוות התחלה/עצירה כפי שנתון; קלט/פלט מוצג לרוב על ידי מקבילית. תווץ ענפי החלטה וכיווני זרימה.
רשום את הערכים בפועל של המשתנים
- מעקב עוקב אחרי העדכונים הנזכרים בסדר. משתן זמני עשוי לשמר ערך שימוחלץ אחרת על ידי חפיפה.
- הצג low, high, middle וערך ההשוואה בחיפוש בינארי; הצג כל משתנה שהשתנה במחזור אריתמטי. הערך מה הפרוצדורה עושה, לא רק את מטרתה המתוכננת.
מסורת חיפוש בינארי מצוינת. השתמש בגבולים כלולים עם אינדקס מתחיל מ-0 ובחציית תחתונה של הממוצע שלהם עבור האמצע. בחיפוש אחר 7 ב-[1,3,5,7,9,11] מתבצעת השוואה באינדקס 2/ערך 5, באינדקס 4/ערך 9, ולאחר מכן באינדקס 3/ערך 7. מספר ההשוואות הוא שלושה לפי מסורת זו.
נגד חיפוש בינארי
הכפלוג של הגודל טוב יותר מבדיקה אחד-אחד, והפרש בין השיטות גדל ככל שהרשימה ארוכה יותר.
בשימוש בגבולות תכלולית אפס-מבוססת וב-floor((low+high)/2), כמה השוואות משתמש חיפוש בינארי כדי למצוא 7 ב-[1,3,5,7,9,11]?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
המדדסים המרכזיים הם 2, 4, ולאחר מכן 3, עם הערכים 5, 9 ו-7. שלושה השוואות לפי הקונבנציה הנ"ל.
השוו עבודה תחת ההנחות שלה
- חיפוש ליניארי יכול להפסיק מוקדם אך עשוי לבדוק את כל n הפריטים. חיפוש בינארי מחלק חזרה ושוב טווח חיפוש ממוין וזקוק לעדכוני גבול עקביים.
- יעילות מתארת כיצד העבודה הנדרשת קנה מידה עם גודל הקלט תחת מודל מוגדר. מיון ראשוני יש לו עלות משלו; קלט לא ממוין לא יכול לסמוך על הבטחת הסדר של החיפוש הבינארי.
ברשימה מסודרת מראש של מיליון פריטים, לכמה השוואות ערך מרכזי לערך מקסימום יכול להגיע החיפוש הבינארי במקרה הגרוע?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל השוואה מחצית את טווח החיפוש הנותר; כ-20 השוואות מספיקות עבור מיליון פריטים מסודרים. הדבר אינו כולל כל עלות של סינון מראש.
חיפוש בינארי אינו עובד על רשימה לא מסודרת, אלא רק באיטיות רבה יותר.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ללא הסדר הנדרש, סילוק חצי מהרשימה עלול לפספס פריט קיים. ייתכן שחלק מהמקרים יצליחו מקרוב, אך נכונות האלגוריתם אינה מובטחת.
בדוק את האפס והאינדקס האחרון המותר. גיליון 4.4 בודק מחזור סיכום המשתמש ב-i קטן מ-n, מה שמפספס את האיבר האחרון. המעקב האוקלידי שלו גם הוא מסביר הסתיימות: כל מחלק חיובי מוחלף בשארית אי-שלילית קטנה עד שהגיעו לאפס.