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

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

סוגיות ב"עיצוב תוכנה" – ניתוח שאלת בגרות

מיכאל שחם
ישיבה תיכונית גבעת שמואל

mik_s@netvision.net.il

 
תקציר

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

 

השאלה:

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

לדוגמא: יש 80 משפחות שיש להן 3 ילדים, ומביניהן:

22 משפחות, שסדר לידת הילדים בהן הוא: בן, בן, בת

13 משפחות, שסדר לידת הילדים בהן הוא: בן, בת, בן

10 משפחות, שסדר לידת הילדים בהן הוא: בת, בת, בת

35 משפחות, שסדר לידת הילדים בהן הוא: בן, בת, בת

לאחר לידת כל ילד מעדכנים את מרשם התושבים בעיר.

 

א.      הצע ייצוג מתאים M למרשם התושבים בעיר "שמחה". לפניך שתי פעולות:

הפעולה מקבלת את מרשם התושבים M ואת מין היילוד G כאשר היילוד הוא ילד ראשון, ומעדכנת את M

הוסף_בכור (M,  G)

הפעולה מקבלת את מרשם התושבים M, את מין היילוד G ואת רצף הילדים שנולדו לפניו S, ומעדכנת את M

עדכן_מרשם (M, G, S)

 

ב.      (1) הגדר ותאר פעולות ממשק למימוש הפעולה עדכן_מרשם (M, G, S). הפעולות יהיו מוגדרות על מבנה הנתונים שהצעת בסעיף א'.

(2)  ממש בסביבת העבודה את הפעולה עדכן_מרשם (M, G, S), תוך שימוש בפעולות הממשק שהגדרת בסעיף ב (1). אין צורך לממש את הפעולות שהגדרת בסעיף ב (1).

ג.       מהי סיבוכיות זמן הריצה של הפעולה עדכן_מרשם (M, G, S) ? נמק.

 

בחירה נכונה של ייצוג המידע

 

בשאלה שלפנינו מופיע הניסוח: "מספר המשפחות שיש להן 1, 2, 3, K  ילדים".

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

הבנה א':  לא קיימת הגבלה על גודל המשפחה.

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

הבנה ב':  ניתן להתייחס אל K כאל גודל קבוע (גם אם איננו ידוע) על סמך השיקולים הבאים:

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

2.    בניגוד לשימוש ה"מסורתי" במשתנה N לציון ערך "גמיש", השימוש ב- "K" מסמל ערך קבוע.  בנוסף, לא צוין בשאלה כי הגודל  "משתנה" או "לא ידוע".

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

 

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

בגרות תשס"א שאלה 4: "...קיימים n צבעים שונים של חרוזים..."

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

בגרות תש"ס שאלה 15: "...בנמל התעופה... יש K מסלולים".

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

 

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

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

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

 

השלכה נוספת שיש לשתי ההבנות הנ"ל הינה לגבי חישוב הסיבוכיות.

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

 

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

 

 

אתחוּל מבנה הנתונים הנבחר

 

סוגיה נוספת בהקשר זה היא אופן האִתחוּל הרצוי של מבנה הנתונים שנבחר.

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

ביחידת הלימוד מושם דגש על מושג ה"אתחול", הכולל בתוכו למעשה שתי פעולות:

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

(פעולה המקבילה להצהרת VAR בפסקל).

ב. השמת ערך התחלתי במשתנה הנ"ל.

לסעיף ב' עשויה להיות השלכה על אופן העבודה העתידי עם הטיפוס.

 

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

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

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

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

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

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

היות ובשלב ההתחלתי אין בעיר ולו משפחה אחת מכל רצף שהוא, יקבלו כל הרצפים את הערך "אפס" עבור מספר המשפחות הקיימות בעיר שהן בעלות אותו הרצף[1].

 

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

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

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

 

הגדרת ממשק לפעולות עזר

 

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

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

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

במסגרת זו נדגיש שתי נקודות:

 

א. היקף הפעולה עד איזו רמת פירוט יש לרדת?

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

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

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

 

ב. הגדרת הפעולות

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

למשל, בדוגמה שלפנינו: נניח כי "רצפי הילדים" מיוצגים ברשימה, וכי ברצוננו לאתר רצף מסוים ברשימה.

נוכל להגדיר פעולה בשם "אַתֵּר ברשימה" , שתתפקד כפעולה אוניברסלית של חיפוש איבר ברשימה.

לחילופין, ניתן לייחד פעולה ספציפית לשאלה זו בשם "אַתֵּר רצף", מבלי להתייחס כלל לעובדה שהאיתור נעשה ע"י חיפוש של איבר ברשימה.

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

 

