תפריט משתמש
|
|||||||
קורס:"שפת C"
מתוך הספר: C - מדריך מקצועי 
הגדרת אלגוריתם ופירוקו למשימותאלגוריתם הוא סדרה של הוראות מדויקות לביצוע משימה נתונה. את הוראות האלגוריתם ניתן לרשום באופן טקסטואלי, בדומה להכנת מתכון לבישול, ע"י תרשים זרימה, ע"י קוד דמוי שפת תכנות (פסאודו-קוד) או בכל צורה אחרת. לדוגמא, נדרש לחשב את המקסימום מבין 3 מספרים שלמים הנתונים מהקלט ולהדפיסו. 1) אלגוריתם טקסטואלי:
2) אלגוריתם ע"י תרשים זרימה:
3) אלגוריתם ע"י פסאודו-קוד: Integer x,y, z, max
read x, y, z if x > y if x > z max <-- x else max <-- z else if y > z max <-- y else max <-- z print max פירוק למשימות משנהתהליך הגדרת האלגוריתם מתחיל בהגדרת המשימה הכללית לביצוע כמשפט בשפת אנוש המתאר את המטרה הכללית של התכנית. משפט זה בדרך כלל מופשט וכללי מדי להבנה ע"י המחשב. בהגדרת הוראות האלגוריתם, יש לקחת בחשבון אילו הוראות בסיסיות ניתנות לביצוע ע"י המחשב, ולאילו נדרשת הגדרה מפורטת יותר. כל הוראה מורכבת שאינה "מובנת" דיה ע"י המחשב ניתנת לפירוק באחד משלושה אופנים:
תהליך הפירוק ממשיך באופן רקורסיבי עד להגעה להוראות ברמת שפת התכנות שאיתה מממשים את האלגוריתם. כמו כן, במהלך הפירוק צצות בעיות ונקודות הדורשות הגדרות נוספות, כגון:
משפטי תנאי ולולאות הם מרכיבים בסיסיים בכל שפת תכנות עילית, ולעתים תכופות נכתבים באופן שמזכיר שפת אנוש. השם הכולל למשפטי התנאי והלולאות הוא "מבני בקרה", ובהמשך נכיר את מבני הבקרה בשפת C. דוגמא: אלגוריתם למציאת ערך מקסימום בקלטכדוגמא להגדרת אלגוריתם ולפירוקו נגדיר את המשימה הבאה:
1) נבצע פירוק של המשימה הכללית ללולאה:
כפי שניתן לראות, המשימה הכללית תורגמה למבנה לולאה הכוללת תנאי לביצוע הלולאה ושתי הוראות לביצוע בגוף הלולאה, ולאחריה הוראת הדפסה של המספר המקסימלי. תנאי הלולאה הוא הצלחה בקריאת מספר לתוך המשתנה x: במצב זה אם המשתמש יקליד תו לא חוקי, או תו מסיים קובץ במקום מספר, הלולאה תסתיים. 2) נמשיך ונפרק את משימות המשנה:
האלגוריתם:
מהתבוננות שנייה באלגוריתם, ניתן לראות שישנה בעיה: max אינו מאותחל. זה עלול לגרום להדפסת תוצאה שגויה, ולכן התכנית אינה תקינה. לאיזה ערך נאתחל את max ? קיימות שתי אפשרויות:
לשם הפשטות נבחר בשיטה השנייה. 3) האלגוריתם בתוספת הוראת האתחול ל- max מובא בעמ' 112. בעיה: כיצד תגיב התכנית במקרה של קלט ריק, כלומר 0 מספרים בקלט? כרגע תגובת התכנית לא מוגדרת, מה שאומר שיודפס ערך לא הגיוני. יש לתקן אותה כך שתודפס הודעה מתאימה במקרה זה. פתרון: נוסיף בדיקה באתחול המשתנה max מהקלט: רק אם פעולת הקלט הצליחה, נבצע את הלולאה ונדפיס לאחריה את ערכו של max. אחרת, נדפיס הודעה למשתמש על קלט ריק. 4) האלגוריתם בצירוף טיפול בקלט ריק מובא בעמ' 112. סוגי מבני בקרה ב- Cמבני הבקרה כוללים את הוראות התנאי (if-else), לולאות ומשפטי בקרה נוספים. הכרנו עד עתה את הוראת if-else, ואת לולאת while. בפרק זה נכיר את שאר מבני הבקרה ב- C. הרשימה הכוללת של מבני הבקרה ב- C:
מבנה בקרה יכול לכלול הוראה אחת או יותר. במידה ויש מספר הוראות יש להקיף אותן ע"י סוגריים מסולסלות { }. משפטי תנאי if-elseמשפטי התנאי מורכבים מההוראות if ו- if-else:
if( תנאי ) הוראה/ות
if( תנאי ) הוראה/ות else הוראה/ות בתוך גוף המשפט יכולה להופיע הוראה בודדת או מספר הוראות, מוקפות ע"י הסוגריים {}.
ניתן לתאר את משפטי התנאי if ו- if-else ע"י תרשים זרימה באופן הבא:
דוגמאות מובאות בעמ' 114-115. לולאותלולאה היא אמצעי לביצוע חוזר של פעולות מסוימות מספר פעמים, או כתלות בתנאי כלשהו. הלולאה מאפשרת חסכון בכתיבת קוד הכולל חזרות - במקום לכתוב קוד זה מספר פעמים כמספר החזרות, הוא נכתב פעם אחת בגוף הלולאה:
כל ביצוע של גוף הלולאה נקרא חזרה (איטרציה). הלולאות ב- C כוללות אפשרויות בקרה מגוונות כגון: הפסקת הלולאה, הפסקת החזרה הנוכחית ומעבר לחזרה הבאה. סוגי הלולאות ב- C:
לולאות while ו- do-while2 סוגי לולאות אלו מבוצעות על פי קיומו של תנאי הלולאה. מבנה תחבירי:
while (תנאי) { הוראות } כל עוד התנאי מתקיים, ההוראות שבגוף הלולאה מתבצעות. תרשים זרימה של לולאת while:
do { הוראות } while (תנאי); ההוראות שבגוף הלולאה מתבצעות כל עוד התנאי מתקיים. תרשים זרימה של הלולאה:
מה ההבדל בין שני סוגי הלולאה? בלולאת while התנאי נבדק לפני ביצוע הלולאה, ולכן אם הוא אינו מתקיים הלולאה לא מבוצעת. בלולאת do-while גוף הלולאה ראשית מתבצע ואח"כ נבדק התנאי, ולכן מובטח לפחות ביצוע של חזרה אחת. תכנית דוגמא: חישוב העצרת של מספר נתון n. העצרת של מספר היא תוצאת מכפלת המספרים 1,2,3..n. לדוגמא, העצרת של 5 היא 1*2*3*4*5 = 120. את משתנה התוצאה נגדיר כ- long double בכדי שיוכל להכיל ערכים גדולים: /* file: azeret1.c */ #include <stdio.h> void main() { long double azeret; int i,n; /* get input */ printf("Enter a positive number:"); scanf("%d",&n); /* initialize variables */ azeret=1.0; i=1; /* loop over numbers 1..n */ while (i<=n) { azeret=azeret*i; i++; } /* output result */ printf("Azeret of %d is %Lg",n,azeret); } דוגמא להרצת התכנית: Enter a positive number:12 Azeret of 12 is 4.79002e+008 בדומה, ניתן לבצע את הלולאה בתכנית כ- do-while: do { azeret=azeret*i; i++; } while (i<=n); מהו ההבדל בין שתי הגרסאות? נניח שבקלט הוכנס המספר 0. העצרת של 0 מוגדרת כ- 1. בלולאת while התנאי ייבדק ומכיוון ש i=1 ו- n=0 תוצאתו תהיה שקר while (i<=n) { azeret=azeret*i; i++; } ולכן אף חזרה לא תתבצע. ערכו של azeret הוא 1 וזו התוצאה המודפסת. לעומת זאת בגרסת do-while החזרה הראשונה מבוצעת do { azeret=azeret*i; i++; } while (i<=n); ולאחריה נבדק התנאי, הנמצא כשקר. עדיין, מכיוון שערכו של i באתחול הוא 1, azeret=1 והתכנית מדפיסה תוצאה נכונה. תרגולקרא/י סעיף זה בספר ובצע/י את תר' 1-2 בעמ' 119.
לולאת forלולאת for היא לולאה כללית נוחה מאוד לביצוע של הוראות מספר פעמים או כתלות בתנאי כלשהו. המבנה שלה מסתמך על הרעיון שכל לולאה מכילה בדרך כלל שלושה חלקים : 1) אתחול 2)בדיקת תנאי הלולאה 3) קידום צעד. תחביר לולאת for : for ( <ביטוי 1> ; <ביטוי 2> ; <ביטוי 3>) { הוראות } בתוך הסוגריים שלאחר המלה for שלושה חלקים, מופרדים ע"י התו ";" :
ניתן לתאר את הוראת for ע"י אלגוריתם טקסטואלי:
כמו כן ניתן לתאר את לולאת for ע"י תרשים זרימה:
נממש את התכנית הנ"ל לחישוב העצרת באמצעות לולאת for: /* file: azeret2.c */ #include <stdio.h> void main() { long double azeret; int i,n; /* get input */ printf("Enter a number:"); scanf("%d",&n); /* compute azeret using for loop */ for(azeret=1.0, i=1; i<=n; i++) azeret=azeret*i; /* output result */ printf("Azeret of %d is %Lg",n,azeret); } קיבלנו תכנית קצרה יותר ומובנית יותר. בלולאת for שבתכנית ביצענו 2 הוראות בביטוי 1 (אתחול הלולאה) ע"י שימוש באופרטור הפסיק "," להפרדה ביניהן: for(azeret=1.0, i=1; i<=n; i++) ניתן כמו כן להשתמש בטכניקה זו גם בביטוי 3, קידום הצעד. מסקנה: הלולאה הנוחה ביותר לכתיבה היא for. לולאת for מכילה בכותרתה את שלושת השלבים הבסיסיים בטיפול בלולאה : אתחול, בדיקת תנאי להמשך הביצוע וקידום/שינוי משתנה. השמטת חלקים בלולאת forבלולאת for אין חובה להגדיר את כל חלקיה: ניתן להשמיט כל אחד משלושת חלקיה או את כולם ביחד. עם זאת, חובה עדיין להפריד בין החלקים ע"י התו ";".
scanf("%d", &num); for(; num< 5; num++) ...
for(i=0; ; i++) /* forever */ { ... }
for(i=0; i< 1000; ) { scanf("%d", &num); i = i + num; printf("current iteration = %d", i); }
for(;;) /* forever */ { ... } מימוש האלגוריתם לחישוב המספר המקסימליכעת, לאחר שהכרנו את מבני הבקרה הבסיסיים ב- C, נממש את האלגוריתם שהגדרנו בתחילת פרק זה למציאת המספר המקסימלי בקלט:
מימוש האלגוריתם ע"י לולאת while מובא בעמ' 122-123. לולאות כפולותניתן לבצע לולאה בתוך לולאה אחרת. דוגמא ללולאה כפולה - הדפסת לוח הכפל של המספרים 1 עד 5 : /* file: luach5x5.c */ #include <stdio.h> void main() { int i, j; for(i=1; i <= 5; i++) { for(j=1; j <= 5; j++) printf("%4d", j*i); putchar('\n'); } } פלט התכנית: 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 5 10 15 20 25 הלולאה החיצונית עוברת על המספרים 1..5 עם האינדקס i. בכל חזרה מבוצעת לולאה פנימית העוברת על המספרים 1..5 עם האינדקס j, ומדפיסה את מכפלת שני האינדקסים.
משפטי continue ו- breakכאשר נמצאים באמצע ביצוע של חזרה בלולאה מסוימת ניתן לסיימה בשני אופנים: 1. הוראת continue - הפסקת החזרה הנוכחית ומעבר לחזרה הבאה בלולאה. דוגמא : for (i=1, azeret=1.0; i<=n; i++) { if (i==3) continue; azeret=azeret*i; } אם n=5 אזי יתבצע: 40 = 5 * 4 * 2 * 1 2. הוראת break - הפסקה מוחלטת של הלולאה ומעבר לביצוע ההוראה העוקבת ללולאה. דוגמא: for (i=1, azeret=1.0; i<=n; i++) { if (i==3) break; azeret=azeret*i; } כעת יתבצע: 2 = 2 * 1 משפט switch-caseההוראה switch משמשת לברירה בין מספר אפשרויות, כלומר להסתעפות רב כוונית. לדוגמא, נתון אלגוריתם לקריאת ערך מספרי בתחום שבין 1..10 ולהדפסתו בצורה טקסטואלית:
מימוש האלגוריתם ע"י משפטי תנאי if-else הוא ארוך ומסורבל: #include <stdio.h> void main() { int x; printf("Enter a number between 4..10:"); scanf("%d",&x); if(x==10 || x==9) printf("High"); else if(x==8 || x==7) printf("Medium"); else if(x==6 || x==5 || x==4) printf("Low"); else printf("Incorrect number!"); } משפט switch-case הוא תחליף טבעי וקריא יותר למימוש הסתעפות רב כוונית. תחביר המשפט: switch( ביטוי ) { case קבוע-שלם : הוראות break; case קבוע-שלם : הוראות break; case קבוע-שלם : הוראות break; default: הוראות } במשפט switch הערך הנבדק מושווה לכל אחד מהערכים שבכניסות ה- case, החל מהראשון. הכניסה הראשונה שנמצאת נכונה גורמת לביצוע סדרת ההוראות שבאותה כניסה. טיפוס הנתון הנבדק בהוראת case חייב להיות ממשפחת השלמים, כלומר שלם או תו. כאשר מזוהה כניסה נכונה בהוראת switch הביצוע נמשך גם לכניסות הבאות עד אשר מזוהה ההוראה break. תכונה זאת נקראת falling-through. נממש את התכנית ע"י משפט switch-case : /* file: switch.c */ #include <stdio.h> void main() { int x; printf("Enter a number between 4..10:"); scanf("%d",&x); switch(x) { case 10 : case 9 : printf("High"); break; case 8 : case 7 : printf("Medium"); break; case 6 : case 5 : case 4 : printf("Low"); break; default: printf("Incorrect number!"); } } סיכום
תרגילי סיכוםבצע/י את תרגילי הסיכום 1-2 שבעמ' 128-129.
|
