מציאת חציון

זמן קריאה: 4 דקות קוד: find_median_of_three.py

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

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

מציאת החציון

השאלה היא כזו – בהינתן שלושה מספרים, איך מוצאים את החציון מביניהם?
פשוט, נכון? כל כך פשוט שזה כמעט מבלבל. הרי אני יודעת איך למצוא את החציון ב-n איברים, אבל איך למצוא את החציון ב-3 איברים? מה הסיבוכיות של דבר כזה? האם זה בכלל משנה?

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

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

10,2,6 – החציון הוא 6, כי מתקיים 2<=6<=10
1,1,3 – החציון הוא 1, כי מתקיים 1<=1<=3
9,9,9 – החציון הוא 9, כי מתקיים 9<=9<=9

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

אז אני אנסה בכל זאת. איך ידעתי שהחציון של 10,2,6 הוא 6?
סביר להניח שאם הייתי מסתכלת על המוח שלי בהילוך איטי, הייתי רואה שהוא עושה משהו כזה – 
מספר ראשון – 10.
האם 10 הוא החציון? הוא גדול גם מ-2 וגם מ-6, ולכן לא יכול להיות החציון.
מספר שני – 2.
האם 2 הוא החציון? הוא קטן גם מ-6 וגם מ-10, ולכן לא יכול להיות החציון.
מספר שלישי – 6.
האם 6 הוא החציון? הוא גדול מ-2 וקטן מ-10. כן! 6 הוא החציון.

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

אלגוריתם – “מצא את החציון”
בהינתן שלושה מספרים – a,b,c – לכל מספר, בדוק אם הוא החציון. אם כן, החזר אותו. אם לא, עבור למספר הבא.

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

אלגוריתם – “האם חציון”
בהינתן שלושה מספרים – x,y,z בדוק האם x גדול או שווה ל-y וגם קטן או שווה ל-z. או האם x גדול או שווה ל-z וגם קטן או שווה ל-y.
אם כן, x הוא חציון.

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

a=10
b=2
c=6

מצא את החציון
לכל מספר – בדוק האם הוא חציון.
האם a הוא חציון?
האם 2<=10<=6 או 6<=10<=2?
לא.
האם b הוא חציון?
האם 6<=2<=10 או 10<=2<=6?
לא.
האם c הוא חציון?
האם 2<=6<=10 או 10<=6<=2?
כן!
c הוא החציון.

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

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

וזהו, סיימנו, הבעיה פתורה. עכשיו רק צריך לנסח אותה בשפת תכנות.
כיוון שפייסבוק זה לא המקום לדברים כאלה, הקוד לפתרון הבעיה נמצא בגיט שלי. כל מי שמתעניין מוזמן להסתכל כאן -.
https://github.com/mgershovitz/maya_solves/blob/master/find_median_of_three.py

---