לסיכום

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

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

 

הפתרונות המוצעים לשאלה:

 

פתרון א' - פתרון זה מבוסס על ההכרעות הבאות בסוגיות שהוזכרו לעיל:

מספר ילדים מקסימלי במשפחה ייחשב כקבוע,

ולכן המרשם מיוצג במבנה קשיח בגודלו (=מערך).

ייצוג

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

אתחול

יוגדרו על "סיפור המעשה" ולא כפעולות כלליות.

פעולות עזר

 

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

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

רמה ב: לכל מספר ילדים, כל הרצפים האפשריים של סדר הלידה.

רמה ג: לכל רצף  שמירת הרצף ומספר המשפחות בעלות אותו רצף.

 

תיאור מילולי של הייצוג:

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

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

עבור כל מספר נתון של ילדים למשפחה (בין 1 ל- k), נשמור את כל הרצפים האפשריים, למשל:

עבור משפחות עם ילד אחד נשמור 2 צירופים: בן, בת.

עבור משפחות עם 2 ילדים נשמור 4 צירופים: בן-בן, בן-בת, בת-בן, בת-בת.

עבור משפחות עם 3 ילדים נשמור 8 צירופים: בן-בן-בן, בן-בן-בת, בן-בת-בן, בן-בת-בת, בת-בן-בן, בת-בן-בת, בת-בת-בן, בת-בת-בת.

(באופן כללי - מספר הצירופים האפשריים של משפחות עם i ילדים הוא i 2).

 

עבור כל רצף יש לשמור את מספר המשפחות שיש בעיר מאותו רצף. לכן כל תא במערך יכיל רשימה של רצפים ובה רשוּמוֹת: בכל רשומה יש שדה מחרוזתי שמייצג את הרצף, ושדה מספרי שמייצג את מספר המשפחות בעלות אותו הרצף. מחרוזת הרצף תורכב מאותיות 'b' עבור בן ו- 'g' עבור בת.

כאמור לעיל, המרשם יאותחל עם כל הרצפים האפשריים לכל מספר ילדים.

 

ייצוג בפסקל:

List_info_type  = RECORD

      Rezef : string;

      num   : integer;

end;

 

Mirsham = array [1.. k ] of  List_type;

 

תיאור גרפי של הייצוג:

פעולות ממשק:

הפעולה יוצרת מרשם כדי לשמור מידע על משפחות שלהן עד k ילדים.

עבור כל מספר ילדים בין 1 ל- k יוכנו כל הרצפים האפשריים עם ערך '0' למספר המשפחות מאותו רצף.

אתחל_מרשם

מציאת מיקומו של הרצףS  ברשימת הרצפים L.

הנחות: L מאותחלת, הרצף S קיים ברשימה.

אַתֵר רצף (L,S)

הפעולה מגדילה באחד את מספר המשפחות עם רצף ילדים הנמצא במיקום P ברשימת הרצפים L.  הנחות: L מאותחלת, P חוקי.

הוסף משפחה לרצף (L,P)

הפעולה מקטינה באחד את מספר המשפחות עם רצף ילדים הנמצא במיקום P ברשימת הרצפים L.  הנחות: L מאותחלת, P חוקי.

הפחתת משפחה מרצף  (L,P)

הפעולה מחזירה את מס' התוים במחרוזת S

אורך מחרוזת (S)

 

מימוש:

עדכן מרשם (S,G,M)

{ אם הרצף הקודם הוא מחרוזת ריקה אזי הילד החדש G הוא בכור, וקוראים לפעולת עזר הנתונה בשאלה}

1. אם   S =  ’ ‘  אזי  "הוסף בכור" (S,G).

{ הילד החדש איננו בכור:}

אחרת:

 

1.1  אורך מחרוזת (S) ß Length

{ מציאת מיקומו של הרצף הנוכחי }

1.2  "אַתֵּר רצף" (M[Length] ,S) ß P

{ הפחתה באחד של מספר המשפחות בעלות הרצף הנוכחי [שלפני הולדת הילד] }

1.3  "הפחת משפחה מרצף" (M[Length],P).

