תפריט משתמש
קורס:"מבוא לתכנות"
מתוך הספר: C - מדריך מקצועי 
אלגוריתם - מה זה?אלגוריתם הוא סדרה של הוראות מדויקות לביצוע משימה נתונה. הוראות האלגוריתם חייבות להיות מובנות וחד-משמעיות למי שאמור לבצע אותו. לדוגמא, נניח שבבעלותנו פיצרייה, וקיבלנו הזמנה טלפונית למשלוח פיצה ללקוח בכתובת מסוימת. ההוראות לשליח עם קטנוע יהיו:
מכיוון שהשליח מבין כל אחת מההוראות והן חד-משמעיות הוא יבצען ללא קושי. לעומתו, מורה לנהיגה על קטנוע לא ייתן לתלמיד בשיעורו הראשון את ההוראה "סע לכתובת זו" מכיוון שהתלמיד לא יודע כיצד לבצע זאת. הוא ייתן לו סדרת הוראות לביצוע תת-משימה זו:
באופן דומה, בהגדרת אלגוריתם ליצירת תכנית מחשב יש לקחת בחשבון אילו הוראות בסיסיות קיימות בשפת התכנות המיועדת. אלגוריתמים כתכנון תכנית מחשבאלגוריתמים משמשים להגדרה מקדימה, לפני כתיבת תכנית המחשב, למשימה הנדרשת לביצוע. את הוראות האלגוריתם ניתן לרשום באופן טקסטואלי, בדומה להכנת מתכון לבישול, ע"י תרשים זרימה, או בכל צורה אחרת. לדוגמא, נתונה המשימה הבאה:
ננסה להגדיר את האלגוריתם לביצוע המשימה:
האם האלגוריתם מוביל לביצוע המשימה? ראשית, נבדוק אם הוראותיו מובנות בשפת התכנות המיועדת:
ונגדיר את ההוראה במפורט:
נכתוב שוב את האלגוריתם במלואו:
תרשים האלגוריתם:
האם הוראות האלגוריתם הן חד-משמעיות? התשובה לכך שוב תלויה בשפת התכנות: בהגדרת המשתנים לא צוין סוג המספר - ממשי או שלם - ולכן היא איננה חד-משמעית בשפת תכנות המפרידה בין טיפוס מספרים שלם לבין ממשי. נכתוב שוב את האלגוריתם, תוך ציון הטיפוס המספרי של המשתנים: משתני הקלט יהיו ממשפחת השלמים. משתנה התוצאה, avg, צריך להיות ממשי מכיוון שהוא מכיל ממוצע, וזה בדרך כלל אינו ערך שלם.
כעת האלגוריתם מוגדר היטב עבור שפות תכנות עיליות. דוגמא שנייה: מציאת המקסימום מבין 3 מספריםנדרש לחשב את המקסימום מבין 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 פירוק האלגוריתם למשימות משנהתהליך הגדרת האלגוריתם מתחיל בהגדרת המשימה הכללית לביצוע כמשפט בשפת אנוש המתאר את המטרה הכללית של התכנית. משפט זה בדרך כלל מופשט וכללי מדי להבנה ע"י המחשב. בהגדרת הוראות האלגוריתם, יש לקחת בחשבון אילו הוראות בסיסיות ניתנות לביצוע ע"י המחשב, ולאילו נדרשת הגדרה מפורטת יותר. כל הוראה מורכבת שאינה "מובנת" דיה ע"י המחשב ניתנת לפירוק באחד משלושה אופנים:
תהליך הפירוק ממשיך באופן רקורסיבי עד להגעה להוראות ברמת שפת התכנות שאיתה מממשים את האלגוריתם. כמו כן, במהלך הפירוק צצות בעיות ונקודות הדורשות הגדרות נוספות, כגון:
משפטי תנאי ולולאות הם מרכיבים בסיסיים בכל שפת תכנות עילית, ולעתים תכופות נכתבים באופן שמזכיר שפת אנוש.
דוגמא שלישית: אלגוריתם למציאת ערך מקסימום בקלטכדוגמא נוספת להגדרת אלגוריתם ולפירוקו נגדיר את המשימה הבאה:
1) נבצע פירוק של המשימה הכללית ללולאה:
כפי שניתן לראות, המשימה הכללית תורגמה למבנה לולאה הכוללת תנאי לביצוע הלולאה ושתי הוראות לביצוע בגוף הלולאה, ולאחריה הוראת הדפסה של המספר המקסימלי. תנאי הלולאה הוא הצלחה בקריאת מספר לתוך המשתנה x: במצב זה אם המשתמש יקליד תו לא חוקי, או תו מסיים קובץ במקום מספר, הלולאה תסתיים. 2) נמשיך ונפרק את משימות המשנה:
האלגוריתם:
מהתבוננות שנייה באלגוריתם, ניתן לראות שישנה בעיה: max אינו מאותחל. זה עלול לגרום להדפסת תוצאה שגויה, ולכן התכנית אינה תקינה. לאיזה ערך נאתחל את max ? קיימות שתי אפשרויות:
לשם הפשטות נבחר בשיטה השנייה. 3) האלגוריתם בתוספת הוראת האתחול ל- max מובא בעמ' 112. בעיה: כיצד תגיב התכנית במקרה של קלט ריק, כלומר 0 מספרים בקלט? כרגע תגובת התכנית לא מוגדרת, מה שאומר שיודפס ערך לא הגיוני. יש לתקן אותה כך שתודפס הודעה מתאימה במקרה זה. פתרון: נוסיף בדיקה באתחול המשתנה max מהקלט: רק אם פעולת הקלט הצליחה, נבצע את הלולאה ונדפיס לאחריה את ערכו של max. אחרת, נדפיס הודעה למשתמש על קלט ריק. 4) האלגוריתם בצירוף טיפול בקלט ריק מובא בעמ' 112.
|
