הרצאה 1 – מבוא למדמ“ח בשפת C

שלום לכולם! בקורס זה נלמד איך פותרים בעיות שונות באמצעות תוכניות מחשב שנכתוב בעצמנו, בשפת תכנות שנקראת C. אנחנו נתחיל מהיסודות הבסיסיים ביותר ונסביר הכל, עם מגוון רחב של דוגמאות והסברים.

אם הגעתם לקורס ללא רקע בתכנות - זהו המקום בשבילכם! אנחנו נבנה את היסודות בצורה מעמיקה ולא נדלג על אף פרט. אם הגעתם עם רקע, זהו גם המקום בשבילכם! אנחנו נעמיק בפתרון תרגילים, נכיר את כל הטריקים להצלחה במבחן ונפרק את הבעיות הקשות ביותר.

למי הקורס מיועד

מטרת הקורס היא ללמוד תכנות בשפת C מהבסיס ומעלה. יש כמה קטגורויות שיכולות להנות ממנו:

1. סטודנטים - אם אתם לוקחים קורס מבוא לתכנות בשפת C באוניברסיטאות השונות, הקורס הזה בנוי להצלחה שלכם במבחן ובקורסי העתיד. נבנה בסיס חזק לקונספטים השונים שלומדים בקורס ונפתור כמה שיותר תרגילים ברמת מבחן על מנת שתוכלו להצליח בו. אפשר להשתמש בקורס לאורך הסמסטר, לקראת המבחן או כחזרה כללית על החומר
2. הכנה לראיונות עבודה - הרבה חברות עורכות ראיונות לתפקידי תוכנה, מהנדסי חשמל ומקצועות אחרים בשפת C או ++C. שליטה בשפה מהמאפיינים הבסיסיים ביותר למורכבים ומאתגרים שביניהם היא קריטית להצלחה בראיונות, וגם כאן הקורס מותאם להצלחתכם.
3. לימוד תכנות כללי - הקורס מלמד שפה אוניברסלית לתכנות, ממנה אפשר להתקדם למגוון עצום של נושאים ושפות אחרות.
4. לימוד מחשבים כללי - למידת שפת C טומנת בחובה הבנה עמוקה של עקרונות בסיסיים במדעי המחשב - זכרון, אלגוריתמיקה ועוד. הקורס יעשה זאת ועוד.

בהצלחה לכולם!

הקדמה להרצאה זו

בהרצאה זו נעשה שני דברים עיקריים:

1. נפגוש כמה מושגים בסיסיים בעולם התכנות והמחשוב.
2. נחשף לדוגמאות קוד עם קונספטים שונים (אותם כמובן עוד לא למדנו).

המטרה היא לקבל תחושה כללית וטעם ראשוני ממה שנלמד לאורך הקורס. אין צורך להבין אותם בצורה עמוקה, אלא רק להתרשם. בהמשך נפרק כל מרכיב שנפגוש בהרצאה זו (ועוד רבים אחרים) ונהפוך למומחים, אבל מטרת ההרצאה הראשונה היא רק לקבל תחושה כללית.

בסיס מדעי המחשב

הגדרה: תוכנית היא סדרה של פקודות מחשב שמטרתן ביצוע משימה מסויימת.

כמה דוגמאות לתוכניות:

1. מחשבון: אם תפתחו את אפליקציית המחשבון במחשב שלכם, תוכלו ללחוץ על האייקונים של המספרים ולבצע כל חישוב שתרצו. לא קשה לדמיין מה הפעולות שהמחשב עושה בשביל להמיר את הקלט לפלט הרצוי.
2. ChatGPT: תוכנית שתוכלו להזין אליה טקסט ולקבל תשובה כלשהי. במקרה זה קשה מאוד לדעת מהן הפעולות שהמחשב עושה בשביל להוציא את הפלט הרצוי.
3. תחזית: אם תפתחו את אפליקציית מזג האוויר בטלפון שלכם, יוצג ללא צורך בקלט מצידכם מהי התחזית לימים הקרובים.

חומרה, תוכנה ושפות תכנות

נהוג להפריד את הנדסת המחשבים ומדעי המחשב לשני חלקים:

1. חומרה (hardware), ההתקנים הפיזיים עליהם שקוראים את התוכנה ומבצעים אותה.
2. תוכנה (software), רצף פקודות שמכונה מבצעת על מנת להשלים משימה כלשהי.

הגדרה: שפת תכנות היא דרך מוסכמת לכתוב תוכנה שלאחר מכן החומרה תבצע.

איך זה מתבצע בפועל?

1. במחשב, בטלפון ובמכשירים אחרים שאנחו משתמשים בהם קיימת יחידה חומרתית בשם מעבד (CPU - Core Processing Unit).
2. תפקיד המעבד הוא לבצע את תוכניות המחשב שהמשתמש מורה לו לבצע.
3. המעבד עובד עם יחידה חומרתית נוספת הנקראת זכרון, בו נשמר המידע בו המעבד משתמש.
4. תוכניות מחשב כתובות בשפה הבינארית - רצף של 0 ו-1 אותן הוא מפורש בדרך מוסכמת.
5. הדרך המוסכמת לפרש את השפה הבינארית נקראת שפת מכונה. לסוגי מחשבים שונים (למשל, מחשבי אפל לעומת ווינדוס) יש בדרך כלל שפת מכונה שונה.
6. קשה מאוד לכתוב תוכניות מורכבות בשפת מכונה, ולכן המתכנתים הראשונים המציאו את שפות התכנות - טקסט קריא יותר לכתיבת תוכניות, שבהמשך יתורגם לשפת מכונה אותה המעבד מבין.

Note

בהמשך נכיר לעומק את השפה הבינארית, אך לא נתעסק בשפת מכונה בקורס זה. בקורסי המשך כמו מערכות ספרתיות ומבנה מחשבים בדרך כלל לומדים לעומק כיצד שפת מכונה ספציפית (למשל, Risc-V) מתרגמת לפעולות חומרתיות על מעבד.

חומרה

בעולם המודרני אנחנו פוגשים בכל מקום מכשירים מסוגים שונים - ממחשבים, טלפונים למכוניות ואף מכונות כביסה חולקים כולם מבנה חומרתי דומה.

נפרוט את החלקים השונים:

1. המעבד (CPU - Central Processing Unit) מכיל יחידה לוגית שמבצעת חישובים שונים, ויחידת בקרה שמורה ליחידה הלוגית איזה חישובים לבצע.
2. המעבד מתקשר עם יחידת הזכרון, בה נשמר המידע בה משתמש המעבד. הזכרון לרוב מחולק ליחידה בשם RAM (Random Access Memory) שמכילה זכרון נדיף, ויחידה בשם דיסק שמכילה זכרון שאינו נדיף.
3. במכשירים רבים קיימות יחידות פריפריאליות שמזינות קלט למכשיר (למשל - מקלדת) או מוציאות פלט ממנו (למשל - מסך).

Note

לארכיטקטורה זו קוראים Von Neumann Architecture, על שם מתמטיקאי ומהנדס הונגרי בשם ג׳ון פון נוימן, שפרסם מודל ראשון שלה ב-1945!

ברוב המקרים, המעבד מוגבל לביצוע פקודות פשוטות מאוד - חיבור וחיסור, טעינה מהזכרון וכתיבה אליו, וכו׳ - מפקודות פשוטות אלו מרכיבים תוכניות מורכבות יותר. כמו כן, מחשבים מודרניים מבצעים פעולות בקצב גבוה מאוד: קצב העבודה של מחשב מודרני הוא בסביבות ה-3.5GHz, או 3.5 מיליארד פעולות בשנייה.

שפות נמוכות וגבוהות

יש המון שפות תכנות שונות, ונהוג לסווג אותן על סקאלה שבין שפות תכנות נמוכות לגבוהות (high level language & low level language). שפת תכנות נמוכה היא שפה שקרובה יותר לשפת מכונה – כל פעולה שנכתבת בשפה נמוכה לרוב הופכת (לאחר התרגום) למספר מצומצם של פעולות בשפת מכונה.

שפות גבוהות יותר, לעומתן, רחוקות יותר משפת מכונה ולכן כל פעולה שמתבצעת בהן יכולה להפוך למספר גדול של פעולות בשפת מכונה. שפות גבוהות יותר יכולות להיות פשוטות יותר לכתיבה, אבל מכיוון שהן “מסתירות” מהמתכנת חלק גדול ממה שמתבצע מאחורי הקלעים, הן מאפשרות שליטה פחות מדויקת (אם בכלל) בכל הפרמטרים של ביצוע תוכנית – זה יכול להוביל לתוכניות יעילות פחות בפרמטרים מסוימים. כך או כך.

Important

שפות הן עיליות/גבוהות רק ביחס זו לזו, והיותה של שפה עילית או תחתית ביחס לאחרת לא קובע האם היא חשובה או רלוונטית יותר בעולם המודרני.

שפת C

בקורס זה נלמד את שפת C, אחת משפות התכנות המוכרות והנפוצות בעולם. השפה יצאה לאור ב-1972 ומאז נמצאת בשימוש נרחב בעולם התכנות ומתאפיינת בפשטות וגמישות, תוך כדי שליטה מדויקת מאוד על המכונה עליה היא רצה. תוכנות מהחשובות בהיסטוריה נכתבו בשפת C - מערכות ההפעלה Windows, Linux ו-MacOS/iOS הן הידועות מביניהן.

ביחס לשפת מכונה C נחשבת שפה גבוהה - עם זאת, ביחס לרבה שפות תכנות מודרניות אחרות (למשל Python), C נחשבת לשפה נמוכה יחסית. כך או כך, היא נמצאת בשימוש נרחב במגוון עצום של שימושים, והפשטות שלה הופכת אותה לטובה מאוד כבחירה לשפת תכנות ראשונה.
בהרצאה הזו נפגוש כמה תוכניות בסיסיות על מנת לקבל תחושה כללית לשפה, ולאחר מכן בהרצאה הבאה נתחיל להגדיר אובייקטים בצורה מסודרת ולכתוב תוכניות משלנו.

Note

שפת C נקראת כך מכיוון שהיא פותחה לאחר שפה קודמת ופרימיטיבית יותר בשם B. באופן מעט מכעיס לא הייתה שפה בשם A לפני B, אלא שפה בשם BCPL. השפה BCPL היוותה את הבסיס לשפה B, שבעצמה הפכה בסופו של דבר לשפת C.

שפת C נכתבה על מנת לשלוט בצורה מדויקת ופשוטה במכונה עליו היא רצה. בהתאם לכך, בשביל ללמוד איך לתכנת בשפה צריך ללמוד כיצד מחשב בנוי ועובד - מהו זכרון,

Hello World

אחד הדברים הבסיסיים ביותר שתוכנית מחשב יוכלה לעשות היא לכתוב על המסך הודעה שהמשתמש יכול לקרוא. כשלומדים שפת תכנות לראשונה, נהוג להציג תוכנית שמדפיסה על המסך את התווים “!Hello world” – בשפת C, זה יראה כך:

#include <stdio.h>
int main() {
    printf("Hello world!\n");
}

פירוק לרכיבים

ללמוד שפת תכנות בפעם הראשונה יכול להראות מפחיד, במיוחד למי שלא תכנת בעבר – מה כל הסימבולים אומרים? איך אדע להשתמש בהם? אנחנו נבנה לאורך הקורס את אוצר המילים שלנו בצורה הדרגתית, וכעת נתחיל במרכיבים החיוניים בלבד. נבחן בפירוט את השורה הבאה:

printf("Hello world!\n");

1. printf – זוהי דוגמא לפונקציה (function), אובייקט שנעבוד איתו המון בקורס ונגדיר בהמשך בצורה מסודרת. בקצרה עכשיו – פונקציה היא קטע קוד שאפשר “לקרוא” לו מכל מיני מקומות ובכך להפעיל אותו. לפונקציות קוד, כמו פונקציות מתמטיות, יש ארגומנטים שהן מקבלות וערך שהן מחזירות. בדוגמא הזו, הארגומנט הוא "Hello world", ואנו לא משתמשים בערך שהיא מחזירה. הפונקציה printf (קיצור של print formatted) מדפיסה למסך את הארגומנטים שהיא מקבלת. נשים לב שהדרך לקרוא לפונקציה היא עם סוגריים () וביניהם הארגומנטים שלה, בדוגמא לכך שבמתמטיקה כותבים \(sin(x)\) עבור קריאה לפונקציה \(sin\) עם הארגומנט \(x\). בהמשך נפרט בהרחבה על איך משתמשים בפונקציות ואיך לכתוב פונקציות בעצמנו.
2. "Hello world!\n" – זוהי דוגמא למחרוזת (string) - אוסף של תווים, שגם עליהם נרחיב מאוד בהמשך הקורס. ב-C מחרוזות מוקפות בגרשיים כפולים " " , והרבה פעמים משמשות ליצוג מייצגות טקסט כלשהו. במקרה זה הטקסט שרצינו להדפיס הוא “Hello world”, בעוד שהתו n\ הוא סימן מוסכם ל-“שורה חדשה” – כלומר, הפונקציה printf תדפיס "Hello world", תגיע לתו n\ ואז תדפיס שורה חדשה. נשים לב שבמקרה זה נתנו לפונקציה ארגומנט אחד והוא "Hello world!\n" – בהמשך נראה שניתן לתת לפונקציות מספר גדול כרצוננו של ארגומנטים.
3. ; – בסוף השורה נכתב התו ';'. התו הזה מסמן סוף של “משפט” בקטע הקוד שכתבנו. בהמשך נרחיב על משפטי קוד, אבל כרגע ניתן להתייחס ל-; כמו נקודה בין משפטים שונים.

שורה זו מרכיבה את עיקר הלוגיקה של התוכנית הפשוטה הזו. שאר המרכיבים מעט מורכבים יותר, אבל נסביר גם אותם בקצרה:

