תודה רבה, זה בשביל המתכונת מחר..

אשריכם.

http://en.wikipedia.org/wiki/Recursion

http://en.wikipedia.org/wiki/Master_theorem

http://en.wikipedia.org/wiki/Recurrence_relation

את שיטת האב לא צריך לבגרות.

לעקוב אחרי ריקורסיה זה באמת שטויות.

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

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

ניקח לדוגמא את השאלה שהייתה לי במתכונת ל2 יח"ל האחרונות (הייתה לפני שבוע):

מה_עושה(l,p,q,s)

{טענת כניסה: הפעולה מקבלת רשימה l ומקומות ברשימה p,q,s

טענת יציאה: _________________

הנחה l מאותחלת ואינה ריקה. p,q,s מקומות ברשימה l}

1)אם p=q אזי החזר_מרשימה(l,s)

2) אחרת אם p<>q אזי

2.1)אחזר מרשימה (l,p) -> אX (הכוונה לX בלבד, אבל אם אני עושה רק X אז הכל מתבלבל בשורה)

2.2) אחזר מרשימה(l,q)->אY (מאותה סיבה ה-א נמצאת גם פה)

2.3) אם x>=y אזי

2.3.1)s<-p

2.3.2) החזר מה_עושה(s, קודם_ברשימה(L,P,(P,Q) א (פשוט חייבים להוסיף אות בעברית בסוף שורה או מה??)

2.4)אחרת אם X<Y אזי

2.4.1) S<-Q

2.4.2) החזר מה_עושה(Q,S, עוקב_ברשימה(L,(L,P) א (שוב העיניין עם זה שצריך להוסיף אות בעברית...)

א) נתונה הרשימה L: 7,14,9,7,8,9

מה יחזיר האלגוריתם לאחר הזימון:

מה עושה(עוקב_ברשימה(עוגן_רשימה(L,(L), קודם_ברשימה(סוףרשימה(L,(L,P), עוקב_ברשימה(עוגן_רשימה(L,(L,(L)

ב)השלם את טענת הכניסה.

בשאלה הזאת אתה יכול לראות שהתנאי עצירה הוא כשאשר 2 המצביעים מצביעים על אותו תא ברשימה L.

מפה מבינים שהמצביעים P + Q בעצם רצים על אברי הרשימה.

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

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

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

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

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

לכן הפעולה תחזיר את הערך "14".

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

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

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

בהצלחה במתכנות.

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

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

הבגרות שנה שעברה הייתה כ"כ קלה שהבן אדם הכי אידיוט בכיתה שלנו (והוא מאוד אידיוט)

קיבל 87. אני יצאתי אחרי שעה מהבגרות (בגרות של 3 שעות,שיהיה ברור) והמורה בעצמו בא

אליי ושואל אותי "קל,הא?" ואני כמובן מאשר (אגב קיבלתי 98,אני עדיין לא יודע על מה ירד לי)

ומה הקטע של מורים למחשבים ולעשות אלגוריתמים עם השם "מה_עושה" או "סוד" למשל,

זה מעצבן אותי, גם לנו היה אלגוריתם במתכונת שנקרא "מה_עושה" (רק שהוא רץ על עצים, והוא היה הדבר הכי פשוט בעולם)

את הבגרות של שנה שעברה סיימתי אחרי 40 דקות, וקיבלתי 100 עגול ויפה (אבל המגל הוריד לי את הציון ב2 נקודות).

lol... לא שמתי לב לתאריך שהוא כתב את ההודעה...

היה לי מבחן ששם רשמתי בשם של הפונ BLABLA, והמורה הורידה לי על זה נק.

רשמת ששם הפונקציה "blabla" והיא הורידה ניקוד?...

תערער על זה, אין למורה שום סיבה לעשות את זה.

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

עקרונית אתה צודק שאין סיבה להוריד נקודה,

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

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

להוסיף תיעוד לתוכנית וכן לתת שמות בעלי משמעות למשתנים - למשל לא לעשות

מערך בשם x אלא מערך בשם students, בתור דוגמא.

ולכן יש היגיון שיורידו לך על זה נקודה, ובדוגרי, זה סה"כ נקודה אחת, ועכשיו אתה

גם יודע לתת שמות בעלי משמעות (ואגב בבגרות אני חושב שמורידים,ולכן המורה מחוייבת

להוריד נקודה, שכן זה חלק מדרישות משרד החינוך)