פרוייקט "התלמיד והמחשב", בעיות 21-24

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

בעיה מס' 21

בבעיה הראשונה אנחנו צריכים לקבל מספרים שמתארים אורכים של צלעות של משולש, ולומר האם המספרים הללו אכן מסוגלים לתאר משולש חוקי. מה זה אומר? מתי מספרים עשויים לא לתאר משולש חוקי? ובכן, תכונה בסיסית של משולשים היא שסכום אורכי כל שתי צלעות הוא גדול או שווה לאורך הצלע השלישית. זו תופעה כל כך בסיסית עד שבמתמטיקה משתמשים בה בכל מקום, תחת השם “אי שוויון המשולש”. בניסוח כללי, אם \( d(a,b) \) הוא המרחק מ-\( a \) אל \( b \) אז אי-שוויון המשולש אומר ש-\( d(a,b)\le d(a,c)+d(c,b) \) לכל “נקודת ביניים” \( c \). אם תציירו משולש שקודקודיו \( a,b,c \) יהיה ברור מה הקשר.

אז איך בודקים שמשולש הוא חוקי? בספר פשוט מבצעים if עם שלושה תנאים, אבל זה הרי קל מדי. אני רוצה פתרון מתחכם שקצת יציג את היכולות של רובי, ויקטין את הצורך שלי לכתוב קוד שהוא דומה-אבל-קצת-שונה (לכתוב “a+b>c וגם a+c>b וגם b+c>a”). אז הנה אבחנה טריוויאלית: אם \( a,b,c \) הם אורכי הצלעות של ה”משולש”, ואם, נניח, $a>b+c$, אז $a+a>a+b+c$, כלומר $2a>a+b+c$. מה שטוב בביטוי הזה הוא שה-\( a+b+c \) הוא סכום קבוע שלא תלוי באיבר הנוכחי שאנחנו בודקים. אז הנה הקריטריון שלנו: משולש הוא לא חוקי אם קיים \( x \) כך ש-$2x>a+b+c$.

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

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

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

הנה הקוד שלי:

class Array
  def exist?
    each{|x| return true if yield(x)}
    false
  end
  def sum
    inject(:+)
  end
end

sides = ARGV.collect{|x| x.to_i}
print "il" if sides.exist?{|a| 2*a > sides.sum}
puts "legal triangle"

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

ההגדרה של sum היא קסם שכבר הראיתי בפוסט קודם, אבל ההגדרה של exist משתמשת בקסם חדש - המילה yield. הרעיון בה הוא כזה: שימו לב של-exist העברתי בשורה 12 כפרמטר בלוק שמקבל קלט a ומבצע בדיקה כלשהי (כלומר, מחזיר ערך שהוא true או false). מה ש-yield בתוך מתודה עושה הוא לקחת את הבלוק שהועבר כקלט למתודה (אם הועבר; אחרת יש לנו תקלה), ו”להריץ” אותו על הפרמטרים שהועברו ל-yield (כלומר, במקרה שלנו a של הבלוק יאותחל להיות ה-x שאנחנו בודקים). אגב, לפייתוניסטים שבחבורה, שימו לב שבפייתון למילה yield יש שימוש דומה-אבל-שונה - זה בהחלט לא אותו השימוש, אז זהירות!

בעיה מס' 22 כאן הבעיה היא זו: נתונים שני מספרים \( a,b \). מה המספר הקטן ביותר \( c \) כך שאם כופלים אותו ב-\( b \) עוברים את \( a \), כלומר \( a < bc \)?

כאן אני קצת תוהה מה השאלה הזו עושה בחלק השני של הספר - היא קלה ולא מחכימה. אבל מילא. הפתרון הוא של שורה קצרה אחת וזהו:

a, b = ARGV.collect{|x| x.to_i}
puts (a/b) + 1

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

בעיה מס' 23 כאן מקבלים מספר כלשהו ומוצאים מה המספר שצריך להוסיף לו כדי לקבל משהו שמתחלק ב-10. הפתרון המקורי בספר מסובך נורא, כי כנראה חסר לו אופרטור סטנדרטי בשפות תכנות, של מודולו. \( a % b \) הוא שארית החלוקה של \( a \) ב-\( b \) וכמעט מה שאנחנו צריכים פה:

a = ARGV.first.to_i
puts (10 - a) % 10

ההוכחה שזה עובד היא חשבון מודולרי בסיסי ואשאיר אותה לכם. רק שימו לב להתנהגות של % על מספרים שליליים: למשל, \( -3 % 10 = 7 \). הסיבה לכך היא שההגדרה של מודולו היא בעצם קצת יותר מורכבת מזו שנתתי למעלה - המשמעות המדויקת של \( a % b \) היא “המספר \( x \) בין 0 ל-\( b-1 \) כך שההפרש \( a-x \) מתחלק על ידי \( b \)”.

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

a = ARGV.first.to_i
puts 2*(a.to_f/2)**2

מה עשיתי פה? משפט פיתגורס. אם אורך הצלע של הריבוע המקורי היא \( a \) אז ממשפט פיתגורס, ריבוע אורך הצלע של הריבוע החדש - כלומר, השטח שלו - הוא \( 2\left(\frac{a}{2}\right)^2 \). למה? כי ציירו את זה רגע לעצמכם ושימו לב שכל צלע של הריבוע החדש היא היתר במשולש ישר זווית שבו הניצבים הם חצי מצלע הריבוע. אם הייתי טורח לפתוח את הביטוי הייתם רואים ששטח הריבוע הוא בדיוק חצי משטח הריבוע המקורי (וגם תעלול של חפיפת משולשים יראה את זה, למי שרוצים הוכחה גאומטרית).

החל מהפעם הבאה - בעיות יותר מעניינות, מבטיח!