{ יצירת הרצף החדש ע"י הוספת הילד החדש לרצף הילדים הקודמים במשפחה [=הוספת תו למחרוזת] }

1.4  S+G   ß NEW_S

{ הוספת הילד החדש מגדילה באחד את אורך הרצף}

1.5  Length + 1 ß Length

{ מציאת מיקומו של הרצף החדש  }

1.6  "אַתֵּר רצף" (M[Length] , NEW_S) ß P

{הגדלה באחד של מספר המשפחות בעלות הרצף החדש}

1.7  "הוסף משפחה לרצף" (M[Length],P).

 

יעילות:

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

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

גודל רשימת הרצפים באורך מסוים שווה ל- 2 בחזקת אורך הרצף, כי הרצף מורכב מ- 2 תוים: b,g.

למשל:     לרצף באורך 1 מספר הצירופים האפשרי הוא 2 בחזקת 1 (בן או בת) = 2.

לרצף באורך 2 מספר הצירופים האפשרי הוא 2 בחזקת 2 = 4.

לרצף באורך 4 מספר הצירופים האפשרי הוא 2 בחזקת 4 = 16.

לכן, מספר סיבובי הלולאה הוא לכל היותר 2 בחזקת  (Length (S.

באיתור הרצף החדש מספר סיבובי הלולאה הוא לכל היותר 2 בחזקת { 1Length (S) +  } 

 (כאשר S הוא הרצף הישן, לפני הוספת הילד החדש).

לכן היעילות היא מעריכית:      O ( 2 Length (S)+1 )

 

אולם, אם מניחים שמספר הילדים המקסימלי למשפחה הוא מספר ידוע ( k ),   אזי גם אורך הרצף המקסימלי הוא קבוע (k ), וגם מספר הצירופים האפשריים באורך k הוא קבוע ושווה ל: 2 k

לכן היעילות תהיה קבועה  -  (1) O.

 

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

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

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

ייצוג

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

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

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

אתחול

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

פעולות עזר

 

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

 

ייצוג בפסקל:

Mirsham = Tree_type ;

Tree_info_type  =  integer;

 

תיאור גרפי של הייצוג:

 

פעולות ממשק:

 

הפעולה יוצרת עץ בינארי ובו שורש בלבד.

אתחל_מרשם

הפעולה מחזירה את מס' התוים במחרוזת S.

אורך מחרוזת (S)

הפעולה מוסיפה לתוכן של שרש העץ T את הערך X. הנחה: T מאותחל.

הוסף-ערך-לצומת (T,x)

הפעולה מוסיפה צומת חדש עם הערך X, כבן ימני של שרש העץ T.

הנחה: T מאותחל, ל-T אין בן ימני.

הוסף בן ימני (T,x)

הפעולה מוסיפה צומת חדש עם הערך X, כבן שמאלי של שרש העץ T.

הנחה: T מאותחל, ל-T אין בן שמאלי.

הוסף בן שמאלי (T,x)

 

עדכן מרשם (S,G,M)

 

1.  אורך מחרוזת (S) ß Length

{ ירידה בעץ לאורך הרצף הנוכחי }

2.  עבור I מ- 1 עד Length בצע:

 

2.1  אםS[I] = ‘b’   אזי : תת עץ ימני (M) ß M

 

אחרת תת עץ שמאלי (M) ß M

{הפחתה באחד של מס' המשפחות

  בעלות הרצף הנוכחי [שלפני הולדת הילד] }

3. הוסף-ערך-לצומת (M,-1).

{אם הילד החדש הוא בן :}

4. אם G = 'b'   אזי:

{אם כבר קיים הרצף החדש במרשם}

4.1 אם לא עץ ריק (תת עץ ימני (M))  אזי:

{הגדלה באחד של מספר המשפחות בעלות הרצף החדש }

הוסף-ערך-לצומת (1, תת עץ ימני (M))

{אם עדיין לא קיים הרצף החדש, יש ליצור אותו בצומת חדש בעץ עם הערך '1' למס' המשפחות}

אחרת: הוסף בן ימני (M,1)

{הילד החדש הוא בת :}

אחרת  { G = 'g'  }

{אם כבר קיים הרצף החדש במרשם}

4.2 אם לא עץ ריק (תת עץ שמאלי (M))  אזי:

{הגדלה באחד של מספר המשפחות בעלות הרצף החדש }

הוסף-ערך-לצומת (1, תת עץ שמאלי (M))

{אם עדיין לא קיים הרצף החדש, יש ליצור אותו בצומת חדש בעץ עם הערך '1' למס' המשפחות}

אחרת: הוסף בן שמאלי (M,1)

 

יעילות:

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

בפקודה 2 יש לולאה, שבמהלכה מטיילים בעץ במסלול שאורכו כאורך הרצף S.

ולכן היעילות היא לינארית: O (Length (S) )

אולם, אם מניחים שמספר הילדים המקסימלי למשפחה הוא מספר ידוע (k), אזי גם אורך הרצף המקסימלי הוא קבוע (k), והיעילות תהיה קבועה  -  (1) O.

 

אתר המרכז הארצי

אתר הבטים

גליון יוני 2002

חזרה לתחילת העמוד

 



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