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

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

הבעיה היא לקבל כקלט פרמטרים שמגדירים סדרה חשבונית או הנדסית, ולהוציא את סכום הסדרה כפלט. בואו נזכיר מה אלו הסדרות הללו. בשני המקרים מדובר על סדרות של מספרים (ואני מניח בפתרונות שלי שאלו אפילו מספרים שלמים) מאורך סופי כלשהו שמסומן ב-\(n\). את הסדרה עצמה אפשר לסמן, למשל, כך: \(a_0, a_1, a_2, \dots, a_{n-1}\). שימו לב שאני מתחיל את מספור האיברים מ-0 ולכן האינדקס של האיבר האחרון הוא \(n-1\). לסדרה חשבונית יש את התכונה המיוחדת שההפרש בין כל שני איברים סמוכים בה הוא מספר קבוע שמסומן ב-\(d\); לסדרה הנדסית יש את התכונה שהמנה של כל שני איברים סמוכים בה היא מספר קבוע שמסומן ב-\(q\). שלושת הפרמטרים של מספר האיברים בסדרה, האיבר הראשון בה וההפרש/מנה הקבוע מאפיינים באופן מוחלט את הסדרה: מאוד קל לראות שהאיבר מספר \(i\) בסדרה חשבונית הוא \(a_0+id\) והאיבר מספר \(i\) בסדרה הנדסית הוא \(a_0q^{i}\).

עכשיו, מה שמבקשים מאיתנו למצוא הוא את סכום האיברים בסדרה, כלומר את \(a_0+a_1+\dots+a_{n-1}\). בעולם האמיתי יש נוסחאות פשוטות שמחזירות את הסכום הזה: \(n\left(a_0+\frac{d(n-1)}{2}\right)\) עבור סדרה חשבונית ו-\(a_0\frac{q^n-1}{q-1}\) עבור סדרה הנדסית. לא קשה להוכיח שהנוסחאות הללו עובדות אבל לא אעשה את זה כרגע כי זה פוסט על תכנות ולא על טורים; הנקודה היא שאני בכלל לא הולך להשתמש בנוסחאות הללו. אני רוצה לחשב את הסכומים בדרך הקשה - לחשב איבר-איבר, ולקחת את הסכום שלהם.

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

sum = 0
case ARGV[0]
when "A"
  a0, d, n = ARGV[1].to_i, ARGV[2].to_i, ARGV[3].to_i
  for i in (0...n) do
    sum = sum + a0+i*d
  end
when "G"
    a0, q, n = ARGV[1].to_i, ARGV[2].to_i, ARGV[3].to_i
    sum = (0...n).collect{|i| a0*q**i}.inject(0){|temp_sum, x| temp_sum + x}
end

puts "The sum is #{sum}"

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

כשאני אומר שהבדיקה היא האם הערך של המשתנה שווה לערך של מה שמופיע אחרי ה-when אני משקר בצורה גסה וגורם למשפטי case להיות הרבה פחות מגניבים ממה שהם. בפועל רובי לא משתמשת באופרטור ההשוואה הרגיל כדי לבצע את ההשוואה אלא באופרטור מיוחד, שמסומן בתור ===, כדי לבצע את ההשוואה, וזה אומר שאפשר לעשות יותר מאשר להשוות שני ערכים: אפשר אחרי ה-when לכתוב טווח של ערכים או סדרה של ערכים והתנאי יתקיים אם הערך שמכיל המשתנה משתייך אליהם; אפשר לכתוב ביטוי רגולרי והתנאי יתקיים אם המחרוזת שהמשתנה מכיל מתאימה לו; אפשר לכתוב מחלקה והתנאי יתקיים אם המשתנה הוא אובייקט ששייך למחלקה הזו... בקיצור, דברים מגניבים למדי (שייתכן מאוד שנשמעו לכם כרגע כמו ג'יבריש, וזה למה אני לא נכנס אליהם). ברובי משפטי case הם דברים מעולים ואני מאוד מחבב אותם. בשפות כמו C הם קצת יותר מושמצים ונדבר על זה כשנגיע לג'אווהסקריפט.

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

sum = (0...n).collect{|i| a0*q**i}.inject(0){|temp_sum, x| temp_sum + x}

מה שקורה כאן הוא דבר די נפוץ ברובי. אנחנו מתחילים מאובייקט שהוא אוסף של מספרים - במקרה הזה, כל המספרים בין 0 ל-9, שמיוצגים על ידי אובייקט של טווח, ואז מתחילים לעשות על האובייקט הזה סדרה של פעולות. הפעולה הראשונה היא collect שמחליפה כל מספר בטווח באיבר המתאים בסדרה ההנדסית. קיבלנו מערך שכולל את כל האיברים בסדרה ההנדסית, ונותר לסכום אותו. לצורך כך אנחנו מגייסים את המתודה inject שפועלת כך: בנוסף למערך שקורא לה היא מקבלת כקלט גם פרמטר נוסף, שבמקרה הזה הוא 0, שהוא "הערך ההתחלתי", ובלוק. בתוך הבלוק ישנם שני משתנים, שאני קורא להם temp_sum ו-x. הרעיון הוא כזה: ראשית inject מאתחלת את temp_sum להיות הערך שהועבר לה - 0 במקרה שלנו. כעת היא עוברת סדרתית על כל אברי המערך, מציבה כל אחד מהם בתוך x, מריצה את הבלוק ומציבה בתוך temp_sum את תוצאת הבלוק, שהיא במקרה הנוכחי הערך temp_sum+x. כל זה מתורגם לסכימה של איברי המערך ולכן להחזרה של התוצאה הנכונה.

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

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

import System.Environment

arithmetic_series_sum :: Int -> (Int -> (Int -> Int))
arithmetic_series_sum a0 d n = foldl (+) 0 [a0 + d*i | i <- [0..n-1]]

geometric_series_sum :: Int -> (Int -> (Int -> Int))
geometric_series_sum a0 q n = foldl (+) 0 [a0 * q^i | i <- [0..n-1]]

series_sum :: [String] -> Int
series_sum ("A":a0:d:n:[]) = arithmetic_series_sum (read a0) (read d) (read n)
series_sum ("G":a0:q:n:[]) = geometric_series_sum (read a0) (read q) (read n)

main = do
  args <- getArgs
  putStrLn (show(series_sum args))

כל החלק עם ה-series_sum לקראת הסוף בא במקום ה-case של רובי. שימו לב לשימוש שלי בתבניות של הקלט ש-series_sum מצפה לקבל, ואיך הוא מאפשר לי לתת שמות שונים למשתנים (d אל מול q). אבל זה משהו שכבר ראינו בפוסטים קודמים - החידוש מגיע במימושים של פונקציות הסכום. בשתיהן אני משתמש ב-list comprehension כדי ליצור את רשימת כל איברי הסדרה; וכדי לחשב את הסכום אני מפעיל פונקציה שנקראת foldl ומקבלת שלושה פרמטרים: הראשון הוא האופרטור +, השני הוא הערך 0 והשלישי הוא המערך. כפי שניתן לנחש, foldl עוברת סדרתית על אברי המערך ומפעילה את האופרטור + בכל פעם על ערך זמני שיש לה (שאותחל להיות 0 על פי הפרמטר שהעברתי) והאיבר הבא בתור מהמערך. הנה איך אפשר לממש את הפונקציה הזו:

foldl f z []     = z
foldl f z (x:xs) = let z' = z `f` x
                   in foldl f z' xs