הפוסט הקודם בסדרה – רקורסיה – חלק א' – הבנת אלגוריתמים רקורסיביים
אחרי שהצלחנו להבין אלגוריתם רקורסיבי שנתון לנו, הקפיצה המחשבתית הגדולה באמת היא לכתוב אלגוריתם כזה בעצמנו. כפי שאמרתי בפוסט הפותח של הסדרה, אני רוצה להציג מספר הסברים ושיטות לפיתוח אלגוריתם רקרוסיבי. לשם כך אני אשתמש בתרגיל יחיד, וכל פעם אפתור אותו בשיטה אחרת.
להמשיך לקרוא "רקורסיה – חלק ב' – כתיבת אלגוריתם רקורסיבי מהסוף להתחלה"
הפוסט הקודם בסדרה – רקורסיה – הקדמה
אז נתחיל מההגדרה הפשוטה ביותר – רקורסיה היא פונקציה שקוראת לעצמה.
אחת הדוגמאות המפורסמות ביותר לרקורסיה היא סדרת פיבונאצ'י. למקרה שאתן לא מכירות – סדרת פיבונאצ'י היא סדרה של מספרים, בה כל מספר הוא הסכום של שני קודמיו בסדרה.
זה לא סוד שאני אוהבת רקורסיות. כתבתי על זה בבלוג, וזו דעה שאני לא מתביישת להביע בפומבי, רקורסיות הן אחת התופעות היפות והאלגנטיות ביותר במדעי המחשב, לטעמי.
לצערי הרב, לרקורסיות יש מוניטין קצת רע, הן נחשבות מאוד מסובכות להבנה ולא כל כך שימושיות – מה שגורם לכך שהמון מתכנתות מתייאשות מהר מהניסיון להבין אותן ומדלגות הלאה.
להמשיך לקרוא "רקורסיה – הקדמה"
אז אתמול היה יום מאוד מיוחד, זה היה יום עם תאריך פלינדרומי – 02.02.2020 (ותודה ללא מדויק שבזכותו שמתי לב.
ואיזו דרך טובה* יותר יש לחגוג יום פלינדרומי מאשר עם אלגוריתם שבודק אם מילה היא פלינדרום?
*אלא אם כן אתן אייבופוביות כמובן. אם כן, אני מתנצלת מראש, ואולי כדאי שתצאו מהפוסט עכשיו 🤷♀️
היי לכולן!
קודם כל, אני רוצה לפתוח ולומר שלקח לי בערך שבוע להתאושש מכמויות הפידבקים החיוביים שקיבלתי על פוסט חיפוש העבודה שלי. קיבלתי המון הודעות ממחפשות עבודה (ומחפשי עבודה) שיכלו להזדהות עם החוויה שלי, ואמרו שהצלחתי לתת להן כלים ומוטיבציה, וכל תגובה כזו שימחה אותי יותר מכפי שאני יכולה לתאר, אז תודה לכל מי שהגיבה, קראה ושיתפה.
אז, בשבוע הבא אני הולכת להעביר הרצאה באירוע Hello World של Mind The Gap – IL, וזו נראתה לי כמו הזדמנות מצוינת לכתוב פוסט שלום עולם חדש!
להמשיך לקרוא "שלום עולם 2"אם שוטטתן בפייסבוק לאחרונה כנראה נתקלתן בהתייחסויות לתרגיל (2+2)2÷8 (ואם לא, כדאי לקרוא את ההסבר של לא מדויק).
בקצרה, מדובר בתרגיל חשבוני שיש לו שני פתרונות אפשריים שנובעים מקונבנציות שונות של כתיבת מתמטית. אפשר להתייחס אליו כך –
8÷2*(2+2) = 8÷2*4 = 4*4 = 16
ואפשר להתייחס אליו כך –
8÷2*(2+2) = 8/(2*(2+2)) = 8/(2*4) = 8/8 = 1
אז לפני שמתחילה מלחמת עולם בסגנון ה-little endians מול ה-big endians, חשבתי לנסות ליצור אלגוריתם שיוכל לשרת את שני המחנות.
הרי, אף אחד לא מתווכח על החישוב עצמו, אלא רק על קונבנציית הכתיבה – אז אני הולכת לבנות מחשבון קסום שאפשר יהיה לקנפג, ויספק לכל משתמשת את התשובה שהיא מחפשת.
בחלק א' של פוסט זה הסברתי שאני רוצה לבנות מחשבון שיוכל לקבל קונפיגורציה של קונבנציית כתיבה, ולפתור תרגילים בהתאם.
הרעיון הגיע מהתרגיל (2+2)2÷8 שהוא ביטוי שיש לו שתי תוצאות שונות בעבור שתי קונבנציות כתיבה שונות.
בחלק הראשון של הפוסט בניתי את המחשבון שלי, ובחלק הנוכחי אני רוצה להוסיף לו קונפיגורציות.
נתון עץ בינארי ושני צמתים בעץ.
המשימה היא למצוא את האב הקדמון המשותף הראשון לשני הצמתים.
איך אני עושה את זה?
אני אתחיל כרגיל מדוגמאות.
בהינתן מסך (המיוצג על ידי מטריצה של פיקסלים צבעוניים) המשימה היא לכתוב פונקציית "מילוי שטחים" שמקבלת נקודה וצבע חדש, וצובעת את כל האזור מסביב לנקודה בצבע החדש.
אוקי, אני אתחיל מדוגמא.
הדוגמא שלי תהיה מטריצה בגודל 3X3 בשני צבעים – 1 ייצג צבע שחור ו-0 ייצג צבע לבן.
A = 1 1 1 1 0 0 1 0 0
להמשיך לקרוא "מילוי שטחים"נתון מערך של מספרים שלמים וחיוביים.
כל מספר במערך מתאר את גודל הקפיצה המקסימלי שאפשר לבצע באותה הנקודה.
המשימה היא לכתוב אלגוריתם שמתחיל באיבר הראשון במערך, ובודק האם אפשר להגיע ממנו לאיבר האחרון במערך.
