חידת התכנות השניה שבחרתי להתמודד עימה, משהו קטן לקראת סוף השבוע, עוסקת במערכים. המקור בו מצאתי אותה (בכוונה לא שמתי קישור, כדי שלא תתפתו לראות שם את הפתרונות בתגובות) טוען שמדובר בחידת תכנות מראיון עבודה.
אז ככה: נתון מערך A בגודל N, שמכיל מספרים שלמים וממוין בסדר עולה. המשימה היא למצוא את כל התאים במערך, שהאינדקס שלהם שווה לערך שבתוכם. כלומר, אם
A[n] = n
אנחנו נרצה לראות את n מוצג על המסך. איך עושים את זה – ואיך עושים את זה עוד יותר טוב?
התוכנה שכתבתי, שוב ב-FPC/Lazarus (שפת Object Pascal), מתחילה באכלוס של מערך A בערכים אקראיים שאינם רחוקים מדי מטווח האינדקסים המקורי (אחרת, הסיכויים למציאת התאמות יהיו אפסיים). לאחר מכן היא ממיינת את המערך בסדר עולה, מציגה את האינדקסים והערכים שבתוכם על המסך (כדי שאוכל לבדוק בעין אם התשובות נכונות) ולסיום מאתרת ומציגה את האינדקסים של התאים שמקיימים את התנאי.
לכאורה, מדובר במשימה מאד טריוויאלית. למה לא לעבור פשוט על כל תא במערך, מההתחלה ועד הסוף, לבדוק אחד-אחד ולהוציא פלט בהתאם? מכיוון שכאשר מדובר בשאלות בראיון עבודה למתכנתים, ברוב המקרים יש איזושהי מלכודת, או לפחות דרך יעילה לפתרון, ומעבר גס על כל המערך לא נחשב דרך יעילה. הפתרון שמצאתי חכם יותר, ואולי אפילו אופטימלי. בתכנות עצמו "נפלתי" בכמה מקומות על שגיאות תחביר טפשיות וטעויות זעירות בלוגיקה, אך כזכור, בדיוק בשביל זה התחלתי את סדרת התרגילים…
[עריכה: רגע אחרי שפרסמתי את הפוסט, הרצתי שוב את התוכנה וגיליתי שהיא פספסה תא מסוים, דבר שלא קרה בכל הבדיקות הקודמות. הקוד תוקן, והתקרית הזו מדגישה את החשיבות של בדיקה יסודית של הקוד – לא רק בעין אלא גם מול סטנדרט אמין ועקבי יותר. במקרה הזה, אפשר לבדוק את התוצאה מול האלגוריתם הנאיבי שהוזכר בפסקה הקודמת. במקרים אחרים זה יכול להיות מסובך יותר… אבל זה כבר נושא לפוסט אחר!]
[עוד עריכה, חשובה מאד: הפתרון שמצאתי קשור, בין השאר, לפרט אחד קטן שהופיע בשאלה המקורית וששכחתי לציין אותו למעלה – המערך אינו כולל ערכים כפולים.]
אני מזכיר: נא לא לכתוב פה בתגובות פתרונות או כיוונים לפתרון – רק שאלות הבהרה והערות כלליות. את הפתרון שלי לחידה הקודמת אתן בפוסט הבא בסדרה. בהצלחה!
מה הסיבוכיות הדרושה?
בדרך הראשונה שעולה לי המקרה הגרוע הוא n, כשאין שום התאמה
בכוונה אני לא מדבר בתרגילים האלה על סיבוכיות – זה אמור להיות אתגר כיפי, לא עבודה לתואר 😉
אני יכול לרמוז לך שכשאין שום התאמה, אתה יכול להגיע לסיבוכיות הרבה יותר טובה מ-n. אגב, הפתרון שלי לחידה הזו מופיע בסוף הרשומה של אתגר מס' 5, אז אתה יכול להסתכל שם – או להיזהר ולא להסתכל, אם אתה רוצה להמשיך לנסות לבד.
נשמע מוזר רבע N
במקרה הגרוע (או הטוב תלוי בהסתכלות) שהכל תואם נקבל N
אמרתי רבע רק בשביל קנה מידה גס מאד – אני לא רוצה להסגיר יותר מדי מהפתרון.
זה נכון שבמקרה קיצוני תהיה לך 100% התאמה. עם זאת, ברוב המקרים יהיו לך הרבה פחות, והממוצע של מספר התאים שצריך לבדוק מצטמצם בהתאם.
יכול להיות שגם הפתרון היעיל הוא מאוד טריוויאלי? לא מצליח להעלות רעיון מתוחכם באמת
מה שנראה טריוויאלי לאדם אחד יכול להיות אתגר רציני לאדם אחר 🙂 בלי להסגיר שום סוד, נאמר ככה: אם מספר התאים שהפתרון שלך צריך לבדוק הוא, בממוצע, רבע N ומעלה, יש מקום לשיפור.
מה שכן, שכחתי לציין עוד פרט אחד שהופיע בבעיה המקורית – המערך אינו כולל ערכים כפולים, ומסתבר שהפתרונות שמתקבלים עם הפרט הזה ובלעדיו הם שונים לגמרי… אני מעדכן את הפוסט בהתאם.