הוכח או הפרך

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

אני אמחיש את הרעיון דרך דוגמא – נניח שנרצה לכתוב שיטה שחתימתה –

public boolean allEven(int[] a)

השיטה תקבל כפרמטר מערך מלא במספרים שלמים חיוביים. השיטה תחזיר true אם כל איברי המערך הם זוגיים, ו-false אחרת.

למשל, עבור המערך הזה – a = {2, 24, 6, 4, 12} השיטה תחזיר true, אבל אם נחליף את האיבר 24 באיבר 23 השיטה תחזיר false.

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

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

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

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

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

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

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

Capture10-1

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

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

אבל רגע, יש פה גם else! ואנחנו יודעים שה-else תמיד, אבל תמיד, מתפקד כמקרה ההפוך של ה-if שמעליו. דהיינו, אם ה-if לא התקיים, ה-else בוודאות יתקיים. אז מה יקרה אם האיבר במקום ה-i הוא זוגי? התנאי לא יתקיים, אז ה-else כן יתקיים, ויחזיר true, כלומר ידווח שכל המספרים זוגיים. אולי כולם זוגיים, אבל צריך להוכיח את זה, כלומר צריך לעבור על כולם.

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

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

Capture10-2

 

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

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

הנה דוגמא לכמה בעיות מהסגנון –

  • בהנתן מערך, האם כל האיברים חיוביים?
  • בהנתן מערך, האם האיברים ממויינים בסדר עולה ממש?
  • בהנתן מערך של שמות בני אדם, האם השם david cohen מופיע במערך?
  • בהנתן מחרוזת, האם היא מורכבת אך ורק מאותיות קטנות?
  • בהנתן אוסף נקודות במישור, האם כל הנקודות נמצאות ברביע הראשון?
  • וכו’.

והנה חידה קטנה לסוף – איך הייתם כותבים שיטה בשם notAllEven, שתחזיר true אם לא כל האיברים זוגיים? כלומר, דווקא אם כל האיברים זוגיים היא תחזיר false. נסו לחשוב מה דרוש כדי להוכיח ומה דרוש כדי להפריך, ואיפה נמצא הקושי.