תפריט משתמש
|
||||||||||||||||||||||||||||||||||||
קורס:"שפת C"
מתוך הספר: C - מדריך מקצועי  פירוק אלגוריתם למשימות עצמאיותבפרק הקודם ראינו כיצד ניתן לפרק אלגוריתם למשימות משנה ע"י שימוש במבני בקרה - משפטי תנאי ולולאות. לפעמים סוג זה של פירוק אינו מספיק. לדוגמא, נתונה המשימה הבא:
מטרת המשימה היא להדפיס את הטבלה הבאה: i power(2,i) power(3,i) - ---------- ---------- 0 1 1 1 2 3 2 4 9 3 8 27 4 16 81 5 32 243 6 64 729 7 128 2187 8 256 6561 9 512 19683
במבט ראשון, נראה שכדאי לפרק את המשימה ע"י לולאה:
כעת יש לפרק את הוראות הלולאה הדורשות את חישוב החזקה: נבצע זאת ע"י לולאה פנימית העוברת על המספרים i..1 ומבצעת הכפלה של 2 או 3 כמספר החזרות. האלגוריתם המלא:
כפי שניתן לראות, res1 ו- res2 מטופלים באופן דומה לחישוב החזקה ה- i-ית של 2 ו- 3 בהתאמה. כל אחד מהם מוכפל j פעמים בבסיס החזקה (2 או 3). בכדי לבצע את חישוב החזקה נכון יש לאתחל את res1 ו- res2 ל- 1. מהם חסרונות פירוק זה?
הגדרת משימה עצמאית ע"י פונקציהבפרק זה נראה כיצד ניתן לפרק משימה כללית למשימות משנה עצמאיות הנקראות פונקציות. פונקציות ניתנות לביצוע בכל שלב של התכנית ופעולתן יכולה להיקבע ע"י פרמטרים. בסיום החישוב הן מחזירות את התוצאה. נחזור לדוגמא הקודמת: את המשימה של חישוב חזקה ניתן להגדיר כפונקציה המקבלת 2 פרמטרים - את הבסיס ואת המעריך - ומחשבת את החזקה: פונקציה power לחישוב חזקה:
כעת ניתן להשתמש בפונקציה שהגדרנו power ע"י ציון שמה והעברת פרמטרים מתאימים. לדוגמא, בכדי לחשב את החזקה של 2 ב- 5 נכתוב power(2,5). אם נרצה לקבל את התוצאה במשתנה res למשל, נכתוב:
נגדיר את אלגוריתם המשימה הכללית תוך שימוש בפונקציה שהגדרנו power :
מנגנון הפונקציות ב- Cפונקציות ב-C הן מנגנון המאפשר חלוקה של משימה מורכבת למשימות קטנות יותר ועצמאיות. חלוקה של התכנית לפונקציות מאפשרת פיתוח מודולרי והדרגתי של התכנית, וכן יכולת טובה יותר לנפות (debug) את השגיאות בתכנית. תכנית בשפת C היא אוסף שטוח (ללא קינון) של פונקציות. אחת הפונקציות חייבת להיותmain( ) - זו הפונקציה שממנה מתחיל ביצוע התכנית. כאשר מפונקציה מסוימת קוראים לפונקציה אחרת מתבצעת הפסקה זמנית בביצוע הפונקציה הקוראת ועוברים לביצוע הפונקציה הנקראת, עד אשר זו מסתיימת. פונקציה נקראת יכולה להמשיך ולקרוא לפונקציה נוספת ובכך ליצור שרשרת קריאות. לדוגמא, נניח שיש לנו תכנית שבה קיימות הפונקציות h(), g(), f(), main(). main מבצעת קריאה ל- f ו- f קוראת לפונקציות g ו- h :
לאחר שהפונקציה הנקרא מסתיימת, חוזר הביצוע לפונקציה הקוראת, אל ההוראה העוקבת להוראת הקריאה לפונקציה. ניתן להעביר מידע ביו הפונקציה הקוראת לנקראת: הפונקציה הקוראת מעבירה רשימת פרמטרים (או ארגומנטים) לפונקציה הנקראת לצורך העיבוד. כאשר הפונקציה הנקראת מסתיימת, היא מחזירה את תוצאת העיבוד לפונקציה הקוראת. תוצאה זו היא הערך המוחזר של הפונקציה. פונקציות לדוגמא שהכרנו (פונקציות סטנדרטיות ב- C): printf(), scanf(), main(). הגדרת פונקציההמבנה התחבירי של הגדרת פונקציה: (<הצהרת פרמטרים>) <שם-הפונקציה> < טיפוס-ערך-המוחזר> } <הגדרות טיפוסים, קבועים ומשתנים> <הוראות> { הגדרות פונקציות יכולות להיות בסדר כלשהו, בקובץ אחד או יותר (בפרק 11 נראה תוכניות מרובות קבצים). כתכנית דוגמא, נממש את האלגוריתם שהגדרנו בתחילת הפרק. ראשית נגדיר פונקציה בשם power להעלאה בחזקה של מספר אחד בשני: /* file: powers.c */ #include <stdio.h> int power (int base, int n) { int result=1; int i; for (i=1; i<=n; ++i) result = result * base; return result; } כעת נכתוב את הפונקציה הראשית בתכנית, main(), תוך שימוש בפונקציה power(): void main() { int i; int res1, res2; printf("%-4s %-13s %-13s\n", "i", "power(2,i)", "power(3,i)"); printf("%-4s %-13s %-13s\n", "-", "----------", "----------"); for (i=0; i<10; ++i) { res1 = power(2,i); res2 = power(3,i); printf("%-4d %-13d %-13d\n", i, res1, res2); } }
פלט התכנית: i power(2,i) power(3,i) - ---------- ---------- 0 1 1 1 2 3 2 4 9 3 8 27 4 16 81 5 32 243 6 64 729 7 128 2187 8 256 6561 9 512 19683 הסבר
int power (int base, int n) { int result=1; int i; ... } ציינו ש- :
for (i=1; i<=n; ++i) result = result * base;
return result ;
res1 = power(2,i); res2 = power(3,i);
קריאה ישירה לפונקציה בהוראת ההדפסהנכתוב את הפונקציה הראשית main שוב באופן מעט שונה: void main() { int i; printf("%-4s %-13s %-13s\n", "i", "power(2,i)", "power(3,i)"); printf("%-4s %-13s %-13s\n", "-", "----------", "----------"); for (i=0; i<10; ++i) printf("%-4d %-13d %-13d\n", i, power(2,i), power(3,i)); } הפעם נקראת הפונקציה power בתוך הוראת ההדפסה, ותוצאתה מועברת ישירות כפרמטר לפונקציה printf לצורך הדפסה: printf("%-4d %-13d %-13d\n", i, power(2,i), power(3,i));
בגרסה זו של הפונקציה main אין צורך בהגדרת המשתנים res1, res2. הכרזה על אבטיפוס פונקציההכרזה על אבטיפוס פונקציה (function prototype) נדרשת כאשר היא נקראת ע"י פונקציה אחרת המופיעה לפניה בקובץ התכנית. נכתוב את התכנית שוב בסדר פונקציות שונה: #include <stdio.h> int power(int base, int n); /* prototype for the function power() */ void main() { int i; printf("%-4s %-13s %-13s\n", "i", "power(2,i)", "power(3,i)"); printf("%-4s %-13s %-13s\n", "-", "----------", "----------"); for (i=0; i<10; ++i) printf("%-4d %-13d %-13d\n", i, power(2,i), power(3,i)); } int power (int base, int n) { int result=1; int i; for (i=1; i<=n; ++i) result = result * base; return result; } השורה int power(int base, int n) ;
היא הכרזה מוקדמת על הפונקציה power הדרושה כדי ש- main תוכל לקרוא לה, הואיל ו- power מופיעה מאוחר יותר מ- main בתכנית. ההכרזה אומרת ש- power מקבלת שני פרמטרים מטיפוס שלם base ו- n ומחזירה ערך מטיפוס שלם. ניתן גם לכתוב את אבטיפוס הפונקציה כך: int power(int, int) ; כלומר לשמות base ו- n אין משמעות בהכרזה על האבטיפוס. יש להבחין בין הכרזה (או הצהרה) על אבטיפוס הפונקציה לבין הגדרת הפונקציה:
הצהרת הפרמטריםבקטע ההצהרה על הפרמטרים אנו קובעים אילו פרמטרים יועברו לפונקציה, כלומר מאיזה טיפוס וכמה פרמטרים. פרמטרים אלה נקראים פרמטרים פורמליים. הפונקציה הקוראת מעבירה לפונקציה הנקראת פרמטרים הנקראים פרמטרים אקטואליים. הפרמטרים הפורמליים הם העתק של הפרמטרים האקטואליים. הם מקבלים את ערכם בתחילת ביצוע הפונקציה:
המהדר בודק התאמה בין הפרמטרים האקטואליים לפרמטרים הפורמליים בקריאה לפונקציה. אם קיימת אי-התאמה הוא ינסה לבצע המרה מרומזת (תוך הודעת אזהרה במידת הצורך) - אחרת הוא יודיע על שגיאה. דוגמא: int power (int base, int n); void main() { int i = 3; float f = 2.5; int res = power(i,f); } בקריאה לפונקציה power המהדר יגלה אי-התאמה בפרמטר השני בין הטיפוס הפורמלי לטיפוס האקטואלי. מכיוון שקיימת המרה מרומזת מממשי לשלם הוא יבצע אותה - כלומר יקצוץ את השבר של f - ותוצאת הפונקציה תהיה power(3,2) = 9. כמו כן תתקבל אזהרה מהמהדר על ביצוע ההמרה. לעומת זאת, אם ננסה לבצע int res = power(i,"hello"); המהדר יודיע על שגיאה מכיוון שאין שיטת המרה ממחרוזת למספר. הצהרה על פרמטר כקבוע ע"י constבדומה להגדרת משתנה כקבוע, ניתן להכריז על פרמטר שפונקציה מקבלת כקבוע. במקרה זה הפונקציה לא תוכל לשנותו - ניסיון לשנותו יגרור הודעת שגיאה בהידור. מכריזים על פרמטר כקבוע ע"י המילה const . לדוגמא: int func(const int c1, const float c2);
כעת לא ניתן לשנות את c1,c2 בתוך הפונקציה func. שאלה: מדוע ומתי להגדיר פרמטר כ- const ? תשובה: כאשר ברור עפ"י תפקידו של הפרמטר שהפונקציה לא אמורה לשנות אותו. לדוגמא, בפונקציה power לעיל, הפרמטרים של הפונקציה הם בסיס החזקה והמעריך. ברור שבמקרה זה הפונקציה לא אמורה לשנות את הפרמטרים. הגדרתם כ- const יכולה לאתר שגיאה אפשרית של המתכנת: int power (const int base, const int n);
באופן עקרוני, נהוג להפריד בין מספר סוגי פרמטרים לפונקציה:
בשפות מסוימות מצהירים על הפרמטר (in, out, inout) בהתאם לסוגו. זה עוזר מאוד הן בתיעוד התוכנה והן ביכולת של המהדר להתריע בפני שגיאות תכנות. בשפת C אופן זה של הכרזה על פרמטרים לא קיים - כחלופה בסיסית פרמטרי הקלט יכולים להיות מצוינים ע"י const. ערך מוחזרהערך המוחזר הוא תוצאת העיבוד בפונקציה. הטיפוס שלו נקבע בכותרת הגדרת הפונקציה. בדוגמא הקודמת טיפוס הערך המוחזר של power() הוא שלם (int), והיא מחזירה את תוצאת החזקה, המוצבת בפונקציה הקוראת למשתנה מקומי שלה:
הערך המוחזר מוחזר ע"י ההוראה return. הוראה זו גם גורמת לסיום הביצוע של הפונקציה וחזרה לפונקציה הקוראת. ברירת המחדל עבור טיפוס הערך המוחזר היא שלם (int). כלומר אם לא מציינים את טיפוס הערך המוחזר הוא מוגדר כ- int. לדוגמא, הגדרת main() ללא ציון הטיפוס מציינת שהיא מחזירה int main() { ... return 0; }
במידה ורוצים להגדיר פונקציה שלא מחזירה כלל ערך, מגדירים את טיפוס הערך המוחזר כ- void. לדוגמא בתכנית power הפונקציה main היא מטיפוס void, כלומר לא מחזירה ערך כלשהו. המרת הערך המוחזרהערך המוחזר מהפונקציה יכול לעבור המרה - מרומזת או מפורשת - כדי להתאים את טיפוסו לטיפוס שאליו מציבים את התוצאה. לדוגמא: float max(float x, float y) { if(x>y) return x; else return y; } void main() { float a=9.4, b=34.8; int i; i = max(a,b); /* convert float to integer implicitly*/ } במקרה זה המהדר יציג הודעת אזהרה. ניתן לבצע המרה מפורשת ע"י i = (int) max(a,b); /* convert float to integer explicitly*/ הפונקציה mainmain היא פונקציה כמו כל פונקציה אחרת הנקראת ע"י מערכת ההפעלה, לכן גם היא יכולה להחזיר ערך. עד עתה, ציינו ש- main אינה מחזירה ערך ע"י ציון void כטיפוס הערך המוחזר. נהוג לציין ש- main מחזירה ערך מטיפוס int המציין את תוצאת הביצוע של התכנית: הצלחה מצוינת ע"י החזרת 0, וכשלון ע"י החזרת מספר שונה מ- 0 (למשל 1). תכנית דוגמא: #include <stdio.h> int main() { int num1; float num2; int n; printf("Please enter 2 numbers - integer and real: "); n = scanf("%d %f", &num1, &num2); if(n!=2) { printf("Incorrect input!"); return 1; } else { printf("The numbers are: %d %.2f", num1, num2); return 0; } } את הערך המוחזר של התכנית ניתן לבדוק מתוך מערכת ההפעלה. צורת הבדיקה תלויה במערכת ההפעלה עליה עובדים, והיא אינה חלק מהגדרת שפת C. לדוגמא, בעמ' 142 מובא קובץ batch המפעיל את התכנית prog.exe. עיין/י בקובץ זה. תרגולקרא/י סעיף זה בספר ובצע/י את תר' 1-2 בעמ' 143.
משתנים ופונקציותהמשתנים ב- C נחלקים ל- 2 סוגים עיקריים:
בהקשר לסוגי המשתנים, קיימים שני מושגים חשובים:
משתנים גלובלייםמשתנה גלובלי נוצר בתחילת התכנית ומתקיים לכל אורכה. תחום הפעולה שלו הוא בכל הקובץ החל מהמקום בו הוא מוגדר (מבחינה זו הוא זהה לפונקציה!). דוגמא: #include <stdio.h> int Xcm; void convert(); int main() { printf("Input a distance:"); scanf("%d",&Xcm); convert(); return 0; } void convert() { float Xinch; Xinch= Xcm / 2.54; printf("%d centimeters are %6.2f inches\n",Xcm,Xinch); } Xcm הוא משתנה גלובלי ה"מוכר" לשתי הפונקציות, main ו- convert, ע"י כך שהוא מוגדר מחוץ להן
int Xcm;
הפונקציה main קוראת את ערכו מהקלט ע"י scanf("%d",&Xcm); ולאחר מכן קוראת לפונקציה convert(). זו האחרונה ממירה את ערכו לסנטימטרים ומדפיסה את הערך החדש. רצוי להמעיט בהגדרת משתנים גלובליים בתכנית משתי סיבות עיקריות:
משתנים מקומייםמשתנה מקומי נוצר בזמן הקריאה לפונקציה : למשתנה מוקצית עמדת זיכרון על מחסנית הקריאות (ראה/י להלן). עם גמר ביצוע הפונקציה היא משתחררת והמשתנה חדל מלהתקיים. משתנה מקומי נקרא לפעמים גם משתנה אוטומטי מכיוון שהוא נוצר אוטומטית בזמן הקריאה לפונקציה והוא נעלם ברגע שהיא מסתיימת. דוגמא: #include <stdio.h> void f(); int main() { int i; for(i=0; i<4; i++) f(); } void f() { int x=0; int y=0; printf("x is %d, y is %d\n", x, y); ++x; ++y; } פלט התכנית: x is 0, y is 0 x is 0, y is 0 x is 0, y is 0 x is 0, y is 0
כפי שרואים, x ו- y מאותחלים בכל קריאה לפונקציה f() מחדש, וקידומם בסוף הפונקציה אינו תורם דבר. משתנה מקומי - סטטיניתן להגדיר משתנה מקומי כך שלא יהיה אוטומטי, אלא ייווצר פעם אחת ויתקיים לכל אורך התכנית. משתנה כזה נקרא משתנה סטטי. אופן ההגדרה: static int x; static float f; ערכו של משתנה סטטי נשמר בין הקריאות לפונקציה בה הוא מוגדר. משתנה סטטי מאוחסן באזור הנתונים (data segment) של התכנית - האזור בו מוגדרים המשתנים הגלובליים - ולכן משך חייו כמשך התכנית. למשל, אם בדוגמא הקודמת נשנה את הגדרת המשתנה x: #include <stdio.h> void f(); int main() { int i; for(i=0; i<4; i++) f(); } void f() { static int x=0; int y=0; printf("x is %d, y is %d\n", x, y); ++x; ++y; } פלט התכנית יהיה: x is 0, y is 0 x is 1, y is 0 x is 2, y is 0 x is 3, y is 0 משתנה מקומי בבלוקניתן להגדיר משתנה מקומי בתוך בלוק. בלוק מצוין ע"י סוגריים מסולסלות בתחילתו ובסופו. במקרה זה המשתנה יוכר רק בתוך הבלוק המגדיר. דוגמא: #include <stdio.h> void main() { int x=2; { int x; x = 3; } printf("x=%d",x); } יודפס: x=2
המשתנה x המוגדר בתוך הבלוק הפנימי שונה מהמשתנה x המוגדר בבלוק הפונקציה main() ולכן ערכו של x החיצוני אינו משתנה. משתנה מקומי בבלוק אינו שימושי בדרך כלל ורצוי להימנע מלהגדירו כך. ככלל, רצוי להגדיר את כל המשתנים המקומיים בתחילת הפונקציה. איתחול משתנים בברירת מחדללמשתנה שלא אותחל קיים ערך ברירת מחדל, בהתאם לסוגו:
סוגי משתנים - סיכום
מבנה זיכרון התכניתקטע הקוד וקטע הנתוניםכאשר התכנית עוברת הידור נוצר קובץ ביצוע (.exe) הכתוב בשפת מכונה, כלומר בשפת המחשב עליו בוצע ההידור. קובץ זה מכיל 2 קטעי זיכרון עיקריים:
קטע הקוד מורכב מפונקציות התכנית הכוללות את הוראות הביצוע בשפת המכונה, כפי שתורגמו משפת C. הן כוללות בדרך כלל הוראות העתקת ערך של משתנה אחד לשני, הדפסת ערך משתנה לפלט, פעולות חישוב מתמטיות, פעולות כתיבה לקבצים וכו'. קטע הנתונים הוא אזור האחסון של המשתנים הגלובליים של התכנית. מכיוון שעל משתנים אלו להתקיים במשך כל התכנית, הוגדר עבורם אזור אחסון זה באופן קשיח. לדוגמא, נתונה התכנית prog.c #include <stdio.h> int g1=8, g2=20; void main() { int x; if(g1>g2) x = g1; else x = g2; printf("x=%d",x); } קובץ הביצוע הנוצר לאחר ההידור כולל את 2 מרכיבי הזיכרון: prog.exe
לאחר סיום ההידור קובץ הביצוע נשמר על הדיסק. כאשר המשתמש מפעיל אותו מערכת ההפעלה טוענת אותו לזיכרון הראשי של המחשב והוא מתחיל להתבצע החל מההוראה הראשונה שבקטע הקוד. לפני תחילת ביצוע התכנית מערכת ההפעלה דואגת להקצות עבורה 4 אזורי אחסון:
מהלך יצירת התכנית וטעינתה לביצוע נראה כך:
שאלה: היכן מאוחסנים שאר נתוני התכנית - כלומר המשתנים המקומיים שבפונקציות? תשובה: משתנים אלה נוצרים על מחסנית הקריאות. מחסנית הקריאותבזמן ריצת התכנית קיים מנגנון המתאר את מצב הקריאות בין פונקציות בתכנית, הנקרא מחסנית הקריאות. הוא נקרא כך מכיוון שמבנה הנתונים שבו המהדר משתמש במנגנון זה הוא מסוג מחסנית (על מבנה נתונים זה נלמד בפרק 14, "טיפוסי נתונים מופשטים"). בכל רגע בזמן ריצת התכנית, משקפת מחסנית הקריאות את מצב הקריאות לפונקציות. לכל פונקציה במחסנית נשמרת מסגרת הפונקציה הכוללת את:
לדוגמא, בתכנית הבאה קיימות 2 פונקציות: int max(int x, int y) { int m; if(x>y) m=x; else m=y; return m; } void main() { int res; int a=8, b=29; res = max(a,b); } בתחילת ריצת התכנית, הפונקציה main() מתבצעת. לפני הקריאה ל- max() מחסנית הקריאות כוללת רק את מסגרת הפונקציה main(). מצב המחסנית הוא:
לאחר הקריאה לפונקציה max() ובמשך ביצועה מצב המחסנית הוא :
בחזרה מהפונקציה max(), מוחזר הערך של m - שהוא המקסימום מבין x,y - על המחסנית:
והערך המוחזר מוצב למשתנה res שבפונקציה main
תמונת הזיכרון הכוללתבעמ' 151-155 מובאת תוכנית דוגמא תוך הדגמת מבנה הזיכרון בכל שלב. עיין/י בעמודים אלו. רקורסיהרקורסיה היא תהליך שבו פונקציה קוראת לעצמה. במילים אחרות, פונקציה הכוללת הוראת קריאה לעצמה נקראת פונקציה רקורסיבית. דוגמא פשוטה לפונקציה רקורסיבית: #include <stdio.h> void main() { puts("hello"); main(); } הסבר: הפונקציה main() מבצעת הדפסה של המחרוזת hello ולאחר מכן קוראת לעצמה. בקריאה הבאה, main() שוב מבצעת הדפסה ושוב קוראת לעצמה:
תהליך זה הוא אינסופי, ולכן על המסך תודפס בלולאה אינסופית המחרוזת hello: hello hello hello hello hello ...
כפי שניתן לראות, פונקציה זו אינה שימושית במיוחד, וכמו כן היא עלולה לתקוע את המחשב. אנו נכתוב כעת דוגמא שימושית יותר לרקורסיה - פונקציה לחישוב העצרת של מספר נתון: #include <stdio.h> int azeret(int n) { if(n<=1) return 1; else return n*azeret(n-1); } void main() { printf("Azeret of 4 is : %d", azeret(4)); } פלט התכנית: Azeret of 4 is: 24 הסבר: הפונקציה azeret מחשבת את העצרת של מספר נתון ע"י קריאה רקורסיבית לעצמה. לפני הקריאה לעצמה היא מבצעת בדיקה של תנאי עצירה : if(n<=1) return 1;
במידה והפרמטר לפונקציה הוא 1 או פחות מוחזר 1. אחרת, הפונקציה מחזירה את העצרת של n-1 ע"י קריאה רקורסיבית: else return n*azeret(n-1);
התכנית קוראת ומדפיסה את ערך העצרת של 4 ע"י הקריאה printf("Azeret of 4 is : %d", azeret(4)); תרשים הקריאות: משחק מגדלי הנוימגדלי הנוי הוא משחק עתיק המציב בפני השחקן את האתגר הבא: נתונים 3 מגדלים, A,B,C, כאשר על מגדל A מושחלות n טבעות:
השחקן נדרש להעביר את הטבעות ממגדל A למגדל C, כך שהן יהיו מסודרות עפ"י סדר, כפי שהן במגדל A - טבעת קטנה נמצאת מעל טבעת גדולה יותר. יש לשמור על הכללים הבאים:
לדוגמא, עבור n=2, הפתרון יהיה:
עבור n=3 הפתרון יהיה:
שאלה: עבור n כלשהו מהו האלגוריתם לפתרון ? תשובה: הדרך הפשוטה ביותר להגדרת האלגוריתם היא באופן רקורסיבי. נגדיר אלגוריתם עבור פונקציה רקורסיבית, move, באופן הבא:
כלומר, הרעיון הוא לפתור בכל שלב את הבעיה עבור מספר קטן ב- 1 של מספר הטבעות, באופן רקורסיבי. קוד התכנית המממשת את האלגוריתם מובא בעמ' 160-161. תרגולקרא/י סעיף זה בספר ובצע/י את התרגיל שבעמ' 162.
סיכום
תרגילי סיכוםבצע/י את תר' 1-4 שבעמ' 163-164.
|
