חידת ראיון עבודה

[מספר6]

חידת ראיון עבודה

המשתנה x מאותחל ל-0. יש n תוכניות שרצות במקביל וכל אחת מקדמת את x בלולאה עד 5. כל תכנית מריצה את הקוד הבא: loop: a = x; if (a == 5) exit; x = a + 1; goto loop; a הוא משתנה פרטי של התוכנית, כלומר, לכל תוכנית יש משתנה אחר בשם a. קריאה וכתיבה ל-x הן פעולות אטומיות, כלומר, אם שתי תוכניות או יותר מנסות בו-זמנית לכתוב ו/או לקרוא את x, אז ייקבע ביניהן סדר שרירותי והקריאות/כתיבות יתבצעו בסדר זה. שאלה: מהו המספר המקסימלי של כתיבות ל-x שעשויות להתבצע?

 

[גיאל]

פשוט

אינסוף, וזה בגלל שתנאי העצירה קצת עקום, נניח שהגענו ל X=4 שני תוכניות קוראות את X עוברות את שלב הבדיקה (A==4) מוסיפות 1 לX כלומר X==6 מעתה כל התוכניות יוסיפו ויכתבו לX מאחר וערכו לעולם לא יהיה 5 (בו נדלג על השלב של X חורג מגודלו וחוזר להיות 0) בעצם תנאי העצירה צריך להיות A>5 או משהוא כזה.

 

[מספר6]

../images/Emo128.gif

שתי התוכניות יעשו השמה x=5

 

[יאיר של תמר]

המקרה המקסימלי...

קודם כל, 2 תוכניות כפי שהוזכר, יכולות לכתוב את אותו מספר לתוך X.. אז המקרה הגרוע הוא ש N-1 תוכניות רושמות 1,2,3,4,5 לתוך X, (כל אחת בנפרד).. ואז מגיעה התוכנית ה-N, (ממש לפני ששאר התוכניות יקראו את X ויגלו שהוא 5)... וכותבת ל-X את המספר 1. ואז שוב, N-1 תוכניות מקדמות את X ל-5... ובדיוק לפני הקריאה האחרונה, התוכנית ה-N רושמת 2.. וכו'.. אם לא התבלבלתי את זה - zzz 5*(n-1) + 4*(n-1) + 3*(n-1) + 2*(n-1) + 1*(n-1) + 5 ה +5 האחרון, הוא עבור התוכנית ה-Nית...

 

[מספר6]

../images/Emo128.gif

יש מקרים יותר גרועים

 

[יאיר של תמר]

ואולי...

אולי, הראשון רושם 1,2,3,4,5 (וכמובן, לפני שהוא מספיק לקרוא את X כ-5..) השני רושם 1 ב-X... ואז שוב, הראשון רושם 2,3,4,5... והשני רושם 2. ואז הראשון רושם 3,4,5 והשני רושם 3.. עד ששניהם רושמים 5. בנקודה זאת, נכנס השלישי ורושם 1.. ואז שוב, הראשון, רושם 2,3,4,5 .. והשני רושם 2... וכו'... עד ששניהם מגיעים ל-5 ואז השלישי רושם 2... וכו' אין לי כח לחשב כמה פעמים זה יוצא.. 1-> 1,2,3,4,5 2-> 1 1-> 2,3,4,5 2-> 2 1-> 3,4,5 . . . 1-> 5 2-> 5 ====== 3-> 1 1-> 2,3,4,5 2-> 2 1-> 3,4,5

 

[מספר6]

אין צורך במספר מדויק

מספיק סדר גודל כפונקציה של n

 

[יאיר של תמר]

משהו...

בגובה N?

 

[יאיר של תמר]

בכל מקרה...

הייתי בשירותים כשלימדו סדרי גודל של ביצוע

 

[מספר6]

אז יש חצי ../images/Emo127.gif

זה אכן המקרה הגרוע ביותר, אבל צריך להגיד כמה כתיבות יתבצעו