1. <include <stdio.h# - ב-C שורת קוד המתחילה ב-# נקראת מאקרו (macro). בקרוב נפגוש תוכנית חשובה הנקראת קומפיילר (compiler) - זוהי תוכנית שתפקידה לקחת את הקוד שכתבנו ולתרגם אותו לשפת מכונה. שורת מאקרו אינה מייצגת קוד בפני עצמה, אלא הוראה לקומפיילר לבצע פעולה כלשהי. במקרה זה, פקודת ה-include# מורה לקומפיילר להדביק את הקובץ stdio.h בקובץ שלנו - הסיבה שאנו זקוקים לכך היא על מנת לקבל גישה לפונקציה printf, הנמצאת בקובץ הזה.
2. ()int main – זו עוד פונקציה. כשהקומפיילר קורא את הקוד שלנו, הוא מחפש פונקציה בשם main ושם קובע את נקודת ההתחלה של התוכנית.
3. {} – התווים ‘{’ ו-‘}’ משמשים בשפת C לאגד ביחד מספר משפטים ליצירת בלוק קוד. במקרה זה התווים האלה משומשים על מנת לאגד ביחד את “הגוף” של פונקציית ה-main בתוכנית.
4. נשים לב שלאחר ה-{ הראשון, השורה הרביעית מתחילה ב-4 רווחים. זוהי קונבנציה הנקראת הזחה או אינדנטציה (indentation) - כל ״בלוק״ קוד חדש מתחיל במספר רווחים על מנת להפריד אותו ויזואלית מאחרים. בשפת C הקומפיילר מתעלם לחלוטין מהזחות ולכן מדובר בקונבנציה בלבד, אבל היא שימושית מאוד בהפיכת הקוד לקריא יותר.  

קריאת קלט מהמשתמש

עכשיו כשאנחנו קצת מכירים מרכיבים בסיסיים של תוכנית בסיסית, נכתוב תוכנית פשוטה נוספת:

#include <stdio.h>
int main() {
    int number;
    scanf("%d", &number);
    printf("You entered %d\n", number);
}

יש הרבה מרכיבים שאנחנו כבר מכירים מהתוכנית הקודמת וכמה חדשים. נסביר אותם בקצרה:

1. int number – זוהי נקראת “הצהרה” (declaration) של משתנה. הצהרות מאפשרות לנו לתת שם למשתנה כלשהו איתו נבצע פעולות וחישובים. לכל משתנה יש טיפוס (type) שמגדיר איך התוכנית מפרשת אותו וכמה מקום הוא צורך בזכרון. להצהרה תמיד יש שני חלקים – הטיפוס (type) של המשתנה ולאחר מכן השם שלו. במקרה זה הצהרנו על משתנה מטיפוס int (קיצור עבור integer, או מספר שלם) ששמו number.

2. scanf("%d", &number) - זוהי שורה מורכבת יותר, נפרק אותה לרכיביה:

   1. scanf - קיצור של scan formatted, זוהי פונקציה מאותה ״משפחה״ כמו print שמתעסקות בקבלת קלט מהמשתמש והצגתו על המסך.
   2. d% - הפונקציה scanf צריכה לדעת איזה סוג משתנה היא צפויה לקבל מהמשתמש בשביל לדעת איך לכתוב אותו בזכרון. הסימון d% הוא סימון מוסכם למשתנה מסוג int - בהמשך נראה סימונים נוספים כמו lf% ו-s% שיסמנו משתנים מסוגים אחרים. number& - הפונקציה scanf שומרת את את המספר שהמשתמש כתב לתוכנית בתוך המשתנה number בשביל שנוכל לעשות בו שימוש אחרי זה. נשים לב לשימוש ב-& לפני שם המשתנה - אנחנו צריכים עוד מעט רקע בשביל להבין מה תפקידו פה בדיוק ולכן נשים לב לקיומו אבל לא ננתח אותו כרגע. ככלל אצבע לבינתיים, כאשר משתמשים ב-scanf בשביל לקרוא קלט מהמשתמש נשתמש ב-& לפני שם המשתנה - ב-printf לא נעשה זאת.

3. לאחר מכן אנחנו מדפיסים את המספר שהכניס המשתמש. גם כאן אנחנו משתמשים במזהה d% בשביל לספר ל-printf איזה סוג משתנה היא צריכה להדפיס, ואז מעבירים אותו כארגומנט נוסף לפונקציה.

איך לומדים בקורס?

חלק גדול מלמידת תכנות היא לדעת איך ללמוד, כיצד להתמודד עם בעיות ואתגרים. מהנדסים מוכשרים בנו בעבר כמעט כל סוג תוכנית שניתן לחשוב עליה, ורוב מוחלט של הבעיות שתתקלו בהן במהלך הלמידה נפתרו כבר בעבר - אפשר למצוא תשובות לשאלות רבות בחיפוש חכם באינטרנט. גם עבודה מושכלת עם מודלי AI יכולה לתת מענה לשאלות שונות.

עם זאת, אם המטרה שלנו היא ללמוד לתכנת עצמאית - יתכן ובשביל להצליח במבחן, בראיון עבודה או בשביל לפתח את הכישורים הללו באופן כללי - שימוש מופרז ב-AI היא סכנה אמיתית להצלחה שלנו. השימוש ב-AI דומה בהקשר הזה לנהיגה במכונית אוטונומית: מחקרים שנעשו על נהגים שעברו למכונית אוטונומית 50% מזמן הנהיגה שלהם מצאו כי הם איבדו בקצב מהיר את יכולת הנהיגה העצמאית שלהם, היו משמעותית בסכנה גדולה יותר לתאונה והתקשו ברכישת הכישורים האלו בחזרה. במידה ולמרות זאת החלטתם להשתמש ב-AI, נסו להשתמש בו יותר בתור מנוע חיפוש ולא בתור פותר בעיות.

למשל, במקום לכתוב:

כתבו:

לכן, בקורס חייבים להקפיד על למידה עצמאית - חייבים לפתוח את יכולת ההתמודדות העצמאית מול שאלה קשה או נקודה למחשבה. במידה ולא נפתח את הכישורים האלו ונפתח תלות ב-AI לכל צרכינו, סביר מאוד להניח שלא נצליח בסיטואציית אמת של מבחן או ראיון עבודה. לכן, ההמלצה שלי היא ללמוד ללא שימוש במודלי AI בכלל. אין ספק כי ל-AI יש תפקיד עצום לשחק בעתיד של כל מתכנת, אבל פוטנציאל הנזק שלו להצלחה שלנו בסיטואציה בה הוא לא ימצא היא ענקית.

לכן, לאורך כל הקורס נציג תרגילים מסוגים שונים - תרגילים מחשבתיים, טכניים וכמובן בעיות קוד לפתרון. נסו לעצור את ההקלטה ולענות על השאלות בעצמכם. חלק מהשאלות יהיו קלות וישמשו לתרגול, וחלק מהשאלות יהיו מורכבות יותר וידרשו חומר המשך או רעיונות יצירתיים. במידה ויש שאלה שלא הצלחתם בשום צורה למצוא לה פתרון,

שאלות ותרגילים

1. מצאו את דף הויקיפדיה של הפונקציה printf ומצאו את הטבלה בה מפרטים את כל המזהים להדפסות (לדוגמא d%).
2. מהי שפת מכונה? למה קשה לכתוב בה תוכניות מורכבות?
3. מה ההבדל בין שפת תכנות נמוכה לגבוהה?
4. מה מיוחד בפונקציית ה-main בשפת C?
5. מה תפקיד הפונקציות printf ו-scanf?
6. איזה שורת מאקרו (macro) צריך לכתוב בקוד לפני שניתן להשתמש ב-printf ו-scanf?

דוגמאות נוספות

כעת נקבל טעימה ממספר קונספטים מתקדמים יותר, אותם נלמד בהרחבה בהמשך הקורס.

קבלת קלט מהמשתמש

#include <stdio.h>
int main() {
  // This program will print the sum of 3 numbers
  /*
  This is the start of a
  multiline comment
  */
  int sum, number1, number2, number3;
  scanf("%d", &number1);
  scanf("%d", &number2);
  scanf("%d", &number3);
  sum = number1 + number2 + number3;
  printf("sum = %d\n", sum);
}

בתוכנית הזו יש שלושה מרכיבים חדשים:

1. בתחילת הקוד מופיעות הערות (comments).כשנרצה לכתוב טקסט חופשי על הקוד שמסביר אותו, נותן לו קונטקסט או עוזר בדרך כזו או אחרת, נשתמש בהערות. הקומפיילר מתעלם לחלוטין מהערות ולכן ניתן לכתוב בהם מה שנרצה. יש בקוד את שני סוגי ההערות בהן תומכת השפה:
   1. שורה המתחילה ב-// הופכת להערה עד לסוף השורה.
   2. הסימון */ הוא סימון לתחילת הערה מרובת שורות (multiline comment), בעוד שהסימון /* מסמן את סוף ההערה. כך ניתן לכתוב הערות שאורכן מספר שורות בלי להתחיל כל אחת מהן ב-//.
2. הצהרנו בתוכנית הזו על ארבעה משתנים – number1, number2, number3, sum. נשים לב שלקיצור ניתן להצהיר על מספר משתנים מאותו סוג באותה שורה עם רווחים ביניהם, כפי שעשינו.
3. לאחר שקראנו 3 מספרים מהמשתמש, ביצענו חישוב – חיברנו את שלושת המספרים וכתבנו את התוצאה למשתמש sum. זו דוגמא לפעולה בסיסית בין כמה משתנים – בהמשך נראה פעולות נוספות שניתן לצפות שאפשר לעשות, כמו חיסור, כפל, חילוק ועוד. נשים לב ל-+ בין המספרים - זוהי דוגמא לאופרטור שפועל בין שני משתנים.

לולאות

מה היה קורה אם היינו רוצים לחבר מאה משתנים? האם היינו צריכים להצהיר על מאה משתנים? כמובן שלא – השפה עוזרת לנו במקרה זה ע“י קונספט שנקרא לולאה, כמו בתוכנית הבאה:

#include <stdio.h>
int main() {
    int sum, i, num;
    sum = 0;
    i = 0;
    while (i < 5) {
        scanf("%d", &num);
        sum = sum + num;
        i = i + 1;
    }
    printf("sum = %d\n", sum);
    fflush(stdout);
}

בתוכנית זו מופיעה הדוגמא הראשונה שראינו ללולאה – דרך לבצע את אותו קטע קוד מספר כלשהו של פעמים. הלולאה בקוד היא מסוג while וניתן לקרוא אותה כך - while (כל עוד) התנאי שבסוגריים מתקיים, בצע את קטע הקוד שבתוך הבלוק. במקרה זה אתחלנו משתנה בשם i ל-0, וביצענו את קטע הקוד כל עוד הוא קטן מ-5. בכל ביצוע של הלולאה הגדלנו אותו ב-1, ולכן לאחר 5 איטרציות הלולאה תסיים ונדפיס את הסכום. זוהי דרך פשוטה לחבר בין מספר כלשהו של מספרים. ביצוע פעולות על האיברים ברשימה מסוימת היא תבנית נפוצה מאוד - בהמשך נראה סוג נוסף של לולאות בשם for הנראה כך:

#include <stdio.h>
int main() {
    int sum = 0, num;
    for (int i = 0; i < 100; i++) {
        scanf("%d", &num);
        sum = sum + num;
    }
    printf("sum = %d\n", sum);
}

לולאת ה-for מכילה מעט יותר מרכיבים (וכמובן שאת כולם נלמד בהמשך). את הלולאה הספציפית שמופיעה כאן ניתן לקרוא כך - התחל עם משתנה int i = 0, בצע את הלולאה כל עוד i < 100, ובכל איטרציה הגדל את i ב-1.

קומפילציה והרצה

עכשיו כשפגשנו כמה תוכניות והכרנו את הרכיבים הבסיסיים, נתעסק מעט בתאוריה ובצורה שבה טקסט שכתבנו בעצמנו הופך להוראות שרצות על המכונה.

נזכיר - המעבד יודע לקרוא שפת מכונה, 0 ו-1 מסודרים בסדר מוסכם אותם הוא מבצע זה אחר זה. צריך לבצע תרגום מהשפה שכתבנו לשפת מכונה - לטובת משימה זו נכתבה תוכנית חשובה מאוד בשם קומפיילר (compiler). הקומפיילר קורא את הקוד שכתבנו, מנתח אותו ומנסה לבצע את התרגום משפת מכונה. אם ביצענו טעות כלשהי, הקומפיילר יכול לבחור לא לקבל אותו - אם כתבנו משהו שלא עומד בדיוק בתחביר (syntax) של השפה, הקומפיילר ידחה את בקשת הקומפילציה שלנו וידפיס שגיאה כלשהי. כמו כן, הקומפיילר יכול להחליט להדפיס אזהרה כלשהי, למשל אם ביצענו פעולה שהיא חוקית אבל הוא חושד שלא תוביל לתוצאה שאנחנו מתכוונים אליה. הקומפיילר הוא כלי מאוד שימושי וכדאי ללמוד להשתמש בו בצורה יעילה.

קוד שאינו עובר קומפילציה

נבחן את התוכנית הבאה:

int main() {
    int x = y;
    printf("%d\n", x);
}

אינטואטיבית, התוכנית אינה מרגישה הגיונית. מהו y? איך אפשר לתת ל-x ערך של משתנה שאינו קיים? כמו כן, לא כתבנו #include <stdio.h> כפי שראינו שיש לעשות קודם.

הקומפיילר יסרב לבצע קומפילציה של התוכנית, וידפיס לנו את השגיאה הבאה:

bad_comp.c:2:13: error: use of undeclared identifier 'y'
    2 |     int x = y;
      |             ^


bad_comp.c:3:5: error: call to undeclared library function 'printf' with type
      'int (const char *, ...)'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
    3 |     printf("%d\n", x);
      |     ^


bad_comp.c:3:5: note: include the header <stdio.h> or explicitly provide a declaration for
      'printf'

הקומפיילר מדפיס מידע שימושי מאוד בשביל לתקן את הקומפילציה של התוכנית!

1. ראשית, הוא מסמן לנו במדויק מה הבעיה. use of undeclared identifier, עם סימון על המשתנה y - הקומפיילר זיהה שהשתמשנו במזהה (identifier) שאינו מוצהר (undeclared) ולכן אין אפשרות לקמפל את התוכנית.
2. כמו כן, הקומפיילר מציין כי השתמשנו בפונקציה שאינה מזוהה printf. במקרה זה, מכיוון שמדובר בשגיאה נפוצה, הקומפיילר גם אומר לנו מה צריך לעשות בשביל לתקן אותה - לבצע include ל-<stdio.h>.

לסיכום, כדאי ללמוד לקרוא את הפלט של הקומפיילר ולהשתמש בו - הוא הכלי החשוב ביותר עבור מתכנת בשפה C.

Note

קיימים מספר קומפיילרים שונים לשפת C - הפופולריים ביניהם הם gcc ו-clang. ההבדלים העיקריים בין הקומפיילרים לא רלוונטי לצרכים שלנו בקורס ולכן ניתן להשתמש בכל אחד מהם, אבל יתכן שבהתאם לקומפיילר בו תשתמשו תראו הודעות שגיאה מעט שונות ביחס לאלו שמופיעים בקורס עבור אותו הקלט. בקורס נשתמש בקומפיילר clang.

לסיכום, אלו השלבים בהם קוד הופך לתוכנית שרצה על החומרה:

1. כתיבת קוד - הרבה פעמים בעורך קוד כלשהו, כמו VS Code או Code::Blocks
2. תיקון שגיאות/אזהרות קומפיילר עד לקומפילציה תקינה
3. תרגום ע״י הקומפיילר משפת C לשפת מכונה
4. הרצה של הקוד - הרבה פעמים ע“י עורך הקוד בו אנחנו משתמשים

Note

לא כל שפות התכנות עוברות קומפילציה. כדוגמא אחרת, קיימות שפות הנקראות ״מפורשות״ (interpreted), אותן מריצים בצורה אחרת. קיימת תוכנה הנקראת interpreter שקוראת קוד בשפות כאלו שורה אחר שורה ומבצעות אותן. דוגמא לשפות כאלה הן Python ו-JavaScript.

עכשיו כשראינו כמה דוגמאות בסיסיות לתוכניות וקיבלנו תחושה כללית עבור השפה, נתחיל ללמוד אותה בצורה מסודרת בהרצאה הבאה.

הרצאה 1.5 - התקנות

בהרצאת ביניים זו ננחה בקצרה כיצד ניתן להתקין אחד משתי תוכנות לכתיבת והרצת קוד - VS Code או Code::Blocks. שתי התוכנות סטנדרטיות, משומשות באופן רחב ע“י סטודנטים ומהנדסים וניתן לכתוב ולהריץ בהן בקלות תוכניות C.

התקנת VS Code

1. גשו ללינק הבא - VS Code Installation.

הרצאה 2 - טיפוסים ואופרטורים

בהרצאה זו נתחיל להכיר בצורה מסודרת את מאפייני השפה. ההרצאות הקרובות יהיו מעין ״רשימת מכולת״ של התחביר בשפת C, או סינטקס (syntax) - מאפיינים בשפה ואיך להשתמש בהם. נתחיל בטיפוסים (types) - דרך להגדיר איך התוכנית מפרשת משתנים שונים. ראינו בהרצאה הקודמת דוגמאות להצהרות משתנים, וכעת נגדיר זאת בצורה מסודרת.

Note

כמו בלימוד של כל שפה, הרבה מהמרכיבים תלויים בזה. יתכן ורק לאחר מספר הרצאות וחזרה מעשית על מה שנלמד תרגישו כי אתם שולטים מספיק בשפה בשביל לקרוא אותה בצורה אינטואיטיבית - זה בסדר ומצופה!

#include <stdio.h>
int main() {
    printf("The program is on its first line.\n");
    printf("The program has reached its second line.\n");
}

#include <stdio.h>
int main() {
    printf("Hello from Studies C language programming course!\n");
    printf("The printf function can be used to print arbitrary text");
    printf("If you have a really long line, you can end the line with quotes "
           "and continue on a new line, like this.\n");
}

int variable = 5;
printf("value = variable");

#include <stdio.h>
int main() {
    int x = 7;
    printf("x is an int variable with value %d\n", x);
}

#include <stdio.h>
int main() {
    int x = 54;
    int y = -5;
    printf("x = %d, y = %d\n", x, y);
}

#include <stdio.h>
int main() {
    int x = 7, y = 3;
    printf("x = %d, y = %d\n", x);
    printf("x = %d\n", x, y);
}

int result = 42;

int result;
char this_is_a_char;
float floatingPointNumber;
double DoubleNumber;

$$ 549 = 9 \cdot 10^0 + 4 \cdot 10^1 + 5 \cdot 10^2 = 9 + 40 + 500 $$

$$ 1101 = 1 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 1 \cdot 2^3=1 + 4 + 8 =13 $$

int x = 549;

00000000 00000000 00000010 00100101

#include <stdio.h>
#include <stdbool.h>
int main() {
    printf("Size of char: %d bytes\n", sizeof(char));
    printf("Size of bool: %d bytes\n", sizeof(bool));
    printf("Size of int: %d bytes\n", sizeof(int));
    printf("Size of float: %d bytes\n", sizeof(float));
    printf("Size of double: %d bytes\n", sizeof(double));
}

00000000 00000000 00000000 01000001

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    int x_ascii = x + '0';
    printf("%d ASCII value = %d", x, x_ascii);
}

5 + '0' = 5 + 48 = 53 = '5'

#include <stdio.h>
int main() {
    int x;
    printf("x = %d\n", x);
}

#include <stdio.h>
int main() {
    char c;
    scanf("%c", &c);
    printf("%c", c + 'a' - 'A') // 'a' - 'A' = 32
}

int x = 6;
x = x + 2;
int y = x;
int z = x + y - 2;

int x = y; // y not declared yet
5 = x; // Can't assign to a constant

כדוגמא נוספת, נעקוב אחרי ערכי משתנים בדוגמא הבאה:

double x;
double y = 2.1;
x = y - 2.2;
y = x + 0.2;

int x = 2;
x += 3; // x = x + 3
x *= -4; // x = x * (-4)
x /= 7; // x = x / 7

int x = 5; // x is 5
int y = ++x; // x is 6, y is 6
int z = y--; // x is 6, y is 5, z is 6

int a = 17, b = 5;
int result = a % b; // result = 2

int x = 65154;
int last_digit = x % 10; //  4

int a = 17, b = 5, c = 17;
bool a_b_equal = a == b; // False!
bool a_c_equal = a == c;
if (a_c_equal) { // True!
    // Do some stuff
}
char char1 = 'a', char2 = 'a';

if (char1 != char2) { // Use directly in comparison
    // Don't do stuff
}

int a = 5, b = 3;
int result1 = a + (b * 2);

int x = 10, y = 4, z = 2;
int result2 = (x - y) / z;

int p = 7, q = 2;
int result3 = (p++) * (--q);

// Program 1
int a = 5, b = 3;
int result1 = a + b * 2;

// Program 2
int x = 10, y = 4, z = 2;
int result2 = (x - y) / z;

// Program 3
int p = 7, q = 2;
int result3 = p++ * --q;

// Program 4
int m = 8, n = 3, k = 2;
int result4 = m / n * k + m % n;

// Program 5
int aa = 3, bb = 4, cc = 5;
int result5 = (aa++ + --bb) * (cc-- - ++aa);

#define EGGS_NEEDED 2
#define FLOUR_NEEDED 5
#include <stdio.h>
#include <stdbool.h>
int main() {
    int eggs = -1;
    int flour = -1;
    printf("Please enter amount of eggs and flour\n");
    scanf("%d", &eggs);
    scanf("%d", &flour);
    bool have_enough_eggs = eggs >= EGGS_NEEDED;
    bool have_enough_flour = flour >= FLOUR_NEEDED;
}

bool can_make_cake = have_enough_flours && have_enough_eggs;

bool can_make_cake = have_enough_flours || have_enough_eggs;

#define EGGS_NEEDED 2
#define FLOUR_NEEDED 5
#include <stdio.h>
#include <stdbool.h>
int main() {
    int eggs = -1;
    int flour = -1;
    printf("Please enter amount of eggs and flour\n");
    scanf("%d", &eggs);
    scanf("%d", &flour);
    bool not_enough_eggs = eggs < EGGS_NEEDED;
    bool not_enough_flour = flour < FLOUR_NEEDED;
}

bool have_enough_flour = !not_enough_flour;

#define EGGS_NEEDED 2
#define FLOUR_NEEDED 5
#include <stdio.h>
#include <stdbool.h>
int main() {
    int eggs = -1;
    int flour = -1;
    printf("Please enter amount of eggs and flour\n");
    scanf("%d", &eggs);
    scanf("%d", &flour);
    bool not_enough_eggs = eggs < EGGS_NEEDED;
    bool not_enough_flour = flour < FLOUR_NEEDED;
    bool can_make_cake = !not_enough_eggs && !not_enough_flour;
}

float f = 5.4;
int x;
scanf("%d", &x);
f += x;

int main() {
    int radius = -1;
    printf("Enter circle radius");
    scanf("%d", &radius);
    printf("Circle area: %d", 3.14 * radius * radius);
}

#define PI 3.14
int main() {
    int radius = -1;
    printf("Enter circle radius");
    scanf("%d", &radius);
    printf("Circle area: %d", PI * radius * radius);
}

1. #define MESSAGE "HELLO WORLD"
2. #define MAX_STUDENTS 500
3. #define ELEMENTS 1024

const double pi = 3.14159;
double r1 = 5.4, r2 = 7.0
const double area = pi * r1 * r1;
// Line below will not compile if uncommented
// area = pi * r2 * r2;

int n;
scanf("%d", &n);

char c1, c2;
scanf("%c%c", &c1, &c2);

int n;
scanf("%d", &n);

int n;
int result = scanf("%d", &n);
if (result != 1) {
    // ...
}

#define GRAVITY 9.8
int main() {
    const double time = 5.4;
    const double velocity = time * GRAVITY;
    printf("Velocity after %.2f secs is %.2f meters/second", time, velocity);
}

int main() {
    const double length = 5.0, width = 3.0;
    const double area_rect = length * width * 0.5;
    printf("Rectangle area: %.2f\n", area_rect);
}

int main() {
    printf("Average: %.2f", (5 + 3.4 + 1.2) / 3);
}

#include <stdio.h>
#define PASSWORD 7521
int main() {
    int password;
    printf("Please enter your password\n");
    scanf("%d", &password);
    if (password == PASSWORD) {
        printf("Access granted!\n");
    } else {
        printf("Access denied!\n");
    }
}

if (boolean statement) {
    // Execute only if statement is true
}
// Continue execution here

#include <stdio.h>
#include <stdbool.h>
int main() {
    int eggs_in_stock = 3;
    int eggs_needed;
    printf("Enter number of needed eggs\n");
    scanf("%d", &eggs_needed);
    if(eggs_in_stock >= eggs_needed) {
        printf("You can make cake!\n");
    }
}

// Code before
if(eggs_in_stock >= eggs_needed)
    printf("You can make cake!");
// Do more stuff after

if(eggs_in_stock >= eggs_needed)
    printf("You can make cake!\n");
    printf("Cake for everybody!");
// Do other stuff

if(eggs_in_stock >= eggs_needed) {
    printf("You can make cake!\n")
}
printf("Cake for everybody!")
// Do other stuff

if (boolean expression) {
    // Execute only if statement is true
} else {
    // Execute only if it isn't
}

#include <stdio.h>
#include <stdbool.h>
int main() {
    int eggs_in_stock = 3, eggs_needed;
    printf("Eggs needed:\n");
    scanf("%d", &eggs_needed);
    if(eggs_in_stock >= eggs_needed) {
        printf("You can make cake!\n");
    } else {
        printf("You cannot make cake!\n");
    }
}

if(...) {
    // Execute if true
}
else {
    // Execute if not
}

if(...)
{
    // Execute if true
}
else
{
    // Execute if not
}

if(something) {
    // do...
} else {
    /// do else ...
}

#include <stdio.h>
int main() {
    int score;
    char grade;
    scanf("%d", &score);
    if(score >= 90) {
        grade = 'A';
    } else if(score >= 80) {
        grade = 'B';
    } else if(score >= 70) {
        grade = 'C';
    } else if(score >= 60) {
        grade = 'D';
    } else {
        grade = 'F'; 
    }
    printf("Your grade is %c\n", grade);
}

if(5 > 7) {
    printf("5 is greater than 7\n");
} else if(5 < 7) {
    printf("5 is smaller than 7\n");
} else if(1 > 0) {
    printf("1 is greater than 0\n");
}

#include <stdio.h>
int main() {
    int ADULT = 18, SENIOR = 65;
    int age;
    scanf("%d", &age);
    if(age >= ADULT) {
        printf("You are an adult\n");
        if(age >= SENIOR) {
            printf("You are a senior\n");
        } else {
            printf("You are not a senior\n");
        }
    } else {
        printf("You are not an adult\n");
    }
}

#include <stdio.h>
int main() {
    int val = 0;
    if (val > 0)
        printf("Positive\n");
        printf("Check complete\n");
    else
        printf("Non-positive\n");
    return 0;
}

boolean expression ? <value if true> : <value if false>;

float discount = total_price > DISCOUNT_LIMIT ? 0.05 : 0;

#include <stdio.h>
#define ADULT 18
int main() {
    int age;
    scanf("%d", &age);
    printf(
        "%s\n", age < ADULT ? 
        "You are not an adult\n" : 
        "You are an adult\n"
    );
}

int jim_age = 30;
int pam_age = 28;
printf("oldest age of jim and pam: %d", jim_age > pam_age ? jim_age : pam_age);

#include <stdio.h>
int main() {
    int secret = 9;
    int guess;
    printf("Enter a guess for the secret number!\n");
    scanf("%d", &guess);
    if (guess == secret) {
        printf("You win - secret was %d!\n", secret);
    } else if (guess < secret) {
        printf("Your guess is smaller than secret!\n");
    } else if (guess > secret) {
        printf("Your guess is bigger than secret!\n");
    }
}

#include <stdio.h>
int main() {
    char grade;
    scanf("%c", &grade);
    if (grade == 'A') {
        printf("Excellent!\n");
    } else if (grade == 'B') {
        printf("Good job\n");
    } else if (grade == 'C') {
        printf("Fair\n");
    } else if (grade == 'D') {
        printf("Needs improvement\n");
    } else if (grade == 'F') {
        printf("Failed\n");
    } else {
        printf("Invalid grade\n");
    }
}

switch (value) {
    case case1:
        // Body if case1
        break;
    case case2:
        // Body if case2
        break;
    // Add more cases if needed
    case default:
        // Body if no other case
}

switch (day) {
    case 1: printf("Monday\n"); break;
    case 2: printf("Tuesday\n"); break;
    case 3: printf("Wednesday\n"); break;
    case 4: printf("Thursday\n"); break;
    case 5: printf("Friday\n"); break;
    case 6: printf("Saturday\n"); break;
    case 7: printf("Sunday\n"); break;
    default: printf("Invalid day\n");
}

#include <stdio.h>
int main() {
    char op;
    double a, b;
    printf("Enter an operator (+, -, *, /, %%, ^): ");
    scanf(" %c", &op);
    printf("Enter two numbers: ");
    scanf("%lf %lf", &a, &b);
    switch (op) {
        case '+':
            printf("Result = %.2f\n", a + b);
            break;
        case '-':
            printf("Result = %.2f\n", a - b);
            break;
        case '*':
            printf("Result = %.2f\n", a * b);
            break;
        case '/':
            if (b != 0) {
                printf("Result = %.2f\n", a / b);
            } else {
                printf("Error: division by zero\n");
            }
            break;
        default:
            printf("Unknown operator\n");
    }
}

#include <stdio.h>
int main() {
    int month;
    printf("Enter month (1–12): ");
    scanf("%d", &month);
    switch (month) {
        case 2:
            printf("28 or 29 days\n");
            break;
        case 4:
        case 6:
        case 9:
        case 11:
            printf("30 days\n");
            break;
        case 1:
        case 3:
        case 5:
        case 7:
        case 8:
        case 10:
        case 12:
            printf("31 days\n");
            break;
        default:
            printf("Invalid month\n");
    }
    return 0;
}

while (boolean expression) {
    // Loop body
}

כשנגיע לתחילת הלולאה, נבדוק האם התנאי מתקיים. במידה וכן, נבצע את קטע הקוד שבתוכה (גוף הלולאה). בסיום גוף הלולאה, נבדוק שוב את התנאי - במידה והוא עדיין מתקיים, נבצע את גוף הלולאה שוב.

#include <stdio.h>
int main() {
    int number = -1;
    while( number <= 0) {
        printf("Enter a positive number\n");
        scanf("%d", &number);
    }
    int i = 2, factorial = 1;
    while(i <= number) {
        factorial *= i++;
    }
    printf("%d! = %d\n", number, factorial);
}

#include <stdbool.h>
while (1) {
    // Infinite loop
}
while  (true) {
    // Infinite loop
}

בהמשך נראה כיצד ניתן לעצור לולאות אינסופיות.

#include <stdio.h>
int main() {
    int secret = 9, guess = -1;
    while (secret != guess) {
        printf("Enter a guess for the secret number!\n");
        scanf("%d", &guess);
        if (guess == secret) {
            printf("You win - secret was %d!\n", secret);
        }
    }
}

do {
    // Loop body
} while (boolean condition);

#include <stdio.h>
int main() {
    int secret = 0, guess;
    do {
        printf("Enter a guess for the secret number!\n");
        scanf("%d", &guess);
    } while (guess != secret);
    printf("You win - secret was %d!\n", secret);
}

int main() {
    int number = -1;
    while (number <= 0) {
        printf("Enter a positive number\n");
        scanf("%d", &number);
    }
    int factorial = 1;
    for (int i = 2; i <= number; i++) {
        factorial *= i;
    }
}

for (expr1; expr2; expr3) {
    body
}

#include <stdio.h>
#define UPPER_BOUND 1000
int main() {
    int sum = 0;
    for (int i = 0; i < UPPER_BOUND; i++) {
        sum += i;
    }
    printf("sum = %d\n", sum);
}

int i;
for (i = 0; i < n; i++) {
    // ...
}

for(;;) {
    // Infinite loop
}

#define N 100
int main() {
    for(int i = 0; i < N; i++) {
        if(i % 3 == 0) {
            continue;
        }
        printf("%d\n", i);
    }
}

#include <stdio.h>
#define UPPER_BOUND 1000 * 1000
#define WANTED_SUM 34
#define NOT_FOUND -1

int main() {
    int wanted_num = NOT_FOUND;
    for (int i = 0; i < UPPER_BOUND; i++) {
        int sum = 0;
        int n = i;
        while (n > 0) {
            sum += n % 10;
            if (sum > WANTED_SUM) {
                break;
            }
            n /= 10;
        }
        if (sum == WANTED_SUM) {
            wanted_num = i;
            break;
        }
    }
    if (wanted_num != NOT_FOUND) {
        printf("wanted number = %d\n", wanted_num);
    } else {
        printf("No such number exists\n");
    }
}

#include <stdio.h>
int main() {
    int input;
    while(1) {
        printf("Enter a positive number\n");
        scanf("%d", &number);
        if(number <= 0) {
            printf("%d is not positive\n", number);
        } else {
            break;
        }
        // Do stuff with positive number
    }
}

#include <stdio.h>
int main() {
    int sum = 0;
    char input;
    while(1) {
        scanf("%d", &input);
        if(input >= '0' && input <= '9') {
            sum += input - '0';
        } else {
            break;
        }
    }
    printf("sum = %d\n", sum);
}

#include <stdio.h>
int main() {
    int num = -1;
    scanf("%d", &num);
    int digits = 1;
    while(num > 0) {
        num /= 10;
    }
    printf("%d digits\n", digits);
}

#include <stdio.h>
int main() {
    for (int i = 1; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
            printf("%d ", i * j);
        }
        printf("\n");
    }
}

הרצאה 4 - פונקציות

בהרצאה זו נגדיר ונרכיב בצורה מסודרת אובייקט שכבר השתשמנו בו המון - פונקציות. פונקציות הן אבן בניין בסיסית בכל שפת תכנות שתלמדו, וסצפיפית ב-C ניתן להשתמש בהן על מנת להפוך את הקוד שלנו להרבה יותר יעיל, קריא ומודולרי.

פגשנו כמה פונקציות עד כה:

1. main - הפונקציה המיוחדת שהקומפיילר קובע בה את תחילת התוכנית. זו פונקציה שמימשנו בעצמנו ולא קראנו לה - מתברר שהקומפיילר הוא זה שקרה לה. כמו כן, אין לה ארגומנטים.
2. printf & scanf - אלו שתי פונקציות שלא כתבנו בעצמנו, אלא הבאנו ממקום אחר ע״י השימוש במאקרו include <stdio.h>#. קראנו לפונקציות אלו באמצעות הסוגריים () והעברנו להן ארגומנטים על מנת שידעו מה להדפיס והיכן לשים קלט מהמשתמש.

כעת הגיע הזמן להגדיר, לממש ולהשתמש בפונקציות משלנו בעצמנו. בניגוד למה שנעשה בדרך כלל בקורס, ראשית נצלול טכנית לכיצד מנגנון הפונקציות עובד, ורק לאחר מכן נדון במוטיבציה ובבעיות שהוא פותר עבורנו. הסיבות לכך יתבררו מיד.

נמשיך בדיון קצר על אורך החיים של משתנים שונים, מתי ניתן להשתמש בהם וכיצד.

זמן חיים ו-scope של משתנים

עד כה כל הגדרנו את כל המשתנים שלנו בתוך פונקציית ה-main. יכולנו להשתמש במשתנה רק לאחר שהצהרנו עליו. עוד מעט כאשר נציג קונספטים חדשים נבחן מדוע ישנם משתנים שמתנהגים אחרת. הנושא הזה מעט טכני ויכול להיות מסובך להבנה - אחרי שנבחן כיצד תמונת הזכרון נראת בקריאה לפונקציות נבין מדוע הוא מהותי וחשוב. לטובת כך נכיר את המושגים הבא:

הגדרה: זמן החיים (lifetime) של משתנה הוא הזמן בו המשתנה קיים בזכרון. לדוגמא, נבחן את התוכנית הבאה:

int main() {
    int x = 5;
    int y = 7;
}

באופן כללי, משתנים חיים מהרגע שהוגדרו ועד סוף הבלוק בהם הוגדרו. בתוכנית הזו זמן החיים של x ארוך משל y - בשורה הראשונה ניתן להשתמש ב-x אך לא ניתן עדיין להשתמש ב-y. כאשר הגענו לסוף הפונקציה בסוגר התחתון {, שני המשתנים ״מתים״ ולא ניתן להשתמש בהם יותר. נבחן דוגמא מעט מורכבת יותר:

int func() {
    int x = 5;
    printf("%d\n", x);
}
int main() {
    int y = 7;
    func1();
    printf("%d\n", y);
}

זמן החיים של המשתנה x הוא מהשורה הראשונה של func ועד לסופה, בעוד ששל y הוא מהשורה הראשונה ב-main עד לסוף ה-main.

לנושא זמן החיים יש משמעות מהותית - למשל בתוכנית הבאה:

#define N 100
int main() {
    int i = 0;
    while(i < N) {
        char c;
        scanf("%c", &c);
        i++;
    }
    printf("last character you entered is %c\n", c);
}

מתברר שתוכנית זו לא תתקמפל בכלל. מדוע? המשתנה c מוגדר בתוך בלוק ה-while ולכן מת בסופו. לכן אי אפשר להשתמש בו לאחר שהבלוק הסתיים. בצורה שונה, אם היינו מנסים להשתמש ב-i לא הייתה בעיה בכלל - i מוגדר בתוך בלוק פונקציית ה-main ולכן אין מניעה להשתמש בו לאחר סיום ה-while.

הערה: יתכן ובקריאה ראשונה לא ברור למה בכלל שהשפה תתנהג בצורה הזאת. מה זה משנה איפה הגדרתי את המשתנה? למה שלא אוכל להשתמש בו? מתברר שהתשובה לכך עמוקה וקשורה לדרך בה שהשפה מתרגמת תוכנה לשפת מכונה ולתמונת הזכרון הנוצרת מכך. קשה להסביר בשלב זה מדוע זה המצב, ולכן נעשה עבודה כעת לשלוט במונחים ובמנגנונים ובהמשך נבין מדוע זו הסיטואציה.

הגדרה: scope (טווח ראייה) של משתנה הוא האיזור בתוכנית בו משתנה ניתן לשימוש.

כמו שראינו, פונקציות יכולות להשתמש רק במשתנים שהעברנו להם. לכן אם נחזור למשל לדוגמא הקודמת:

int func() {
    int x = 5;
    printf("%d\n", x);
}
int main() {
    int y = 7;
    func1();
    printf("%d\n", y);
}

ה-scope של y הוא פונקציית ה-main וה-scope של x הוא func. אם היינו כותבים שורה כמו x = 7 ב-main או y = 2 ב-funcz, התוכנית לא הייתה מתקמפלת. הסיבה לכך? ה-scope של המשתנים מוגבל לבלוק בו הם מוגדרים.

הגדרה: משתנים המוגדרים בתוך בלוק ומתים בסופו נקראים משתנים לוקאליים. זמן החיים וה-scope של משתנים לוקאליים זהה - מהרגע שהוגדרו ועד סוף הבלוק.

כעת נציג כמה אופציות שונות למיקום ההגדרה של משתנים ונבחן את המשמעות והשימוש של כל אחד.

משתנים גלובאליים

משתנה גלובאלי הוא משתנה שלא מוכרז בתוך אף בלוק {}, אלא כשורה בפני עצמה בקובץ - לרוב בראש הקובץ. לדוגמא:

#include <stdio.h>
char c = 'a';
int main() {
    printf("global var = %c\n", c);
    c = 'b';
    printf("global var = %c\n", c);
}

זמן החיים של משתנים גלובאליים וה-scope שלהם זהה - מתחילת התוכנית ועד סופה.

ניתן לקרוא ולכתוב למשתנים גלובאליים מכל מקום בתוכנית. עוד מעט נראה שפונקציות יהוו בלוק קוד משל עצמן, ולכן משתנים גלובאליים יכולים להיות דרך מפתה להציג מידע שצריך לדעת בהרבה מקומות בתוכנית. זמן החיים של משתנה גלובאלי הוא זמן החיים של התוכנית עצמה. עם זאת, בהמשך נראה כי משתנים גלובאליים יכולים להוביל לבאגים משמעותיים ולכן רצוי לצמצם את השימוש בהם למינימום.

משתנים סטאטיים

משתנים סטאטיים הם מעין שילוב בין משתנים לוקאליים למשתנים גלובאליים. זמן החיים שלהם הוא כמו של גלובאלי - מתחילת התוכנית ועד סופה, אבל ה-scope שלהם מוגבל לבלוק בו הם מוגדרים - בדרך כלל פונקציה. הדרך להגדיר משתנה סטאטי הוא ע“י מילת המפתח static - למשל כמו בדוגמא הבא:

void count_times_called() {
    static int times_called = 0;
    printf("I was called %d times", times_called++);
}

int main() {
    count_times_called();
    count_times_called();
    count_times_called();
}

משתנה סטאטי מאותחל פעם אחת בתחילת התוכנית, כלומר השורה הראשונה בפונקציה שהגדרנו מתבצעת פעם אחת בלבד.

int classify_number(int n) {
    if(n >= 0) {
        if(n == 0) {
            return IS_ZERO;
        } else {
            if(n <= 100) {
                return BETWEEN_0_AND_100;
            } else {
                return LARGER_THAN_100;
            }
        }
    } else {
        return IS_NEGATIVE;
    }
}

int main() {
    int x = y;
    int y = 7;
}

void f1(void) {
    printf("Hi from f1\n");
    f2();
}
void f2(void) {
    printf("Hi from f2\n");
}
int main() {
    f1();
}

void f1(void);
void f2(void);

void f1(void) {
    printf("Hi from f1\n");
    f2();
}
void f2(void) {
    printf("Hi from f2\n");
}
int main() {
    f1();
}

int clamp(int lower, int higher, int x) {
    if (x <= lower) {
        return lower;
    }
    if (x >= higher) {
        return higher;
    }
    return x;
}

int clamp(int lower, int higher, int x) {
    if(x <= lower) {
        return lower;
    } else if(x >= higher) {
        return higher;
    }
    return x;
}
int max2(int x, int y) {
    return a > b ? a : b;
}
int max_of_clamp(int lower, int higher, int x, int y) {
    return max2(clamp(lower, higher, x), clamp(lower, higher, y));
}

// Pass arguments to equation in the format ax^2 + bx + c = 0
float solve_quadratic(float a, float b, float c);

$$ x_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac} }{2a} $$

#include <math.h>
#include <stdio.h>
#define NO_REAL_SOLS 1
// discr - short for discriminant
float calculate_discr(float a, float b, float c) {
    return pow(b, 2) - 4 * a * c;
}
float calculate_solution(float a, float b, float discr) {
    return (-b + sqrt(discr)) / (2 * a);
}
float solve_quadratic(float a, float b, float c) {
    float discr = calculate_discr(a, b, c);
    if (discr < 0) {
        printf("No real solutions!\n");
        return NO_REAL_SOLS;
    }
    return calculate_solution(a, b, discr);
}

#include <stdio.h>

#define SECONDS_IN_MINUTE 60
#define MINUTES_IN_HOUR 60
#define SECONDS_IN_HOUR (SECONDS_IN_MINUTE) * (MINUTES_IN_HOUR)

int extract_hours(int seconds) { return seconds / SECONDS_IN_HOUR; }
int extract_minutes(int seconds) { return seconds / SECONDS_IN_MINUTE; }
void convert_seconds_to_time(int seconds) {
    int hours = extract_hours(seconds);
    seconds %= SECONDS_IN_HOUR;
    int minutes = extract_minutes(seconds);
    seconds %= SECONDS_IN_MINUTE;
    printf("%d : %d : %d\n", hours, minutes, seconds);
}

#include <stdio.h>
#define PI 3.14
double calculate_ellipse_area(double r1, double r2) {
    return PI * r1 * r2;
}
void show_ellipse_area(double r1, double r2) {
    printf("area: %.2lf", calculate_ellipse_area(r1, r2));
}
int main() {
    double r1, r2;
    scanf("%lf%lf", &r1, &r2);
    show_area(r);
}

מצביעים (pointers)

עד כה התעסקנו במשתנים מסוגים שונים. כמה דוגמאות לתזכורת:

1. int x = 5 - מספר שלם.
2. float pi = 3.14 - מספר עשרוני.
3. double e = 2.17 - מספר עשרוני ברמת דיוק גבוהה.
4. 'char c = 'g - תו בודד.

כעת נתחיל לדבר על מצביעים - משתנים חדשים שיסייעו לנו מאוד בפתרון בעיות מורכבות יותר, ולמעשה ישלימו לנו כמעט לגמרי את כל הכלים שאנחנו צריכים בשביל לבנות כל תוכנית שנרצה.

מצביעים ידועים לשמצה בתור נושא קשה מאוד להבנה, ובמידה מסוימת של צדק - הם קונספטואלית שונים ממה שפגשנו עד כה. עם זאת, העקרון העומד מאחוריהם מאוד פשוט. אנו השקענו מאמץ גדול בלמידה של תמונת הזכרון, וכעת נראה שזה ישתלם עבורינו מאוד.

#include <stdio.h>
void swap(int a, int b) {
    int tmp = a;
    a = b;
    b = tmp;
}
int main() {
    int a = 1;
    int b = 5;
    printf("before call to swap: a = %d, b = %d", a, b);
    swap(a, b);
    printf("after call to swap: a = %d, b = %d", a, b);
}

type var = some_value;
type *ptr = &var;
type another_var = *ptr;

void swap(char *x, char *y) {
    char tmp = *x;
    *x = *y;
    *y = tmp;
}
void sort(char *a, char *b, char *c) {
    if (a <= b) {
        swap(a, b);
    }
    if (a <= c) {
        swap(a, c);
    }
    if (b <= c) {
        swap(b, c);
    }
}

#include <stdio.h>
void swap(int* a, int* b) {
    if (a == NULL || b == NULL) {
        printf("passed NULL pointer!\n");
        return;
    }
    // ... rest of swap
}

#include <stdio.h>
void swap(int* a, int* b) {
    if (!a || !b) {
        printf("passed NULL pointer!\n");
        return;
    }
    // ... rest of swap
}

הרצאה 6 - מערכים סטאטיים ודינמיים

מערכים סטאטיים

נפענח בעיה פשוטה. נניח שיש לנו קורס עם 3 סטודנטים ואנחנו רוצים לבצע כל מיני פעולות פשוטות - קבלת ממוצע, חציון וכו’. יתכן ונכתוב קוד שנראה כך:

int main() {
    double grade1, grade2, grade3;
    double avg = calc_avg(grade1, grade2, grade3);
    /// etc...
}

זה נראה הגיוני. עם זאת, זה מאוד לא ניתן להרחבה (scalable) - מה יקרה שיהיו בקורס 10 סטודנטים? או 100 או 1000? כמובן שלא מצופה מאיתנו להגדיר משתנה לכל ערך שנרצה להגדיר. הבעיה אותה נרצה לפתור היא למעשה - כיצד נטפל במספר שרירותי של אובייקטים מסוג מסוים?

הגדרה: מערך (array) הוא סדרה באורך שרירותי של משתנים מאותו הטיפוס.

לפני הגדרה מדויקת, כרגיל ניתן דוגמא להתרשמות. נרצה להגדיר מערך של 100 ציונים 100 סטודנטים ולגשת לחלק מהציונים עצמם. ניתן לעשות זאת כך:

int main() {
    double grades[100];
    grades[64] = 90;
    // grades[500] = 30; <- Error!
}

נפרט מה אנו רואים בדוגמא. בהתחלה, הגדרנו את המשתנה grades -

נפרט:

1. המשתנה grades הוא מערך באורך 100 של משתנים מסוג double.
2. עבור i כלשהו המקיים i >= 0 && i < 100, המשתנה grades[i] הוא האיבר ה-i במערך. במקרה זה, i נקראה האינדקס של האיבר במערך.

הערות:

1. האיבר הראשון במערך הוא grades[0] ולא grades[1]. ברוב שפות התכנות מתחילים לספור מערכים מ-0 ולא מ-1.
2. כרגע אנו עוסקים במערכים סטאטיים שגודלם הוא בהכרח מספר קבוע. למשל, קטע הקוד הבא לא יתקמפל:, והסיבה לכך עמוקה וקשורה למחסנית הקריאות:

int array_length;
scanf("%d", &array_length);
int array[array_length];

ניתן לתת ערכים התחלתיים למשתנים שבתוך המערך ע“י הסינטקס הבא:

int first_primes[6] = {2, 3, 5, 7, 11, 13};

3. איברים במערך סטאטי יושבים בכתובת עוקבות בזכרון. למשל אם הקצנו מערך של int בכתובת 100, מכיוון שגודל כל איבר הוא 4 בתים (sizeof(int) == 4) האיברים ישבו בכתובות 108, 104, 100 וכך הלאה.

לדוגמא - ננתח את הציונים כפי שרצינו קודם:

#define STUDENTS 100
int main() {
    double grades[STUDENTS];
    for(int i = 0; i < STUDENTS; i++) {
        scanf("%.2lf", &students[i]);
    }
    int grades_sum = 0;
    for(int i = 0; i < STUDENTS; i++) {
        sum += grades[i];
    }
    printf("Course average: %.2lf\n", grades_sum / STUDENTS);
}

אלגוריתמים

כעת, נפגש עם האלגוריתם הראשון שננתח בקורס. יתכן ויש לנו הבנה אינטואטיבית של המושג, אבל לשלמות רצוי שנגדיר אותו על מנת שכולנו נדבר את אותה השפה:

הגדרה: אלגוריתם הוא סדרת פעולות מדויקות לביצוע משימה או פתרון בעיה כלשהי המתחשב בכל המקרים האפשריים.

כלומר, בהנתן בעיה מסוימת, אלגוריתם הוא סדר פעולות שיש לבצע על מנת לקבל פתרון לבעיה.

הגדרה מדויקת של הבעיה היא קריטית לחלוטין על מנת למצוא לה פתרון. בדרך כלל בקורס נתאר בעיות בצורה של קלט ופלט - כלומר, בהנתן קלט מסוים, נרצה להפעיל אלגוריתם כלשהו על מנת לקבל פלט מסוים. כמה דוגמאות לבעיות:

1. בהנתן מספר חיובי n, יש לקבוע האם הוא ראשוני או לא. הקלט הוא מספר חיובי והפלט הוא משתנה בוליאני שערכו true אם הקלט ראשוני ו-false אחרת.
2. בהנתן מערך של ציונים במבחן, יש לחשב את הממוצע. הקלט הוא מערך הציונים והפלט הוא משתנה שמכיל את הממוצע שלהם.
3. בהנתן מערך כלשהו של מספרים arr ומספר כלשהו x, יש לקבוע האם x נמצא במערך או לא. הקלט הוא מערך ומספר והפלט הוא משתנה בוליאני שערכו true אם x נמצא במערך ו-false אחרת.

דוגמא

ננתח את הבעיה הבאה: נרצה להדפיס את כל המספרים הראשוניים בין 0 למספר כלשהו N הנתון ב-define#. לטובת זאת קיים אלגוריתם עתיק בשם ה-Sieve of Eratosthenes, שפותר את הבעיה בצורה יעילה. האלגוריתם פועל לפי השלבים הבאים:

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

בתרגום לקוד, התוכנית שלנו תראה כך:

1. נייצר מערך של משתנים שגודלו N + 1- איבר במערך עבור כל המספרים מ-0 ועד N, כולל (לכן N + 1 ולא N).
2. מעניין אותנו רק האם האיבר באינדקס מסוים ראשוני או לא ולא מה ערכו, ולכן המערך יהיה מסוג bool.
3. מכיוון שהאלגוריתם פוסל מספרים ראשונים, נאתחל את כל המערך להיות true.

נממש:

#include <stdbool.h>
#define N 1000
void sieve(void) {
    bool is_prime[N + 1];
    for(int i = 2; i <= N + 1; i++) {
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for(int p = 2; p * p <= N; p++) {
        if(!is_prime(p)) {
            continue;
        }
        for(int i = p; i <= N / p; i++) {
            prime[i * p] = false;
        }
    }
    printf("Primes between 0 and %d are:\n", N);
    for(int i = 0; i < N; i++) {
        if(is_prime[i]) {
            printf("%d, " i);
        }
    }
}

הערה: שימוש ב-sizeof על מערך מחזיר את מספר הבתים במערך:

#define N 10
#define K 20
int main() {
    int int_arr[N];
    char char_arr[K];
    printf("int_arr size = %d, char_arr size = %d\n", sizeof(int_arr), sizeof(char_arr));
}

מערכים רב-מימדיים

בדוגמא הקודמת, הגדרנו מערך באופן הבא int grades[NUM_STUDENTS] - רשימה של מספרים שמייצגת את הציונים של הסטודנטים בקורס מסוים. זו דוגמא למערך חד-מימדי - לכל אובייקט יש אינדקס אחד בלבד. למשל, הציון של הסטודנט הראשון בקורס הוא grades[0]. בצורה דומה, ניתן להגדיר מערכים דו-מימדיים - מערכים בהם לכל אובייקט יש שני אינדקסים. כמו כן, באופן כללי ניתן להגדיר מערכים רב-מימדיים עם מספר מימדים לבחירתנו.

למשל, נניח שיש קבוצה של 50 סטודנטים ושכל אחד מהם לוקח 3 קורסים. ניתן לחשוב על כל ציון של סטודנט בתור בתור איבר עם שני אינדקסים - אחד עבור מספר הקורס והשני עבור מספר הסטודנט. הדרך להגדיר מערך דו-מימדי מסוג כזה דומה מאוד להגדרת מערך חד-מימדי:

#define NUM_COURSES 3
#define NUM_STUDENTS 50
int grades[NUM_COURSES][NUM_STUDENTS];

אינטואיטיבית, מערך דו-מימדי הוא מערך שכל איבר בו הוא בעצמו מערך. המערך grades כעת הוא מערך באורך 3 שכל איבר בו הוא מערך באורך 50.

דוגמא קלאסית למערך דו-מימדי היא הגדרת מטריצה בקוד. אינטואיטיבית ניתן לחשוב על מטריצה בתור מערך דו-מימדי - כמו שכותבים במתמטיקה עם שני אינדקסים $a_{ij}‎$, נרצה לכתוב בקוד משהו בסגנון של a[i][j].

int matrix[3][4];

נדגיש שיש משמעות מהותית לסדר בו האינדקסים מופיעים: המשתנה matrix הוא מערך שכל איבר בו הוא מערך של 4 איברי int. למשל, matrix[1] (אינטואיטיבית - השורה השנייה במטריצה) הוא מערך של 4 int-ים. המשתנה matrix[1][2] הוא משתנה int רגיל.

בשביל לאתחל מערך דו-מימדי, ניתן לקנן (nest) את אתחולי המערכים שראינו קודם. נניח למשל שנרצה לכתוב את המטריצה הבאה בקוד:

הדרך להצהיר עליה בקוד תהיה כך:

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

להזכירכם, הקומפיילר מתעלם מרווחים בקוד - ההזחות והחלוקה לשורות היא למען קריאות הקוד עבור המתכנת ואין לה משמעות פרקטית. המשמעות החשובה היא פתיחת סוגריים מסולסלים {} לאתחול המערך הכולל matrix, ואז בתוכו אתחול כך מערך כשורה עם {} משל עצמו.

אין הגבלה למספר המימדים שמערך יכול לקבל:

int multidim_array[5][4][99][205][10];

דוגמא: כתבו תוכנית שמחברת ומכפילה 2 מטריצות וכותבת את התוצאה לתוך מטריצה שלישית, כאשר גדלי המטריצות הם 10x10.

#define SIZE 10
int main() {
    int A[SIZE][SIZE], B[SIZE][SIZE], C[SIZE][SIZE];
    
    // Matrix addition
    for(int i = 0; i < SIZE; i++) {
        for(int j = 0; j < SIZE; j++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }

    // Matrix multiplication
    for(int i = 0; i < SIZE; i++) {
        for(int j = 0; j < SIZE; j++) {
            for(int k = 0; k < SIZE; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

מערכים, מצביעים, ותמונת הזכרון

ראינו בהרצאה קודמת כיצד פונקציות מרכיבות את תמונת הזכרון על מחסנית קריאות - כל פונקציה הנקראת (גם main) מקצה על מחסנית הקריאות את הארגומנטים שהיא מקבלת והמשתנים הלוקאליים שהיא מגדירה. כל הקצאה כזו נקראת stack frame. כעת נרצה לבחון כיצד האירוע הזה נראה כשמשתמשים במערכים.

נבחן למשל את התוכנית הבאה:

int main() {
    int x = 78;
    char letters[4] = {'a', 'b', 'c', 'd'};
    float pi = 3.14;
}

כאשר אנו מגדירים מערך סטאטי באורך n בזכרון, הקומפיילר מתייחס לכך כאילו הקצנו n משתנים - דוחף אותם ברצף זה אחר זה למחסנית הקריאות. מחסנית הקריאות תראה כך:

כלומר, מערכים סטאטיים תמיד מוגדרים בצורה רציפה בזכרון.

בצורה דומה, מערכים רב-מימדיים נדחפים על מחסנית הקריאות כמערך אחד גדול של איברים - למשל בתוכנית הבאה:

#define N 2
int main() {
    char x = 'x';
    int matrix[N][N] = {
        {1, 2},
        {3, 4}
    };
}

מחסנית הקריאות תראה כך:

הקומפיילר מאפשר לנו “לראות” בקוד את המערך הרב-מימדי בתוך מערך של מערכים כפי שנוח לנו, אבל בפועל בזכרון מקצה את האיברים ברצף זה אחר זה.

מערכים ומצביעים

עכשיו כשהכרנו מהם מערכים, הגיע הזמן לחבר אותם לאובייקט שאנחנו כבר מכירים היטב - מצביעים. כפי שראינו כעת, כשאנחנו מגדירים מערך סטאטי int numbers[5], הקומפיילר מקצה 5 int-ים זה אחר ברצף על המחסנית. מעבר לכך, מסתבר שהמשתנה numbers עצמו הוא מצביע - ספציפית, לאיבר הראשון במערך! כלומר מתקיים:

int numbers[5];
numbers == &numbers[0];

כלומר, הטיפוס של המשתנה numbers הוא *int. כשאנחנו משתמשים בסינטקס numbers[i], אנחנו מבקשים מהקומפיילר לבצע את הפעולות הבאה:

1. התחל בכתובת בזכרון ש-numbers מכיל
2. התקדם בזכרון i איברים
3. בצע dereference * לאיבר הגעת אליו

הדבר הזה מאוד דומה לאריתמטיקה של מצביעים, ומסתבר שלא במקרה! הסינטקס numbers[i] הוא קיצור נחמד שהשפה מציעה לנו לביטוי קצת יותר ארוך שכבר פגשנו:

// Lines are equivalent
numbers[i];
*(numbers + i);

כלומר, ניתן לחשוב שמערכים ומצביעים הם שקולים לחלוטין. זה נכון לרוב השיקולים - בהמשך נראה מספר הבדלים ביניהם.

מערכים ופונקציות

נניח כעת שנרצה להעביר מערכים לפונקציות. מכיוון שראינו שמערך הוא למעשה מצביע לאיבר הראשון במערך, נוכל להעביר מצביע כפי שעשינו כבר:

int calc_avg(int* grades, int grades_len) {
    int sum = 0;
    for(int i = 0; i < grades_len; i++) {
        sum += grades[i];
    }
    printf("sizeof grades: %d\n", sizeof(grades));
    return sum / grades_len;
}
#define NUM_GRADES 5
int main() {
    int grades[NUM_GRADES] = {90, 45, 32, 100, 93};
    printf("Average is: %d", calc_avg(grades, NUM_GRADES));
}

נשים לב שאנחנו חייבים לתת לפונקציה את אורך המערך במידה ונרצה לבצע איטרציות מעליו - אחרת, אין לה דרך לדעת כמה איברים יש בו - מצביע הוא כתובת בזכרון ולא מעבר לכך. כמו כן, כאשר נדפיס את גודל המשתנה grades, נקבל 8 בתים - גודל של מצביע סטנדרטי במערכת 64bit.

עם זאת, כפי שראינו קודם, מערכים סטאטיים הם מערכים שהקומפיילר יודע מראש בזמן קומפילציה מה גודלם - אחרת הוא לא יכל להקצות אותם. לכן, קיימות שתי דרכים נוספות להעביר מערכים סטאטיים לפונקציות, שנראת מעט שונה מהעברת המצביע:

int calc_avg(int grades[], int grades_len);
// or like this:
int calc_avg(int grades[NUM_GRADES], int grades_len);
#define NUM_GRADES 5
int main() {
    int grades[NUM_GRADES] = {90, 45, 32, 100, 93};
    printf("Average is: %d", calc_avg(grades, NUM_GRADES));
}

הסינטקס שונה קצת, אבל המשמעות זהה - הקומפיילר מזהה את grades בתוך מצביע לאיבר כלשהו, שאנחנו לאחר מכן עושים בו שימוש כמערך. במקרה זה אנחנו אומרים שהמערך דועך למצביע (array decay to pointer). הסיבה שנגיד שהוא דועך היא מכיוון שהפונקציה מפרשת את המערך כמצביע, לא ניתן לבצע sizeof ולקבל את גודל המערך כמו שראינו בעבר:

int calc_avg(int grades[], int grades_len) {
    // rest of code
    printf("sizeof(grades) = %d\n", sizeof(grades)); // 8! sizeof(ptr)
}
#define NUM_GRADES 5
int main() {
    int grades[NUM_GRADES] = {90, 45, 32, 100, 93};
    printf("Average is: %d", calc_avg(grades, NUM_GRADES));
}

המערך “מאבד” את המידע על גודלו מכיוון שהוא מועבר לפונקציה כמצביע. לכן, צורות הכתיבה עם [] בהעברה לפונקציה אינן מומלצות - כתיבה בצורה int fn(int* arr, int len) היא המועדפת ובה נשתמש בקורס.

התמונה מסתבכת כאשר מדברים על מערכים דו-מימדיים. להזכירכם, מערכים רב-מימדיים נשמרים בזכרון כרצף של מערכים על מחסנית הקריאות. נבחן למשל את התוכנית הבאה:

int main() {
    int array[4][3];
    array[1][2] = 0;
}

כך שתמונת הזכרון נראת כך:

כאשר נזכיר שה-“רווחים” הקטנים שציירנו בין המערכים אינם באמת קיימים.

מה למעשה אנחנו מבקשים מהקומפיילר לעשות?

1. הקצה עבורינו מערך של 4 איברים, בו כל איבר הוא מערך של 3 משתני int.
2. גש למערך השני מתוך החמישה ובתוכו לאיבר השלישי.
3. כתוב לתוכו 0.

נפענח את שלב 2. בשביל להגיע למערך השני, הקומפיילר צריך לדעת כמה איברים יש בכל מערך - הוא יודע את המידע הזה מההקצאה, 3 איברים. לכן הוא מפענח את הפקודה array[1][2] בתור - התקדם 3 איברים ואז 2 איברים וכך תגיע לאיבר הרצוי.

באופן כללי, עבור מערך דו-מימדי int arr[N][M], גישה לאיבר arr[i][j] תפורש באופן הבא כאריתמטיקת מצביעים:

כלומר, הקומפיילר צריך לדעת כמה איברים יש בכל שורה, אבל לא רלוונטי לדעת כמה שורות יש. כעת נבחן את אותה הדוגמא בדיוק, רק בתוך פונקציה:

void fn(int array[][]) {
    array[1][2] = 0;
}
int main() {
    int array[4][3];
    fn(array);
}

כעת הקומפיילר בתוך הפונקציה לא יודע כמה איברים יש בכל שורה! זו בעיה מהותית, ולכן נהיה חייבים להעביר אותו:

void fn(int array[][3]) {
    array[1][2] = 0;
}
int main() {
    int array[4][3];
    fn(array);
}

כל הסיפור המורכב הזה יכול להמנע אם נעביר מערכים לפונקציות כמצביעים יחד עם אורך המערכים שהם מייצגים במקום להתעקש על מערכים, ולכן כך נעשה בדרך כלל.

סיכום

נסכם את ההבדלים בין מערכים סטאטיים למצביעים:

1. הצהרה על מערך סטאטי, למשל int arr[5], מקצה עבורו זכרון ישירות. לעומת זאת, הצהרה על מצביע int* arr שלא מצביע לכלום לא מקצה זכרון עבורו.
2. מידע על גודל הזכרון - שימוש ב-sizeof על מערך סטאטי תחזיר את גודל כל הזכרון שכל האיברים במערך תופסים, לעומת על מצביע שתחזיר את הגודל שהמצביע לוקח.
3. לא ניתן לשנות לאן מערך “מצביע” - למשל כאן נקבל שגיאת קומפילציה:

int arr1[4];
int arr2[3];
arr1 = arr2; // Compilation error!

הערות:

1. נשים לב שמערכים נשלחים לפונקציה כמצביע, ולכן בהכרח עוברים by reference! אין דרך להעביר מערך by value לפונקציה.
2. נשים לב שכשאנחנו מעבירים מצביע שמייצג מערך לפונקציה, אנחנו חייבים לספק ביחד איתו גם את אורך המערך - הפונקציה מקבלת מצביע בלבד, ללא מידע על כמה איברים יש בו.

הקצאה דינמית (dynamic allocation)

עד כה המערכים בהם השתמשנו היו בעלי גודל סטאטי - כלומר, ידוע בזמן קומפילציה, לפני שהתוכנית רצה. כמו כן, ראינו שהצהרה על מערך עם גודל דינמי - כלומר, ידוע רק בזמן ריצת התוכנית - הוא בלתי אפשרי. מדוע? הסיבה לכך קשורה למחסנית הקריאות וזו אחת הסיבות העיקריות שהקדשנו זמן רב להבנה עמוקה שלה. זו נקודה קריטית ולכן הקדישו זמן להבנה עמוקה שלה.

נניח שנרצה מערך בגודל דינמי ונכתוב משהו בסגנון הזה:

int array_length;
scanf("%d", &array_length);
int array[array_length];

מה ביקשנו בעצם מהקומפיילר? תקצה לנו על מחסנית הקריאות מערך באורך array_length. עם זאת, לקומפיילר אין מושג איזה מספר המשתמש יכניס! הוא לא יודע להגיד בזמן הקומפילציה כמה בתים על מחסנית הקריאות צריך לפנות בשביל שיהיה מספיק מקום לכל המערך, ולכן יסרב לקמפל את הקוד שלנו.

ניתן לחשוב שמדובר בבעיה לא קריטית, אבל זו תהיה טעות. נניח שאנחנו כותבים תוכנית שקוראת מקובץ אקסל את הציונים של כל הסטודנטים בקורס ומכניסה אותם למערך בשביל לחשב עליהם סטטיסטיקות. כל סמסטר יש מספר שונה של סטודנטים - איך על התוכנית לפעול? תוכניות שצריכות לבצע פעולות התלויות בקלט הן מהנפוצות ביותר ולכן לא נוכל להסתפק בהקצאת זכרון סטאטית בלבד.

נאפיין את הפתרון שאנחנו רוצים, בדומה לאיך שהקומפיילר עובד עם הקצאות סטאטיות:

1. אנחנו צריכים דרך בה התוכנית שלנו תקצה גודל מסוים של זכרון שאינו על מחסנית הקריאות - זאת בדומה לדחיפה על מחסנית הקריאות של הקומפיילר.
2. אנחנו צריכים לקבל מצביע לאותו איזור בזכרון שהקצנו - זאת בדומה להכרזה על מערך סטאטי.
3. אנחנו צריכים לדעת “לשחרר” את הזכרון אחרי שסיימנו איתו - זאת בדומה לקיפול המחסנית בסוף קריאה לפונקציה.

פונקציית malloc

לטובת הבעיה הזו קיימת פונקציה מיוחדת וחשובה מאוד בשפה בשם malloc (קיצור של memory allocation), המוגדרת בספרייה <stdlib.h>. הפונקציה מקבלת את גודל הזכרון בבתים שהמתכנת מבקש ומחזירה מצביע לאותו הזכרון. מכיוון שהקומפיילר לא אחראי כבר על ההקצאה הזו, הוא לא יכול “לקפל” אותו עבורינו כשלא נצטרך אותו יותר - באחריותנו כמתכנתים יהיה לעשות זאת. חתימת הפונקציות הרלוונטיות היא:

#include <stdlib.h>
void* malloc(size_t size);
void free(void* ptr);

הפונקציה מחזירה כתובת כללית בזכרון מסוג *void - הגיוני מכיוון שאנחנו מבקשים ממנה בלוק זכרון ללא מידע על הטיפוס שבלוק זה ייצג. size_t הוא טיפוס המוגדר בקובץ <stdlib.h> שמייצג גודל אי-שלילי כלשהו. free תקבל מצביע שהוחזר ע״י malloc ותשחרר אותו.

דוגמא: נניח שאנחנו רוצים תוכנית בה המשתמש יכניס זה אחר זה ציונים של סטודנטים ולאחר מכן יקבל סטטיסטיקות עליהם. ננסה לכתוב תוכנית מלאה לחלוטין - בדיקות של כל המשתנים הרלוונטים, לולאות במקומות המתאימים וכו׳.

#include <stdlib.h>
#include <stdio.h>
int calc_avg(int* grades);
int calc_median(int* grades);
void grades_statistics(void) {
    int num_students;
    do {
        printf("Enter a positive number of students in course\n");
        scanf("%d", &num_students);
    } while(num_students <= 0);
    int* grades = (int*)malloc(num_students * sizeof(int));
    if(!grades) { // can also write grades != NULL
        printf("could not allocate memory - exiting\n");
        return;
    }
    for(int i = 0; i < num_students; i++) {
        printf("Enter grade for student number %d\n", i);
        scanf("%d", &grades[i]);
    }
    printf("Course with %d students: %d average, %d median\n",
        num_students, calc_avg(grades), calc_median(grades));
    free(grades);
}

נשים לב לכמה נקודות חשובות:

1. במידה ו-malloc נכשלת היא מחזירה NULL. חובה לבדוק כל קריאה ל-malloc עבור החזרת NULL! באופן כללי, malloc אמורה להכשל רק במצבי קיצון ולכן סיטואציה זו אינה נפוצה ברוב המקרים, אבל כדאי להכנס להרגל של הבדיקה - אחרת יתכן והתוכנית שלנו נכשל ולא נדע אפילו למה.
2. הארגומנט שהעברנו ל-malloc הוא num_students * sizeof(int). זו דרך קלאסית להשתמש ב-malloc - גודל הזכרון שאנחנו צריכים הוא מספר המשתנים הרצויים כפול גודל הזכרון הנדרש לכל אחד מהם. באופן כללי יש לבצע כך הקצאת מערך דינמי.
3. לאחר סיום השימוש בזכרון ביצענו free. נרחיב מיד על נושא זה, אבל חובה לשחרר כל זכרון שהקצנו לאורך התוכנית. כמו כן, את השחרור עצמו רצוי לבצע מיד עם סיום השימוש בזכרון.

free ושחרור זכרון

free יכולה להיות מבלבלת מעט וקשה להבנה מכיוון שהיא לא נותנת שום אינדיקציה להצלחתה, ובמידה ולא נשתמש בה - לא נבחין מיידית בזה גם. אם כן, למה היא חשובה בכלל?

הזכרון במערכת שלנו הוא משאב מוגבל במגוון דרכים - הדרך הבסיסית ביותר היא גודל הזכרון הפיזי במחשב בו אנחנו עובדים. כמו שראינו קודם, גודל הזכרון הפיזי במחשב הוא מספר סופי כלשהו. כאשר אנחנו מבצעים malloc, התוכנית שלנו מסמנת בלוק זכרון כמוקצה מתוך כלל הזכרון הזמין - לאף גורם אחר על המחשב אין רשות לגשת לבלוק הזכרון שלנו. כאשר אנחנו משחררים בלוק זכרון, אנחנו מאפשרים לגורמים אחרים במחשב שלנו לעשות שימוש חוזר באותו הבלוק. כשאנחנו שוכחים לעשות זאת, אף אחד אחר לא יכול להשתמש בבלוק זה, למרות שהוא לא נמצא בשימוש שלנו יותר.

אם שכחנו לשחרר הקצאת malloc אחת שלא מקצה הרבה זכרון, ככל הנראה לא תהיה לכך השפעה שלילית על ריצת התוכנית והמחשב שלנו. נניח למשל שנוריד את שורת ה-free בפונקציית הסטטיסטיקות שכתבנו לעיל, ופונקציה זו נקראת כל פעם שסטודנט רוצה לחשב את הממוצע שלו. מהר מאוד הקצאת הזכרון של התוכנית תעלה דרמטית, עד לקריסה של התוכנית ו/או המחשב - אף תוכנית אחרת לא יכולה להתנהל כי אין זכרון פנוי.

באג מסוג זה נקרא דליפת זכרון והוא עם פוטנציאל חמור מאוד. בהמשך כשרצף הקריאות בין פונקציות יתחיל להסתבך, נראה שגם קשה לדעת בדיוק איפה יש לבצע free, למשל כשפונקציה A תחזיר מצביע שהגיע מ-malloc ופונקציה B אחרת ״תקבל עליו אחריות״ ותצטרך לשחרר אותו בהמשך. לדוגמא, נבחן תוכנית הקוראת ל-grades_statistics שהגדרנו קודם, בה הורדנו את שחרור עם free:

int calc_avg(int* grades);
int calc_median(int* grades);
void grades_statistics(void) {
    int num_students;
    do {
        printf("Enter a positive number of students in course\n");
        scanf("%d", &num_students);
    } while(num_students <= 0);
    int* grades = (int*)malloc(num_students * sizeof(int));
    // ... rest of function
    // free(grades);
}
int main() {
    int i = 0;
    while(1) {
        printf("Printing stats forcourse number %d\n", i++);
        grades_statistics();
    }
}

התוכנית מבצעת בלולאה אינסופית את הפונקציה. כל הקצאה כזו מקצה גודל כלשהו ולא משחררת אותו - לאורך זמן וקריאות מרובות, הזכרון של התוכנית יתחיל להתכלות, ובמידה והתוכנית תרוץ לאורך זמן יתכן והזכרון כולו יגמר.

הערות:

1. כאשר אנו מקצים דינמית בתוך פונקציה ומשחררים בסופה, דרך טובה לזכור לעשות זאת היא לכתוב את malloc ו-free בזוגות:

void my_fn(int n) {
    int* mem = (int*)malloc(sizeof(int) * n);
    // ... rest of program using mem
    free(m);
}

ואז להשלים את שאר התוכנית בין malloc ל-free.

2. (העשרה) malloc מבקשת את הזכרון הזה ממערכת ההפעלה, שמקצה אותו על איזור מיוחד בזכרון שסימטרי למחסנית ונקרא “ערימה” (heap). זה ההבדל הטכני מהקצאה סטאטית ע״י הקומפיילר שמבצע זאת על גבי המחסנית.

3. (העשרה) לא נכון בדיוק להגיד ש-free מקצה זכרון פיזי ושהוא המשאב שנגמר כשלא משחררים זכרון. בקורסים מתקדמים תלמדו שהמשאב שנגמר נקרא זכרון וירטואלי המנוהל ע״י מערכת ההפעלה, והקשר שלו לזכרון הפיזי הוא מיוחד ומעניין.

חיפוש מספר במערך

כעת נשתמש בידע שצברנו על מערכים על מנת לייצר אלגוריתם הפותר בעיה קלאסית - בהנתן מערך ומספר כלשהו, כיצד נמצא את האינדקס של המספר במערך, אם קיים?

פתרון פשוט, קל ונכון הוא חיפוש בכל המערך. המימוש אינטואיטיבי מאוד:

#define NOT_IN_ARRAY -1
int search_in_array(int* arr, int len, int target) {
    for(int i = 0; i < len; i++) {
        if(arr[i] == target) {
            return i;
        }
    }
    return NOT_IN_ARRAY;
}

במקרה בו המספר אינו במערך, נצטרך לעבור על המספרים לפני שנדע זאת - נבצע סה“כ len השוואות ואז נצא. זהו למעשה המקרה הגרוע ביותר - אם המספר במערך נסיים לכל היותר ב-len השוואות גם כן. ניתן לשאול האם זהו האלגוריתם היעיל ביותר שניתן לייצר לבעיה הזו - זוהי שאלה שננתח בצורה מדויקת ומתמטית בהמשך הקורס כאשר נדון בסיבוכיות, אבל כעת ננסח אותה בצורה אינטואיטיבית:

בעיה: בהנתן מערך באורך n, האם ניתן למצוא את האינדקס של מספר target, אם קיים, בפחות מ-n השוואות במקרה הגרוע ביותר?

זוהי לא שאלה קלה, אבל ניתן להוכיח שהתשובה היא לא בצורה מדויקת:

1. נניח בשלילה שקיים אלגוריתם שמוצא את האינדקס של target, אם קיים, ב-k < n השוואות.
2. מכיוון שיש n איברים וביצענו k השוואות, נותרו n - k איברים אליהם לא ביצענו השוואה.
3. עבור כל מערך בו target הוא אחד מה-n - k איברים הללו, האלגוריתם שלנו נכשל.

כלומר - הוכחנו בצורה מדויקת שהאלגוריתם בו מבצעים איטרציה על כל המערך הוא היעיל ביותר. האם נוכל למצוא בעיה קרובה לבעיה הזו בה יש אלגוריתם יעיל יותר?

חיפוש מספר במערך ממוין

מסתבר שיש בעיה קרובה לבעיה הקודמת - חיפוש מספר במערך ממוין.

הגדרה: מערך ממוין של שלמים באורך n הוא מערך בו לכל i < j בין 0 ל-n מתקיים arr[i] <= arr[j]. כלומר, המערך לא יורד - כל איבר קטן/שווה מהאיבר שמימינו במערך.

נגדיר את הבעיה מחדש:

בעיה: בהנתן מערך ממוין arr באורך n ומספר target, האם ניתן למצוא את האינדקס של target, אם קיים, בפחות מ-n השוואות?

מתברר שניתן לנצל את התכונה הזו בשביל לחתוך בצורה משמעותית. נבחן דוגמא:

נניח שאנחנו מחפשים את את המספר 2 במערך, שנמצא באינדקס 3. במקום להתחיל מתחילת המערך, נתחיל מהאמצע. האמצע בין 0 ל-10 הוא 5 - arr[5] = 6. זהו לא המספר שאנחנו מחפשים, אבל כאן ניתן להשתמש בצורה חכמה בעובדה שהמערך ממוין! המספר שמצאנו גדול מהמספר שאנחנו מחפשים, ולכן אם המספר שאנחנו מחפשים קיים, מובטח שהוא נמצא אך ורק לשמאלו של המספר שמצאנו. מימין ל-6 מובטח ששאר המספרים גדולים מ-6, ולכן גם בהכרח גדולים מ-2. כלומר, תחום החיפוש החוקי שלנו הוא עכשיו האיברים המסומנים:

צמצמנו בחצי את מספר האיברים שיש לחפש בהם! נחצה את האיברים הירוקים שוב באמצע ונשווה לאמצעי. כעת האמצע בין 0 ל-5 (עם עיגול כלפי מטה) הוא 2, כאשר arr[2] = 1. שוב לא מצאנו את המספר שחיפשנו, אבל מובטח לנו שהוא מימין ל-arr[2], אם הוא קיים! נחפש מימין לו בלבד כעת, ולא נשכח שצמצמנו את האיברים האחרים:

כעת נותרו שני איברים בלבד. האמצע בין 3 ו-4 (עם עיגול כלפי מטה) הוא 3 = 2 / (4 + 3), כאשר arr[3] = 2 - מצאנו את האיבר הרצוי ב-3 השוואות בלבד!

לאלגוריתם זה קוראים חיפוש בינארי, והוא מהווה שיטה קלאסית לחיפוש במערכים ממוינים. נכתוב אותו בצורה מסודרת, בהנתן מערך ממוין באורך n ומספר מטרה target:

1. התחל את החיפוש בכל המערך - הגדר גבול שמאלי left = 0 וגבול ימני right = n - 1, ובצע איטרציות כל עוד low < high.
2. חשב את אמצע המערך, mid = (low + high) / 2.
3. אם המספר באמצע קטן מ-target, המשך את החיפוש מימין - קבע את low = mid + 1.
4. אם המספר באמצע גדול מ-target, המשך את החיפוש משמאל - קבע את high = mid - 1.
5. אחרת, המספר באמצע שווה ל-target - החזר אותו.
6. אם יצאנו מהלולאה, סימן שלא מצאנו את המספר במערך.

נכתוב מימוש:

#define NOT_FOUND -1
int binary_search(int* arr, int n, int target) {
    int low = 0;
    int high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(target > arr[mid]) {
            low = mid + 1;
        } else if(target < arr[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return NOT_FOUND;
}

הערה: בהרבה קורסים וספרים קוראים לאלגוריתם זה “אריה במדבר”.

חיפוש בינארי - ניתוח מתמטי

כעת נבצע ניתוח מתמטי של כמות הפעולות הנדרשות לביצוע חיפוש בינארי. בהמשך כשנלמד על סיבוכיות נבין יותר את החשיבות של ניתוח זה. כעת, ננתח שאלה פשוטה - כמה פעולות יש לבצע בחיפוש בינארי של מערך באורך n?

נניח לפשטות ש-n הוא חזקה של 2, כלומר k שלם כך ש-n = 2^k. בכל איטרציה במהלך החיפוש הבינארי, גודל תת-המערך בו אנחנו מחפשים נחתך בחצי, עד שגודלו 1 בעת ההשוואה האחרונה. כלומר, גודל המערך בכל איטרציה יהיה:

1. n
2. n / 2
3. n / 4 … עד לאיטרציה ה-t בה גודל תת-המערך הוא n / 2^t. כמה איטרציות יקח להגיע ל-1?

כלומר, מספר האיטרציות הוא $\log(n)$. בחיפוש רגיל בו נשווה איטרטיבית לכל איבר במערך, מספר הפעולות יהיה $n$. האם מדובר בהבדל משמעותי? מסתבר שכן!

כלומר, כשהחיפוש האיטרטיבי יבצע מיליון איטרציות, חיפוש בינארי מבצע 20 בלבד! זה הבדל משמעותי מאוד, עם אינדיקציה ברורה ללמה החיפוש שלנו אחרי אלגוריתמים יעילים יותר הוא נכון וחשוב.

תרגילים

תרגיל 1

נתון מערך ממוין של int באורך n > 0 ומספר מטרה target. כתבו פונקציה המחזירה את המספר הקרוב ביותר ל-target במערך.

פתרון

פתרון פשוט ואינטואיטיבי יהיה חיפוש איטרטיבי במערך לאורכו. נשתמש בפונקציית עזר לערך מוחלט בשביל לוודא שאנחנו מסתכלים על מרחקים אבסולוטים:

int abs(int a) {
    return a >= 0 ? a : -a;
}
int find_closest(int* arr, int n, int target) {
    int min_distance = MAX_INT;
    int closest = arr[0];
    for(int i = 0; i < n; i++) {
        int curr_distance = abs(target - arr[i]);
        if(curr_distance < min_distance) {
            min_distance = curr_distance;
            closest = arr[i];
        }
    }
    return closest;
}

עם זאת, זהו פתרון שלא משתמש בעובדה שהמערך ממוין. תמיד כשנתון מערך ממוין כדאי לחשוב בכיוון של חיפוש בינארי. יש הרבה אופציות שונות למקרים שהפונקציה שלנו צריכה לטפל בהם - נכתוב אותם:

2. כל המספרים במערך גדולים מהמספר.
3. כל המספרים במערך קטנים מהמספר.
4. המספר נמצא במערך - אם כן, חיפוש בינארי ימצא אותו.
5. המספר נמצא בין האיבר הקטן ביותר במערך לאיבר הגדול ביותר במערך.

למקרים 1 ו-2 מספיקים בדיקות לאיבר הראשון והאחרון של המערך - מכיוון שהמערך ממוין מספיק להשוות אליהם. למקרה 3 אפשר להשתמש בחיפוש בינארי. עבור מקרה 4, יתקבל כי low ו-high יהיו חסמים תחתון ועליון בהתאמה של target, ורק צריך לבדוק איזה מהם יותר קרוב - נשתמש עבור כך בפונקציית עזר לערך מוחלט:

int abs(int a) {
    return a >= 0 ? a : -a;
}
int find_closest(int* arr, int n, int target) {
    if(target <= arr[0]) {
        return arr[0];
    }
    if(target >= arr[n - 1]) {
        return arr[n - 1];
    }
    int low = 0;
    int high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(target > arr[mid]) {
            low = mid + 1;
        } else if(target < arr[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    if(abs(arr[low] - target) < abs(arr[high] - target)) {
        return arr[low];
    } else {
        return arr[high];
    }

}

תרגיל 2 - סעיף א׳

נתון מטריצה בפורמט מערך דו-מימדי של שלמים int** matrix עם מימדים int n, int m. נתון כי כל שורה במערך ממוינת. כתבו פונקציה המבצעת חיפוש בינארי במטריצה.

פתרון

אין לנו מידע מעבר לכך שכל המערכים במטריצה ממוינים, ולכן אין אופטימיזציות שניתן לעשות מעבר לחיפוש בינארי בכל אחד מהמערכים עד למציאה:

#define NOT_FOUND -1
int bsearch(int* arr, int n);
int bsearch_matrix(int** matrix, int n, int m, int target) {
    for(int i = 0; i < n; i++) {
        int index = bsearch(matrix[i], m, target);
        if(index != NOT_FOUND) {
            return index;
        }
    }
    return NOT_FOUND;
}

תרגיל 2 - סעיף ב׳

כעת נתון כי מעבר לכך שכל שורה ממוינת, האיבר האחרון בכל שורה קטן/שווה מהאיבר הראשון בשורה אחריו. למשל:

כתבו פונקציה המבצעת חיפוש בינארי אופטימלי במטריצה.

פתרון

כעת נתון כי השורות במטריצה ממוינות וכל שורה ממוינת ביחס לשורות מעליה ומתחתיה. כלומר, אם היינו ״משטחים״ את המטריצה לשורה אחת היינו יכולים לבצע חיפוש בינארי רגיל. ניתן לעשות זאת, אבל זה ידרוש העתקה של כל המטריצה וזכרון נוסף, ואין בכך צורך אמיתי. במקום זאת, נתייחס למטריצה כמערך ממוין אחד ארוך, מחולק לשורות. האתגר כעת מגיע מחישוב האינדקסים הנכונים בלי להתלבל במימדי המטריצה. למשל, עבור המטריצה בדוגמא, היינו רוצים לבצע חיפוש בינארי למטריצה ״מושטחת״ שנראת כך:

נבחן את הבעיה מחדש:

1. במטריצה יש m*n - 1 איברים. נמספר את כל האיברים במטריצה מ-0 ל-mn - 1 בהתאמה.
2. בהנתן אינדקס כלשהו i במערך ה-״מושטח״, הוא שייך לשורה ה-i / m ולעמודה ה-i % m. ניתן לחשוב על זאת כך - בהנתן i, המספר i / m הוא מספר השורות המלאות שניתן להכניס ב-i מספרים, ו-i % m הוא השארית שיש להתקדם לתוך אותה שורה לאחר מכן.
3. נבצע את החיפוש הבינארי בצורה זהה למקרה המוכר, רק שאת השליפה של האיבר מהמערך נעשה בצורה מעט זהירה יותר עם האינדקסים הנכונים.

#define NOT_FOUND -1
int bsearch_matrix(int** matrix, int n, int m, int target) {
    int low = 0, high = n * m - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int row = mid / m;
        int col = mid % m;
        int val = matrix[row][col];
        if (val == target) {
            return mid;
        } if (val < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return NOT_FOUND;
}

תרגיל 3

בהנתן מספר שלם חיובי n, כתבו פונקציה שמחשבת את השורש שלו מעוגל לשלם הקרוב ביותר. על הפונקציה שלכם לבצע לכל היותר $c\log_2 n$ פעולות, כאשר $c$ קבוע חיובי כלשהו.

פתרון

ניתן בהתחלה לחשוב - מה הקשר בין השאלה הזו לחיפוש בינארי? הרמז נמצא בדרישה לביצוע לכל היותר $c\log_2n$ פעולות. ראינו כי חיפוש בינארי מבצע סקאלה של $\log_2n$ פעולות, ולכן יתכן שאפשר לבצע פה משהו שדומה לחיפוש בינארי. כיצד?

שאלות ותרגילים

1. נתונה וריאציה על בעית החיפוש במערך הממוין - בהנתן מערך ממוין ומספר כלשהו lower_bound, יש למצוא מספר כלשהו במערך שקטן מ-lower_bound. כתבו את הפונקציה bsearch_find_lower(int* arr, int n, int lower_bound) שפותרת את הבעיה.
2. נתון מערך int* temps באורך שמדד את הטמפרטורה בכוס כל דקה לאורך n דקות. מצאו את הדקה הראשונה בה המים היו רותחים (כלומר, הטמפרטורה הייתה גדולה;שווה מ-100 מעלות).
3. מה יחזיר אלגוריתם החיפוש הבינארי במידה וקיימים מספר מקרים של target במערך נתון?
4. נתונה וריאציה על בעית החיפוש במערך ממוין - יש למצוא את האינדקס הראשון של המספר המבוקש. למשל, אם המערך הוא:

ורוצים למצוא את המספר 3, יש להחזיר את האינדקס 2 בלבד - האינדקס 3 הוא טעות. כתבו את הפונקציה bsearch_find_first(int* arr, int n) הפותרת את הבעיה.

5. נתון מערך ממוין שהזיזו אותו בצורה ציקלית ב-k איברים. למשל, עבור המערך הבא:

והזזה ציקלית של k = 2, נקבל את המערך הבא:

כתבו פונקציה המבצעת חיפוש בינארי במערך שהוזז ציקלית ב-k איברים.

6. נתון מערך ממוין של שלמים באורך n - 1. נתון כי כל השלמים בין 0 ל-n - 1 (כולל) מופיעים במערך, חוץ מאחד בודד שאינו מופיע. כתבו פונקציה שמוצאת את המספר שאינו מופיע.

תרגיל - מימוש מבנה נתונים

כעת רכשנו מספיק כלים בשביל לממש מבנה נתונים פשוט. בתרגיל נכתוב מערכת שמנהלת בית קולנוע - נוכל למכור כרטיסים, להוסיף צופים, להקרין סרטים לפי לוח זמנים וכו׳.

כל צופה שמזמין כרטיס מזין את הפרטים הבאים במערכת:

• תעודת זהות - מספר int חיובי בין 0 ל-999, כולל.
• שם - מחרוזת *char שאורכה לכל היותר MAX_NAME_LEN, קבוע שערכו 100.
• חבילת הטבות - מספר int שערכו מספר בין 0 ל-2. כל צופה מקבל אוכל ושתייה במזנון לפי חבילת ההטבות שבחר - 0 לא מקבל כלום, 1 מקבל פופקורן ו-2 מקבל פופקורן ושתייה.

על המערכת להשתמש ב-id של כל צופה כמזהה למבנה הנתונים:

char* names;
int* package;

לדוגמא, מגיע צופה בשם "John" עם תעודת זהות 534 ורוכש חבילת הטבות 1. הקולנוע מעניק לו את המזהה 0, ובהתאמה מעדכן את מבני הנתונים:

int id = 534;
names[id ] == "John";
package[id] = 1;

דרישות למימוש

בתרגיל יש לממש את הפונקציות הבאות:

void theater_init(char** names, int* packages);
bool insert_viewer(char** names, int* packages);
void theater_close(char** names, int* packages);

שיפעלו לפי הדרישות הבאות:

• theater_init תאתחל את מבנה הנתונים בכל דרך לבחירתכם.
• insert_viewer תקבל את מבנה הנתונים ותקרא עם scanf את תעודת הזהות, השם וחבילת ההטבות של צופה חדש אחד, עם Enter ביניהם. הפונקציה תחזיר true הפונקציה תוודא שהערכים שהצופה החדש מכניס חוקיים, ולא תכניס אותו אם לא. הפונקציה לא תכניס צופה חדש אם אין לו מקום בקולנוע. הפונקציה תחזיר true אם הצליחה להכניס את הצופה, ו-false אחרת.
• theater_close תשחרר את כל הזכרון הדינמי שהוקצה ותסיים את ריצת הקולנוע.

פתרון

הרצאה 7 - מחרוזות (strings)

אחרי שלמדנו להשתמש במערכים, נדגים הרבה ממה שלמדנו על סוג מיוחד של מערכים - מחרוזות. נזכיר כמה פרטים שראינו כבר בעבר:

1. הטיפוס char מייצג תו בודד, שגודלו בייט אחד (sizeof(char) = 1).
2. את הערך בזכרון שמכיל המשתנה אנחנו ממירים באמצעות טבלת ASCII לקבלת התו עצמו.
3. ניתן לייצר מערך של תווים *char בצורה דומה למערך של שלמים שפגשנו, *int.

כעת נדון במערכי תווים מסוג *char, שהרבה פעמים ישמשו אותנו בשביל לייצג טקסט. בדרך כלל כשהשתמשנו במערכים, העברנו ביחד עם המערך את האורך שלו - כמו למשל בחיפוש בינארי:

int binary_search(int* array, int len, int target);

לעומת זאת, במערכי תווים ננקוט בגישה שונה. במקום להעביר ביחד עם מערך תווים את האורך שלו, נסמן בתו מיוחד את סוף המערך. התו 0\ הוא בעל ערך ASCII של 0 ונקרא null terminator. נשתמש בו לטובת הסימון הזה:

הגדרה: מחרוזת היא מערך תווים []char שהתו האחרון בו הוא 0\.

למשל, המחרוזת “HelloWorld” בזכרון נראת כך:

ניתן להגדיר מחרוזות בכמה צורות שקולות:

1. כמערך תווים:

char* str = {'H', 'e', 'l', 'l', 'o', '\0'};

2. עם string literal:

char* str = "Hello";

3. בכתיבה לכל איבר:

char str[6]; // string len is 5 + 1 fo
str[0] = 'H';
str[1] = 'e';
str[2] = 'l';
str[3] = 'l';
str[4] = 'o';
str[5] = '\0';

הערות:

1. נשים לב שיש הבדל דק אבל חשוב שכעת אפשר להבין בנוגע להצהרה על משתני char לעומת מחרוזות *char. הצהרה עם גרשיים יחידיים 'x' היא על משתנה char שמכיל תו, בעוד שעם גרשיים כפולים "x" היא על המחרוזת המתאימה:

char single_char = 'x'; // 1 byte
char* string = "x"; // pointer to {'x', '\0'}, 2 bytes

2. המשמעות של הוספת תו הסיום 0\ היא בשביל להכיל n תווי מחרוזת יש להשתמש ב-n + 1 בתים - n בשביל התווים עצמם ו-1 עבור 0\.
3. ניתן להדפיס מחרוזת עם printf עם המזהה s%:

#include <stdio.h>
char* str = "My favorite number is - ";
int fave;
scanf("%d", &fave);
printf("%s %d", str, fave);

מחרוזת היא מערך לכל דבר - ניתן לבצע עליו איטרציה:

char* str = "Learning computer science in C!";
for(int i = 0; str[i] != '\0'; i++) {
    printf("str[i] = %c\n", str[i]);
}

דוגמאות

1. כתבו פונקציה המקבלת מחרוזת ומחזירה את מספר האותיות הקטנות שבה.

int count_lowercase(char* str) {
    int lowercase = 0;
    for(int i = 0; str[i] != '\0'; i++) {
        if(str[i] >= 'a' && str[i] >= 'z') {
            lowercase++;
        }
    }
    return lowercase;
}

2. כתבו פונקציה שמחשבת אורך מחרוזת.

int strlen(char* str) {
    int len = 0;
    while(*str) {
        len++;
        str++; // Pointer arithmetic!
    }
    return len;
}

הערה: ניתן להשתמש בכתיבה while(*str) באופן שקול לכתיבה while(*str != '\0') מכיוון שערך ה-ASCII של 0\ הוא 0, ולכן ערכו בהמרה לבוליאני הוא false - כל תו אחר יקבל את הערך true.

<string.h>

בדומה לספריות אחרות שפגשנו כמו <stdlib.h> או <stdio.h>, קיימת ספריה בשם <string.h> שמכילה מספר גדול של פונקציות שימושיות בשימוש במחרוזות. כמה דוגמאות:

1. strcmp - פונקציה המשווה בין שתי מחרוזות ומחזירה 0 אם כל תו בהן זהה, אחרת ערך גדול מ-0.
2. strcat - משרשרת שתי מחרוזות זו לזו.
3. strcpy - מעתיקה את כל התווים ממחרוזת אחת לאחרת.

רוב הפונקציות בספריה פשוטות ואינטואיטיביות, וזה תרגיל מצוין לנסות לממש אותן בעצמכם.

תרגיל

נתונה מחרוזת str המורכבת מתווים ומספר אי-שלילי של רווחים. למשל:

1. "Hello world"
2. "i am learning "
3. "5rasd33asd"
4. ""

כתבו את הפונקציה int last_word_len(char* str) שמחזירה את האורך של המילה האחרונה במחרוזת, כאשר כל מילה מופרדת מהאחרות על ידי מספר גדול מ-0. למשל, עבור הדוגמאות הבאות יוחזר:

1. 5
2. 8
3. 10
4. 0

פתרון

פתרון אינטואיטיבי יכול להיות לסרוק מתחילת המחרוזת לסופה למציאת המילה האחרונה. עם זאת, נשים לב שאין צורך להתחיל בתחילת המחרוזת אלא בסופה - כך נצטרך לסרוק רק את המילה האחרונה. נפעל לפי השלבים הבאים:

1. נחשב את אורך המחרוזת בשביל להתחיל לסרוק את המילה מהסוף להתחלה.
2. נדלג על רווחים שיתכן וקיימים בסוף המילה.
3. נסרוק מימין לשמאל עד שנמצא רווח נוסף או את תחילת המחרוזת.

int strlen(char* str) {
    int len = 0;
    while(*str++) {
        len++;
    }
    return len;
}
int last_word_len(char* str) {
    int i = strlen(str) - 1; // step 1
    while(str[i] == ' ') { // step 2
        i--;
    }
    int word_len = 0;
    while(i >= 0 && s[i] != ' ') { // step 3
        i--;
        word_len++;
    }
    return word_len;
}

תרגיל

נתונה מחרוזת letters ומחרוזת word המורכבות מאותיות קטנות באנגלית בלבד. כתבו פונקציה bool can_create_word(char* letters, char* word) שקובעת האם ניתן להרכיב את המחרוזת word מהאותיות במחרוזת letters בלבד, כאשר ניתן להשתמש בכל אות כמספר הפעמים שמופיעה ב-letters. אין חובה להשתמש בכל האותיות מ-letters. לדוגמא, מהמחרוזת pudgy penguins ניתן להרכיב את המילים design ו-genius, אבל לא ניתן להרכיב את paparazzi.

פתרון

נפרק את השאלה שאנחנו שואלים. למעשה, אנחנו שואלים - האם עבור כל אות ב-word, מספר הפעמים שבה היא מופיעה ב-word היא לפחות מספר הפעמים שהיא מופיעה ב-letters? מכיוון שמספר האותיות הקטנות באנגלית הוא סופי, נקצה מערך סטאטי שיספור את התדירות של הופעת כל אות ב-letters, ולאחר מכן נעבור על כל האותיות ב-word ו-״נחלק״ אותן.

bool can_create_word(char* letters, char* word) {
    int letter_freq['z' - 'a' + 1] = {0};
    for(int i = 0; letters[i]; i++) {
        char letter = letters[i];
        letter_freq[letter - 'a']++;
    }
    for(int i = 0; word[i]; i++) {
        char letter = word[i];
        if(--letter_freq[letter - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

יש בפתרון כמה נקודות מורכבות:

1. מספר האותיות הקטנות הוא:
   'z' - 'a' + 1
   מכיוון ש-'a' ו-'z' הן אותיות קטנות בפני עצמן. אי-הוספת ה-1 היא טעות קלאסית הנקראת off-by-one וכדאי מאוד להזהר מהן ע“י בדיקה מדויקת של האלגוריתם.
2. הגדרנו מערך בו לכל אות קטנה יש מיקום בו נספרת התדירות שלו במחרוזת letters. בשביל לקבל את המיקום של אות כלשהי במערך, חיסרנו את 'a' ממנה - כך קיבלנו שהמקום של 'a' במערך הוא 0, של 'b' במערך הוא 1 וכך הלאה.
3. לאחר מכן, בכל שלב “חילקנו” את התדירויות ב-letters ל-word ע“י אופרטור ה--- (לפני המשתנה!), ואז בדקנו האם “חרגנו” ע:“י השוואה ל-0.

תרגיל

ממשו את שתי הפונקציות הבאות:

int str_to_int(char* str);
char* int_to_str(int n);

הפונקציה הראשונה תקבל מחרוזת המורכבת מתווי ASCII של ספרות בלבד ([0-9]) ותחזיר את המספר שהן מייצגות - לדוגמא, המחרוזת "953" תחזיר את המספר 953. הפונקציה השנייה תקבל מספר ותחזיר מחרוזת תקינה המייצגת את המספר.

פתרון

הפונקציה הראשונה יחסית פשוטה למימוש. מחרוזות קוראים משמאל לימין, ולכן נתקל בהתחלה בספרה הגבוהה ביותר של המספר, ואז אחת אחריה וכו’. עבור כל ספרה נכפיל ב-10 בשביל להסיט את הספרה מקום אחד שמאלה, נהפוך כל תו ASCII במחרוזת למקביל המספרי שלו ע“י חיסור של התו '0' ואז נוסיף את הספרה עצמה. נשים לב למקרה קצה חשוב - אם המספר שלילי, התו הראשון הוא - ויש לטפל בכך!

#include <stdbool.h>
int str_to_int(char* str) {
    int n = 0;
    int sign = str[0] == '-' ? -1 : 1;
    int i = 0;
    if(sign == -1) {
        i++;
    }
    while(str[i]) {
        n = n * 10 + (str[i++] - '0');
    }
    return n * sign;
}

הפונקציה השנייה מעט מורכבת יותר למימוש. נפעל לפי השלבים הבאים:

1. נתחיל במציאת מספר הספרות במספר. נעשה זאת ע“י חלוקת ב-10 עד שנגיע ל-0 - מכיוון שחלוקת int-ים ב-C מעגלת כפי מטה, נקבל בדיוק את מספר הספרות. נזהר להשתמש ב-do-while במקום ב-while על מנת שעבור המספר 0 עדיין נקבל אורך של 1 לפחות.
2. נקצה מחרוזת באורך שקיבלנו ועוד 1 עבור ה-null terminator. נכתוב לסוף המחרוזת את ה-null terminator.
3. כעת, מכיוון שמחרוזת קוראים משמאל לימין, נסרוק את המספר בצורה הפוכה. בכל שלב ניקח את המודולו לחלוקה ב-10 על מנת לחלץ את הספרה עצמה ונוסיף לכך '0' בשביל להמיר ממספר לתו ASCII. לאחר זאת נחלק את המספר ב-10 בשביל לקדם בספרה אחת את האיטרציה.

#include <stdlib.h>
#include <stdbool.h>
char* int_to_str(int n) {
    int tmp = n, len = 0;
    bool negative = n < 0;
    do {
        len++;
        tmp /= 10;
    } while(tmp);
    int total_len = len + (negative ? 1 : 0);
    char* s = malloc(total_len + 1);
    if(!s) {
        return NULL;
    }
    s[total_len] = '\0';
    int abs_n = negative ? -n : n;
    for (int i = total_len - 1; i >= negative; i--) {
        s[i] = (abs_n % 10) + '0';
        abs_n /= 10;
    }
    if (negative) {
        s[0] = '-';
    }
    return s;
}

תרגיל מסכם - כתיבת ספריית מחרוזות

מהי ספרייה?

בתרגיל זה נכתוב ספריית קוד לטיפול במחרוזות. פגשנו ספריות אחרות בשפת C - למשל <stdlib.h> או <stdio.h>. בצורה הפשוטה ביותר, ניתן להגדיר ספרייה בשפת C בתוך קוד שאינו מכיל פונקציית main - כלומר, הקוד בספריה אינו מיועד לשימוש בפני עצמו, אלא כחלק מקטע קוד אחר. לדוגמא, הפונקציה printf המופיעה ב-<stdio.h> היא בדיוק כזו - זו לא תוכנית בפני עצמה, אלא פונקציה שמטרתה להיות בשימוש בקטעי קוד אחרים, כפי שראינו לאורך הקורס.

טסטים ובדיקות

הצורה בה מממשים וכותבים ספרייה הוא מעט שונה ממה שראינו עד כה. במקום לכתוב תוכנית ראשית ופונקציות נוספות שתומכות אותה, המטרה היא לכתוב פונקציות כלליות שמבצעות משימה ספציפית. עם זאת, בתהליך בדיקת הקוד שלנו, רצוי מאוד דווקא כן לכתוב תוכנית ראשית שמוודאת שהפונקציות שלנו אכן מבצעות את העבודה שיעדנו להן.

לדוגמא, נניח שנרצה לכתוב פונקציה שמקבלת ספרה [0-9] ומדפיסה את ערך ה-ASCII שמתאים לה. ניתן לעשות זאת כך (שימו לב לבאגים!)

int ascii_value(int digit) {
    return digit + '0';
}

יתכן ואנחנו מרוצים מהפונקציה שלנו, ויתכן שלא (רמז - לא בהכרח). צעד נוסף קלאסי בתכנות היא כתיבת תוכנית בדיקה, שבוחנת את התנהגות הפונקציה שלנו:

int ascii_value(int digit) {
    return digit + '0';
}
#define N_TEST_CASES 5
int main() {
    int test_cases[] = {0, 1, 5, 12, -1};
    for(int i = 0 ; i < N_TEST_CASES; i++) {
        int test = test_cases[i];
        printf("ascii_value(%d) = %d", test, ascii_value(test));
    }
}

זוהי דוגמא פשוטה לאחת הקונספטים החשובים ביותר בתכנות - טסטים! טסטים היא הדרך הטובה ביותר לבדוק שהקוד שלנו עושה מה שאנחנו מצפים שהוא יעשה. הרעיון הוא פשוט - נריץ את הפונקציה שלנו ונשווה את התוצאות שקיבלנו לתוצאות הצפויות. אם הן שוות, מעולה - אחרת, נתקן את הקוד שלנו עד שנצליח. טסט טוב הוא טסט שמכסה גם את המקרים הקלאסיים עליהם חשבנו כשכתבנו את הפונקציה והיא נבנתה בשביל לטפל בהם, אבל לא רק - הוא צריך להכיל מקרי קצה שונים ומשונים שלא בהכרח חשבנו עליהם בהתחלה, אבל כדאי שהפונקציה שלנו תדע לטפל בהם.

לדוגמא, בקטע הקוד הזה אנחנו בודקים את הפונקציה עבור 0, 1, 5 - אלו אכן המקרים להם ציפינו, בהם מתקבל ספרה בודדת ואי-שלילית. עם זאת, המקרים הנוספים שונים מאוד - מה כדאי שהפונקציה שלנו תעשה כאשר היא מקבלת מספר בעל 2 ספרות, או מספר שלילי? כמובן שערך ה-ASCII של 12 אינו 12 + '0' - זהו התו > בכלל! לכן, יתכן שבעקבות הטסטים נשנה את הפונקציה שלנו באופן הבא:

#define INVALID_DIGIT -1
int ascii_value(int digit) {
    if(digit < 0) {
        printf("passed negative number, no ASCII value - two chars!");
        return INVALID_DIGIT;
    }
    if(digit / 10 > 0) {
        printf("passed more than 1 digit, no ASCII value");
        return INVALID_DIGIT;
    }
    return digit + '0';

int use_ascii_value(int digit) {
    // Some code ...
    int val = ascii_value(digit);
    if(val == INVALID_DIGIT) {
        printf("Could not use ascii_value with %d", digit);
        return INVALID_DIGIT;
    }
    // ... some more code that uses val
}

וכעת הפונקציה שלנו הרבה יותר עמידה בפני תקלות ובעיות. מעבר לכך, היא אינפורמטיבית - היא מספרת לכל מי שקורא לה בדיוק מה קרה במידת ומתקיימת שגיאה.

ספריית מחרוזות

כעת נבחן את רשימת הפונקציות שיש לממש. בכל הפונקציות ניתן להניח שקיים למחרוזות הניתנות null terminator (כלומר, הן מחרוזות חוקיות).

int strlen(char* str)

פונקציה זו תחזיר את מספר התווים במחרוזת, לא כולל ה-null terminator. לדוגמא, עבור המחרוזת char* s = {'a', 'b', 'c', '\0'} יוחזר הערך 3. על המימוש לעמוד בסיבוכיות זמן של $\Theta(n)$ וסיבוכיות מקום $\Theta(1)$, כאשר $n$ הוא אורך המרחוזת.

int strcmp(char* str1, char* str2)

פונקציה זו תשווה בין שתי מחרוזות. אם בכל אינדקס התווים משני המחרוזות זהים, הפונקציה תחזיר 0 - אחרת, הפונקציה תחזיר את ההפרש בין שני התווים הראשונים ששונים. במידה ואחת המחרוזות קצרה מהשנייה, כל תו ״חסר״ במחרוזת זו יחשב כתו 0\ עם ערך 0. לדוגמא, עבור המחרוזות "char* str1 = "abc ו-"char* str2 = "abc יוחזר 0, בעוד שעבור "char* str1 = "abc ו-"char* str2 = "a יוחזר 'b' - '\0'. על המימוש לעמוד בסיבוכיות זמן של $\Theta(k)$ וסיבוכיות מקום $\Theta(1)$, כאשר $k$ הוא אורך המחרוזת המינימלי מבין שתי המחרוזות.

int strcat(char* dst, char* src)

פונקציה זו תשרשר את המחרוזת src לקצה המחרוזת dst כך שתתקבל מחרוזת אחת ב-dst. המחרוזת תחזיר את אורך המחרוזת dst לאחר השרשור. ניתן להניח ש-dst ו-src הן מחרוזות חוקיות וכי יש מספיק מקום במערך ה-char ש-dst מצביע אליו בשביל להכיל את src בנוסף. לדוגמא, עבור המחרוזות "char* s1 = "abc ו-"char* s2 = "xyz, קריאה ל-strcat(s1, s2) תחזיר 6 והמחרוזת s1 תכיל את התווים הבאים בתחילתה:

על הפתרון לעמוד בסיבוכיות זמן של $\Theta(k)$ וסיבוכיות מקום של $\Theta(1)$, כאשר $k$ הוא אורך המחרוזת המקסימלי מבין שתי המחרוזות.

char* strstr(char* str, char* substr)

פונקציה זו תחזיר מצביע למקרה הראשון בו מופיע substr ב-str, ו-NULL במידה ואין מקרה כזה.

הרצאה 8 - מיון

עשינו המון עד כה! להכניס רשימה של כל הנושאים

בהרצאה זו, בניגוד להרצאות קודמות, לא נפגוש אלמנט חדש של השפה -למעשה פגשנו כבר רוב מוחלט של הסינטקס הקיים בשפת C. כעת, נשתמש בכל הידע והטכניקות שלמדנו בשביל לפתור בעיה קלאסית במדעי המחשב - מיון (sorting). המטרות יהיו:

1. להכיר וללמוד לממש מספר אלגוריתמים שונים שיפתרו את הבעיה
2. שימוש בכל הכלים שלמדנו עד כה בצורה נכונה
3. ניתוח של האלגוריתמים - איזה אלגוריתם טוב יותר או פחות, ולמה? נעשה זאת לפי עקרון הסיבוכיות, אותו נלמד בהרצאה הבאה.

כפי שנפגוש מיד, מיון היא בעיה קלאסית וחשובה במדעי המחשב - היא פשוטה להבנה, שימושית מאוד ומופיעה באינספור בעיות אחרות. נשתמש בה כמעין דוגמא מסכמת לכל מה שלמדנו, בה נשתמש בכל הכלים שהכרנו עד כה וננתח בעזרתה כדאיות של שימוש במימושים ואלגוריתמים.

בעיית המיון

הגדרה: נתון מערך של איברים arr מסוג כלשהו באורך n. נקרא למערך ממוין אם לכל שני איברים עוקבים במערך a[i] ו-a[i + 1] (כאשר i ו-i + 1 בין 0 ל-n - 1) מתקיים a[i] <= a[i + 1].

ההגדרה די אינטואיטיבית - מערך ממוין הוא מערך בו האיברים מסודרים בסדר עולה - או ליתר דיוק, לא יורד. מערך int ממוין למשל יכול להיות:

בעוד שמערך char ממוין יכול להיות:

בקורס נתעסק בעיקר במיון מערכי int לפשטות, אבל כפי שלמדנו, מערכי char הם גם רק מספרים שאנחנו ממפים באמצעות ASCII לתווים - המיון שלהם נעשה בדיוק באותה צורה.

בשביל לקבל תחושה למורכבות הבעיה, נסו למיין בעצמכם מערך - ללא מחשב או קוד, אלא על דף נייר או בראש. קחו לדוגמא את המערך הבא:

זהו המערך מהדוגמא הקודמת, רק מבולגן מעט. לנסות לפתור בעיה במדעי המחשב בעצמכם לפני מעבר לקוד ומתן הוראות למחשב היא דרך קלאסית למצוא אלגוריתמים פשוטים - לתת למחשב לחקות את המעשים הפשוטים שלנו.

מיון “אינטואיטיבי”

הנה דרך אינטואיטיבית שבה אני עבדתי. כתבתי על נייר את המערך ועוד עותק ריק שלו:

חיפשתי את האיבר המקסימלי ברשימה - זה 100, שמתי אותו במקום האחרון:

סימנתי גם את ה-100 באדום כדי שיהיה ברור שהוא כבר מוין. המשכתי לאיבר המקסימלי הבא שהוא לא 100 - יש לנו שני איברי 25 ולכן לא משנה איזה ניקח, למשל את הראשון:

וכך הלאה עד למערך הממוין. פשוט סה“כ, נכון? לנו כבני אדם לחלוטין. כעת, ננסה לפרק את האלגוריתם הפשוט שהגדרנו לפתרון הבעיה להוראות שהמחשב ידע לעקוב אחריהן:

1. ראשית אנחנו צריכים, בנוסף למערך הנתון, מערך נוסף לשבץ בתוכו את התוצאות. נשתמש ב-malloc או נקצה סטאטית מערך נוסף בשביל זה.
2. צריך כעת למצוא את האיבר המקסימלי במערך - נעבור על כל המערך ונחפש אותו. נצטרך לעבור ממש על כל האיברים מכיוון שתמיד יתכן שהאיבר המקסימלי יהיה בסוף (כפי שקרה באיטרציה השנייה שלנו).
3. נצטרך לסמן באיזשהי דרך את המספרים שכבר “הוצאנו” מהמערך המקורי למערך המתמיין. אנחנו לא יכולים פשוט “לצבוע” את המערך - אפשר למשל להקצות מערך נוסף של משתנים bool בשם sorted המאותחל ל-false - כאשר sorted[i] == true אם כבר הוצאנו את האיבר ה-i מהמערך המקורי. אם מובטח לנו למשל שהמערך חיובי בלבד, אפשר למשל לסמן איברים שהוצאנו ב-1- ובכך לייתר את הקצאת המערך הנוסף.
4. אם נניח ש-n הוא אורך המערך, לאחר n איטרציות המערך החדש יהיה ממוין. נצטרך להחזיר את המערך הממוין ולוודא שיודעים שצריך להשתמש בו ולא במערך הקודם.

מורכב יותר מהצורה האינטואיטיבית שבה הגענו למימוש בעצמנו! בעיות שמרגישות פשוטות לפעמים קשות לתרגום לשפת תכנות. כעת נפגוש מספר אלגוריתמים פשוטים יותר שפותרים את בעיית המיון בדרך שיותר מותאמת לצורה שבה מחשב עובד ולא בני אדם.

Max Sort

הבעיה העיקרית במימוש האינטואיטיבי שניסינו הייתה שצריך להקצות מערכים נוספים להתסבך עם בדיקות איתם. אולי אפשר לקחת את הקונספט של בחירת האיבר המקסימלי כל פעם ולשדרג אותו מעט?

Max Sort הוא אלגוריתם מיון שעושה בדיוק את זה. במקום להכניס את האיבר המקסימלי למערך נוסף, ניקח את האיבר המקסימלי ונחליף אותו עם האיבר במקום הנכון. נראה דוגמא - נחזור למערך שהתחלנו איתו:

נעבור איבר-איבר ונזהה את האיבר המקסימלי - זהו 100 ולכן מקומו במערך הממוין הוא האיבר האחרון. נחליף בינו לבין האחרון:

כעת נרצה למצוא את האיבר המקסימלי השני, זה שקטן/שווה ל-100. נשים לב שמובטח לנו ש-100 נמצא במקום הנכון, ולכן אין צורך להסתכל על האיבר האחרון במערך, ויש להחליף הלפני אחרון במערך. נקבל ש-25 במקום ה-1 (מתחילים לספור מ-0) צריך להתחלף עם 7 במקום הלפני אחרון:

נשים לב שקיימים שני 25 במערך, ולכן אין מניעה שהיינו בוחרים גם את השני מביניהם להחלפה. נמשיך כך עד שהמערך יהיה ממוין!

כעת נרצה לממש בקוד מיון את האלגוריתם. נכתוב במילים את השלבים שינחו אותנו במימוש:

1. יש לקבל כפרמטרים למימוש מצביע למערך int* arr ואורכו int n.
2. יש למיין את ה-len איברים הראשונים של המערך בכל איטרציה, כאשר len מאותחל לאורך המערך n ויורד ב-1 בכל איטרציה.
3. נמצא את האיבר המקסימלי מתוך len האיברים הראשונים ונחליף אותו עם האיבר ה-len במערך.

עבור שלב 2 נכתוב פונקציה שמוצאת את האינדקס של האיבר המקסימלי מתוך ה-len איברים הראשונים, ועבור שלב 3 נשתמש בפונקציית ה-swap שלמדנו לממש:

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int get_max_index(int* arr, int len) {
    int max_index = 0;
    for(int i = 1; i < len; i++) {
        if(arr[i] > arr[max_index]) {
            max_index = i;
        }
    }
    return max_index;
}
void max_sort(int* arr, int n) {
    for(int len = n; len > 0; len--) {
        int max_index = get_max_index(arr, len);
        swap(&arr[len - 1], &arr[max_index]);
    }
}

הערה: קיים אלגוריתם מקביל ל-Max Sort בשם Min Sort, שעובד בצורה דואלית ע“י מציאת האלמנט המינימלי בכל שלב.

Bubble Sort

מיון בועות הוא דוגמא נוספת לאלגוריתם פשוט למימוש למיון. הרעיון הוא כזה - נעבור על כל המערך, איבר אחר איבר, ונשווה בין כל שני איברים סמוכים. אם הם לא ממוינים - כלומר, a[i - 1] > a[i] - נחליף ביניהם. כך איברים גדולים “יבעבעו” כלפי מעלה. כאשר לא נשארו איברים לבעבע, נדע שסיימנו.

נדגים על המערך הקודם - זוהי הצורה ההתחלתית שלו:

באיטרציה הראשונה 3 ו-100 בסדר הנכון ולכן לא נחליף ביניהם, ואז:

וכך הלאה, כאשר 100 מבעבע עד הסוף באיטרציה הראשונה:

כלומר, בסוף האיטרציה הראשונה האיבר המקסימלי יהיה בסוף, בדומה ל-Max Sort - כעת יש לבעבע רק את ה-n - 1 איברים שנשארו.

נממש:

#include <stdbool.h>
void swap(int* a, int* b);
void bubble_sort(int* arr, int n) {
    bool sorted = true;
    int len = n;
    while(len > 0 && !sorted) {
        for(int i = 1; i < n; i++) {
            if(arr[i - 1] > arr[i]) {
                swap(&arr[i - 1], &arr[i]);
                sorted = false;
            }
        }
    }
}

תרגילים

1. נתונה חתימת הפונקציה וההגדרות:

#define ASCENDING 0
#define DESCENDING 1
void hybrid_max_sort(int* arr, int n, int direction);

כאשר הפרמטר direction קובע אם הפונקציה ממיינת עם Max Sort את האיברים בסדר עולה או בסדר יורד. ממשו את הפונקציה.

2. מיון Bidirectional Bubble Sort הוא וריאציה של Bubble Sort בו לאחר ביצוע איטרציה עולה לאורך המערך ובעבוע איברים גדולים כלפי מעלה, מתבצעת איטרציה יורדת לאורך המערך ובעבוע איברים קטנים כלפי מטה. ממשו את void bidir_bubble_sort(int* arr, int n).
3. נתון מערך int* arr באורך 2n כאשר n מספר שלם חיובי. כתבו פונקציה המקבלת מערך כזה ואורכו הממיינת בסדר עולה את המספרים באינדקסים הזוגיים ובסדר יורד את המספרים באינדקסים האי-זוגיים.
4. כתבו פונקציה המקבלת מערך ואורכו וממיינת את המספרים לפי ערכם המוחלט.
5. כתבו פונקציה המבצעת מיון לבחירתכם ומחזירה את התוצאה במערך חדש, תוך כדי שהיא לא משנה את המערך המקורי ולא מבצעת העתקות מיותרות בין המערך המקורי לחדש.
6. כתבו פונקציה המקבלת מטריצה, מספר שורותיה ומספר עמודותיה וממיינת כל עמודה בסדר עולה.

תכונות אלגוריתמי מיון

עכשיו שהכרנו מספר פתרונות לבעיה, נבצע עצירה קצרה בסיור שלנו בעולם אלגוריתמי המיון בשביל לדון בתכונות השונות לפיהן ניתן לסווג אלגוריתמים. לכל אלגוריתם יש יתרונות וחסרונות, עם סיבות להשתמש בו במקרים מסוימים או לוותר עליו.

יציבות

הגדרה: מיון יציב הוא מיון בו הסדר בין אלמנטים שווים במערך הלא ממוין נשמר לאחר המיון.

נבחן למשל את המערך המיוחד הזה:

במקרה זה, כל איבר במערך מכיל שני “שדות” - מספר ואות. בתכנות C מעט מתקדם יותר ניתן לייצר משתנים עם מספר שדות הנקראים Structs (דומים ל-Classes משפות תכנות אחרות). נניח כעת שנרצה למיין את המערך לפי המספר של איבר. כאשר נבצע למשל Bubble Sort נקבל את השלבים הבאים:

אם נסמן ב-i(x) האינדקס של איבר x במערך, נשים לב שמתקיים i(2a) < i(2b) גם במערך המקורי וגם במערך הממוין. זו דוגמא לכך ש-Bubble Sort הוא באופן כללי מיון יציב.

שאלה: איזה שינוי קטן ניתן לבצע ב-Bubble Sort שלא ישבור את האלגוריתם (כלומר, האלגוריתם עדיין יבצע מיון) אבל יהפוך אותו ללא יציב?

In Place

הגדרה: אלגוריתם מיון נקרא In Place אם הוא מבצע את המיון על גבי המערך המקורי ללא הקצאת מערך נוסף.

Bubble Sort ו-Max Sort, שני האלגוריתמים שפגשנו עד כה, הם In Place - מיד נפגוש אלגוריתמים נוספים שמשתמשים בזכרון נוסף בשביל להאיץ את תהליך המיון.

סיבוכיות זמן ומקום (Time & Space Complexity)

השארנו את התכונות המעניינות ביותר של האלגוריתמים לסוף - כמה הם יעילים. באופן כללי יש שני משאבים שאלגוריתמים צורכים מאיתנו ונבדלים זה מזה בהם:

1. זמן: כמה זמן מעבד נדרש בשביל לבצע את האלגוריתם. באופן כללי נרצה שהזמן שלוקח אלגוריתם יהיה מינימלי, על מנת לסיים את המשימה כמה שיותר מהר ולהתפנות למשימות אחרות.
2. זכרון: כמה זכרון נדרש בשביל לבצע את האלגוריתם. באופן כללי, זכרון הוא משאב מוגבל, ולכן נרצה שהזכרון שלוקח אלגוריתם יהיה מינימלי.

בהרצאה הבאה נלמד לעומק כיצד מנתחים בצורה מתמטית ומדויקת את צריכת הזמן והזכרון של אלגוריתמים שונים לפי תורה הנקראת סיבוכיות (complexity). סיבוכיות זמן וזכרון תהיה לרוב הגורם המכריע לפיו נבחר באלגוריתם כזה או אחר.

דוגמא: Bogosort הוא אלגוריתם מיון בו מגרילים רנדומלית לכל איבר במערך מקום חדש, ואז בודקים האם המערך ממוין. למעשה, “מערבבים” את המערך כמו חפיסת קלפים ומקווים שהוא יהיה ממוין. זהו כמובן אלגוריתם לדוגמא בלבד, ללא שימושים פרקטיים - עם זאת, ניתן אינטואיטיבית להבין כי סיבוכיות הזמן שלו תהיה משמעותית גדולה יותר מאשר של Max Sort או Bubble Sort.

מיון מיזוג (Merge Sort)

נמשיך בסקירת אלגוריתמי המיון עם מיון מיזוג. זהו אלגוריתם משמעותית יותר מורכב מהשניים שפגשנו עד כה, אבל בהרצאה הבא נראה שסיבוכיות הזמן שלו טובה יותר משל האלגוריתמים שפגשנו עד כה. תחילה, נדון בתת בעיה פשוטה יותר ונשתמש בפתרון שלה לטובת המיון.

מיזוג מערכים ממוינים

נניח שנתונים שני מערכים קלט ממוינים arr1, arr2. נרצה לקבל מערך פלט שלישי ממוין arr3 שמכיל את כל האיברים בשני המערכים. אין חובה שהמערכים יהיו באותו האורך. לדוגמא:

כיצד נעשה זאת?

1. נחזיק אינדקס לכל אחד משלושת המערכים - שני אינדקסים לקריאה משני מערכי הקלט ואינדקס לכתיבה למערך הפלט.
2. בכל שלב נשווה בין האיברים משני מערכי הקלט, נכתוב את המינימלי למערך הפלט ונקדם את האינדקס של המערך שלקחנו.
3. לאחר שנגמרו האיברים באחד המערכים, נכתוב ישירות את האיברים שנשארו בשני למערך הפלט.

נסמן את האינדקסים בהתאמה ב-i1, i2, i3. נתאחל את כולם ל-0:

נשווה בין שני האיברים הראשונים. 9 < 4 ולכן נכתוב אותו ראשון ונקדם את האינדקסים i1 ו-i3:

כעת יש מספר איברים שווים - ניתן לקחת אותם למערך הפלט בכל סדר לבחירתנו, עד שנגיע למצב הבא:

נכניס את 10 מ-arr2, את 11 מ-arr1 ואז נוותר ללא איברים ב-arr1. נותר עוד איברים ב-arr2 - נכניס את 15 מ-arr2 ונקבל:

מימוש מיזוג מערכים בקוד

האלגוריתם שלנו עובד! נכתוב מימוש שלו - נניח שאנחנו מקבלים את שלושת המערכים כקלט ואת אורכם של השניים הראשונים:

void merge(int* arr1, int len1, int* arr2, int len2, int* arr3) {
    for(int i1 = 0, i2 = 0, i3 = 0; i1 < len1 && i2 < len2; i3++) {
        if(arr1[i1] < arr2[i2]) {
            arr3[i3] = arr1[i1++];
        } else {
            arr3[i3] = arr2[i2++];
        }
    }
    // Copy leftover elements from either array
    while(i1 < len1) {
        arr3[i3++] = arr1[i1++];
    }
    while(i2 < len2) {
        arr3[i3++] = arr1[i2++];
    }
}

מיון מיזוג

כעת נראה כיצד ניתן להשתמש במיזוג מערכים ממוינים לטובת מיון. זה נשמע קצת כמו הגדרה מעגלית - בשביל למזג אנחנו צריכים מראש למיין, אז כיצד נשתמש במיזוג בשביל מיון? נשים לב לעובדה חשובה - מערכים באורך 1 הם בהגדרה ממוינים. נוכל להשתמש בעובדה זו באופן הבא - נתחיל במיזוג של “מערכים” באורך 1 זה עם זה, עד שכל המערך יורכב מרצף של מערכים ממוינים באורך 2. נמזג את כל המערכים באורך 2 עד שכל המערך יורכב מרצף של מערכים ממוינים באורך 4. כך נמשיך במיזוג עד שנקבל מערך אחד ממוין.

לפשטות, נניח שאורך המערך הוא חזקה של 2, n = 2^k. המימוש של האלגוריתם מעט מורכב, ביחוד החלק של חישוב האינדקסים בצורה מדויקת. מכיוון ש-malloc יכולה להכשל, נגדיר שהמיון מחזיר false אם היא נכשלה, אחרת true, ולא נשכח לשחרר את הזכרון:

#include <stdlib.h>
#include <stdbool.h>
void merge(int* arr1, int len1, int* arr2, int len2, int* arr3);
int merge_sort(int* arr, int n) {
    int* tmp_arr = (int*)malloc(sizeof(int) * n);
    if(!tmp_arr) {
        return false;
    }
    for (int len = 1; len < n; len *= 2) {
        for (int i = 0; i < n; i += 2 * len) {
            merge(arr + i, len, arr + i + len, len, tmp_array);
            for (int j = 0; j < 2 * len; j++) {
                arr[i + j] = temp_array[j];
            }
        }
    }
    free(tmp_arr);
    return true;
}

נפרק את שלבי האלגוריתם בצורה מסודרת:

1. נתחיל בהקצאת עבור המערך לתוכו נבצע מיזוג.
2. הלולאה החיצונית מגדירה איטרציות על גדלי מערך הולכים וגדלים - 1, ואז 2, ואז 4, וכך הלאה.
3. הלולאה הפנימית מבצעת איטרציות על כל תתי המערכים שיש למזג. למשל, כשאורך המערכים אותם ממזגים הוא 2, i מקבל את הערכים 0, 4, 8 וכך הלאה.
4. המערכים הנשלחים ל-merge נכתבים באריתמטיקת מצביעים. למשל, כשאורך המערכים אותם ממזגים הוא 2, מתחילים בשליחה של arr ו-arr + 2, כאשר המיזוג מתבצע לתוך המערך הזמני.
5. בסיום המיזוג מעתיקים את האיברים הרלוונטים חזרה למערך המקורי.

נבחן דוגמא:

נתחיל במיזוג מערכים באורך 1 למערכים באורך 2, כאשר מיד לאחר שלב זה נעתיק את התוצאה מהמערך הזמני למקורי:

נמשיך במיזוג מערכים באורך 2 למערכים באורך 4:

נסיים במיזוג שני המערכים באורך 4 למערך אחד באורך 8:

וקיבלנו מערך ממוין!

הערות:

1. ההנחה כי אורך המערך הוא חזקה של 2 נעשת כאן לפשטות על מנת להמנע ממקרי קצה, אבל ניתן לספק אותה מעשית בצורה פשוטה - נרחיב כל מערך לחזקה הקרובה ביותר של 2 אליו, ו-“נרפד” את הקצוות המורחבים באיברים לא רלוונטיים למיון (למשל INT_MAX).
2. לפעמים נהוג ללמד את השלב של ההעתקה מהמערך הזמני חזרה למערך שלנו עם memcpy, פונקציה המעתיקה מכתובת אחת בזכרון לאחרת. חתימת הפונקציה היא void* memcpy(void* dst, void* src, size_t count) - שני מצביעים ליעד והמקור, ומספר הבתים שיש להעביר (דומה ל-malloc). כך ניתן להחליף את הלולאה הפנימית ביותר עם השורה הבאה:

memcpy(arr + i, tmp_arr, 2 * len * sizeof(int));

תרגילים ושאלות

1. כתבו מימוש לפונקצית merge_descend שממזגת שני מערכים ממוינים בסדר יורד למערך אחד ממוין בסדר יורד. חתימת הפונקציה תהיה:

void merge_descend(int* arr1, int len1, int* arr2, int len2, int* arr3);

2. קבעו האם Merge Sort הוא אלגוריתם מיון יציב או לא.
3. נתונה הפונקציה הבאה:

int* merge_array_list(int** array_list, int array_list_len, int* arrays_len);

כאשר arrays_list הוא מערך של מערכים ממוינים שמספר המערכים בו הוא arrays_list_len, והאורך של המערך array_list[i] הוא arrays_len[i]. כתבו פונקציה הממזגת את כל המערכים למערך אחד שיוקצה דינמית ויוחזר מהפונקציה.

הרצאה 9 - סיבוכיות זמן ומקום (Time & Space Complexity)

הרצאה זו תהיה מעט שונה מהקודמות - לא נלמד בה סינטקס שימושי, נפגוש בעיות חדשות או נפתח אלגוריתמים לפתרון שלהם. בהרצאה נצלול לעולם הסיבוכיות, ונרכוש כלים לניתוח האלגוריתמים אותם אנחנו כותבים, בדגש על צריכת המשאבים שלהם.

ההרצאה תדרוש מאיתנו מספר כישורים מתמטיים שנזכיר בקצרה לפני, והיא יכולה להרגיש “זרה” ולא קשורה בדיוק לשאר נושאי הקורס. אנחנו נסביר את הכל מההתחלה ועד הסוף ולא נוותר על אף פרט, אבל חשוב להדגיש שהיא דורשת מעט פתיחות מחשבתית - זהו נושא חדש לחלוטין עם אוריאנטציה הרבה יותר מתמטית משאר הקורס.

באופן כללי, אלגוריתמים צורכים שני משאבים עיקריים:

1. זמן: אם נפתח שעון בתחילת האלגוריתם ונסגור אותו בסופו, כמה זמן יעבור?
2. זכרון: אם נמדוד את כמות הבתים שהאלגוריתם מקצה לטובת ריצתו, כמה נקבל?

נפתח דרך שיטתית להשוות בין צריכת המשאבים הללו בין אלגוריתמים שונים.

Big-O Notation

בחלק זה נגדיר בצורה מתמטית מדויקת מספר מושגים שישמשו אותנו לטובת הגדרת הסיבוכיות - בהמשך נראה כיצד נוכל להשתמש במושגים אינטואיטיביים יותר.

ראשית, נרצה לבודד אינוריאנטים בין אלגוריתמים שונים - דברים שאינם משתנים בין אם נשתמש באלגוריתם A או B. הקבוע המשמעותי ביותר הוא גודל הקלט שהאלגוריתם צריך לעבד - למשל, נזכר בדוגמא של חיפוש במערך ממוין:

int find_in_array(int* arr, int n);

בין אם נפעיל חיפוש בינארי או חיפוש איטרטיבי במערך, גודל המערך זהה בין שני האלגוריתמים.לכן, נרצה להביע את צריכת המשאבים של האלגורימים כפונקציה של גודל הקלט, אותו נסמן בדרך כלל ב-$n$. למעשה, לכל אלגוריתם קיימת פונקציה $f(n)$ שמתארת את זמן הריצה שלו בהנתן גודל קלט מסוים. נסיק כמה מסקנות לגביה:

1. היא חיובית - כל אלגוריתם לוקח לפחות צעד אחד.
2. היא מונוטונית לא יורדת - כאשר $n$ גדל, מספר הצעדים לא יכול לקטון.
3. היא משתנה בין מחשב למחשב - מחשב חזק יותר יכול לבצע יותר פעולות ליחידת זמן ממחשב חלש יותר.

נקודה 3 בעייתית מבחינתנו. אנחנו לא רוצים להשוות בין כל מחשב לכל מחשב אחר - לכן הניתוח שלנו יתמקד באותם אינוריאנטים שלא משתנים ממחשב למחשב. בנקודות 1-2 נוכל להשתמש בצורה חכמה יותר.

חסם עליון

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות \( f(n), g(n) \). נסמן כי \( f(n) = O(g(n)) \) אם קיים \(c>0\) ו-\( N \) שלם כך שלכל \(n>N\) מתקיים \( c \cdot g(n) \ge f(n) \).

אינטואיטיבית, ההדרה אומרצ

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות $f(n), g(n)$. נסמן כי $O(g(n)) = f(n)$ אם קיים $0<c$ ו-$N$ שלם כך שלכל $N<n$ מתקיים $g(n) \cdot c \ge f(n)$.

אינטואטיבית, ההגדרה אומרת שהחל ״ממקום מסוים״, $g(n)$ תמיד גדולה מ-$f(n)$. בלשון הדיבור, אומרים ש-“$f(n)$ היא O (האות O) של $g(n)$״.

לדוגמא, עבור:

אפשר להראות כי:

כאשר החלפנו את האיברים $\log n$ ו-$1$. לכן מתקיים $O(n^2)=f(n)$.

חסם תחתון

קיימת הגדרה סימטרית לכיוון ההפוך, עם סימון אחר:

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות $f(n), g(n)$. נסמן כי $\Omega (g(n)) = f(n)$ אם קיים $0<c$ ו-$N$ שלם כך שלכל $N<n$ מתקיים $g(n) \cdot c \le f(n)$.

וכעת ניתן לשלב את שתי ההגדרות להגדרה שתעניין אותנו:

הגדרה: אם מתקיים $O(g(n)) = f(n)$ ו-$\Omega (g(n)) = f(n)$, אז נאמר ש-$g(n)$ היא חסם אסימפטוטי של $f(n)$ ונסמן $\Theta(g(n)) = f(n)$.

השיטה לחישוב החסם האסימפטוטי של פונקציה נתונה כלשהי $f(n)$ פשוטה - צריך למצוא את הגורם ״החזק ביותר״ בפונקציה, זה שגדל במהירות הגדולה ביותר - והוא החסם, לאחר השמטה של האיברים ה-״חלשים״ יותר. למעוניינים, מצורפת הוכחה לכך בהמשך - נקבל עובדה זו באופן אינטואטיבי לשאר.

דוגמאות:

1. עבור פולינום כללי:

ניתן לחסום את $f(n)$ משני הכיוונים ע״י פולינומים $^kn$, ולכן $\Theta(n^k)=f(n)$. למעשה השמטנו את כל האיברים שאינם החזק ביותר. כמו כן, נשים לב שהשמטנו את הקבוע הכפלי של $^kn$ - אין צורך בו, מכיוון שההגדרה מדברת על כך שקיים קבוע כללי.

2. עבור:

ניתן לכתוב:

גם כאן, זיהינו כי מתקיים $\sqrt n < n$ באופן כללי, ולכן גם $\sqrt n < n \log n$. כלומר, $n \log n $ הוא הגורם השולט על הפונקציה ולכן ניתן להשמיט את $\sqrt n$.

סיבוכיות אלגוריתם

הגדרה: נתונה פונקציה $f(n)$ המתארת את זמן הריצה או צריכת הזכרון של אלגוריתם מסוים. סיבוכיות הזמן או המקום בהתאמה של האלגוריתם היא החסם האסימפטוטי של הפונקציה: $\Theta (f(n))$.

דוגמא: נניח שקיימת פונקציה שזמן הריצה שלה מתואר ע״י הפונקציה הבאה:

כאשר $_ik$ הם קבועים הקשורים למחשב הספציפי בו האלגוריתם רץ. סיבוכיות הזמן של האלגוריתם הוא, כפי שראינו עבור פולינום כללי, $\Theta (n^2)$. נשים לב לכמה יתרונות עיקריים בגישת הגדרה זו:

1. אנחנו מסתכלים על האיבר הדומיננטי כאשר הקלט גדול - כאשר $\infty \rightarrow n$ האיברים שאינם $^2n$ פחות רלוונטים, וזה מאפשר לנו להתעסק בעיקר ולהשוות בין אלגוריתמים עם התנהגות אסימפטוטית דומה.
2. אנחנו מבטלים את התלות במחשב הספציפי עליו האלגוריתם רץ, ומתעסקים בניתוח כללי של האלגוריתם עצמו.
3. יש לנו כעת דרך שיטתית להשוות בין אלגוריתמים שונים ולהחליט מי מהן עדיף לנו.

תלות הסיבוכיות בקלט

שאלה שניתן לשאול כעת היא תלות הסיבוכיות בקלט. נבחן למשל את הדוגמא הבאה: נתון מערך arr לא ממוין באורך n, ואנו מעוניינים למצוא את האינדקס (אם קיים) של מטרה כלשהי target. מכיוון שהמערך לא ממוין ואין לנו מידע נוסף עליו, המטרה יכולה להיות בכל מקום בו, ואין דרך להמנע מאיטרציה על כל המערך. עם זאת, אפשר לבחון שני מקרי קיצון שונים:

• המטרה נמצאת באינדקס 0 - במקרה זה, נמצא את המטרה בפעולה אחת והסיבוכיות היא לכאורה $\Theta(1)$. זהו גם המקרה הטוב ביותר האפשרי עבור הקלט.
• המטרה נמצאת באינדקס n - 1 - במקרה זה, נמצא את המטרה ב-n פעולות והסיבוכיות היא לכאורה $\Theta(n)$. זהו גם המקרה הגרוע ביותר האפשרי עבור הקלט.

מה נכון?

מעתה והלאה, כאשר נדבר על סיבוכיות, תמיד נדבר על המקרה הגרוע ביותר. הסיבה לכך היא שכך ניתן להבטיח חסם עליון על זמן הריצה של האלגוריתם. בדוגמא הזו של חיפוש לינארי בקלט, יתכנו מקרים בהם אורך הקלט לא יהיה גורם משמעותי על זמן הריצה של האלגוריתם, מכיוון שהאינדקס בו נמצא המטרה הוא 0. עם זאת, ניתן להגיד בוודאות כי זמן הריצה של לכל היותר אסימפטוטי ל-$\Theta(n)$.

דוגמאות

חיפוש בינארי

ניתחנו קודם את הסיבוכיות של חיפוש בינארי וראינו כי הפונקציה המתארת את זמן הריצה היא:

מכיוון ש-$\log$ בבסיסים שונים נבדלים זה מזה רק בקבוע כפלי, ניתן לכתוב בפשטות כי סיבוכיות הזמן של חיפוש בינארי היא $\Theta (\log n)$. כאשר ננתח את סיבוכיות המקום של האלגוריתם, נשים לב שאנחנו מקצים 3 משתנים בלבד - מספר קבוע שאינו תלוי בגודל הקלט $n$ בכלל. לכן, סיבוכיות המקום של האלגוריתם היא $\Theta (1)$.

Bubble Sort

במיון בועות יש להסתכל על המקרה הגרוע ביותר. נסתכל למשל על מערך ממוין הפוך:

באיטרציה הראשונה של מיון בועות, ה-5 יבעבע כלפי מעלה עד למצב הבא:

ובאיטרציה הבאה 4 יצטרך לבעבע שוב עד למעלה, אבל מכיוון שאנחנו יודעים שהאיבר הגדול ביותר כבר נמצא באינדקס n - 1, נצטרך לבעבע רק עד ל-n - 2:

וכך הלאה. כלומר, במקרה הגרוע ביותר, נבצע בכל איטרציה מספר יורד של פעולות, לסה״כ הבא:

זוהי סדרה חשבונית עם הפרש $1=d$ ו-$n$ איברים, שסכומה:

כלומר, סיבוכיות הזמן היא $\Theta(n^2)$. בהמשך נראה שזוהי סיבוכיות זמן לא מוצלחת מאוד עבור אלגוריתם מיון, ושניתן לעשות זאת בסיבוכיות טובה יותר.

מיזוג

להזכירכם, הנה הקוד לביצע מיזוג מערכים ממוינים:

void merge(int* arr1, int n, int* arr2, int m, int* arr3) {
    for(int i1 = 0, i2 = 0, i3 = 0; i1 < len1 && i2 < len2; i3++) {
        if(arr1[i1] < arr2[i2]) {
            arr3[i3] = arr1[i1++];
        } else {
            arr3[i3] = arr2[i2++];
        }
    }
    // Copy leftover elements from either array
    while(i1 < len1) {
        arr3[i3++] = arr1[i1++];
    }
    while(i2 < len2) {
        arr3[i3++] = arr1[i2++];
    }
}

נסמן ב-n את אורך המערך הראשון וב-m את אורך המערך השני. בכל איטרציה של המיון אנחנו מקדמים או את i1 או את i2 - גם לאחר מכן, בהעתקת שארית המערכים, אנחנו בכל איטרציה מקדמים אינדקס למערך הרלוונטי. כמו כן, בכל איטרציה אנו מבצעים מספר קבוע של פעולות, שאינו תלוי בגודל הקלט. כלומר, מספר הפעולות פרופורציונלי (שווה עד כדי קבוע כפלי) לסכום אורכי המערכים, n + m. לכן, נגיד כי סיבוכיות הזמן של מיזוג מערכים ממוינים היא לינארית בסכום אורכי המערכים, או:

הקצנו לטובת הפונקציה גודל קבוע שאינו תלוי בקלט (מספר משתנים בודדים), ולכן סיבוכיות המקום של המיזוג היא $\Theta(1)$.

הערה: פונקציה לינארית היא פולינום ממעלה ראשונה, מהצורה $b+an=f(n)$.

מיון מיזוג

מצאנו את סיבוכיות הזמן של מיזוג, ולכן יהיה פשוט יותר למצוא את סיבוכיות הזמן של מיון באמצעות מיזוג (Merge Sort). במיון מיזוג מתחילים במיזוג של מערכים באורך 1, לאחר מכן 2, 4 עד למיון של כל המערך (כאשר נניח לפשטות שהמערכים באורך חזקה של 2, $^k2=n$). לכן, כפי שראינו, מספר האיטרציות של מיזוג שיתבצעו הוא $\log_2n$. כמו כן, ראינו כי כל מיזוג מכיל $m+n$ איטרציות כאשר $m,n$ הם אורכי המערכים הממוזגים. כמו כן, בכל איטרציה יש למיין מספר יורד של מערכים - בהתחלה $^{k-1}2$, ואז $^{k-2}2$ וכך הלאה.

כלומר, בשלב ב-$h$ של המיון, ישנם $^{k-h}2$ מערכים למיין, שאורך כל אחד מהם $^{h}2$. לכן מספר הפעולות בכל שלב היא:

וישנם $\Theta(n)=\log_2n$ שלבים למיון, כך שסה״כ סיבוכיות הזמן של מיון מיזוג היא:

הוכחה - מציאת חסם אסימפטוטי

ננסח את הטענה הקודמת בצורה מדויקת יותר:

טענה: תהי $f(n)$ פונקציה

תרגילים

תרגיל 1

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

int f(int n) {
    int a = 1;
    while(a < n) {
        a *= 2;
    }
    for(int i = 0; i < 10000000; i++) {
        printf("a + i = %d", a + i);
    }
    return a;
}

כרגיל, אנחנו מעוניינים למצוא את סיבוכיות הזמן כתלות בגודל הקלט n ולכן ניתן להשמיט כל מספר קבוע של פעולות. אף על פי ש-10000000 הוא מספר שנראה גדול, הוא עדיין קבוע, ולכן כל הלולאה השנייה מתבצעת ב-$\Theta(1)$. הלולאה הראשונה לעומתה מתבצעת כל עוד a < n, כאשר a מוכפל ב-2 בכל איטרציה. דרך נוחה להבין כמה איטרציות לולאה מתבצעת היא לחשוב מה קורה באיטרציה ה-k עבור מספר טבעי כלשהו. באיטרציה ה-k מתקיים $^k2=a$, ולכן האיטרציה האחרונה תתקיים כאשר:

כלומר, יתקיימו לכל היותר $\log_2n$ איטרציות של הלולאה, לסה״כ סיבוכיות זמן של $\Theta(\log n)$. סיבוכיות המקום היא $\Theta(1)$ מכיוון שמוקצה מספר קבוע של משתנים שאינו תלוי בקלט.

תרגיל 2

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n. הניחו שסיבוכיות הזמן של malloc היא $\Theta(1)$.

void f(int n) {
    int* arr = malloc(n * sizeof(int));
    int** ptrs = malloc(n * sizeof(int*));
    for(int i = 0; i < n; i++) {
        ptrs[i] = malloc(n * sizeof(int));
        for(int j = 0; j < n; j++) {
            arr[i] = j;
            arr[j] = i;
        }
    }
    free(arr);
    for(int i = 0; i < n; i++) {
        free(ptrs[i]);
    }
    free(ptrs);
}

נתחיל בסיבוכיות הזמן. הקוד מכיל זוג לולאות מקוננות הרצות שתיהן מ-0 ועד n, ועוד לולאה יחידה ללא קינון עם אותן גבולות - היא קצרה יותר ולכן תהיה זניחה ביחס לראשונה. הלולאה החיצונית רצה n איטרציות, כאשר בכל איטרציה של הלולאה החיצונית יש n איטרציות של הלולאה הפנימית. לכן סיבוכיות הזמן היא:

מבחינת סיבוכיות המקום, הקצנו מערך אחד arr באורך n ואז מערך של מערכים באורך n, שאורך כל אחד מהמערכים בו הוא n. לכן סיבוכיות המקום היא גם:

שאלה 3

חשבו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void f(int* a, int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n && a[i] < a[j]; j++);
    }
}

הפונקציה אינה משתמשת בזכרון דינמי (או רקורסיה, עליה נלמד בהרצאה הבאה) ולכן סיבוכיות המקום שלה היא $\Theta(1)$. מבחינת סיבוכיות המקום, הפונקציה מכילה שתי לולאות מקוננות. החיצונית רצה n איטרציות ללא תלות בפנימית. עם זאת, מספר האיטרציות של הלולאה הפנימית תלוי בקלט! כיצד נדע? להזכירכם, אנחנו תמיד מסתכלים בסיבוכיות על המקרה הגרוע ביותר - הקלט עבורו סיבוכיות הזמן הכי גרועה שיכולה להיות. ניתן לייצר מערך קלט a עבורו התנאי a[i] < a[j] לכל i, j , כך שלכל אחת מ-n האיטרציות החיצוניות יהיו n איטרציות פנימיות. לכן סיבוכיות הזמן היא:

המקרה הגרוע ביותר הוא תמיד זה שלפיו נבחן את הסיבוכיות.

שאלה 4

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void f(int n) {
    for(int i = 2; i < n; i *= i);
}

מבחינת סיבוכיות מקום, מוקצה מספר קבוע של משתנים ולכן היא $\Theta(1)$. סיבוכיות הזמן מעט יותר מורכבת. ננסה לחשב - מהו ערכו של i באיטרציה ה-k? נכתוב כמה מהערכים הראשונים:

אם נכתוב את הערכים הראשונים כחזקות של 2, קצת יותר קל לראות את הסדרה:

בכל איטרציה מתקיים מספר קבוע של פעולות, כאשר מספר האיטרציות $k$ מקיים:

שאלה 5

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void g(int k) {
    for(int l = 0, m = 0; l < n || m < n * n; l++, m++);
}
void f(int n) {
    for(int i = 0; i <= n; i += 10) {
        g(i);
        g(n - i);
    }
}

הרצאה 10 - רקורסיה

מבוא

רקורסיה היא אחד הקונספטים המעניינים ושימושיים במדעי המחשב, וספציפית בשפת C. הוא ידוע לשמצה בתור קשה להבנה ושימוש, אבל אנחנו נעשה מאמץ לפרק אותו לחלקים ולהבין כיצד להשתמש בו בצורה נכונה וחכמה. ישנן בעיות שפתרונן הרקורסיבי פשוט לאין שיעור מפתרונן ״הרגיל״.

לטובת הבנה עמוקה של הנושא, נבחן מקרה דוגמא קלאסי - חישוב עצרת של מספר.

חישוב עצרת איטרטיבי

הנה בעיה - בהנתן מספר n שלם כלשהו, חשבו את העצרת שלו. מימוש פשוט וקל יכול להיות כזה:

int factorial(int n) {
    if(n >= 2) {
        return n;
    }
    int result = 1;
    for(int i = n; i > 1; i++) {
        result *= i;
    }
    return result;
}

זהו פתרון פשוט שיעבוד בצורה מצוינת לפי הגדרת העצרת:

נרצה לבחון דרך אחרת לפתור את הבעיה. היא אולי תראה בהתחלה לא טבעית, אבל הבנה טובה שלה תהיה קריטית להמשך.

חישוב עצרת רקורסיבי

נשים לב לעובדה הבאה בנוגע לעצרת - ניתן בקלות לפשט את הבעיה של חישוב $!n$ לבעיה פשוטה יותר, של חישוב $!(1-n)$, מכיוון שמתקיים:

כלומר, אין צורך בכלל לדעת את $!n$ אם אנחנו יודעים את $!(1-n)$. מצד שני, ניתן לחשוב שלא עשינו כלום בכך - איך נחשב כעת את $!(1-n)$? באופן מפתיע, נעשה את אותה הפעולה שוב!

למעשה, נוכל לעשות זאת עד שנגיע למספר שאנחנו יודעים בוודאות מהי העצרת שלו ללא חישוב - במקרה זה, המספר $1$:

כאשר הגענו ל-$!1$ הפסקנו לבצע את הפירוק של $!(1-n)\cdot n=!n$, מכיוון שאנו יודעים שמתקיים על פי ההגדרה $1=!1$.

פתרון בעיה ע״י פירוק שלה למספר מקרים של פשוטים יותר של אותה בעיה נקרא רקורסיבי. למעשה, בכל שלב כתבנו את בעיית העצרת כבעיית עצרת פשוטה יותר, עם כפל במספר כלשהו - עד שהגענו למקרה כלשהו בו ידענו לפתור נאיבית את הבעיה. מקרה זה נקרא מקרה הבסיס ונרחיב עליו בהמשך.

כעת נממש את הפתרון שלנו בקוד. הוא יכיל מאפיין מעניין שטרם פגשנו:

int factorial(int n) {
    if(n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

פונקציה כמו factorial הזו, הקוראת לעצמה, נקראת רקורסיבית. אין שום מניעה שפונקציה תקרא לעצמה בשפת C - ניתן לחשוב על זאת כמעין לולאה. כאשר הוספנו את מקרה הבסיס של n <= 1, דאגנו לתנאי עצירה לאותה הלולאה.

הערה: המימוש הנ״ל בעייתי במספר מובנים - n יכול להיות שלילי, ועבור n > 12 מתקיים כי !n גדול מטווח היצוג של משתנה int. ניתן לכתוב מימושים נכונים יותר המתחשבים ביותר מקרי קצה או מכירים בהם.

רקורסיה

כעת נגדיר בצורה פורמאלית יותר את הדרך לפתרון בעיות בצורה רקורסיבית. מה אנחנו צריכים? נניח שנתונה לנו:

1. בעיה כלשהי שיש לפתור עבור גודל קלט $n$ כלשהו.
2. מקרה בסיס (או מקרי בסיס) עבורו אנחנו יודעים את פתרון הבעיה.
3. דרך לכתוב את הבעיה מחדש בהנתן $n$ אחר, כאשר שימוש חוזר בכתיבה תביא אותנו למקרה הבסיס. כל כתיבה כזו נקראת צעד רקורסיה.

נבחן דוגמא נוספת - נחשב חזקה של מספר כלשהו באופן רקורסיבי. נתון הביטוי, עבור $n$ שלם כלשהו:

ראשית יש למצוא את מקרה הבסיס כדי שנדע לאיזה כיוון יש לצעוד רקורסיבית. אנחנו יודעים , למשל, כי לכל $x$ מתקיים:

ולכן נרצה לצעוד רקורסיבית עם $n$ יורד - זה בדרך כלל יהיה המקרה. כיצד ניתן להוריד את $n$? אפשר לכתוב את הפונקציה כך:

מצאנו את מקרה הבסיס ואת צעד הרקורסיה! נכתוב מימוש:

int power(int x, int n) {
    if(n == 0) {
        return 1;
    }
    return x * power(x, n - 1);
}

דוגמא 1

כעת, כשאנחנו מרגישים יותר בנוח עם רקורסיה, נפתור בעיה שהפתרון הרקורסיבי שלה טוב חכם ונכון הרבה יתר מהפתרון האיטרטיבי שלה. בעיה: כתבו פונקציה שמקבלת מספרים מהמשתמש ומדפיסה אותם בסדר הפוך לסדר קבלתם, עד לקבלת מספר שלילי.

פתרון איטרטיבי

ראשית נדגים כיצד הפתרון האיטרטיבי מסורבל מאוד וקשה. מכיוון שצריך להדפיס את המספרים בסדר הפוך, אנחנו צריכים בהכרח לשמור את כל המספרים אצלנו עד האחרון ורק אז להתחיל להדפיס אותן הפוך. אנחנו לא יודעים כמה מספרים הולכים להגיע, ולכן אי אפשר לדעת מראש כמה מקום צריך להקצות. נקצה מערך בגודל התחלתי כלשהו, ובמידה ונחרוג ממנו נקצה אחד כפול ממנו בגודל ונעתיק את התוצאות אליו:

#include <stdlib.h>
#include <stdio.h>
void print_reverse(void) {
    int len = 32;
    int* arr = malloc(len * sizeof(int));
    int i = 0;
    while(i < len) {
        scanf("%d", &arr[i]);
        if(arr[i] < 0) {
            break;
        }
        if(++i == len) {
            len *= 2;
            int* new_arr = malloc(len * sizeof(int));
            for(int i = 0; i < len / 2; i++) {
                new_arr[i] = arr[i];
            }
            free(arr);
            arr = new_arr;
        }
    }
    for(int j = i - 1; j >= 0; j--) {
        printf("%d\n", arr[j]);
    }
    free(arr);
}

הפתרון מאוד לא פשוט - הוא דורש לקיים מערך שגדל במידת הצורך, לבדוק לו קצוות וכו׳ - מורכב ולא טריוויאלי בכלל.

פתרון רקורסיבי

הפתרון הרקורסיבי פשוט מאוד. תנאי העצירה הוא קבלת מספר שלילי, וצעד הרקורסיה הוא קבלת מספר נוסף.

#include <stdio.h>
void print_reverse(void) {
    int n;
    scanf("%d", &n);
    if(n < 0) {
        return;
    }
    print_reverse();
    printf("%d\n", n);
}

כמעט קשה להאמין שהפתרון הזה תקין, אבל מסתבר שזה כל מה שצריך בשביל לפתור את הבעיה באופן רקורסיבי. טוב להזכר כאן בקונספט מחסנית הקריאות שהתעסקנו בו בעבר - מכיוון שכל קריאה חדשה ל-()print_reverse נדחפת על מחסנית הקריאות, בהכרח האחרונה תסתיים לפני שאחת לפניה תסתיים, ומובטח סדר הפוך להדפסות כרצוי.

סיבוכיות זמן ומקום בתכנות רקורסיבי

נבחן את הפתרון לבעיית ההדפסה ההופכית שפיתחנו קודם:

#include <stdio.h>
void print_reverse(void) {
    int n;
    scanf("%d", &n);
    if(n < 0) {
        return;
    }
    print_reverse();
    printf("%d\n", n);
}

נרצה לנתח את סיבוכיות הזמן והמקום של האלגוריתם הזה. סיבוכיות הזמן פשוטה יחסית - אם אורך הקלט הוא n, נבצע n קריאות לפונקציה print_reverse כאשר בכל קריאה נבצע מספר קבוע של פעולות, לסה״כ $\Theta(n)$. סיבוכיות המקום מעט מורכבת יותר. להזכירכם, כל קריאה לפונקציה דוחפת stack frame חדש על מחסנית הקריאות - המשתנים הלוקאלים של הפונקציה, כתובות חזרה וכו׳. הקריאה הרקורסיבית מתבצעת $n$ פעמים, ולכן נקצה $\Theta(n)$ זכרון על מחסנית הקריאות!

זהו חסרון מפתיע של תכנות רקורסיבי - בגלל שאנחנו משתמשים במחסנית הקריאות בתור מבנה הנתונים שלנו, באופן טבעי הקצנו עליה זכרון בסקאלה של הפתרון שאנחנו צריכים.

כדוגמא נוספת, נחשב את סיבוכיות הזמן והמקום של חישוב עצרת איטרטיבי אל מול רקורסיבי:

int factorial_recursive(int n) {
    if(n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
int factorial_iterative(int n) {
    int result = 1;
    for(int i = n; i > 1; i--) {
        result *= n;
    }
    return result;
}

בפתרון הרקורסיבי נבצע $n$ קריאות רקורסיביות עם $\Theta(1)$ פעולות בכל קריאה, ולכן נקבל סיבוכיות זמן של $\Theta(n)$ וסיבוכיות מקום של $\Theta(n)$ - בגלל ההקצאות על הקריאות הרקורסיביות על מחסנית הקריאות. הפתרון האיטרטיבי, לעומתו, לוקח את אותו $\Theta(n)$ בסיבוכיות הזמן, אבל מקצה מספר משתנים בודדים ולכן סיבוכיות המקום שלו היא $\Theta(1)$!

הערות:

1. למרות החסרון בשימוש במקום הזה של פתרון רקורסיבי, הרבה פעמים שימוש ברקורסיה מפשט משמעותית פתרון בעיות והרבה פעמים נרצה להשתמש בו. חשוב להיות מודעים למשמעויות ולוודא שאנחנו לא מקצים יותר מדי זכרון.
2. חשוב מאוד להיות מודעים לצריכת הזכרון של פתרונות רקורסיביים - טעות קלאסית במבחן היא לשכוח זאת ולקבל סיבוכיות מקום שגויה עבור פונקציות רקורסיביות.
3. ניתן לחשוב שאולי אפשר להמנע מהצורך להקצות stack frame חדש בעת קריאה רקורסיבית - הרי ניתן לכל הפחות להפטר מכתובת החזרה, מכיוון שאנחנו חוזרים לאותו מקום! מתסבר שזה נכון, וקיימות שפות תכנות גבוהות יותר עם מנגנון בשם Tail Call Optimization שמעלימות את הצורך בשימוש בזכרון נוסף לצורך קריאות רקורסיביות. בשפת C המנגנון הזה לא קיים לצערנו.

תרגילים

תרגיל 2

סדרת פיבונאצ׳י היא סדרת מספרים רקורסיבית המוגדרת ע״פ הנוסחא הבאה:

כלומר, כל איבר בסדרה הוא סכום שני האיברים לפניו, כאשר שני האיברים הראשונים מוגדרים להיות $1$.

סעיף א׳

כתבו פונקציה רקורסיבית שמקבלת מספר אי-שלילי n ומחזירה את המספר במקום ה-n בסדרת פיבונאצ׳י.

פתרון

סדרת פיבונאצ׳י מוגדרת באופן טבעי בצורה רקורסיבית - צעד הרקורסיה ומקרי הבסיס מוגדרים לנו באופן טבעי בהגדרת הסדרה. לכן כתיבת הפונקציה אינה מאוד מסובכת:

int fib(int n) {
    if(n == 0 || n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

סעיף ב׳

חשבו כמה קריאות לפונקציה fib מתבצעות עבור fib(5). מהו fib(5)?

פתרון

נפרק לגורמים את הקריאות הרקורסיביות עד למקרה הבסיס:

כלומר, מתבצעות 7 קריאות לפונקציה! נשים לב שחישבונ את fib(2) למשל 3 פעמים שונות - מאוד לא יעיל.

סעיף ג׳

נתון כעת כי יש לחשב את fib של מספרים שונים מספר מאוד גדול של פעמים לאורך ריצת תוכנית כלשהי, אבל עדיין באופן רקורסיבי. כתבו שיפור לפונקציה הקודמת שמשתמשת במערך עזר סטאטי כך שחישוב כל איבר בסדרה מתבצע לכל היותר פעם אחת לאורך ריצת התוכנית. נתון כי הערך המקסימלי עבורו תקרא fib הוא 20.

פתרון

בשביל לחשב רק פעם אחת כל איבר בסדרה, נוכל להשתמש במערך עזר שיכיל את החישובים הקודמים. נאתחל אותו לערך לא חוקי כדי שנוכל להבדיל בין ערכים שחושבו לערכים שעוד לא הגענו אליהם, ונקבל את הפתרון הבא:

#include <stdbool.h>
#define MAX_FIB 21
#define NEW_CALC -1
int fib(int n) {
    static int fibs[MAX_FIB];
    static bool initialized = false;
    if(!initialized) {
        fibs[0] = 1;
        fibs[1] = 1;
        for(int i = 2; i < MAX_FIB; i++) {
            fibs[i] = NEW_CALC;
        }
        initialized = true;
    }
    if(fibs[n] != NEW_CALC) {
        return fibs[n];
    }
    fibs[n] = fib(n - 1) + fib(n - 2);
    return fibs[n];
}

שאלה 3

כתבו פונקציה רקורסיבית שהופכת מחרוזת נתונה in-place ללא לולאות. ניתן להניח שהמחרוזת שניתנת תקינה באורך $0\le n$.

פתרון

ראשית, משמעות הדרישה ל-in-place היא לבצע את ההיפוך למחרוזת על גבי הזכרון עליו המחרוזת הוקצאה, ללא העתקה למקום אחר בזכרון. שאלה זו דורשת מפורשות מימוש ללא לולאה, מכיוון שבמקרה זה המימוש האיטרטיבי הרבה יותר קל מהמימוש הרקורסיבי. הוא יראה בערך כך:

void swap(char* c1, char* c2);
void reverse_str(char* str) {
    int len = strlen(str);
    int l = 0, r = len - 1;
    while(l < r) {
        swap(&str[l++], &str[r--]);
    }
}

מדובר על לולאה עם שני אינדקסים שנעים זה לכיוון זה. כאשר ממירים לולאה לאינדוקציה, נוח להכניס פונקציה נוספת לקוד, אליה נקרא עם האינדקסים המעודכנים של הלולאה. זו נשתמש טכניקה קלאסית ברקורסיה - פונקציית עזר עם פרמטרים אחרים, שתקרא מתוך הפונקציה שאנו מממשים:

void swap(char* c1, char* c2);
void reverse_str_aux(char* str, int l, int r) {
    if(l >= r) {
        return;
    }
    swap(&str[l++], &str[r--]);
    revese_str_aux(str, l + 1, r - 1);
}
void reverse_str(char* str) {
    reverse_str_aux(str, 0, strlen(str) - 1);
}

שאלה 4

כתבו פונקציה רקורסיבית ללא לולאות שמחזירה true אם מחרוזת היא פלינדרום, ואחרת false. פלינדרום הוא מחרוזת ששווה למחרוזת ההופכית שלה.

פתרון

מדובר על עדכון קל לאלגוריתם בשאלה הקודמת שכתבנו. במקום להחליף בין כל שני תווים הופכיים, נבדוק אם הם שווים:

void is_pali_aux(char* str, int l, int r) {
    if(l >= r) {
        return true;
    }
    if(str[l] != str[r]) {
        return false;
    }
    return is_pali_aux(str, l + 1, r - 1);
}
void is_pali(char* str) {
    return is_pali_aux(str, 0, strlen(str) - 1);
}

שאלה 5

כתבו פונקציה שלוקחת מחרוזת ומוחקת ממנה תווים סמוכים זהים in-place. לאחר הפונקציה המחרוזת לא תכיל שום שני תווים סמוכים זהים. לדוגמא, המחרוזת aaaabbccc תהפוך ל-abc. כתבו ללא לולאות.

פתרון

נחזיק שני מצביעים למחרוזת - אחד לקריאה ואחד לכתיבה. המצביע לקריאה יקרא קדימה כל עוד הוא רואה את אותו תו - וכשיסיים, נבצע כתיבה. נמשיך כך עד לסוף המחרוזת, כאשר שני המצביעים יתחילו מאותו מקום:

void remove_duplicates_aux(char* read, char* write) {
    if(!(*read)) {
        *write = '\0';
        return;
    }
    *write = *read;
    char* next = skip_duplicates(read);
}
void remove_duplicates(char* str) {
    remove_duplicates_aux(str, str);
}

הרצאה 11 - מיון רקורסיבי

בהמשך להרצאה על רקורסיה, מסתבר כי ישנם אלגורימי מיון שמימוש רקורסיבי שלהם (במקום איטרטיבי) הוא מוצלח ואלגנטי. בהרצאה זו נפגוש מספר אלגוריתמים כאלו וננתח אותם לעומק.

מיון מיזוג רקורסיבי

מתברר כי את אלגוריתם המיון היעיל שלמדנו, Merge Sort, ניתן לממש בצורה רקורסיבית באופן מוצלח. האלגוריתם מעצם הוויתו מתאים למימוש רקורסיבי - הרי אנחנו שוברים את המערך הממוין לחלקים קטנים יותר, ומשתמשים בתת-מערכים ממוינים על מנת למזג בצורה יעילה.

תנאי העצירה באלגוריתם יהיה גודל תת-המערך הממוזג - ניתן לעצור עבור מערכים בגודל 1. צעד הרקורסיה יהיה הקטנת גודל המערך ואז מיזוג שלו, יחד עם העתקה ממערך העזר למערך המקורי:

#include <stdlib.h>
void merge(int* arr1, int len1, int* arr2, int len2, int* dst);
void merge_sort_aux(int* arr, int n, int* tmp_arr);
void merge_sort(int* arr, int n) {
    int* tmp_arr = malloc(n * sizeof(int));
    merge_sort_aux(arr, n, tmp_arr);
    free(tmp_arr);
}
void merge_sort_aux(int* arr, int n, int* tmp_arr) {
    if(n <= 1) {
        return;
    }
    int low = n / 2;
    int high = n - low;
    merge_sort_aux(arr, low, tmp_arr);
    merge_sort_aux(arr + low, right, tmp_arr);
    merge(arr, low, arr + low, high, tmp_arr);
    for(int i = 0; i < n; i++) {
        arr[i] = tmp_arr[i];
    }
}

מבחינת סיבוכיות זמן, מתבצעות $\Theta(\log n)$ קריאות לפונקציה הרקורסיבית שאורכה $\Theta(n)$, ולכן בדומה למימוש האיטרטיבי נקבל $\Theta(n \log n)$. מבחינת סיבוכיות המקום, אנו מקצים $\Theta(n)$ זכרון עבור מערך העזר, ומכיוון שמתבצעות $\log n$ קריאות רקורסיביות אנחנו מקצים גם $\Theta(\log n)$ מקום עבור מחסנית הקריאות. סה״כ מתקיים שסיבוכיות המקום היא:

כלומר, הסיבוכיות זהה לחלוטין לסיבוכיות במימוש האיטרטיבי.

Quick Sort

שאלות מבחן

הנחות

1. ניתן להשתמש בטיפוס bool ובפונקציה malloc ללא שימוש ב-include#.
2. ניתן להניח שסיבוכיות הזמן של malloc(n) היא $\Theta(1)$ לכל n.
3. שלום שלום, ( \Theta = 5 ).
4. למשל אפשר לקבל \( x = 5 \)
5. ואולי גם אפשר לכתוב \( \theta(5) = 5 \)

שאלה 1

נתון מערך שלמים שאורכו n, בו כל האיברים אי-שליליים (גדולים/שווים ל-0) וקטנים ממש מקבוע x נתון. נגדיר מערך k-יחודי בתור מערך בו אם האיבר a מופיע, כל המספרים שבמרחק k ממנו לא מופיעים. כלומר, בהנתן איבר a במערך k-יחודי, האיברים הבאים לא מופיעים:

למשל, המערך הבא הוא 2-יחודי, ואינו 3-יחודי:

סעיף א

כתבו פונקציה המקבלת מערך ואורכו, וקובעת האם הוא 1-יחודי. על הפתרון לעמוד בדרישות סיבוכיות זמן \( \Theta(n + x) \) וסיבוכיות מקום \( \Theta(x) \).

פתרון

ננסה לפרק את הדרישה. מערך 1-יחודי הוא מערך בו אם המספר a מופיע, המספרים a - 1 ו-a + 1 אינם מופיעים. השאלה מאפשרת להשתמש בסיבוכיות מקום $\Theta(x)$ - זו אינדיקציה טובה מאוד להשתמש במערך באורך $x$. אפשר להשתמש במערך כזה על מנת לסמן את האיברים שכבר פגשנו בדגל בוליאני - בהגעה לאיבר a, נבדוק האם פגשנו כבר את האיברים a - 1 ו-a + 1. כמו כן, נבדוק האם a לא מופיע פעמיים. נבדוק בזהירות את האינדקסים על מנת לוודא שאנחנו לא חורגים מגודל המערך ונקבל את הפתרון הבא:

bool is_one_unique(int* arr, int n, int x) {
    bool* visited = malloc(sizeof(bool) * x);
    for(int i = 0; i < x; i++) {
        visited[i] = false;
    }
    bool is_unique = true;
    for(int i = 0; i < n; i++) {
        int a = arr[i];
        if((a >= 0 && visited[a - 1]) ||
            (a < x - 1 && visited[a + 1]) ||
            visited[a]) {
            is_unique = false;
            break;
        }
        visited[a] = true;
    }
    free(visited);
    return true;
}

מבחינת סיבוכיות, הפונקציה שלנו מבצעת שתי לולאות של x ו-n איטרציות בהתאמה, ובכל אחת מבצעת מספר קבוע של פעולות, ולכן סיבוכיות הזמן היא אכן $\Theta({n+x})$. סיבוכיות המקום היא $\Theta(x)$.

סעיף ב

כתבו פונקציה שמקבלת את אותם הפרמטרים ומחזירה האם מערך הוא k-יחודי. על הפתרון לעמוד בסיבוכיות זמן של $\Theta({nk + x})$.

פתרון

הגישה לא מאוד שונה מהסעיף הקודם. טריק חשוב שניתן ללמוד בשאלה הוא להשתמש בסיבוכיות הזמן המבוקשת בשביל להבין מה הפתרון הנדרש. בשביל לקבוע האם מערך הוא k-יחודי כש-$1 = k$, קיבלו סיבוכיות של $\Theta({n+x})$, השקולה ל-$\Theta({nk+x})$ עבור $1=k$. לכן נדרש רק להתאים מעט את הגישה שלנו. לכל מספר a במערך, במקום לבדוק אותו רק מול שני שכניו המיידים, כעת יש לבדוק אותו מול k שכניו - זה יהפוך ל-$nk$ בשתי לולאות מקוננות:

bool is_one_unique(int* arr, int n, int x) {
    bool* visited = malloc(sizeof(bool) * x);
    for(int i = 0; i < x; i++) {
        visited[i] = false;
    }
    bool is_unique = true;
    for(int i = 0; i < n; i++) {
        int a = arr[i];
        int start = (a - k < 0) 0 : a - k;
        int end = (a + k >= x) ? x - 1 : a + k;
        for(int j = start; j <= end; j++) {
            if(visited[j]) {
                is_unique = false;
                break;
            }
        }
        visited[a] = true;
    }
    free(visited);
    return true;
}

שאלה 2

נתוך מערך שלמים באורך n. לכל אינדקס i במערך, נגדיר פונקציה $f(i)$ שערכה הוא ההפרש בין סכום האיברים בין 0 ל-i (כולל) לבין סכום האיברים בין i + 1 ל-n - 1:

למשל, עבור המערך [1, 5, 3-, 10, 2] והאינדקס i = 1, מתקיים:

כתבו פונקציה המקבלת מערך ואורכו ומחזירה את האינדקס עבורו $f(i)$ מינימלית. אם יש מספר אינדקסים $i,j$ עבורם $f(i) = f(j)$ ניתן להחזיר כל אחד מהם. על הפתרון שלכם לעמוד בסיבוכיות זמן $\Theta(n)$ וסיבוכיות מקום $\Theta(1)$.

פתרון

זו שאלה שדורשת מעט להתחכם עם הגישה שלנו. פתרון אחד יכול להיות לחשב מפורשות את $f(i)$ לכל $i$ בגבולות המערך ולקחת את המינימלי - עם זאת, זה לא עומד בדרישות הסיבוכיות (חישוב n פעמים סכום של כל המערך יגיע לסיבוכיות $\Theta(n^2)$). עם זאת, נשים לב שאם נעשה חישוב עזר קטן של סכום איברי המערך, נוכל לחסוך חישוב חוזר בכל איטרציה. נסמן:

1. $s$ יהיה סכום כל המערך (אותו ניתן לחשב בריצה אחת על איברי המערך ב-$\Theta(n)$)
2. $_1p$ יהיה סכום איברי המערך מ-0 ועד i כלשהו (האיבר הראשון ב-$f(i)$)
3. $_2p$ יהיה סכום איברי המערך מ-i + 1 ועד n - 1 (האיבר השני ב-$f(i)$)

בהנחה שחישבנו את $s$ ו-$_1p$, מתקיים:

כלומר, אפשר לחשב את סכום המערך, ואז לבצע איטרציה על המערך, לעדכן את שני הסכומים ולבחור את המינימלי שראינו עד כה.

int min_f(int* arr, int n) {
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int s1 = 0, s2;
    int min_val = INT_MAX;
    int min_index = 0;
    for(int i = 0; i < n; i++) {
        s1 += arr[i];
        s2 = sum - s1;
        if(s1 - s2 <= min_val) {
            min_val = s1 - s2;
            min_index = i;
        }
    }
    return min_index;
}

שאלה 3

בהנתן מערך ממוין arr, נגדיר נקודת שבת בתור אינדקס i עבורו מתקיים arr[i] = i. כתבו פונקציה שמקבלת מערך ואורכו ומחזירה אינדקס של נקודת שבת אם קיימת, אחרת 1-. על הפתרון לעמוד בסיבוכיות זמן של $\Theta(\log n)$ וסיבוכיות מקום $\Theta(1)$.

פתרון

הרצאה XXX - Preprocessor

אחד האובייקטים המעניינים והשימושיים ביותר למתכנת מתקדם ב-C הוא ה-C preprocessor, או ה-CPP (לא להתבלבל עם השפה ++C). למעשה השתמשנו בו לא מעט עד כה - צירפנו קבצים ע״י include#, הגדרנו קבועים ע״י define# וכו׳. עם זאת, לא גידרנו את תחילת יכולתו של ה-CPP - הוא יכול לחסוך המון זמן וכתיבת קוד מחודשת, אך יכול להיות גם מרושע ולגרום לבאגים קשים מאוד לדיבוג. בהרצאה זו נפגוש מספר שימושיים - מספר מהם יהיה קלאסיים וכאלה שחשוב להכיר בשביל להשתמש בשפה בצורה נכונה, אחרים יהיו יותר משונים ומעניינים.

אופרטור ה-stringify

האופרטור מאפשר לקחת שורת טקסט בדיוק כמו שהיא ולהפוך אותה ל-string literal, או מחרוזת פשוטה. האופרטור מדביק את ה-token שמימינו בצורה מפורשת במקום שבו הוא נמצא.