שלום, המסמך הזה נבנה לטובת אלו מכם שניגשים לראיונות עבודה בהייטק הישראלי. היוצר הבלעדי הוא (במקרה) אחי: ברק מנוס ישנם פרסומים רבים של מסמך זה ברחבי האינטרנט, בייחוד על-ידי חברות השמה ש"לקחו" בעלות על התוכן, מבלי לתת קרדיט הולם (אם בכלל) ליוצר המסמך, שהוא, ורק הוא (!) כתב וערך את כל תוכן המסמך, בהסתמך על הידע והנסיון הרב שצבר כמהנדס תוכנה בהייטק הישראלי. במידה ויהיו עדכונים למסמך זה (תשובות לשאלות חדשות), ממכם, או מברק בכבודו ובעצמו - אתם תראו אותם קודם כל פה (ורק אחר כך באתרים שהעתיקו מכאן). בקרוב אצרף פורום לשאלות\תשובות שלכם, בינתיים שלחו אלינו למייל: ברק barakman@yahoo.com או נעם noam@logonos.com חומר טכני לראיון עבודה
· חלק "צפוי" · חלק "בלתי צפוי" · דוגמא לתיאור של פרוייקט
· אינטל · רפא"ל · חברה שאני לא זוכר את השם שלה · בי.איי.טי.אם · איי.בי.אם · אלביט · מייקרוסופט · קיי.אל.איי · צורן · ספקטרום דיינאמיקס · פריסקייל · צ'ק פוינט · די.אס.פי.ג'י · ראד לייב · נייס · סאמסונג · ג'אנגו · דיסקרטיקס · ג'י.אי · אם-סיסטמס · אופטיבייס · קוואלקום · קוריג'נט · דיון נטוורקס · סיווה די.אס.פי · שאלות ששמעתי מאחרים
· סמלים בתוכנה · פונקציות מחלקה · תכנות מונחה עצמים · ניהול שכבות הזיכרון · ניהול תהליכים וחוטים
כל מה שכתוב כאן מתבסס על הידע והניסיון שלי (אז קחו את זה בערבון מוגבל). barakman@yahoo.com.
השלב הטכני בראיונות עבודה מתחלק לשני חלקים:
חלק "צפוי"
חלק "בלתי צפוי"
דוגמא לתיאור של פרוייקט 1. תיאור כללי: ... 2. מעבד: ... 3. מערכת הפעלה: ... 4. סביבת פיתוח: ... 5. שפת תכנות: ... 6. בקרת תצורה: ... 7. תיאור מפורט: ... 8. חבילת עבודה עיקרית: ...
ריכזתי כמה שאלות טכניות מתוך כל מיני ראיונות עבודה. לא את כל השאלות זכרתי, כי בחלק מהמקרים רשמתי אותן די הרבה זמן אחרי הראיון עצמו. מעבר לזה, השתדלתי לא לרשום יותר מפעם אחת שאלות שחזרו על עצמן כמה פעמים. בקיצור, לא כדאי להסיק מכמות השאלות או מהתוכן שלהן לגבי הקושי של הראיון בכל אחת מהחברות...
אינטל (חיפה)
רפא"ל (לשם)
חברה שאני לא זוכר את השם שלה (תל אביב)
בי.איי.טי.אם (יוקנעם)
איי.בי.אם (חיפה)
אלביט (חיפה) לא ממש זוכר. הייתה בעיקר שאלה אחת, ארוכה מדי בשביל לתאר פה...
מייקרוסופט (חיפה)
· 4 פעולות שמקבלות שלושה אופרנדים כל אחת. · 255 פעולות שמקבלות אופרנד אחד כל אחת. · 16 פעולות שלא מקבלות אופרנדים כלל. א. האם ניתן לתכנן מעבד כזה? הסבר. ב. נסח תנאי שיבדוק אם ניתן לתכנן מעבד עבור המקרה הכללי: · K1 פעולות שמקבלות P1 אופרנדים באורך של L1 ביטים. · K2 פעולות שמקבלות P2 אופרנדים באורך של L2 ביטים. · ... · Kn פעולות שמקבלות Pn אופרנדים באורך של Ln ביטים.
קיי.אל.איי (מגדל העמק)
צורן (חיפה)
א. כתוב פונקציה שמקבלת תו ובודקת אם הוא נמצא במערך. ב. מצא דרך לשפר את זמן הריצה של הפונקציה שכתבת.
ספקטרום דיינאמיקס (טירת הכרמל)
פריסקייל (הרצליה פיתוח)
צ'ק פוינט (רמת גן)
· void* malloc() – מקצה שטח זיכרון של 8 בתים, ומחזירה את הכתובת שבה הוא מתחיל. · void free(void* p) – מקבלת כתובת שבה מתחיל שטח זיכרון של 8 בתים, ומשחררת אותו. תכנן שיטה לנהל את הזיכרון, וממש את הממשק כך שיאפשר הקצאה של 8 בתים כל עוד יש מקום פנוי.
די.אס.פי.ג'י (הרצליה פיתוח)
א. הגדר וממש את הפונקציה. האם ניתן לשפר את זמן הריצה שלה? ב. האם ייתכן מצב מסוים, שבו הפונקציה לא תעתיק את הנתונים במדויק?
א. נניח שבפונקציה רשום a=b. האם במהלך ריצת התוכנית תמיד תוכל לדעת בוודאות מהו הערך של a? אם לא, איך תשנה את הקוד על מנת להבטיח את זה? ב. נניח שבפונקציה רשום b=a. האם במהלך ריצת התוכנית תמיד תוכל לדעת בוודאות מהו הערך של b? אם לא, איך תשנה את הקוד על מנת להבטיח את זה?
char* strcat(char* first, char* last) { char buff[100]; sprintf(buff,"%s%s",first,last); return buff; } מה לא תקין בפונקציה?
ראד לייב (תל אביב)
נייס (רעננה) שאלו רק לגבי פרוייקטים שעבדתי עליהם...
סאמסונג (הרצליה פיתוח) ראיון של משאבי אנוש. כשהיא שאלה מה הממליצים שרשמתי יגידו עליי, אמרתי לה שאני לא יודע, ושאולי יהיה יותר פשוט אם היא תתקשר אליהם במקום לשאול אותי. כנראה שבגלל זה לא עברתי...
ג'אנגו (נתניה)
· OS_small_malloc(int sz) – יכולה להקצות 512 בתים לכל היותר. · OS_large_malloc(int sz) – יכולה להקצות 512 בתים לכל הפחות. · OS_free(void* p, int sz) – משחררת sz בתים מכתובת p בזיכרון. א. ממש את הפונקציה void* malloc(int sz). תפקידה הוא להקצות זיכרון בכל גודל, ובכפולות של 16 בתים. ב. ממש את הפונקציה void free(void* p). תפקידה הוא לשחרר זיכרון שהוקצה באמצעות הפונקציה הקודמת. ג. שכלל את הפונקציה free, כך שתדפיס הודעת שגיאה כאשר מתבצע ניסיון לשחרר זיכרון שכבר שוחרר בעבר.
· הפונקציה void CreateTimer(void (*func)(), int seconds), שתפקידה הוא ליצור Timer. · הפונקציה void StartTimers(), שתפקידה הוא להפעיל את כל ה-Timer'ים שקיימים במערכת. כל Timer שמופעל, צריך לבצע השהיה של מספר שניות ולאחר מכן לקרוא לפונקצית ה-Callback. דוגמא לשימוש ב-Timer'ים: CreateTimer(func1,3); CreateTimer(func2,7); CreateTimer(func3,10); StartTimers(); הפעולות הבאות צריכות להתבצע (בצורה טורית): · השהיה של 3 שניות ואחריה קריאה ל-func1. · השהיה של 4 שניות ואחריה קריאה ל-func2. · השהיה של 3 שניות ואחריה קריאה ל-func3.
דיסקרטיקס (נתניה)
void func(int* x) { x = (int*)malloc(sizeof(int)); *x = 17; } מה תדפיס התוכנית הבאה, ומה לא תקין בה? void main() { int y = 42; func(&y); printf("%d",y); }
ג'י.אי (טירת הכרמל)
void main() { const char* arr = "abcde"; char* ptr = (char*)malloc(strlen(arr)+1); for (int i=0; i<strlen(arr)+1; i++) *ptr++ = arr[i]; free(ptr); } מה לא תקין בתוכנית?
int func() { int a = 1; a++; return a; } ה-Thread הראשון מתחיל לרוץ וקורא לפונקציה. כשהוא מסיים את השורה הראשונה, מתבצע Context Switch. ה-Thread השני מתחיל לרוץ וקורא לפונקציה. כשהוא מסיים את השורה השניה, מתבצע שוב Context Switch. מהו הערך של המשתנה a בשלב הזה?
אם-סיסטמס (רעננה)
אופטיבייס (הרצליה פיתוח)
קוואלקום (חיפה)
קוריג'נט (תל אביב)
דיון נטוורקס (יקום)
סיווה די.אס.פי (הרצליה פיתוח)
1. Load(loc,buf) – טעינת 1KB מכתובת loc בזיכרון החיצוני לכתובת buf בזיכרון הפנימי (250 Cycles). 2. Store(loc,buf) – טעינת 1KB מכתובת buf בזיכרון הפנימי לכתובת loc בזיכרון החיצוני (250 Cycles). 3. Process(buf) – עיבוד של 1KB נתונים בכתובת buf בזיכרון הפנימי (600 Cycles). פעולות 1 ו-2 הן פעולות DMA, וניתן לבצע כל אחת מהן במקביל לפעולה 3 (אבל לא במקביל לפעולה השניה). כתוב תוכנית מהירה ככל האפשר, שקוראת 60KB של נתונים מהזיכרון החיצוני, מעבדת אותם בזיכרון הפנימי וכותבת אותם בחזרה לזיכרון החיצוני (מותר להניח שקוד התוכנית לא תופס מקום בזיכרון הפנימי).
long func(short x) { long res = 0; static short array[20000]; extern short const_array[20000];
for (int i=19999; i>0; i--) array[i] = array[i-1]; array[0] = x;
for (int j=0; j<20000; j++) res += (long)array[j]*const_array[j]; return res; } פעולת גישה למערך לוקחת חמישה Cycles'ים, וכל פעולה אחרת (+, -, *, = וכו') לוקחת Cycle אחד. א. מה הפונקציה עושה, ומהו זמן הריצה שלה? ב. נתונות שתי פעולות חדשות: 1. inc_mod(i,n) ç i = (i+1)%n (הגדל את i ב-1 מודולו n). 2. dec_mod(i,n) ç i = (i-1+n)%n (הקטן את i ב-1 מודולו n). כל אחת מהן לוקחת Cycle אחד. מצא דרך לשפר את זמן הריצה של הפונקציה, וחשב אותו מחדש.
שאלות ששמעתי מאחרים
א. תאר אלגוריתם שבודק אם הביטוי הוא חוקי או לא. ב. אותה בעיה, כאשר קיים סוג רביעי של סוגריים, שבו אין הבדל בין סוגר שמאלי לסוגר ימני: | |.
א. כתוב תוכנית שמחשבת את מספר האפשרויות השונות (קומבינציות שונות של קפיצות), שבהן ספיידרמן יכול לטפס על הבניין. ב. מהי סיבוכיות הזמן שלה ומהי סיבוכיות הזיכרון שלה? ג. הראה שניתן לשנות את התוכנית כך שהיא תתבצע בזמן לינארי. ד. הראה שניתן לשנות את התוכנית כך שהיא תתבצע בזיכרון קבוע.
שאלות ששמעתי מאחרים (המשך)
כל קטע נתון כשתי נקודות במישור: [(x1,y1) , (x2,y2)]. מצא את המספר הגדול ביותר של נקודות חיתוך בין ישר מאונך כלשהו לבין הקטעים. לדוגמא, בשרטוט המצורף ישנן 4 נקודות חיתוך כאלה לכל היותר.
א. void* MyMalloc(int size) ב. void MyFree(void* ptr)
· INC Rx – הגדלת הערך שב-Rx ב-1. · DEC Rx – הקטנת הערך שב-Rx ב-1. · CLR Rx – איפוס הערך שב-Rx. · JUMP Rx LABEL – ביצוע קפיצה ל-LABEL, אם הערך שב-Rx שונה מאפס. א. בצע בעזרת הפעולות הנ"ל R3çR2*R1. האם ניתן לוותר על חלק מהפעולות ולממש אותן באמצעות הפעולות האחרות? ב. האם הקוד שכתבת עובד נכון גם עבור מספרים שליליים (כלומר, כאשר מתייחסים לערכי הרגיסטרים בשיטת המשלים ל-2)?
א. האם מובטח שהערך של x בסיום הריצה של שני קטעי הקוד יהיה אותו ערך בכל פעם? ב. אם לא, הוסף לאחד מקטעי הקוד (או לשניהם) רצף פעולות שיבטיח את זה. מה יהיה הערך של x בסיום?
שאלות ששמעתי מאחרים (המשך) 100.האם פונקצית מחלקה סטאטית יכולה להיות וירטואלית? מדוע? 101.ספינה צריכה להגיע לאי, כאשר בדרך ישנם הרבה קרחונים. איך ניתן לחשב את המסלול הקצר ביותר שהספינה יכולה לעשות בשביל להגיע לאי בלי לעבור דרך הקרחונים? מותר להניח שמיקום הספינה ומיקום האי נתונים כנקודות במישור, ושכל קרחון מיוצג כמצולע (אוסף של קודקודים) במישור. 102.נתונים שני מיכלים. במיכל הראשון יש ליטר חלב ובמיכל השני יש ליטר סירופ שוקולד. לוקחים כוס מהמיכל הראשון, מוזגים למיכל השני ומערבבים. לאחר מכן לוקחים כוס מהמיכל השני, מוזגים בחזרה למיכל הראשון ומערבבים שוב. מהו היחס בין ריכוז החלב במיכל הראשון לריכוז סירופ השוקולד במיכל השני? 103.שלושה אנשים רוצים לדעת מהו ממוצע המשכורות שלהם. איך הם יכולים לחשב את הממוצע הזה בלי שאף אחד יגלה לאחרים מהי המשכורת שלו (ובלי להיעזר באיש נוסף)? 104.בהינתן מספר שבו ישנם N ביטים שערכם 1, מצא את הערך של N תוך שימוש ב-N איטרציות לכל היותר. 105.נתון מערך של N מספרים שלמים, שכולל את כל הערכים בתחום [1-N, 1]. אחד המספרים מופיע במערך פעמיים. מצא את הערך שלו, תוך מעבר אחד על המערך ובלי להשתמש בזיכרון נוסף. 106.ממש הכפלה של מספר כלשהו ב-7, ללא שימוש בפעולת כפל או בפעולת חיבור. 107.
108.שלושה גברים צריכים להיות עם אשה אחת, כאשר יש ברשותם רק שני קונדומים. איך ניתן לעשות את זה בצורה בטוחה עבור כולם (גם האשה וגם הגברים)? 109.נתון מספר שלם לא מסומן (unsigned int). הגדל אותו ב-1, ללא שימוש בפעולת חיבור או בפעולת חיסור. 110.נתונה סדרה של N מספרים. מצא את תת הסדרה הרצופה המקסימלית (מבחינת סכום איברים) שקיימת בה. 111.ידוע שאפשר למצוא איבר במערך ממוין תוך שימוש ב-O(log(N)) פעולות, ע"י חיפוש בינארי. נניח שסובבנו את המערך סביב ציר כלשהו, למשל: מ-{1,2,3,4,5} ל-{3,4,5,1,2}. מצא שיטה למצוא איבר במערך החדש (כאשר ציר הסיבוב לא ידוע לך), תוך שימוש באותה סיבוכיות זמן. 112.ממש שער XOR בעזרת שערי NAND בלבד. 113.אצן A ואצן B מתחרים בריצת 100 מטר. אצן A מסיים 5 מטרים לפני אצן B. בשביל לעשות את המירוץ יותר הוגן, הם מבצעים אותו שוב, אלא שהפעם אצן A מתחיל 5 מטרים מאחורי אצן B. בהנחה ששניהם רצים בדיוק באותו קצב שבו הם רצו בפעם הראשונה, מי מהם ינצח בפעם השניה? (בלי לבצע חישובים אלגבריים). 114.חולה מקבל מהרופא שלו בקבוק של 30 כדורים מסוג X ובקבוק של 30 כדורים מסוג Y. ההוראות של הרופא: "במשך 30 יום, אתה צריך לקחת כל יום כדור אחד מכל סוג, ואתה צריך לקחת את שני הכדורים ביחד". ביום הראשון, החולה מוציא כדור אחד מסוג X ושני כדורים מסוג Y (בטעות). כל הכדורים נראים בדיוק אותו דבר, כך שאין לו אפשרות לדעת איזה כדור הוא צריך להחזיר לבקבוק. הוא לא יכול לקנות בקבוקים חדשים, כי הם מאד יקרים. איך הוא יכול לקחת את התרופות לפי ההוראות שהרופא נתן לו?
שאלות ששמעתי מאחרים (המשך) 115.נתון מערך שמכיל N מספרים שלמים בתחום [0…N-1]. בדוק אם קיים בו ערך כלשהו שמופיע יותר מפעם אחת. 116.שני שחקנים משחקים זה מול זה. ישנה קופה משותפת עם 0 מטבעות, וכל שחקן בתורו שם בה 1, 2 או 3 מטבעות. בתחילת המשחק בוחרים מספר X כלשהו, והשחקן שמביא את הקופה ל-X מטבעות, מנצח. המגבלה היחידה על הערך של X, היא ש-X לא מתחלק בשלמות ב-4. מצא שיטה לניצחון בטוח עבור השחקן שמתחיל ראשון. 117.כמה פעמים ברציפות מופיעה הספרה 0 בסוף הייצוג העשרוני של המספר 100 עצרת? 118.++C – איך ניתן לדעת מהו מספר האיברים: א. במערך שהוקצה בצורה סטאטית (לדוגמא, Type Array[10])? ב. במערך שהוקצה בצורה דינאמית (לדוגמא, Type Array=new Type[10])? 119.++C – הסבר מה לא תקין בקטעי הקוד הבאים: א. T* p=0; delete p; ב. T* p=new T[10]; delete p; 120.++C – מה זה RTTI ואיך זה עובד? 121.נתונים המעגל והמשתנים הבאים: א. חשב את קוטר המעגל כפונקציה של המשתנים a, b, c, e, f. ב. חשב את קוטר המעגל כפונקציה של המשתנים a, b, c בלבד.
122.נתונה יחידה לוגית בעלת שתי כניסות A ו-B ושתי יציאות C ו-D: C = min(A,B), D = max(A,B). באמצעות יחידות מסוג זה בלבד, עליך לבנות יחידה חדשה עם ארבע כניסות וארבע יציאות, כך שהמספרים ביציאות יהיו ממוינים בסדר עולה. המימוש צריך להיות פשוט ככל שניתן (שימוש במספר קטן ככל האפשר של יחידות).
123.נתון שעון בעל תדר כלשהו. באמצעות יחידות מסוג D-Flip-Flop ושערים לוגיים מכל סוג, צריך לבנות מחלק תדר לשעון (כלומר, שעון חדש שיעבוד בחצי מהתדר של השעון המקורי). 124.נתונים פתילים A ו-B. כאשר מדליקים את פתיל A בקצה, הוא מתחיל לבעור ומתכלה לאחר 60 דקות. כאשר מדליקים את פתיל B בקצה, הוא מתחיל לבעור ומתכלה לאחר 30 דקות. קצב הבעירה של שני הפתילים אינו קבוע (למשל, יכול להיות שכעבור 55 דקות יישרף רק חצי מפתיל A, וב-5 הדקות הבאות יישרף כל החצי השני שלו). כיצד ניתן למדוד 45 דקות בעזרת שני הפתילים? כעת נתונים פתילים A ו-C, כאשר פתיל C מתכלה גם הוא לאחר 60 דקות בקצב בעירה שאינו קבוע (ושאינו בהכרח זהה לקצב הבעירה של פתיל A). כיצד ניתן למדוד 45 דקות בעזרת שני הפתילים האלה? 125.הפיכת סדר הביטים ביחידת זיכרון: א. כתוב פונקציה שמקבלת בית, ומחזירה את הבית ההפוך לו מבחינת סדר הביטים שלו. ב. כתוב פונקציה שעושה את אותה פעולה עבור בית, בזמן קבוע ביחס למספר הביטים שלו. ג. כתוב פונקציה שעושה את אותה פעולה עבור רגיסטר, בזמן קבוע ביחס למספר הביטים שלו.
סמלים בתוכנה:
סמלים בתוכנה נועדו לייצג ערכים כלשהם, ע"מ להקל על כתיבת הקוד ועל קריאתו. כל הסמלים בתוכנה מוחלפים ע"י הקומפיילר בערכים שהם מייצגים: · סמלי מאקרו, טיפוס ותבנית (#define, typedef, template) נודעו לייצג ערכים קבועים כלשהם. סמלים אלה מוחלפים כבר בשלב ה-Preprocessing, בערכים שנקבעו עבורם ע"י המתכנת. · שאר הסמלים – שמות של משתנים ופונקציות – נועדו לייצג כתובות זיכרון במהלך ריצת התוכנית. סמלים אלה מוחלפים במהלך הקומפילציה עצמה, בכתובות שנקבעות עבורם ע"י הקומפיילר.
כשתוכנית נכנסת למצב ריצה, היא מקבלת מרחב זיכרון קבוע (Memory Address Space) שבו היא פועלת. שמות של משתנים ופונקציות שהוחלפו במהלך הקומפילציה בכתובות, קיבלו בשלב הזה ערכים יחסיים ולא מוחלטים. כלומר, כל הכתובות שאליהן התוכנית ניגשת, נמצאות למעשה ב-Offset כלשהו מתחילת מרחב הזיכרון שמוקצה עבורה.
מרחב הזיכרון שבו התוכנית פועלת, מורכב משלושה חלקים בסיסיים: 1. אזור נתונים (Data Section). 2. אזור קוד (Code Section). 3. מחסנית (Stack).
על מנת להריץ את התוכנית, המעבד משתמש ברגיסטרים באופן הבא: · רגיסטר ה-IP (Instruction Pointer) מצביע תמיד על הפקודה הבאה לביצוע, שרשומה באזור הקוד. · רגיסטר ה-SP (Stack Pointer) מצביע תמיד על המקום הבא שפנוי במחסנית.
כאמור, במהלך הקומפילציה, שמות של משתנים ופונקציות מוחלפים בכתובות זיכרון: · שמות של משתנים מוחלפים בכתובות, אשר בזמן ריצה יהיו שייכות לאזור הנתונים או למחסנית. · שמות של פונקציות מוחלפים בכתובות, אשר בזמן ריצה יהיו שייכות לאזור הקוד.
המשתנים שמשויכים לאזור הנתונים מתחלקים לארבעה סוגים: 1. משתנים גלובאליים לא סטאטיים – מוכרים בכל הקבצים בתוכנית. 2. משתנים גלובאליים סטאטיים – מוכרים רק בקובץ שבו הם מוגדרים. 3. משתנים לוקאליים סטאטיים – מוכרים רק בפונקציה שבה הם מוגדרים. 4. משתנים מחלקתיים סטאטיים – מוכרים רק במחלקה שבה הם מוגדרים (ובאובייקטים מסוגה). ההבדל בין הסוגים השונים הוא אך ורק ב-Scope שבו הקומפיילר מכיר אותם. בזמן ריצה אין ביניהם שום הבדל. בנוסף לזה, הכתובות של המשתנים האלה נשארות קבועות במשך כל ריצת התוכנית (ביחס לתחילת מרחב הזיכרון שלה).
המשתנים שמשויכים למחסנית הם המשתנים הלוקאליים שאינם סטאטיים. השמות שלהם מוחלפים בכתובות, שבזמן ריצה יהיו בעצמן יחסיות לערך של רגיסטר ה-SP: · עבור פונקציה כלשהי, מצב המחסנית (רגיסטר ה-SP) עשוי להיות שונה בכל פעם שהפונקציה נקראת. · כלומר, מיקום המשתנים של הפונקציה ביחס לתחילת המחסנית עשוי להיות שונה בכל פעם שהפונקציה רצה. לכן, הכתובות של המשתנים האלה לא בהכרח נשארות קבועות במשך כל ריצת התוכנית (אפילו בתוך מרחב הזיכרון שלה).
משתנים מחלקתיים שאינם סטאטיים, משויכים או לאזור הנתונים או למחסנית (בהתאם לאובייקט שאליו הם שייכים).
הפונקציות, שמשויכות כולן לאזור הקוד, מתחלקות לארבעה סוגים: {גלובאליות , מחלקתיות} × {סטאטיות , לא סטאטיות}. גם כאן, בדומה למשתנים שמשויכים לאזור הנתונים, אין בין הסוגים השונים של הפונקציות שום הבדל בזמן ריצה. הכתובות של הפונקציות נשארות, כמובן, קבועות במשך כל ריצת התוכנית (בלי קשר לסוגים שלהן).
לסיכום: · כל הסמלים בתוכנית מייצגים ערכים כלשהם, שנקבעים עוד לפני ריצת התוכנית. · שמות של משתנים ופונקציות מוחלפים במהלך הקומפילציה, ובמקומם באות כתובות זיכרון. · כתובות אלה הן לא קבועות במרחב הזיכרון הפיזי של המחשב, אלא יחסיות לתחילת מרחב הזיכרון שמוקצה לתוכנית בכל פעם שהיא רצה. חלקן קבועות במרחב הזיכרון הזה וחלקן משתנות אפילו ביחס לתחילתו (במהלך ריצת התוכנית). פונקציות מחלקה:
ההבדל בין פונקצית מחלקה לא סטאטית לפונקצית מחלקה סטאטית:
*כתובת האובייקט יכולה להישלח דרך המחסנית או ברגיסטר כלשהו (תלוי בקומפיילר).
ההבדל בין קריאה לפונקצית מחלקה לא וירטואלית לקריאה לפונקצית מחלקה וירטואלית (בעזרת מצביע):
קריאה לפונקציה הלא וירטואלית void MyClass::Func1( ) בעזרת המצביע MyClass* myPtr :
Ax = myPtr //Get the address of the instance Bx = MyClass::Func1 //Get the address of the function Push Ax //Push the address of the instance into the stack Push Bx //Push the address of the function into the stack CallF //Save some registers and jump to the beginning of the function
קריאה לפונקציה הווירטואלית void MyClass::Func2( ) בעזרת המצביע MyClass* myPtr :
Ax = myPtr //Get the address of the instance Bx = myPtr->__vfptr //Get the address of the instance's V-Table Cx = Bx + MyClass::Func2_Num //Add the number of the function in its class Dx = *Cx //Get the address of the appropriate function Push Ax //Push the address of the instance into the stack Push Dx //Push the address of the function into the stack CallF //Save some registers and jump to the beginning of the function
כלומר, ביחס לקריאה לפונקציה לא וירטואלית, קריאה לפונקציה וירטואלית דורשת עוד שתי פעולות Read (קריאת הערך של המצביע ל-V-Table וקריאת ערך כלשהו מתוך ה-V-Table) ועוד פעולת Add אחת (חיבור בין רגיסטר למספר קבוע). תכנות מונחה עצמים:
המונח OOD/OOP לא מתייחס לשפת תכנות כלשהי שמאפשרת דברים ששפת תכנות רגילה לא מאפשרת, אלא מגדיר קונספט שמאפשר לתכנן ולממש תוכנה באופן דומה לתכנון ולמימוש של מערכות אחרות (שאינן בהכרח קשורות לתחום).
הקונספט הזה שם דגש על שני אלמנטים עיקריים: 1. סגירות (Encapsulation). 2. גזירה (Derivation).
הרעיון שעומד מאחורי אלמנט הסגירות, הוא בניית חלקים שונים בתוכנה כמודולים עצמאיים ובלתי תלויים. אפשר להסתכל על מודול בתוכנה כעל "קופסה שחורה", שמסוגלת לבצע מספר משימות מוגדרות: 1. מה היא מסוגלת לבצע – חשוף בפני כל הצרכנים (המשתמשים). 2. איך היא מבצעת את זה – ידוע רק ליצרן (המממש).
הרעיון הזה מאפשר למספר רב של אנשים לתכנן ולממש חלקים שונים של תוכנה מורכבת, מבלי להצטרך ולהכיר את המבנה הפנימי של כל חלק וחלק. במקום זה, כל אחד צריך להכיר לעומק רק את החלק שלו (מה הוא מסוגל לבצע ואיך הוא מבצע את זה), ואילו את שאר החלקים מספיק לו להכיר מבחוץ (מה הם מסוגלים לבצע). העקרון הוא די דומה לעקרון השימוש בספריות LIB או DLL, למעט העובדה שהן נתונות כקוד מקומפל ולכן המבנה הפנימי שלהן כבר מוסתר מהמשתמש.
הרעיון שעומד מאחורי אלמנט הגזירה, הוא שימוש במודולים קיימים ומוכרים לצורך הרחבתם. ישנן שתי תבניות כלליות שבעזרתן ניתן להרחיב מודול A למודול B: 1. ליצור את מודול B ולשים בתוכו עצם מסוג A, בנוסף לתכונות הספציפיות שרצויות בו (במקרה הזה, B has an A). 2. לגזור את מודול B ממודול A, ולהוסיף לו את התכונות הספציפיות שרצויות בו (במקרה הזה, B is an A).
הרעיון הזה מאפשר לקחת ממשק מוכר ולהוסיף לו פונקציות חדשות, בלי לממש מחדש את אלה שכבר קיימות. לדוגמא, נניח שמודול A מייצג טייפ שמאפשר Play ו-Stop, ומודול B מייצג טייפ חדשני שמאפשר גם Rewind. פס הייצור של מודול A כבר קיים, ובנוסף, קהל הצרכנים כבר מכיר את הממשק שלו. לכן, במקום ליצור את מודול B מהתחלה, נרחיב את פס הייצור של מודול A ונוסיף לו את מימוש הממשק של מודול B.
כלי נוסף שטמון בשיטת הגזירה, הוא הכללה של קבוצות של מודולים שנגזרים מאותו מקור, ולכן בעלי אופי דומה. לדוגמא, נניח שמודול A מייצג מכשיר גנרי להשמעת מוזיקה, ומודולים B ו-C מייצגים פטיפון וטייפ בהתאמה: · ברשותנו אוסף של פטפונים וטייפים, ואנחנו צריכים לבצע לכל מכשיר ניקוי-ראש פעם בשנה. · פעולת ניקוי הראש יכולה להתבצע רק במעבדה מתאימה, והמעבדה הזולה ביותר היא זאת שמתמחה רק בזה. · בנוסף, אסור שאף אחד ינסה לבצע שום דבר אחר עם המכשירים, מכיוון שזה עלול להוריד מערכם. הפתרון המתאים ביותר לבעיה, הוא להגדיר את פעולת ניקוי הראש בממשק של מודול A. מימוש הפעולה עצמו יכול להתבצע במודול A, או במודולים B ו-C בנפרד (או גם וגם). הכלי הזה נקרא Polymorphism, והוא מיושם באמצעות הורשה ופונקציות וירטואליות.
לסיכום, שיטת הגזירה מאפשרת להרחיב מודולים קיימים, בלי הצורך לשנות אותם או להכיר את המימוש שלהם. חשוב לציין שהגמישות הזאת היא לא מושלמת: על מנת להוסיף מודול חדש לתוכנה קיימת, צריך לקמפל אותה מחדש (כלומר, דרוש קוד המקור של התוכנה). הדרך היחידה להרחיב תוכנה בלי הצורך לקמפל את קוד המקור שלה מחדש, היא באמצעות שימוש בספריות DLL.
ניהול שכבות הזיכרון:
שכבת הזיכרון הבסיסית ביותר – הרגיסטרים: · המעבד יכול לגשת אליה ישירות לצורך פעולות של קריאה או כתיבה. · בנוסף, הוא יכול לבצע עליה את כל הפעולות החישוביות שמוגדרות בו. · לא ניתן לאחסן בשכבה הזאת מידע, שישמר גם כאשר תיפסק אספקת מתח סדירה. · מהירות הגישה הממוצעת אל השכבה הזאת היא הגבוהה ביותר (ביחס לשאר שכבות הזיכרון).
מעליה נמצאת שכבת הזיכרון הפנימי (Ram): · המעבד יכול לגשת אליה ישירות לצורך פעולות של קריאה או כתיבה. · בנוסף, הוא יכול לבצע עליה חלק מהפעולות החישוביות שמוגדרות בו. · לא ניתן לאחסן בשכבה הזאת מידע, שישמר גם כאשר תיפסק אספקת מתח סדירה. · בדרך כלל, השכבה הזאת מורכבת משני חלקים:
מעליה נמצאת שכבת הזיכרון המישני (Hard Disk): · המעבד לא יכול לגשת אליה ישירות לצורך פעולות של קריאה או כתיבה. · בנוסף, הוא לא יכול לבצע עליה אף אחת מהפעולות החישוביות שמוגדרות בו. · ניתן לאחסן בשכבה הזאת מידע, שישמר גם כאשר תיפסק אספקת מתח סדירה. · מהירות הגישה הממוצעת אל השכבה הזאת היא הנמוכה ביותר (ביחס לשאר שכבות הזיכרון).
על מנת שרצף פעולות (קטע קוד) כלשהו יוכל לרוץ על המעבד, הוא חייב להיטען לזיכרון הפנימי. המונח זיכרון וירטואלי מתאר צורת ניהול מתוחכמת של הזיכרון הפנימי, תוך שימוש בזיכרון המישני. מיפוי כתובות הזיכרון הווירטואלי לכתובות בזיכרון הפיזי מתבצע בעזרת יחידת ניהול הזיכרון (MMU).
המטרה העיקרית של הזיכרון הווירטואלי היא לאפשר בכל רגע נתון הרצה של תוכנית, גם כאשר היא דורשת יותר מקום מסך כל הזיכרון הפנימי הפנוי באותו רגע. השיטה היא פשוטה – על מנת שקטע קוד כלשהו יוכל לרוץ על המעבד, הדבר היחידי שחייב להיות בזיכרון הפנימי בכל רגע הוא הפעולה הבאה לביצוע: · כאשר יש צורך בנתון כלשהו, יחידת ניהול הזיכרון מחפשת אותו ב-Cache. · אם הנתון לא נמצא שם (Miss), יחידת ניהול הזיכרון מחפשת אותו ב-Ram. · אם הנתון לא נמצא שם (Page Fault), יחידת ניהול הזיכרון מחפשת אותו ב-Hard Disk. בכל שלב, במידה והנתון לא נמצא במקום המתאים, יחידת ניהול הזיכרון "משדרגת" את המיקום שלו לפי יוריסטיקה כלשהי (למשל, Last Recently Used), ע"מ לשפר את זמן הגישה אליו בעתיד. דבר זה בא, כמובן, על חשבון נתון אחר. כאשר אין מספיק מקום בזיכרון הפנימי, יחידת ניהול הזיכרון מוציאה נתונים באופן זמני לזיכרון המישני, עד אשר יהיה צורך בהם.
מטרה נוספת של הזיכרון הווירטואלי היא להסיר מהמשתמש את הצורך להכיר כתובות זיכרון אבסולוטיות ולעבוד איתן. המשתמש הפוטנציאלי יכול להיות המתכנת, הקומפיילר ואפילו מערכת ההפעלה. הגישה של כל אלה לזיכרון יכולה להתבצע בצורה "שקופה", ורק בזמן ביצוע פעולה שדורשת גישה לזיכרון, ה-MMU נעזר ברגיסטר ה-Base Address ובמפת הזיכרון הווירטואלי ע"מ לחשב את כתובת היעד המדויקת. בנוסף, העובדה שעבור כל תהליך מוגדר מרחב זיכרון משלו, מאפשרת למערכת ההפעלה להגן מפני גישה של תהליכים אחרים לאותו מרחב זיכרון (שוב, תוך שימוש ברגיסטר ה-Base Address ובמפת הזיכרון הווירטואלי).
ניהול תהליכים וחוטים:
תהליך (Process) הוא למעשה תוכנית בביצוע. כאמור, הגנה על תהליך מפני תהליכים אחרים מתבצעת בעזרת יחידת ניהול הזיכרון, שממפה את כתובות הזיכרון הווירטואלי לכתובות בזיכרון הפיזי. עבור כל תהליך ישנם רגיסטרים, שבעזרתם מוגדר מרחב הזיכרון הפיזי שלו. בכל פעולת גישה של תהליך כלשהו לזיכרון, כתובת היעד מחושבת באמצעות ערכי הרגיסטרים שלו וטבלת הזיכרון הווירטואלי, כך שלמעשה הוא לא יכול לגשת למרחב הזיכרון הפיזי של אף תהליך אחר.
על מנת לדמות סביבה שבה דברים מתבצעים במקביל (Multi Tasking), מערכת ההפעלה מחליפה כל הזמן בין תהליכים. בכל רגע נתון, רק תהליך אחד נמצא במצב ריצה, וכל שאר התהליכים שקיימים במערכת נמצאים במצב המתנה. החלפה בין תהליכים דורשת שימור של המצב הנוכחי עבור התהליך שיוצא (עובר מריצה להמתנה), ושחזור של המצב הקודם עבור התהליך שנכנס (עובר מהמתנה לריצה). החלפה כזאת נקראת החלפת הקשר (Context Switch), והיא כוללת את התוכן של מרחב הזיכרון ואת ערכי הרגיסטרים.
כל תהליך מורכב מחוט (Thread) אחד או יותר, אותם הוא יוצר במהלך הריצה שלו. מערכת ההפעלה מבצעת החלפת הקשר בין חוטים, בדומה להחלפת הקשר בין תהליכים. בצורה כזאת, התהליך (שמייצג תוכנית כלשהי) יכול בעצמו לדמות ביצוע של מספר דברים במקביל. החלפת הקשר בין חוטים של אותו תהליך היא יותר מצומצמת מהחלפת הקשר בין תהליכים שונים. היא לא כוללת את התוכן של מרחב הזיכרון, מכיוון שמרחב הזיכרון הזה משותף לכל החוטים של התהליך.
כאמור, אין צורך לבנות תוכנית, כך שהתהליך שמייצג אותה יהיה מוגן מפני תהליכים אחרים – מערכת ההפעלה דואגת לזה. לעומת זאת, בבניית תוכנית שיוצרת חוטים, יש צורך לסנכרן ביניהם, כך שהגישה שלהם לזיכרון (שמשותף לכולם) תהיה סדירה ודטרמיניסטית. בגלל שמערכת ההפעלה שולטת על זמן הכניסה של כל חוט לריצה ועל זמן היציאה שלו ממנה, לא ניתן לדעת מתי כל חוט (ביחס לחוט אחר של אותו תהליך) ניגש לזיכרון המשותף, ולכן צריך לתזמן את הגישה הזאת.
לעיתים קיימים קטעי קוד (רצף של פעולות) אשר חוטים מסוימים מריצים, ובמהלכם הם ניגשים לאותו אזור בזיכרון המשותף. אם אחד מהחוטים מבצע גישה לצורך כתיבה, אז קטע הקוד של כל אחד מהם מוגדר קריטי (Critical Section). המשמעות היא, שכאשר חוט כלשהו נמצא במהלך הקטע הקריטי שלו, אסור לחוטים האחרים לבצע את הקטע הקריטי שלהם. לצורך כך, יש לממש מנגנון שיבטיח מניעה הדדית (Mutual Exclusion). המנגנון שממומש, חייב גם למנוע מצב שבו קבוצה של חוטים נמצאת בהמתנה "ציקלית" לכניסה של אחד מהם לקטע הקריטי (מניעת Deadlock). בנוסף, הוא גם חייב למנוע מצב שבו חוט כלשהו ממתין לנצח להתחיל את הקטע הקריטי שלו (מניעת Starvation).
שיטות בסיסיות להגנה על קטע קוד קריטי: 1. Disable/Enable Interrupts – נגדיר את הקטע הקריטי של כל חוט כפעולה אטומית (רצף של פעולות, אשר בתחילתו הפסיקות מנוטרלות ובסופו הן מאופשרות, ולכן במהלכו לא יכולה להתבצע החלפת הקשר). הבעיה היא, שבזמן שחוט כלשהו יבצע את הקטע הקריטי שלו, אף חוט אחר לא יוכל לרוץ (גם לא לצורך ביצוע של פעולות מחוץ לקטע הקריטי). 2. Busy Wait – נגדיר משתנה x=1 בזיכרון המשותף (משתנה גלובאלי). כל חוט שיגיע לקטע הקריטי שלו:
הבעיה היא, שחוט יכול לעבור מהמתנה לריצה רק בשביל "לגלות" שהערך של x הוא עדיין 0. מצב כזה יכול לחזור על עצמו הרבה פעמים, כשבכל פעם מתבצעת החלפת הקשר ומתבזבז זמן. 3. Mutex – נגדיר אובייקט Mtx, עם ממשק של שתי פעולות אטומיות:
כל חוט יבצע את הפעולה Mtx.Wait( ) בתחילת הקטע הקריטי שלו, ואת הפעולה Mtx.Signal( ) בסופו. האובייקט Mtx ימוקם בזיכרון המשותף, וכך יוכר ע"י כל החוטים. בנוסף, הוא ישמור רשימה של החוטים שהוא הוציא להמתנה. בניגוד לשיטת ה-Busy Wait, החסימה של החוט בתחילת הקטע הקריטי לא מתבצעת בקוד של החוט עצמו ע"י המתנה "על" משתנה גלובאלי. במקום זה, היא מתבצעת ע"י בקשה ממערכת ההפעלה להוציא את החוט להמתנה. היתרון בכך הוא, שאין צורך לבצע החלפת הקשר על מנת ש"קוד ההמתנה" של החוט ירוץ במעבד. הסבר: מה שבעצם קורה כאשר Mtx מוציא חוט להמתנה, הוא שהחוט קורא לפונקציה, שבסופה הוא מבקש ממערכת ההפעלה להוציא אותו להמתנה (קריאת מערכת Block). כך שלמעשה, בעזרת מנגנון ה-Mutex, כל חוט שמגיע לקטע הקריטי כאשר חוט אחר כבר נמצא בו, מוציא את עצמו להמתנה. חוט שמסיים את הקטע הקריטי, מבקש ממערכת ההפעלה להוציא מהמתנה את החוט שנמצא בה הכי הרבה זמן (קריאת מערכת Wakeup). תשובה לשאלה 1 שלב ראשון – נעביר את כל הכדורים האדומים לתחילת המערך:
שלב שני – באופן דומה, נעביר את כל הכדורים הירוקים לסוף המערך... סיבוכיות זמן – O(N), סיבוכיות זיכרון – O(1).
תשובה לשאלה 2 על מנת להפוך רשימה מקושרת חד-כיוונית: void Node::Swap(Node* pNext) { if (pNext != NULL) { pNext->Swap(pNext->m_pNext); pNext->m_pNext = this; } }
void List::Reverse() { if (m_pHead != NULL) { m_pHead->Swap(m_pHead->GetNext()); m_pHead->SetNext(NULL); } Node* pTemp = m_pHead; m_pHead = m_pTail; m_pTail = pTemp; } על מנת להפוך רשימה מקושרת דו-כיוונית: void Node::Swap() { if (m_pNext != NULL) { m_pNext->Swap(); m_pNext->m_pNext = this; } m_pPrev = m_pNext; }
void List::Reverse() { if (m_pHead != NULL) { m_pHead->Swap(); m_pHead->SetNext(NULL); } Node* pTemp = m_pHead; m_pHead = m_pTail; m_pTail = pTemp; }
תשובה לשאלה 3 נשתמש בשני גלאים שמונחים בצורה טורית: גלאי A לפני הכניסה לאולם וגלאי B אחרי הכניסה לאולם. עבור כל גלאי נחזיק משתנה בוליאני f, שמאותחל ל-0. בנוסף, נחזיק מונה של מספר האנשים שבתוך האולם בכל רגע נתון. כאשר A מזהה תנועה:
כאשר B מזהה תנועה:
בעיה אפשרית עלולה להיווצר כאשר מישהו משנה את דעתו באמצע הדרך (בין הגלאים) וחוזר.
תשובה לשאלה 4 כאשר הזמן הנוכחי לא נמצא בין זמן ההתחלה לזמן הסיום של ה-Task, ה-Task לא קיים. כאשר הזמן הנוכחי כן נמצא בין זמן ההתחלה לזמן הסיום של ה-Task, נבצע את הבדיקה הבאה:
STATE Task::GetState(iCurrentTime) { if (m_iBeginTime<=iCurrentTime && iCurrentTime<=m_iEndTime) { int iRem=(iCurrentTime-m_iBeginTime)%(m_iRunTime+m_iPendTime); if (iRem<m_iRunTime) return RUNNING; else return PENDING; } else return NOT_ALIVE; } ההנחה היא כמובן, שה-Task תמיד מתחיל במצב ריצה. אם הוא מתחיל במצב המתנה, אז צריך להחליף את התנאי iRem<m_iRunTime בתנאי iRem>=m_iPendTime.
תשובה לשאלה 5 כדי לדעת כמה אובייקטים מסוג מסוים קיימים בכל רגע נתון, צריך להוסיף למחלקה שלהם משתנה סטאטי שסופר אותם. בכל Constructor של המחלקה צריך להגדיל את המשתנה הזה ב-1, וב-Destructor שלה צריך להקטין אותו ב-1.
תשובה לשאלה 6 המילה השמורה static מייצגת "תכונה", אשר ניתן לאפיין בעזרתה משתנים ופונקציות:
לפירוט נוסף – חלק 3 (חומר כללי: סמלים בתוכנה). תשובה לשאלה 7 נבצע N איטרציות. באיטרציה מספר i:
void RandReorder(Song* inputArray[N], Song* outputArray[N]) { for (int i=0; i<N; i++) { int index = Rand()%(N-i); outputArray[i] = inputArray[index]; Swap(inputArray,index,N-1-i); } } שיטה נוספת: באופן חד-פעמי, נחשב רשימה של כל המספרים בתחום (1,N) אשר אין להם אף מחלק משותף עם N. בכל פעם שנרצה לסדר את השירים מחדש:
לפי חוק הציקליות בחבורות (או משהו כזה), אנחנו נעבור כל שיר פעם אחת בדיוק לפני שנחזור לשיר הראשון. בעיות אפשריות: א. זמן חישוב הרשימה החלקית עלול להיות ארוך (למרות שזה לא עקרוני, כי מחשבים אותה רק פעם אחת). ב. על פני הרבה הרצות של הפונקציה, לא נקבל את כל הסידורים האפשריים של N שירים בהתפלגות אחידה (כמו בפתרון הראשון). למעשה, חלק גדול מהסידורים האפשריים לא נקבל כלל. הסיבה לכך היא: · מספר הסידורים השונים שנוכל לקבל בשיטה הזאת = גודל הרשימה החלקית < N. · מספר הסידורים השונים האפשרי עבור N שירים = 1 * 2 * … * N = N עצרת.
תשובה לשאלה 8 על מנת להבטיח שאף אחד לא יוכל ליצור באופן ישיר עצם מהסוג של מחלקה כלשהי, ישנן שתי אפשרויות: א. לשים את ה-Constructor ב-protected של המחלקה. ניתן יהיה ליצור עצמים של מחלקות שיורשות ממנה. ב. לשים את ה-Constructor ב-private של המחלקה, ולהוסיף לה פונקציה סטאטית, שיוצרת עצם מהסוג שלה ומחזירה מצביע אליו (בדומה לשיטת ה-Singleton, למעט העובדה שזה לא חייב להיות העצם היחידי מסוגה).
תשובה לשאלה 9 המנורות שיישארו דלוקות: אלה שמספר המחלקים של האינדקס שלהן הוא אי-זוגי. האינדקסים שמספר המחלקים שלהם הוא אי-זוגי: מספרים ריבועיים – 1, 4, 9, 16...
תשובה לשאלה 10 אם לא ידוע מי מתחיל, אז אין שיטה כזאת, כי זה פרדוקס (אם הייתה שיטה כזאת, אז יש סיכוי שהשחקן השני היה משתמש בה ומנצח – סתירה). השחקן הראשון שמתחיל יכול לנצח: א. את המטבע הראשון הוא צריך לשים במרכז השולחן. ב. עבור כל מטבע שהיריב שלו שם, הוא צריך לשים מטבע בצד הנגדי (בקו ישר ובמרחק שווה מהמרכז).
תשובה לשאלה 11 צריך לשים כדור אדום אחד בסל בראשון, ואת כל שאר הכדורים (אדומים ושחורים) בסל השני. נחשב את ההסתברויות הבאות:
נקבל את התוצאה:
תשובה לשאלה 12 נניח שמספר הניסיונות שצריך לבצע בשביל לגלות באיזה קומה הכדורים נשברים, הוא לכל הפחות N. על מנת להבטיח שנבצע לכל היותר N ניסיונות, נשתמש באלגוריתם הבא (החל מ k=N ועד ל k=1): 1. נעלה k קומות ונזרוק את הכדור הראשון. אם הוא נשבר, נרד k-1 קומות: · נזרוק את הכדור השני. אם הוא נשבר: גילינו את מספר הקומה. · אחרת, נעלה קומה אחת ונחזור על התהליך. 2. אחרת, נקטין את k ב-1 ונחזור על התהליך. הסבר:
o אם הוא נשבר, ננסה את הכדור השני החל מקומה 1 ועד לקומה 1-N (או עד שהוא יישבר). o סה"כ, ביצענו לכל היותר N ניסיונות (פעם עבור הכדור הראשון, 1-N פעמים עבור הכדור השני).
o אם הוא נשבר, ננסה את הכדור השני החל מקומה 1+N ועד לקומה 2-N+N (או עד שהוא יישבר). o סה"כ, ביצענו לכל היותר N ניסיונות (פעמיים עבור הכדור הראשון, 2-N פעמים עבור הכדור השני).
חישוב הערך של N עבור בניין בן 100 קומות:
תשובה לשאלה 13 את בית מספר 1 נצלם תמיד (כדי שבכל מקרה תהיה לנו תמונה, אם אין אחריו עוד בית). את בית מספר 2 נצלם בהסתברות 1/2, תוך שימוש בפונקציה Rand()%2. את בית מספר 3 נצלם בהסתברות 1/3, תוך שימוש בפונקציה Rand()%3. את בית מספר X נצלם בהסתברות X/1, תוך שימוש בפונקציה Rand()%X. נוכיח באינדוקציה שעבור N בתים, ההסתברות לקבל תמונה של כל אחד ואחד מהם היא זהה:
o לפי הנחת האינדוקציה עבור k בתים, ההסתברות לתמונה של כל אחד ואחד מהם היא זהה. ערכה של ההסתברות הזאת הוא 1/k. o לפי האלגוריתם, את בית מספר 1+k נצלם בהסתברות 1/(k+1), ולכן ההסתברות שתישאר בידינו תמונה של אחד מ-k הבתים הקודמים היא 1-1/(k+1), כלומר k/(k+1). o מכיוון שעבור k הבתים הקודמים, ההסתברות לתמונה של כל אחד ואחד מהם היא עדיין זהה, נקבל שערכה של ההסתברות הזאת הוא עכשיו [k/(k+1)]/k, כלומר 1/(k+1). o מסקנה – ההסתברות לתמונה של בית מספר k+1 זהה להסתברות לתמונה של כל אחד מ-k הבתים הקודמים. ערכה של ההסתברות הזאת הוא 1/(k+1).
תשובה לשאלה 14 אותו עקרון כמו בתשובה לשאלה 7.
תשובה לשאלה 15 פונקציות וירטואליות הן הכלי שבעזרתו (ובעזרת הורשה) ניתן ליישם Polymorphism ב-++C:
לפירוט נוסף – חלק 3 (חומר כללי: פונקציות מחלקה).
תשובה לשאלה 16 מימוש פונקציות עם מספר לא קבוע של ארגומנטים הוא דבר שימושי ב-C. ב-++C, אפשר להשתמש בערכי Default עבור הארגומנטים שהפונקציה מקבלת. חתימה של פונקציה עם מספר לא קבוע של ארגומנטים נראית כך: void func(int x, …) . הערך המוחזר של הפונקציה יכול להיות מכל סוג שהוא, וחייב להיות לפחות ארגומנט אחד מוצהר. לאחר הארגומנטים המוצהרים באות שלוש נקודות (...), שמעידות על מספר לא קבוע של ארגומנטים. בכל פעם שמתבצעת קריאה לפונקציה (במהלך ריצת התוכנית), הארגומנטים מועברים אליה במחסנית. במימוש של הפונקציה, על מנת לגשת אל הארגומנטים שמועברים אליה אבל לא מוצהרים בחתימה שלה:
למשל, אם שולחים לפונקציה מחרוזת, אז היא מקבלת את הכתובת בזיכרון שבה נמצאים התווים של המחרוזת. לדוגמא, עבור הקריאה הזאת לפונקציה: short y = 1000; int sum = func(1,y,5000,"abc"); אפשר לממש את הפונקציה כך: int func(char x, …) { short y = (short)((int*)&x+1)[0]; //y = 1000 int z = (int )((int*)&x+2)[0]; //z = 5000 char* s = (char*)((int*)&x+3)[0]; //s[0…2] = "abc" return x+y+z+s[0]; //1+1000+5000+'a' = 6098 } אפשר לממש את זה בצורה יותר נוחה בעזרת va_list, va_start, va_end, va_arg (מוגדרים בקובץ stdarg.h). החסרון העיקרי בפונקציה מהסוג הזה: מכיוון שסוגי הארגומנטים ומספרם לא ידועים, מי שמממש אותה צריך "לנחש" אותם. בפונקציה printf למשל, זיהוי סוגי הארגומנטים ומספרם מתבצע לפי המחרוזת שהיא מקבלת (בארגומנט הראשון):
הבעיה היא, שאם בקריאה לפונקציה היא מקבלת פחות ארגומנטים ממה שהיא מניחה שהיא קיבלה, היא ניגשת למקום בזיכרון שאין לו משמעות ברורה ("זבל"). בנוסף, כאשר גודל הארגומנט שנשלח שונה מהגודל שהיא מניחה שהוא, היא "יוצאת מסינכרון" לגביו ולגבי כל שאר הארגומנטים שבאים אחריו (הגודל יכול להיות 4 בתים או 8 בתים). דוגמאות: א. הרצה של printf("%d %d",5) : · הפונקציה ניגשת לאזור שלא הוגדר עבורה בזיכרון וקוראת "זבל" (או מפילה את התוכנית). ב. הרצה של printf("%d %f",1.2,3.4) : · הפונקציה מקבלת שני ארגומנטים בגודל 8 בתים ובפורמט Floating-Point כל אחד. · מ-4 הבתים הראשונים היא קוראת מספר בפורמט Fixed-Point. · מ-8 הבתים הבאים היא קוראת מספר בפורמט Floating-Point. · מ-4 בתים האחרונים היא מתעלמת. מכיוון שסוגי הארגומנטים ומספרם לא ידועים גם לקומפיילר, הוא לא ייתן אזהרות או שגיאות קומפילציה עבור קריאה לפונקציה כזאת עם ארגומנטים שאינם "חוקיים" מבחינתה (כמו בדוגמאות הנ"ל). התוצאה – שגיאות בזמן ריצה. תשובה לשאלה 17 על מנת לסנכרן בין שני החוטים, נבצע Busy Wait באופן הבא: 1. נגדיר משתנה לוקאלי y=1, שבעזרתו נדע את מספר האיטרציה שבה נמצא כל חוט. 2. נגדיר משתנה גלובאלי x=0, ונבצע עליו Busy Wait ב"נקודת ההמתנה" של כל חוט. for (int y=1; ; y++) { … … DisableInterrupts(); x++; //Load x, Inc, Store x EnableInterrupts(); while (x < y*2) { } … … } הסבר:
הערות: א. השימוש ב-Busy Wait עלול להיות בזבזני, מכיוון שבזמן שהחוט הראשון ממתין שהחוט השני יגיע לאותה נקודה, יכולות להתבצע החלפות הקשר רק לצורך בדיקת הערך של x (בקוד של החוט הראשון). ב. פעולת ההגדלה של x מורכבת מרצף של מספר פקודות מכונה, וע"מ שבמהלכה לא תוכל להתבצע החלפת הקשר, היא מוגדרת כפעולה אטומית (ע"י ניטרול הפסיקות בתחילתה ואיפשור הפסיקות בסופה).
עבור N חוטים אפשר לבצע Busy Wait באופן דומה, אבל השימוש בו יהיה הרבה יותר בזבזני מבחינת זמן, מכיוון שהפעם ייתכנו החלפות הקשר לצורך בדיקת הערך של x, בקוד של כל אחד מהחוטים שממתינים שהערך הזה יגיע ל-N. לכן, על מנת לסנכרן בין N חוטים, נבצע Priority Inversion באופן הבא: while (true) { … … DisableInterrupts(); if (x < N-1) { DecreaseThisThreadPriority(); x++; } else { IncreaseAllThreadsPriority(); x = 0; } EnableInterrupts(); … … } הסבר:
תשובה לשאלה 18 נסמן מחרוזת באורך של n תווים באופן הבא: S[1…n]. נממש פונקציה רקורסיבית, שמקבלת מחרוזת S[1…n] ומחזירה את רשימת כל הפרמוטציות שלה:
1. נקרא לפונקציה עם תת המחרוזת S[x+1…n], ע"מ לקבל את רשימת כל הפרמוטציות שלה. 2. נקבל רשימה באורך של (n-x)! מחרוזות, כל אחת באורך של n-x תווים. 3. נעבור על הרשימה, ולכל מחרוזת נוסיף את התו S(x) בכל מקום אפשרי. 4. לכל מחרוזת יש לנו n-x+1 מקומות אפשריים להוסיף את התו S(x). 5. נקבל רשימה חדשה באורך של (n-x+1)! מחרוזות, כל אחת באורך של n-x+1 תווים.
List Permute(String string) { if (string.length == 0) return EmptyStrings(1); List prevList = Permute(SubString(string,1,string.length)); List nextList = EmptyStrings(string.length*prevList.length); for (int i=0; i<prevList.length; i++) { for (int j=0; j<string.length; j++) { nextList[i*string.length+j] += SubString(prevList[i],0,j); nextList[i*string.length+j] += string[0]; nextList[i*string.length+j] += SubString(prevList[i],j,string.length-1); } } return nextList; } הערות: א. הפונקציה EmptyStrings(n) תחזיר רשימה של n מחרוזות ריקות. ב. הפונקציה SubString(str,i,j) תחזיר תת מחרוזת של str, החל מאינדקס i (כולל) ועד לאינדקס j (לא כולל).
תשובה לשאלה 19 מציאת האינדקס של המופע הראשון של תו כלשהו מ-Set ב-String:
int FirstIndex(const char* string, const char* set) { bool array[256] = {false}; for (int i=0; i<strlen(set); i++) array[set[i]] = true; for (int j=0; j<strlen(string); j++) if (array[string[j]] == true) return j; return -1; } סיבוכיות הזמן שווה לסכום אורכי הקלט. סיבוכיות הזיכרון היא כמספר התווים האפשריים. אם התווים יהיו בקוד רחב יותר, נצטרך מערך גדול יותר, ולכן סיבוכיות הזיכרון תהיה גבוהה יותר. במקרה כזה אפשר להשתמש ב-Hash Table יותר מתוחכמת (המערך הוא למעשה מימוש של Hashing ישיר). סביר להניח שכדי למצוא את המקום המתאים לתו כלשהו ב-Hash Table כזאת, נצטרך יותר מפעולה אחת. על מנת להשיג את אותה סיבוכיות זמן, נצטרך לממש טבלה שמאפשרת Hashing בעזרת מספר קבוע של פעולות (וללא כל תלות באורך הקלט). בנוסף, נצטרך לדאוג שגודל הטבלה הזאת לא יהיה תלוי במספר התווים האפשריים. אפשרות נוספת: פשוט לעבור על התווים ב-String לפי הסדר, ועבור כל תו לבדוק אם הוא נמצא ב-Set. במקרה הזה לא נצטרך זיכרון נוסף בכלל, אבל סיבוכיות הזמן תגדל מסכום אורכי הקלט למכפלת אורכי הקלט.
תשובה לשאלה 20 ע"מ לייצג את המילון בצורה יעילה אפשר להשתמש ב-Hash Table, שכל תא בה מייצג את האות הראשונה במילה. בנוסף, בכל תא תהיה Hash Table, שכל תא בה מייצג את האות השניה במילה, וכן הלאה באופן דומה. תא שמייצג את האות האחרונה במילה כלשהי יכיל גם את פירוש המילה. למעשה, המילון מיוצג באמצעות עצים: לכל אות קיים עץ שמחזיק את כל המילים שמתחילות בה. סיבוכיות הזמן של הפעולות השונות (הוספת מילה, חיפוש מילה, מחיקת מילה) תלויה בסוג ה-Hash Table שנממש. סיבוכיות הזיכרון של המילון תלויה גם היא בסוג ה-Hash Table. לדוגמא, אם נשתמש ב-Hash Table ישירה (מערך), סיבוכיות הזמן תהיה לינארית באורך הקלט. לעומת זאת, סיבוכיות הזיכרון תהיה מאד בזבזנית, מכיוון שמבנה המילון יאפשר קיום של כל קומבינציה אפשרית בכל אורך שהוא (עד גבול מסוים שיוגדר מראש). ע"מ למצוא במילון את כל המילים שהן פרמוטציות של מילה מסוימת, ישנן שתי אפשרויות: א. נשתמש בפונקציה שתוארה בתשובה לשאלה 18, ונבדוק עבור כל פרמוטציה שהפונקציה מחזירה אם היא נמצאת במילון. הבעיה היא, שנצטרך לעבור על כל הפרמוטציות האפשריות של המילה, גם אם רובן לא נמצאות במילון. ב. נתאים לכל אות מספר ראשוני ייחודי, ולכל מילה את מכפלת המספרים שמייצגים את האותיות שלה. בגלל שכולם ראשוניים, מובטח לנו מספר ייחודי עבור כל מילה והפרמוטציות שלה. נבצע מעבר חד-פעמי על המילון ונשמור כל קבוצת פרמוטציות במערך, כאשר המספר שמייצג את הקבוצה הוא האינדקס שלה במערך. הבעיה היא, שזה לא כל כך מעשי, כי המספרים שמייצגים את המילים יכולים להיות עצומים.
תשובה לשאלה 21 ישנם סה"כ 4096 רצפים אפשריים: 4096 = 12^2. כאמור, כל אופרנד הוא באורך 3 ביטים. עבור 4 פעולות שמקבלות שלושה אופרנדים כל אחת, דרושים לנו 2048 רצפים שונים: 2048 = (3*3)^2 * 4. עבור 255 פעולות שמקבלות אופרנד אחד כל אחת, דרושים לנו 2040 רצפים שונים: 2040 = (3*1)^2 * 255. עבור 16 פעולות שלא מקבלות אופרנדים כלל, דרושים לנו 16 רצפים שונים: 16 = (3*0)^2 * 16. סה"כ דרושים לנו 4104 רצפים שונים – יותר ממספר הרצפים האפשריים, ולכן לא ניתן לתכנן מעבד כזה. תנאי עבור המקרה הכללי: אסור שהסכום ∑[Ki * 2^(Pi*Li)] יהיה יותר גדול ממספר הרצפים האפשריים.
תשובה לשאלה 22 קידוד העץ לקובץ:
הערה – כאשר לצומת יש פחות משני בנים, נרשום 0 (במקום מספר סידורי) עבור כל בן שחסר לו. פענוח הקובץ לעץ:
הערה – מכיוון שקודדנו את העץ בשיטת Pre-Order, כתובתו של השורש תהיה במקום הראשון במערך.
תשובה לשאלה 23 מחלקה אבסטרקטית זאת מחלקה שיש בה פונקציות וירטואליות טהורות, ולכן אי אפשר ליצור עצמים מהסוג שלה. הפונקציות הווירטואליות של מחלקה כזאת מגדירות ממשק גנרי, אשר מחלקות שנגזרות (יורשות) ממנה צריכות לממש.
תשובה לשאלה 24 פונקציה וירטואלית: א. במחלקה שבה היא מוגדרת – חייבים לממש אם רוצים לאפשר יצירה של עצמים מסוגה. ב. במחלקות שיורשות ממנה – לא חייבים לממש (אפשר ליצור עצמים מסוגן בכל מקרה). פונקציה וירטואלית טהורה: א. במחלקה שבה היא מוגדרת – לא חייבים לממש (אי אפשר ליצור עצמים מסוגה בכל מקרה). ב. במחלקות שיורשות ממנה – חייבים לממש אם רוצים לאפשר יצירה של עצמים מסוגן.
תשובה לשאלה 25 Copy Constructor זה פונקצית מחלקה, שמקבלת עצם מסוג המחלקה By Reference. קריאה ל-Constructor הזה מתבצעת כאשר מאתחלים עצם בשורת ההצהרה (לדוגמא, A a2=a1), וכאשר שולחים לפונקציה כלשהי או מחזירים מפונקציה כלשהי עצם By Value (בשני המקרים האלה, ה-Copy Constructor יוצר עצם חדש במחסנית הפונקציה). כאשר ה-Copy Constructor של מחלקה כלשהי לא מוגדר באופן מפורש ע"י המתכנת, הקומפיילר מגדיר אותו בתור ברירת מחדל. במקרה כזה, ה- Copy Constructorפשוט מעתיק את השדות של העצם שהוא מקבל (לתוך העצם שלו). אם חלק מהשדות האלה הם מצביעים לזיכרון, אז שני העצמים מתייחסים לאותו אזור בזיכרון ועלולים לבצע עליו את אותן פעולות. לדוגמא, כאשר מדובר בזיכרון שהוקצה בצורה דינאמית, שני העצמים עלולים לשחרר את אותו הזיכרון.
תשובה לשאלה 26 כאשר הקומפיילר עובר על הקוד ומתרגם אותו לפקודות מכונה:
כאשר מופיעה בקוד קריאה לפונקציה וירטואלית באמצעות מצביע לאובייקט כלשהו, הקומפיילר לא יודע איזה פונקציה בשרשרת ההורשה צריכה להתבצע, מכיוון שהסוג המדויק של האובייקט המוצבע נקבע רק בזמן ריצה. במקרה כזה, הקומפיילר לא יכול לתרגם את הקריאה לפונקציה לפקודת קפיצה לכתובת. הפתרון – V-Table:
לפירוט נוסף – חלק 3 (חומר כללי: פונקציות מחלקה).
תשובה לשאלה 27 Singleton – תכן של מחלקה (Design Pattern), שמאפשר ליצור רק עצם אחד מסוגה בכל המערכת. בקובץ ה-h נרשום: class MyClass { public: static MyClass* CreateInstance(…); private: MyClass(…); static MyClass* m_pInstance; }; בקובץ ה-cpp נרשום: MyClass* MyClass::m_pInstance = NULL; MyClass* MyClass::CreateInstance(…) { if (m_pInstance == NULL) m_pInstance = new MyClass(…); return m_pInstance; } הערות: א. מכיוון שה-Constructor של המחלקה נמצא ב-private: אי אפשר ליצור עצם מסוגה בצורה מפורשת, או לרשת אותה וליצור עצם של מחלקה שנגזרת ממנה. ב. המשתנה הסטאטי של המחלקה יצביע לעצם היחיד מסוגה: הפונקציה הסטאטית של המחלקה תיצור עצם חדש פעם אחת, ותחזיר מצביע אליו בכל פעם שתיקרא.
תשובה לשאלה 28 סמאפור זה מושג כללי, ו-Mutex זה סוג ספציפי של סמאפור:
תשובה לשאלה 29 תקשורת בין תהליכים:
תקשורת בין חוטים:
לפירוט נוסף – חלק 3 (חומר כללי: ניהול תהליכים וחוטים).
תשובה לשאלה 30 פונקציה שמקבלת שתי מחרוזות ומשווה ביניהן: bool strcmp(const char* str1, const char* str2) { int i; for (i=0; str1[i]!=0 && str2[i]!=0; i++) if (str1[i] != str2[i]) return false; return str1[i] == str2[i]; }
תשובה לשאלה 31 ממשק של פונקציות עבור תור (FIFO): void Create(Queue* pQueue); void Destroy(Queue* pQueue); bool IsFull(const Queue* pQueue); bool IsEmpty(const Queue* pQueue); bool Insert(Queue* pQueue, Item* pItem); bool Extract(Queue* pQueue, Item** pItem);
תשובה לשאלה 33 Mutex זה סמאפור בינארי עם תכונה ייחודית, שנועדה לצורך הגנה על קטע קוד קריטי:
תשובה לשאלה 34 הבדלים בין תהליך (Process) לחוט (Thread): א. תהליך לא יכול לגשת לשום חלק במרחב הזיכרון של תהליכים אחרים. חוט יכול לגשת לזיכרון הגלובאלי של חוטים אחרים ששייכים לאותו תהליך. ב. תקשורת בין תהליכים יכולה להתבצע רק בעזרת משאבים של מערכת ההפעלה. תקשורת בין חוטים ששייכים לאותו תהליך יכולה להתבצע גם דרך הזיכרון הגלובאלי. ג. הגנה על תהליך מפני פעולות של תהליכים אחרים היא באחריות מערכת ההפעלה בלבד. הגנה על חוט מפני פעולות של חוטים אחרים ששייכים לאותו תהליך היא באחריות המתכנת. ד. החלפת הקשר בין תהליכים כוללת את התוכן של מרחב הזיכרון של כל תהליך ואת ערכי הרגיסטרים. החלפת הקשר בין חוטים ששייכים לאותו תהליך כוללת רק את המחסנית של כל חוט ואת ערכי הרגיסטרים. לפירוט נוסף – חלק 3 (חומר כללי: ניהול תהליכים וחוטים).
תשובה לשאלה 35 פונקציה שמקבלת תו ובודקת אם הוא נמצא במערך של מיליון תווים: bool check(char c) { for (int i=0; i<N; i++) //Push i, Push N, Compare, Push i, Inc, Pop i if (arr[i] == c) //Push arr, Push i, Add, Load, Push c, Compare return true; return false; } אפשר לחסוך את קריאת הערך של i פעם נוספת בכל איטרציה: bool check(char c) { char* end = arr+N; for (char* ptr=arr; ptr!=end; ptr++) if (*ptr == c) //Push ptr, Load, Push c, Compare (removed "Push i, Add") return true; return false; } אפשר לחסוך את השוואת הערך של i עם מיליון בכל איטרציה: bool check(char c) { char x = arr[N-1]; if (x == c) return true; arr[N-1] = c; for (int i=0; ; i++) //Push i, Inc, Pop i (removed "Push i, Push N, Compare") if (arr[i] == c) break; arr[N-1] = x; return i<N-1; } אפשר כמובן לשלב בין שתי האפשרויות.
תשובה לשאלה 36 נניח שהנהר, החוואי והפרה ממוקמים באופן הבא:
החוואי והפרה ממוקמים בנקודות קבועות. החוואי צריך ללכת אל הפרה דרך הנקודה (x,0), שנמצאת על גדת הנהר. לכן, אפשר לתאר את המרחק שהחוואי צריך ללכת כפונקציה של הנקודה הנ"ל: f(x) = √(x²+n²) + √((p-x)²+q²). על מנת למצוא את המרחק המינימלי שהחוואי צריך ללכת, אפשר לגזור את הפונקציה ולהשוות את הנגזרת לאפס. הבעיה היא שהנגזרת של הפונקציה היא די מסובכת, וקשה למצוא את הערך של x שבו היא מתאפסת. במקום זה, נסתכל על ה"השתקפות" של החוואי והפרה ביחס לגדת הנהר שקרובה אליהם:
נעביר קו ישר בין החוואי וה"השתקפות" של הפרה. נקודת החיתוך של הקו הזה עם גדת הנהר, היא הנקודה שאליה החוואי צריך ללכת. משוואת הישר: n = a*0+b , -q = a*p+b è b = n , a = -(q+n)/p è y = -(q+n)/p*x+n נקודת החיתוך: y = -(q+n)/p*x+n , y = 0 è -(q+n)/p*x+n = 0 è x = n*p/(q+n) è [n*p/(q+n) , 0]
תשובה לשאלה 37 נתונה צורה כאוסף של קודקודים. נחשב באופן חד-פעמי את המשוואות של כל אחת מהצלעות שלה. בהינתן נקודה כלשהי, צריך לבדוק אם היא נמצאת בתוך הצורה, מחוץ לצורה או על השפה של הצורה: א. אם קיימת צלע, אשר נקודת הקלט מקיימת את המשוואה שלה וגם נמצאת בין שני הקודקודים שלה, אז נקודת הקלט נמצאת על השפה של הצורה. אחרת, היא נמצאת בתוך הצורה או מחוץ לצורה. ב. נעביר דרך נקודת הקלט ישר שמקביל לציר ה-X, ונבחר נקודה על הישר שנמצאת מחוץ לצורה (נקודה שקואורדינטת ה-X שלה קטנה מקואורדינטות ה-X של כל קודקודי הצורה). ג. נסרוק את הישר החל מאותה נקודה ועד לנקודת הקלט, ונספור כמה פעמים הוא חותך את צלעות הצורה (נתעלם מצלעות שנמצאות בדיוק על הישר). ד. אם ספרנו מספר אי-זוגי של פעמים, אז נקודת הקלט נמצאת בתוך הצורה, ואם ספרנו מספר זוגי של פעמים, אז נקודת הקלט נמצאת מחוץ הצורה. לדוגמא, בשרטוט הבא נקודת הקלט נמצאת בתוך הצורה, כי הישר שעובר דרכה חותך את הצורה שלוש פעמים:
תשובה לשאלה 38 רשימת הערכים שאיתה מאתחלים את המערך תהיה חלק מקוד התוכנית (קובץ ה-Image) בכל מקרה. אם המערך יוגדר בתוך הפונקציה, אז קוד הפונקציה יכיל (בנוסף לערכים) גם פקודות של השמת ערכים לתוך המערך. אם המערך יוגדר מחוץ לפונקציה, אז רשימת הערכים שלו תשב ב-Data Section ותיטען לזיכרון ביחד עם קוד התוכנית. כלומר, הקוד לא יכלול את פקודות ההשמה ולכן גודל התוכנית יהיה קטן יותר. בנוסף, הפונקציה לא תאתחל את המערך בכל פעם שהיא תיקרא, ולכן גם תרוץ מהר יותר.
תשובה לשאלה 39 נמלא מערך במספרים 0 עד N-1 (לפי הסדר), ונבצע N איטרציות. באיטרציה מספר i נחשב מספר אקראי j, ונחליף בין האיבר שיושב במקום ה-i לאיבר שיושב במקום ה-j: for (i=0; i<N; i++) array[i] = i; for (i=0; i<N; i++) Swap(array,i,Rand()%N);
תשובה לשאלה 40 נשתמש בטבלת עזר (תכנון דינאמי) – בכל משבצת בטבלת העזר נרשום את הסכום הכי גדול של מסלול כלשהו שמסתיים במשבצת שמקבילה לה בטבלה המקורית:
סיבוכיות זמן – O(N^2), סיבוכיות זיכרון – O(N^2).
תשובה לשאלה 42 נבנה גרף באופן הבא:
בהינתן שני זמרים x ו-y:
תשובה לשאלה 43 המשימה: צריך לממש פונקציה שמקצה 8 בתים כל עוד יש מקום פנוי בזיכרון, ופונקציה שמשחררת 8 בתים. הבעיה: צריך לעקוב אחרי המקומות הפנויים בזיכרון. בהתחלה כולו פנוי, אבל בהמשך יכולים להיווצר "חורים". שיטת העבודה:
מכיוון שגודל הזיכרון הוא 1MB, כל כתובת היא באורך של 20 ביטים, ולכן ניתנת לשמירה בשטח של 8 בתים.
מבנה הנתונים:
פונקציה להקצאת הזיכרון: void* malloc() { void* p = (void*)listHead; listHead = (dword*)(*listHead); return p; } פונקציה לשחרור הזיכרון: void free(void* p) { *((dword*)p) = listHead; listHead = (dword*)p; }
תשובה לשאלה 44 כאשר תוכנית מכילה משתנים או אובייקטים גלובאליים, האתחול שלהם חייב להתבצע לפני שהפונקציה main נקראת. אתחול של משתנה גלובאלי בערך ידוע מראש (לדוגמא, int x=5), כלל לא מתורגם לקוד. ערך כזה "מוטמע" בתוכנית (כחלק מקובץ ה-Image) ונטען איתה לזיכרון כאשר היא מתחילה לרוץ. אתחול של משתנה גלובאלי בערך שאינו ידוע מראש (לדוגמא, int z=x+y), מתורגם לקוד שמתבצע אחרי שהתוכנית נטענת לזיכרון ולפני שהפונקציה main נקראת. גם הצהרה על אובייקט גלובאלי אשר מוגדר עבורו Constructor, מתורגמת לקוד שמתבצע כבר בשלב הזה. לסיכום, תוכנית שנכתבה ב-C או ב-++C, לא בהכרח מתחילה לרוץ מהפונקציה main.
תשובה לשאלה 45 הבדלים שחשוב להתייחס אליהם במהלך כתיבת קוד גנרי:
o מעבדי Little Endian מתייחסים לבית הראשון ביחידה כ-LSB ולבית האחרון ביחידה כ-MSB. o מעבדי Big Endian מתייחסים לבית הראשון ביחידה כ-MSB ולבית האחרון ביחידה כ-LSB.
o ישנם קומפיילרים שמתייחסים לביט הראשון במבנה כ-LSB ולביט האחרון במבנה כ-MSB. o ישנם קומפיילרים שמתייחסים לביט הראשון במבנה כ-MSB ולביט האחרון במבנה כ-LSB. שני ההבדלים האלה יכולים להיות משמעותיים בעיקר כאשר מדובר בקידוד ופענוח של נתונים שעוברים בתקשורת. נקודה נוספת שחשוב להתייחס אליה, היא הגודל שהקומפיילר מקצה לטיפוסים שונים (כמו char, short, int, long). תשובה לשאלה 46 מימוש הפונקציה: void memcopy(void* dst, void* src, int len) { for (int i=0; i<len; i++) ((byte*)dst)[i] = ((byte*)src)[i]; } אפשר לשפר את זמן הריצה של הפונקציה בכמה דרכים: א. שימוש בטיפוס יותר גדול מ-byte (לדוגמא, word או dword), על מנת לבצע מספר קטן יותר של איטרציות. דבר כזה יחייב שמספר הבתים (len) יתחלק בשלמות בגודל של הטיפוס, וגם שהמצביעים (src ו-dst) יהיו Aligned לגודל של הטיפוס, או שהמעבד יוכל לבצע Unaligned Load/Store במידה והם לא. ב. קידום של המצביעים src ו-dst במקום שימוש באינדקס i, על מנת לחסוך את קריאת הערך שלו בכל איטרציה. כלומר, רצף הפקודות [Push ptr, Push i, Add, Load] יוחלף ברצף הפקודות [Push ptr, Load, Load], עבור כל אחד מהמצביעים הנ"ל. מצבים שבהם הפונקציה לא תעתיק את הנתונים במדויק, יכולים להתרחש כאשר:
תשובה לשאלה 47 Context Switch בין Task'ים לא יכול להתבצע כאשר הפסיקות מנוטרלות.
תשובה לשאלה 48 כאשר בפונקציה רשום a=b, לא תמיד נוכל לדעת בוודאות מהו הערך של a, מכיוון שלא ידוע איך הפונקציה נקראה (ע"י איזה Task ועם איזה פרמטרים). על מנת להבטיח שתמיד נוכל לדעת בוודאות מהו הערך של a, נצטרך להתייחס לקטע הקוד הזה (a=b) כאל קטע קוד קריטי, ולהגן עליו בהתאם. ישנן מספר אפשרויות: א. ניטרול ואיפשור הפסיקות (Disable/Enable Interrupts). ב. המתנה על משתנה גלובאלי אחר (Busy Wait). ג. שימוש בסמאפור ייעודי (Mutex). כאשר בפונקציה רשום b=a: אותה תשובה, אלא אם כן הערך של a נשאר קבוע במשך כל התוכנית. לפירוט נוסף – חלק 3 (חומר כללי: ניהול תהליכים וחוטים).
תשובה לשאלה 49 בפונקציה הנתונה בשאלה קיימות שתי בעיות: א. הפונקציה מחזירה את הכתובת שבה נמצא המערך buff. מכיוון שהמערך הזה מוקצה על המחסנית של הפונקציה (הקצאה סטאטית), הוא "מפסיק להתקיים" כאשר הפונקציה מסתיימת, ולכן הכתובת שתוחזר לא תכיל ערכים מוגדרים (אלא "זבל"). ב. הפונקציה מעתיקה לתוך המערך buff את המחרוזות שמוצבעות ע"י first ו-last. אם סכום האורכים של המחרוזות האלה הוא יותר גדול מהאורך של buff, אז הפעולה הזאת תגרום לדריסת זיכרון. אפשר לפתור את שתי הבעיות ע"י הקצאה דינאמית: char* buff = new char[strlen(first)+strlen(last)+1] .
תשובה לשאלה 50 התהליך של קפיצה לשגרת פסיקה וחזרה ממנה, מתבצע באופן דומה לתהליך של קפיצה לפונקציה וחזרה ממנה:
בדרך כלל, פקודת החזרה משגרת פסיקה נקראת RetI ופקודת החזרה מפונקציה נקראת RetF.
תשובה לשאלה 51 על מנת לנתק צומת מרשימה מקושרת, צריך לחבר את הצומת שקודם לו לצומת שבא אחריו. על מנת לבצע את זה ב-(1)O, מספיק לדעת מהו הצומת שקודם לו, וממנו אפשר להגיע ב-(1)O גם לצומת שבא אחריו. מכיוון שהרשימה המקושרת היא חד-כיוונית ולא ניתן למצוא את הצומת הקודם ב-(1)O, נעביר את הבעיה לצומת הבא. נשמור באופן זמני את הנתונים של הצומת הבא, נמחוק אותו ונעתיק אותם אל הצומת הנוכחי. void Cut(Node* curr) { Node temp = *(curr->next); free(curr->next); *curr = temp; } הסבר: הפונקציה לא מוחקת "פיזית" את הצומת המבוקש, אלא מעבירה אליו את התוכן של הצומת הבא אחריו (שאותו הפונקציה כן מוחקת "פיזית"). התוצאה הסופית היא רשימה מקושרת, ש"נראית" כאילו הצומת המבוקש נמחק ממנה.
תשובה לשאלה 52 נתונה רשימה מקושרת חד-כיוונית. נבדוק אם יש בה מעגל, באופן הבא:
bool SearchLoop(Node* head) { Node temp; while (head!=&temp && head!=NULL) { Node* next = head->next; head->next = &temp; head = next; } return head == &temp; } הערות: א. סיבוכיות הזמן של האלגוריתם היא (N)O. ב. פירוט של שיטות אחרות לפתרון הבעיה, אפשר למצוא בתשובה לשאלה 84.
תשובה לשאלה 55 התוכנית הנתונה בשאלה תדפיס 42, מכיוון שהמשתנה x שהפונקציה func מקבלת הוא משתנה מקומי, ולכן שינוי הערך שלו לא ישפיע על הערך של המשתנה שנשלח אליה מהפונקציה main (הכתובת של המשתנה y). הבעיה בתוכנית, היא שהפונקציה func מקצה זיכרון וכותבת בו (באמצעות המשתנה המקומי x) את הערך 17. כאשר היא מסתיימת, המצביע "נאבד" ולא ניתן לשחרר את הזיכרון שהוקצה (התוצאה – דליפת זיכרון).
תשובה לשאלה 56 הפונקציה הנתונה בשאלה, מבצעת את הפעולות הבאות:
כלומר, היא מקצה זיכרון במקום אחד ומשחררת זיכרון ממקום אחר.
תשובה לשאלה 57 מכיוון שהמשתנה a הוא משתנה מקומי בפונקציה func, הוא יתקיים בנפרד בכל Thread: ב-Thread הראשון הערך שלו יהיה 1, וב-Thread השני הערך שלו יהיה 2.
תשובה לשאלה 58 אפשרות ראשונה:
אפשרות שניה:
תשובה לשאלה 59 שיטות לבדוק מהי "צריכת ה-Stack" המקסימלית: א. אפשר למלא את ה-Stack בערך קבוע כלשהו, להריץ את התוכנית הרבה פעמים ולמצוא את גודל השטח שכבר לא מכיל את הערך הזה. לדוגמא: for (int i=0; i<STACK_SIZE; i++) SP[i]=0x12345678 . ב. אפשר לשמור את הערך המקסימלי של ה-Stack Pointer במספר מקומות בתוכנית, להריץ אותה הרבה פעמים ולמצוא את הערך המקסימלי מבין כל אלה שהתקבלו. לדוגמא: if (MaxSP<SP) MaxSP=SP .
תשובה לשאלה 61 כאשר פונקצית מחלקה מבצעת delete this, מערכת ההפעלה מנסה לשחרר את שטח הזיכרון שבו נמצא האובייקט, שבאמצעותו הפונקציה נקראה. אם שטח הזיכרון הזה לא הוקצה בצורה דינאמית, אז סביר להניח שהתוכנית תקרוס. כלומר, למעשה ניתן לקרוא לפונקציה כזאת רק באמצעות אובייקט שהוקצה בצורה דינאמית.
תשובה לשאלה 62 העברת משתנה By Reference היא מעין "הכלאה" של העברת משתנה By Value והעברת משתנה By Pointer:
יש לשיטה הזאת מספר יתרונות: א. ביצוע Casting בצורה "בטוחה" – כאשר משתנה מועבר כמצביע, ניתן לבצע עליו Casting למצביע מכל סוג אחר, בלי שיתקבלו שגיאות או אזהרות בזמן קומפילציה. כתוצאה מכך, עלולות להיות שגיאות בזמן ריצה. ב. הגדרת Copy Constructor – אפשרית רק כאשר הוא מקבל את האובייקט By Reference. העברת האובייקט By Value תהיה שקולה לקריאה רקורסיבית ל-Copy Constructor (כי האובייקט יווצר מחדש במחסנית). ג. יצירת מחלקות Template – פניה לאובייקט שמועבר By Reference נכתבת בקוד כמו פניה לאובייקט שמועבר By Value. הדבר הזה מאפשר לכתוב קוד אחיד וליצור Template'ים עבור שני הסוגים (בלי "כוכבית" או "חץ").
תשובה לשאלה 63 על מנת שאובייקט מסוג D יכיל אובייקט אחד מסוג A, צריך להגדיר את מחלקות B ו-C באופן הבא:
על מנת שאובייקט מסוג D יכיל שני אובייקטים מסוג A, צריך להגדיר את מחלקות B ו-C באופן הבא:
כאשר אובייקט מסוג D מכיל שני אובייקטים מסוג A, הגישה לכל אחד מהם צריכה להתבצע באופן הבא:
בדוגמא הנ"ל, var ו-func הם משתנה ופונקציה של מחלקה A, והגישה אליהם מתבצעת דרך מחלקות B ו-C.
תשובה לשאלה 64 פונקציה שהופכת מטריצה של מספרים, ללא שימוש בזיכרון נוסף: void Transpose(int** matrix, int n) { for (int i=0; i<n; i++) { for (int j=i; j<n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } }
תשובה לשאלה 65 תקלה מתרחשת במצב הבא:
על מנת לזהות תקלה, תחנה B צריכה:
בכל פעם שתחנה A שולחת Msg חדש, תחנה B צריכה:
בכל פעם שתחנה H מחזירה Ack חדש, תחנה B צריכה:
על מנת שמציאת Msg תוכל להתבצע ב-O(1), תחנה B צריכה:
הערה: תחנה B צריכה להתייחס ל-Msg'ים ול-Ack'ים רק באמצעות המספרים המזהים שלהם.
תשובה לשאלה 66 הבעיה במצב המתואר בשאלה, היא ש-A עלול להמתין ש-C יסיים להשתמש במשאב המשותף, בזמן ש-B מונע מ-C לרוץ כי הוא בעדיפות גבוהה יותר. כלומר, B עלול בצורה עקיפה למנוע מ-A לרוץ, למרות שהוא בעדיפות נמוכה יותר. הפתרון הוא לבצע Priority Inversion: לפני ש-C ניגש אל המשאב המשותף, הוא צריך להעלות את העדיפות שלו, כך שהיא תהיה מעל העדיפות של B ומתחת לעדיפות של A. כאשר C מסיים להשתמש במשאב המשותף, הוא צריך להחזיר את העדיפות שלו לערך המקורי שלה.
תשובה לשאלה 67 מציאת המיקום של הביט השלישי שערכו 1, ברגיסטר של 32 ביטים: int FindThird1(int reg) { int count = 0; for (int i=0; i<32; i++) { count += (reg>>i)&1; if (count == 3) return i; } return -1; } שיפור זמן הריצה של הפונקציה – נחשב באופן חד-פעמי את המערכים הבאים:
מציאת המיקום של הביט השלישי שערכו 1 (בעזרת המערכים הנ"ל): int FindThird1Fast(int reg) { int count = 0; int* Locations[4] = {NULL, First1, Second1, Third1}; for (int n=0; n<4; n++) { int unit = (byte)(reg>>(8*n)); if (count + NumOf1s[unit] < 3) count += NumOf1s[unit]; else return 8*n+Locations[3-count][unit]; } return -1; } הסבר:
תשובה לשאלה 68 נכין רשימה ממוינת לפי זמני ההתחלה של ה-Task'ים, ורשימה ממוינת לפי זמני הסיום של ה-Task'ים. נעדכן מונה שיספור את מספר Task'ים שרצו בכל רגע נתון, ומשתנה שישמור את הערך המקסימלי של המונה הזה. נעבור על הרשימה הראשונה, ובאיטרציה מספר X:
סיבוכיות זמן (כאשר מספר ה-Task'ים במערכת הוא N): · את סעיף 2 ניתן לבצע בעזרת חיפוש בינארי, כלומר ב-O(log(N)). · את שני הסעיפים האחרים ניתן לבצע ב-O(1). · סה"כ – O(N*log(N)).
תשובה לשאלה 71 החבר צריך לשלוח לך מנעול קפיצי פתוח. אתה צריך לשים את המכתב בתוך מזוודה, לנעול אותה עם המנעול הקפיצי ולשלוח אליו חזרה.
תשובה לשאלה 72 נסמן:
ידוע לנו:
ולכן נובע:
אם נרצה שיתקיים:
אז נצטרך שיתקיים:
וזה בלתי אפשרי (לנסוע חזרה ב"אפס זמן").
תשובה לשאלה 73
הערה: באפשרות הראשונה תיתכן גלישה במהלך החישובים, אבל היא לא תשפיע על התוצאה הסופית.
תשובה לשאלה 74 אלגוריתם לסידור המשתנים בסדר עולה: 1. נבנה לפי הטבלה גרף, שבו כל צומת מייצג משתנה כלשהו, ולכל שני צמתים שמייצגים X ו-Y, אם Y>X אז יש קשת מ-X ל-Y. כמובן שלא יכולים להיות מעגלים בגרף, כי לא יכול להיות מצב שבו …<X>Z>Y>X. בהנחה שלכל זוג משתנים נתון בטבלה היחס ביניהם, נקבל גרף של רכיב אחד (ולא של מספר רכיבים בלתי קשירים). 2. נבצע על הגרף מיון טופולוגי באופן הבא: א. נקצה רשימה שבה נרשום את המשתנים בסדר עולה, נבחר צומת כלשהו ונבצע חיפוש לעומק (DFS). ב. כל פעם ש"נסיים" צומת (לאחר שעברנו על כל הקשתות שיוצאות ממנו), נכניס אותו לתחילת הרשימה. הערה: המיון הטופולוגי אפשרי, מכיוון שאין מעגלים בגרף.
תשובה לשאלה 75 האסירים מחלקים לעצמם מספרים בין 1 ל-N, וקובעים ביניהם מה כל אסיר צריך לעשות כאשר הוא יוצא החוצה. בנוסף, לפני שהמנהל מחזיר אותם לתאים, הם דואגים שהמנורה תהיה כבויה.
תשובה לשאלה 76 אפשר לגלות מי הם שני המספרים החסרים, גם אם אחד מהם הוא המינימום או אחד מהם הוא המקסימום (או גם וגם). בנוסף, אפשר לעשות את זה במעבר אחד על המערך (אז אולי חסרים תנאים מגבילים בשאלה הזאת): 1. נעבור על המערך ונחשב את סכום המספרים שלו ואת מכפלת המספרים שלו (נסמן S0 ו-P0 בהתאמה). 2. מכיוון ש-m ו-n ידועים, ניתן לחשב את הסכום ואת המכפלה של כל המספרים בתחום [m,…,m+n+1]. 3. נחשב את סכום שני המספרים שחסרים ואת מכפלת שני המספרים שחסרים (נסמן S ו-P בהתאמה): S = ∑[m,…,m+n+1] – S0 , P = ∏[m,…,m+n+1] – P0 . 4. נסמן את שני המספרים שחסרים x1,x2. מתקיים: x1 + x2 = S וגם x1 * x2 = P . 5. קיבלנו שתי משוואות בשני נעלמים, ומכאן הפתרון הוא פשוט: x1,x2 = [-S ± √(S²-4P)] / -2 . הערה: עברנו על המערך בסך הכל פעם אחת בלבד (בשלב מספר 1).
תשובה לשאלה 77 מכיוון שיש 4 מתגים שכל אחד מהם נמצא באחד מ-2 מצבים (On או Off), ישנם סה"כ 16 מצבים אפשריים לשולחן כולו, כאשר ב-2 מתוכם הנורה דולקת. נשייך את 2 המצבים האלה לקבוצה אחת, ונחלק את 14 המצבים הנותרים לקבוצות של מצבים שהם סימטריים זה לזה (ביחס לשולחן):
המטרה היא למצוא רצף של פעולות, שיביא כל אחד מהמצבים בקבוצות A, B, C ו-D למצב כלשהו בקבוצה N: · עבור קבוצה A קיימת פעולה X, שמעבירה כל אחד מהמצבים בה למצב כלשהו בקבוצה N. · לכן, מספיק למצוא רצף של פעולות, שיביא כל אחד מהמצבים בקבוצות B, C ו-D למצב כלשהו בקבוצות A או N. · עבור קבוצה B קיימת פעולה Y, שמעבירה כל אחד מהמצבים בה למצב כלשהו בקבוצות A ו-N. · לכן, מספיק למצוא רצף של פעולות, שיביא כל אחד מהמצבים בקבוצות C ו-D למצב כלשהו בקבוצות A, B או N. · עבור קבוצות C ו-D קיימת פעולה Z, שמעבירה כל אחד מהמצבים בהן למצב כלשהו בקבוצות A, B או N. נגדיר את הפעולות הנ"ל, אשר מתוכן נבצע אחת בכל שלב (לאחר שהמפסק הראשי יורד):
נגדיר את סדר הפעולות (משמאל לימין) אשר במהלכו או בסיומו הנורה תדלוק, בלי קשר למצב ההתחלתי של השולחן:
תשובה לשאלה 78 נתייחס לסודוקו כאל טבלה של 9 שורות, שבכל אחת ישנן 9 משבצות. בכל שורה נתחיל במשבצת אחרת, ונמלא את המספרים 1 עד 9 לפי הסדר:
הנוסחא הכללית: Table[i][j] = ( ( i * 6 - i / 3 + j ) % 9 ) + 1 סימון: Table – טבלה של 9 × 9 משבצות, i,j – אינדקסים בין 0 ל-8
תשובה לשאלה 79 קיימים שלושה סוגים של סוגריים: ( ), [ ], { }. נחלק את הסוגים השונים לשתי קבוצות: א. סוגרים שמאליים הם כאלה שמתחילים סוגריים: ), ], }. ב. סוגרים ימניים הם כאלה שמסיימים סוגריים: (, [, {. על מנת לבדוק אם ביטוי שמכיל את שלושת הסוגים הוא חוקי:
o כאשר ניתקל בסוגר שמאלי, נכניס אותו למחסנית (פעולת Push). o כאשר ניתקל בסוגר ימני, נבדוק אם המחסנית ריקה. אם כן, נפסיק את סריקת הביטוי ונכריז שהוא לא חוקי. אחרת, נוציא את האיבר האחרון שהכנסנו למחסנית (פעולת Pop) ונבדוק אם הוא סוגר שמאלי מאותו סוג. אם לא, נפסיק את סריקת הביטוי ונכריז שהוא לא חוקי.
אם קיים סוג רביעי של סוגריים, שבו אין הבדל בין סוגר שמאלי לסוגר ימני: | |, אז כאשר ניתקל בסוגר מהסוג הזה, לא נוכל לדעת אם לבצע Push או Pop. לכן, נוציא את האיבר האחרון שהכנסנו למחסנית ונבדוק אם הוא מאותו סוג. אם לא, נכניס אותו בחזרה למחסנית, ובנוסף נכניס גם את הסוגר שניתקלנו בו למחסנית.
תשובה לשאלה 80 עבור N=1, נקבל שטח בגודל 2×2 ללא המשבצת הימנית התחתונה, שאותו נוכל לרצף
באמצעות הצורה
עבור N=2, נקבל שטח בגודל 4×4 ללא המשבצת הימנית התחתונה, שאותו נוכל לרצף
באמצעות הצורות
נניח שניתן לרצף שטח בגודל N^2 × N^2 ללא המשבצת הימנית התחתונה, עבור N=k. נוכיח שניתן לרצף שטח בגודל N^2 × N^2 ללא המשבצת הימנית התחתונה, עבור N=k+1:
o את חלק מספר 1 נמקם בפינה השמאלית העליונה, כך שהמשבצת החסרה תהיה בפינה הימנית התחתונה שלו. o את חלק מספר 2 נמקם בפינה הימנית העליונה, כך שהמשבצת החסרה תהיה בפינה השמאלית התחתונה שלו. o את חלק מספר 3 נמקם בפינה השמאלית התחתונה, כך שהמשבצת החסרה תהיה בפינה הימנית העליונה שלו. o את חלק מספר 4 נמקם בפינה הימנית התחתונה, כך שהמשבצת החסרה תהיה בפינה הימנית התחתונה שלו.
לדוגמא, באמצעות השטח שקיבלנו עבור N=2, נבנה שטח עבור N=3: מספר הצורות שבהן נשתמש בשביל לרצף שטח בגודל n^2 × n^2 ללא המשבצת הימנית התחתונה:
תשובה לשאלה 81 תוכנית שבודקת כמה ביטים דלוקים יש בבית אחד: int CountOnes(byte x) { #define BITS_PER_BYTE (8*sizeof(byte)) int res = 0; for (int i=0; i<BITS_PER_BYTE; i++) res += (x>>i)&1; return res; } על מנת שהתוכנית תתבצע בזמן קבוע, אפשר להיעזר בטבלה (Hash Table): int CountOnesFast(byte x) { #define VALS_PER_BYTE (1<<BITS_PER_BYTE) static bool first_time = true; static int table[VALS_PER_BYTE] = {0}; if (first_time == true) { for (int i=0; i<VALS_PER_BYTE; i++) table[i] = CountOnes(i); first_time = false; } return table[x]; } את הטבלה נחשב באופן חד-פעמי (בעזרת הפונקציה הראשונה), והטרייד אוף יהיה בצריכת הזיכרון. תשובה לשאלה 82 קריאה ל-Count(N) תחזיר את מספר האפשרויות השונות לטיפוס על בניין בן N קומות: int Count(int num) { if (num<3) return num; return Count(num-1)+Count(num-2); } סיבוכיות הזמן היא אקספוננציאלית – O(2^N), כי זה מספר הפעמים שהפונקציה נקראת. סיבוכיות הזיכרון היא אקספוננציאלית, כי כל קריאה לפונקציה דורשת מקום נוסף במחסנית (שגם היא חלק מהזיכרון). אפשר לפתור את הבעיה בצורה איטרטיבית במקום בצורה רקורסיבית: int Count(int num) { int prev = 1; int curr = 1; for (int i=1; i<num; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; } בפתרון הזה, סיבוכיות הזמן היא לינארית – O(N), וסיבוכיות הזיכרון היא קבועה – O(1). תשובה לשאלה 83 סה"כ, ישנם חמישה מצבים. מצב "שארית 0" הוא המצב ההתחלתי. מצב "שארית 0" הוא גם מצב ACCEPT. חמישית מהחיצים (2 מתוך 10) מגיעים אליו. כל שאר המצבים שקולים למצב REJECT.
עבור כל קלט (0 או 1) מתבצע: NextState = (2 * CurrState + Input) % 5
תשובה לשאלה 84 על מנת לדעת אם קיימת "לולאה" ברשימה מקושרת חד-כיוונית, מספיק למצוא צומת A, שאחריו ברשימה קיים צומת B עם קשת ל-A. מכיוון שמותר להשתמש רק בזיכרון בגודל קבוע, נניח שקיימים שני צמתים כאלה בקטע שבין הצומת הראשון ברשימה לצומת K כלשהו (בהמשך הרשימה), ונחפש אותם באופן הבא:
bool SearchLoop(List* list) { for (Node* tail = list->head; tail != NULL; tail = tail->next) { if (tail->next == tail) return true; for (Node* curr = list->head; curr != tail; curr = curr->next) { if (tail->next == curr) return true; } } return false; } סיבוכיות הזמן של האלגוריתם היא O(N^2), וסיבוכיות הזיכרון שלו היא O(1). שיטה נוספת (באדיבות רותם ויוליה):
בשיטה הזאת, סיבוכיות הזמן היא O(N) וסיבוכיות הזיכרון היא O(1).
תשובה לשאלה 85 (באדיבות רותם) אין טריק שמבטיח ניצחון, כי ייתכן שכל המספרים במערך שווים, ואז יהיה תיקו. יש טריק שמבטיח ניצחון או תיקו: השחקן שמתחיל, יכול להביא למצב שבו הוא ייקח את כל האיברים שנמצאים במקומות הזוגיים והיריב שלו ייקח את כל האיברים שנמצאים במקומות האי-זוגיים, או להיפך. לכן, כל מה שהוא צריך לעשות, זה לסכום כל קבוצה בנפרד ולבחור את זאת עם הסכום הגדול ביותר. לדוגמא, נניח שיש במערך N איברים (כאמור, N מספר זוגי), ושסכום האיברים שנמצאים במקומות הזוגיים גדול יותר מסכום האיברים שנמצאים במקומות האי-זוגיים. על מנת לקחת את כל האיברים שנמצאים במקומות הזוגיים:
o אם היריב לוקח את איבר מספר 1, השחקן לוקח את איבר מספר 2, שנמצא במקום זוגי. o אם היריב לוקח את איבר מספר N-1, השחקן לוקח את איבר מספר N-2, שנמצא גם הוא במקום זוגי.
תשובה לשאלה 86 על מנת לבדוק אם המספר A הוא חזקה שלמה של שתיים, נתייחס לשני מקרים: א. 0 = A. אפשר להחליט שכן (A שווה לשתיים בחזקת מינוס אינסוף) או שלא. ב. 0 < A. נסתכל על כל הביטים שמייצגים את A, עד ל-MSB (הביט הכי שמאלי שערכו 1): · A הוא חזקה שלמה של שתיים, אם ורק אם רצף הביטים שמייצג אותו הוא מהצורה 0...10. · אם נפחית 1 ממספר בעל רצף כזה של ביטים, כולם יתהפכו ונקבל מספר בעל רצף ביטים הפוך: 1...01. · אם נפחית 1 ממספר בעל רצף אחר של ביטים, לא כולם יתהפכו ולכן לא נקבל מספר בעל רצף ביטים הפוך. · כלומר, פעולת and בין המספר A למספר 1-A תיתן אפס, אם ורק אם המספר A הוא חזקה שלמה של שתיים. תשובה לשאלה 87 פונקצית מחלקה מקבלת את הכתובת של האובייקט שקרא לה, אבל בצורה בלתי מפורשת (כלומר, מוסתר מהמתכנת). את קוד האסמבלי אפשר לבנות, כך שהכתובת של האובייקט תעבור לפונקציה דרך המחסנית או באחד הרגיסטרים. הקומפיילר של Visual Studio 6.0 בונה את קוד האסמבלי, כך שהיא מקבלת את כתובת האובייקט ברגיסטר ECX. לפירוט נוסף – חלק 3 (חומר כללי: פונקציות מחלקה).
תשובה לשאלה 88 כל 8 פיקסלים (ביטים) אפשר לייצג באמצעות בית אחד. בכל שורה בתמונה ישנם N פיקסלים, ולכן N/8 בתים. אפשרות ראשונה: א. נחשב טבלה שתתאים לכל בית את הבית ההפוך לו: Byte table[1<<8] = {0}; for (int i=0; i<(1<<8); i++) for (int j=0; j<8; j++) table[i] |= ((i>>j)&1)<<(8-j-1); ב. נעבור על התמונה (מערך דו-מימדי מסוג Byte) ונבצע: for (int m=0; m<M; m++) for (int n=0; n<N/8; n++) outputImage[m][N/8-n-1] = table[inputImage[m][n]]; אפשרות שניה: א. נגדיר Bit-Field בגודל של בית, שמכיל 8 ביטים: typedef struct { Byte bit1:1; Byte bit2:1; … Byte bit8:1; } Bits; ב. נעבור על התמונה (מערך דו-מימדי מסוג Bits) ונבצע: for (int m=0; m<M; m++) { for (int n=0; n<N/8; n++) { outputImage[m][N/8-n-1].bit8 = inputImage[m][n].bit1; outputImage[m][N/8-n-1].bit7 = inputImage[m][n].bit2; … outputImage[m][N/8-n-1].bit1 = inputImage[m][n].bit8; } } יתרונות וחסרונות: באפשרות הראשונה נצטרך לחשב טבלה לפני היפוך התמונה, אבל במהלך היפוך התמונה נבצע פחות פעולות קריאה וכתיבה מאשר באפשרות השניה. מצד שני, בהנחה שהטבלה היא הרבה יותר קטנה מהתמונה, סיבוכיות הזמן והזיכרון שכרוכה בה היא שולית. בכל אחת משתי האפשרויות (אם ההנחה הנ"ל נכונה), סיבוכיות הזמן והזיכרון היא O(M*N).
תשובה לשאלה 89 (באדיבות יוליה) תחילה נמיין את הנקודות הנתונות לקסיקוגרפית לפי קואורדינטות ה-X שלהם. תוך כדי המיון נזכור איזה נקודות מתחילות קטע ואיזה נקודות מסיימות קטע. למשל, ניתן להצמיד מערך של ביטים, כאשר 1 מסמן נקודת התחלה ו-0 מסמן נקודת סיום. במידה ויש כמה נקודות בעלות קואורדינטות X זהות, נבצע מיון מישני באופן הבא – נמקם תחילה את כל הנקודות שמתחילות קטע, ואחריהן את כל הנקודות שמסיימות קטע. כעת נאתחל Count = MaxCount = 0, נעבור על רשימת הנקודות הממוינת ונבצע:
מספר נקודות החיתוך המקסימלי הוא הערך של MaxCount בסיום. הסיבה לביצוע המיון המישני:
הערה: בקואורדינטות ה-Y של הנקודות הנתונות אין שימוש כלל.
תשובה לשאלה 90 Constructor של מחלקה כלשהי לא יכול להיות וירטואלי, כי: קריאה לפונקציה וירטואלית של אובייקט כלשהו מתבצעת בעזרת ה-V-Table של המחלקה שאליה האובייקט שייך. כל אובייקט מחזיק מצביע ל-V-Table המתאים, אבל המצביע הזה מאותחל רק בזמן ריצה, כאשר האובייקט נוצר. כלומר, המצביע הזה למעשה מאותחל רק כאשר מתבצעת קריאה ל-Constructor של האובייקט, ולכן ה- Constructor לא יכול להיות וירטואלי. חוץ מזה, אין שום הגיון ב-Constructor וירטואלי. הרעיון מאחורי פונקציות וירטואליות, הוא שאפשר לקרוא להן בלי לדעת מהו הסוג המדויק של האובייקט שבאמצעותו מבצעים את הקריאה. כאשר יוצרים אובייקט (כלומר, קוראים בצורה בלתי מפורשת ל-Constructor), יודעים בדיוק איזה סוג רוצים ליצור, ולכן אין שום צורך במנגנון הזה. Destructor של מחלקת בסיס (מחלקה שיורשים ממנה) צריך להיות וירטואלי, כי: כאשר יוצרים ע"י הקצאה סטאטית אובייקט שנגזר ממחלקת הבסיס, אז בסיום הפונקציה (אם האובייקט הוא לוקאלי) או התוכנית (אם האובייקט הוא גלובאלי), ה-Destructor של האובייקט נקרא אוטומטית, ובסיום העבודה שלו הוא גם קורא אוטומטית ל-Destructor של מחלקת הבסיס. במצב כזה, אין משמעות לעובדה שה-Destructor של מחלקת הבסיס הוא וירטואלי. לעומת זאת, כאשר יוצרים ע"י הקצאה דינאמית (new) אובייקט שנגזר ממחלקת הבסיס, אז יש לשחרר אותו בצורה מפורשת (delete). אופרטור ה-delete מקבל את המצביע לאובייקט, שיכול להיות מהסוג של מחלקת הבסיס של האובייקט. במצב כזה, אם ה-Destructor הוא וירטואלי, אופרטור ה-delete קורא ל-Destructor של המחלקה האמיתית של האובייקט, שבסיום העבודה שלו קורא אוטומטית ל-Destructor של מחלקת הבסיס. אחרת, אופרטור ה-delete קורא ל-Destructor של מחלקת הבסיס של האובייקט, וה-Destructor של המחלקה האמיתית של האובייקט לא מתבצע כלל. לדוגמא, נניח שמחלקת הבסיס היא A, וקיימת מחלקה B שנגזרת ממנה: עבור A* ptr = new B מתבצע:
עבור delete ptr מתבצע:
כשה-Destructor של מחלקה B מסיים, הוא קורא ל-Destructor של מחלקה A.
ה-Destructor של מחלקה B לא נקרא כלל. לפירוט נוסף – חלק 3 (חומר כללי: פונקציות מחלקה).
תשובה לשאלה 91 על מנת למנוע פניה למערכת ההפעלה בכל פעם שמתבצעת הקצאה דינאמית של אובייקט מסוג A, נגדיר במחלקה A את האופרטור new, אשר יחזיר מצביע לאובייקט מסוג A. מכיוון שאנחנו רוצים למנוע פניה למערכת ההפעלה, האופרטור שנממש יצטרך להחזיר מצביע לאובייקט מסוג A (או מסוג שנגזר מ-A) שכבר קיים במערכת. כלומר, נצטרך להחזיר מצביע לאובייקט שהוקצה בצורה סטאטית. זה לא יכול להיות אובייקט לוקאלי (במחסנית של האופרטור שמימשנו), מכיוון שאסור שפונקציה תחזיר מצביע למשתנה לוקאלי שלה, ולכן זה חייב להיות אובייקט גלובאלי או אובייקט סטאטי במחלקה כלשהי שאינה המחלקה A (כי לא ניתן להגדיר בתוך מחלקה אובייקט מסוג המחלקה עצמה). אפשרות נוספת היא פשוט להחזיר מצביע NULL. חתימת האופרטור בתוך המחלקה A: void* operator new(unsigned int stAllocateBlock, char chInit ); דוגמא לקריאה לאופרטור: A* a=new(6) A;
תשובה לשאלה 92 שיטה ליישם ב-++C את מנגנון הפונקציות הווירטואליות ללא שימוש במילה השמורה virtual: מחלקה שמספקת ממשק של פונקציות וירטואליות, היא מחלקת בסיס למחלקות אחרות (שיורשות ממנה). בכל פעם שנגדיר מחלקת בסיס, נוסיף לה משתנה type, שלפיו נדע את הסוג המדויק של כל אובייקט שנוצר. הערך של type צריך לאפשר לנו לזהות את סוג האובייקט. לדוגמא, הוא יכול להיות מחרוזת עם שם המחלקה שלו. בכל Constructor של מחלקת הבסיס ושל המחלקות שיורשות ממנה נאתחל את type. מכיוון שאף Constructor לא יכול להיות וירטואלי, מובטח לנו שכאשר האובייקט נוצר, type יקבל את הערך הנכון. בפועל, כל Constructor קורא קודם כל ל-Constructor שלפניו בשרשרת ההורשה, ורק אז מבצע את הקוד שלו עצמו. כלומר, לפעמים המשתנה type יקבל ערך יותר מפעם אחת, אבל הערך האחרון שהוא יקבל יהיה הערך הנכון. למשל, נניח שמחלקה A היא מחלקת הבסיס ומחלקות B ו-C יורשות ממנה. מכיוון שלא ניתן להשתמש במילה השמורה virtual, כל קריאה לפונקציה של A בעזרת מצביע מסוג A, תביא אותנו לפונקציה של A גם אם העצם המוצבע הוא מסוג B או C. לכן, בכל פונקציה של A שנרצה שתהיה וירטואלית, נבדוק את הערך של type ונזהה את סוג המחלקה שהפונקציה שלה צריכה להתבצע. אם זיהינו שסוג האובייקט הוא A, נבצע את הקוד שהגדרנו עבור המחלקה A (אם אין הגדרה כזאת, לא נבצע כלום). אם זיהינו שסוג האובייקט הוא B או C, נמיר את ה-this שברשותנו למצביע מתאים, ונקרא בעזרתו לפונקציה של המחלקה המתאימה. מכיוון שאנחנו יודעים בוודאות מהו סוג האובייקט שלנו, ההמרה של ה-this למצביע מהסוג הזה והקריאה לפונקציה בעזרתו יהיו "חוקיות" (לא נקבל שגיאה בזמן ריצה). דוגמא למימוש של פונקציה "וירטואלית" במחלקה A: int A::func() { if (type == 'A') return 0; else if (type == 'B') return ((B*)this)->func(); else //if (type == 'C') return ((C*)this)->func(); } הערות: א. השימוש במשתנה type ובהמרת המצביעים (כמו בדוגמא הנ"ל) דומה לשימוש באופרטור dynamic_cast, שבזמן ריצה בודק את הסוג האמיתי של העצם המוצבע לפני שהוא ממיר את המצביע לסוג הנדרש. אם הבדיקה מראה שהם זהים, אז האופרטור מחזיר מצביע מתאים. אחרת, הוא מחזיר NULL. על מנת להשתמש באופרטור הזה, צריך לוודא שקיימת בקומפיילר אופציית RTTI (Run-Time Type Information), שמאפשרת לקבל אינפורמציה לגבי סוג האובייקט בזמן ריצה. ב. באופן כללי, גם השימוש ב-RTTI וגם השיטה הנ"ל ליישום של מנגנון הפונקציות הווירטואליות, נוגדים את הקונספט של OO. הרעיון בקונספט הזה הוא הכללה של אובייקטים דומים, ושימוש בהם בלי לדעת מהו הסוג המדויק של כל אחד (Polymorphism). כאן עשינו בדיוק את ההיפך – בדקנו את סוג האובייקט וביצענו פעולה מסוימת בהתאם. ג. בנוסף, בכל פעם שנרצה לגזור (לרשת) ממחלקת הבסיס מחלקה חדשה, נצטרך לשנות את קוד הפונקציות ה"ווירטואליות" של מחלקת הבסיס. כלומר, נצטרך לקמפל וללנקג' גם את קוד המקור של מחלקת הבסיס (בנוסף לקוד המקור של המחלקה החדשה). תשובה לשאלה 93 נניח לשם הפשטות שיש במערך מספר זוגי של איברים:
לאחר שקיבלנו N½ ערכי מינימום ו- N½ ערכי מקסימום:
סך הכל, מספר ההשוואות שביצענו הוא N½1 = N½ + N½ + N½.
תשובה לשאלה 94 ניעזר בטבלה בגודל M על N, על מנת לפתור את הבעיה בעזרת תכנון דינאמי: א. כל משבצת בטבלה תייצג את הריבוע המקסימלי של פיקסלים מאותו צבע, שהפינה הימנית התחתונה שלו היא הפיקסל המקביל בתמונה. כלומר, בכל משבצת נרשום את אורך הצלע של הריבוע שאותו היא מייצגת. ב. בכל המשבצות בשורה הראשונה ובטור הראשון בטבלה נרשום 1, מכיוון שזהו אורך הצלע של הריבוע שכל אחת מהן מייצגת. ג. נעבור על הטבלה בצורה סדרתית (משמאל לימין בכל שורה, לפי סדר השורות), ולכל משבצת נחשב את הערך המתאים לה באופן הבא: · נבדוק את הצבע של משבצת [i][j] ושל 3 המשבצות [i-1][j-1] , [i-1][j] , [i][j-1] . · אם הצבעים של חלק מ-4 המשבצות שונים זה מזה, אז משבצת [i][j] מייצגת ריבוע שאורך הצלע שלו הוא 1. · אם הצבעים של כל 4 המשבצות זהים זה לזה, אז משבצת [i][j] מייצגת ריבוע שאורך הצלע שלו הוא 1 + הערך המינימלי מבין הערכים שרשומים ב-3 המשבצות [i-1][j-1] , [i-1][j] , [i][j-1] . ד. לסיום, נעבור על הטבלה ונמצא את הערך המקסימלי שרשום בה. נניח, למשל, שהתמונה נראית כך:
כאשר נגיע למשבצת הרביעית בשורה השלישית, הטבלה תיראה כך:
נחשב את הערך של המשבצת הזאת כך: x = 1+Min(1,2,2) = 2.
תשובה לשאלה 95 בפונקציה MyMalloc נקצה 4 בתים מעבר לכמות הבתים הנדרשת, ונרשום בהם את מספר הבתים שהוקצו: void* MyMalloc(int size) { int* mem = malloc(sizeof(int)+size); mem[0] = sizeof(int)+size; return (void*)(mem+1); } בפונקציה MyFree נקרא מ-4 הבתים הראשונים את מספר הבתים שהוקצו, ונשחרר את כמות הבתים הזאת: void MyFree(void* ptr) { int* mem = (int*)ptr-1; int size = mem[0]; free((void*)mem,size); } תשובה לשאלה 96 ניהול החוצצים יתבצע באופן הבא:
א. כל אלמנט יקבל מקום בזיכרון (או שהתוכנית לא תעבור קומפילציה, ואז נדע שיש בעיה). ב. כל אלמנט יישב באותו מקום בזיכרון, וזמן הגישה אליו לא ישתנה בכל פעם שהתוכנית תרוץ.
נאתחל N "באפרים" בכתובות של החוצצים ובדגלי "פנוי", ונכניס אותם למחסנית – O(N).
נוודא שהמחסנית לא ריקה, נוציא ממנה "באפר", נשנה את הדגל שלו ל"תפוס" ונחזיר אותו כפלט – O(1).
נוודא שהדגל של ה"באפר" שקיבלנו כקלט הוא "תפוס", נשנה אותו ל"פנוי" ונכניס אותו למחסנית – O(1). שינוי השדות של מבנה הנתונים "באפר" יתאפשר רק בתוך הפונקציות הנ"ל.
תשובה לשאלה 97 הכפלת רגיסטר 1R ברגיסטר 2R, והכנסת התוצאה לרגיסטר 3R: CLR R3 //R3 = 0 CLR R7 //R7 = 0 CLR R8 //R8 = 0 Loop_R1: DEC R1 //R1 = R1 - 1 INC R7 //R7 = R7 + 1 Loop_R2: DEC R2 //R2 = R2 - 1 INC R8 //R8 = R8 + 1 INC R3 //R3 = R3 + 1 JUMP R2 Loop_R2 //if (R2 > 0) goto Loop_R2 Restore_R2: DEC R8 //R8 = R8 - 1 INC R2 //R2 = R2 + 1 JUMP R8 Restore_R2 //if (R8 > 0) goto Restore_R2 JUMP R1 Loop_R1 //if (R1 > 0) goto Loop_R1 Restore_R1: DEC R7 //R7 = R7 - 1 INC R1 //R1 = R1 + 1 JUMP R7 Restore_R1 //if (R7 > 0) goto Restore_R1 הערות:
פעולות שניתן לממש באמצעות פעולות אחרות: |
|
|
|
|
High-Tech Job Interview Q&A - שאלות ראיון עבודה הייטק |