Integer to Roman

Q: מהי סיבוכיות הזמן של המרת מספר שלם למספר רומי?

O(1) . הקלט הוא לכל היותר 3999, לכן הלולאה החמדנית בודקת 13 שורות בטבלה ומוסיפה לכל היותר 15 סמלים. אם היה מותר להשתמש במספרים גדולים יותר ולכתוב אותם באמצעות M חוזר, זמן הריצה היה גדל בהתאם ל־ num / 1000 .

Q: למה 3999 הוא המספר הגדול ביותר שמותר?

M היא האות הגדולה ביותר, ואסור שאות תופיע ארבע פעמים ברצף, לכן MMM הוא הגבול של האלפים, ו־3999 הוא MMMCMXCIX . מספרים גדולים יותר נכתבו באמצעות סימנים נוספים, כמו קו מעל אות כדי להכפיל אותה ב־1000.

בינונימתמטיקה וסימולציה אלגוריתם חמדן

+10

לספרות רומיות יש שבע אותיות: M 1000, D 500, C 100, L 50, X 10, V 5 ו־I 1. האותיות מופיעות מהגדולה לקטנה ומצטברות, ולכן 7 הוא VII. אף אות לא חוזרת ארבע פעמים ברצף: 4, 9, 40, 90, 400 ו־900 נכתבים IV, IX, XL, XC, CD ו־CM — אות קטנה שמחסרים מהאות הגדולה שאחריה. רק בששת הזוגות האלה מופיעה אות קטנה לפני אות גדולה.

בהינתן מספר שלם num, החזר את הספרה הרומית שלו.

פונקציה

intToRoman(num: integer) → string

numinteger: מספר שלם מ־1 עד 3999
מחזירהstring: הספרה הרומית של num באותיות גדולות

אילוצים

1 ≤ num ≤ 3999

דוגמאות

קלט: num = 49
פלט: "XLIX"
הסבר: 49 הוא 40 + 9, לכן הספרה היא XL ואז IX: XLIX. IL אינו מותר, כי I מחסרת רק ב־IV וב־IX.

קלט: num = 2026
פלט: "MMXXVI"
הסבר: ב־2026 אין את הספרות 4 או 9, לכן אין צורך בזוג והאותיות מסתכמות כך: 1000 + 1000 + 10 + 10 + 5 + 1 הם MMXXVI.

קלט: num = 944
פלט: "CMXLIV"
הסבר: 944 הוא 900 + 40 + 4, וכל חלק הוא זוג חיסורי: CM, XL ו־IV מתחברים ל־CMXLIV.

שאלת המשך

בהינתן מחרוזת, האם תוכל לבדוק אם היא ספרה רומית בצורה התקנית הזאת, כך ש־XLIX מתקבלת ואילו IIII, IL ו־VX נדחות?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

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

כתוב זאת בצורה מצטברת, ואז קצר את הצורות הארוכות

האינטואיציה

התעלם בהתחלה מהזוגות: כתוב כמה שיותר M שאפשר, אחר כך D, וכן הלאה עד I. עבור 944 מתקבלת הצורה DCCCCXXXXIIII. הצורה החיבורית הזאת שונה מהצורה התקנית רק כשספרה היא 4 או 9, והמקומות האלה הם תמיד אחת משש מחרוזות שיש להן צורה קצרה: DCCCC היא CM, CCCC היא CD, LXXXX היא XC, XXXX היא XL, VIIII היא IX ו-IIII היא IV.

החלף את DCCCC לפני CCCC, אחרת 900 יהפוך ל-DCD; אותו הדבר נכון גם בעשרות ובאחדות. לצורה החיבורית יש לכל היותר 18 אותיות (3999), לכן העבודה היא O(1), במחיר של מעבר שני וכמה מחרוזות זמניות.

אלגוריתם

עבור כל אחת משבע האותיות, מ־M ועד I, הוסף אותה כאשר num גדול או שווה לערכה, וחסר את הערך בכל פעם.
החלף את DCCCC ב־CM, ואז את CCCC ב־CD.
החלף את LXXXX ב־XC, ואז את XXXX ב־XL.
החלף את VIIII ב־IX, ואז את IIII ב־IV.
החזר את המחרוזת.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

חמדני על פני 13 הערכים

האינטואיציה

מיינו את שבע האותיות ואת ששת הזוגות לפי ערך: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. בחירה בערך הגדול ביותר שמתאים היא תמיד הדרך הנכונה. כל ערך במקום עשרוני נמוך יותר קטן מהערך הקטן ביותר במקום שמעליו, ולכן הלולאה מסתיימת במקום אחד לפני שהיא מגיעה למקום הבא. בתוך מקום, הערכים 9, 5, 4 ו־1 מייצגים כל ספרה בדרך המקובלת: 9 הוא הסמל של 9, הערכים 5 עד 8 הם הסמל של 5 בתוספת עד שלושה סמלים של 1, 4 הוא הסמל של 4, והערכים 1 עד 3 הם סמלים של 1.

עבור 3746 הלולאה כותבת MMM, D, CC, XL, V, I: MMMDCCXLVI. בטבלה יש 13 שורות, והתשובה כוללת לכל היותר 15 אותיות, לכן זמן העבודה הוא O(1), במעבר אחד.

אלגוריתם

רשמו את 13 הערכים עם הסמלים שלהם, מ־1000 ועד 1, כולל הזוגות.
התחילו במחרוזת ריקה.
עבור כל שורה, כל עוד num גדול או שווה לערך, הוסיפו את הסמל והחסירו את הערך.
החזירו את המחרוזת לאחר שכל השורות הושלמו.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

מלכודות ומקרי קצה

הצבת D לפני CM בטבלה. כך מתקבל DCD עבור 900.
שימוש ב-if במקום ב-while עבור כל שורה. עבור 3000 צריך M שלוש פעמים; עם if מתקבל MCMDCDCXCX.
המצאת זוגות אחרים. 99 הוא XCIX, לא IC, ו-45 הוא XLV, לא VL.
ב-C, שימוש במאגר קטן מדי. התשובה הארוכה ביותר, עבור 3888, מכילה 15 אותיות, ולכן נדרשים 16 בתים עם אפס סיום; הצורה החיבורית דורשת 19.

שאלות נפוצות3

מהי סיבוכיות הזמן של המרת מספר שלם למספר רומי?

O(1). הקלט הוא לכל היותר 3999, לכן הלולאה החמדנית בודקת 13 שורות בטבלה ומוסיפה לכל היותר 15 סמלים. אם היה מותר להשתמש במספרים גדולים יותר ולכתוב אותם באמצעות M חוזר, זמן הריצה היה גדל בהתאם ל־num / 1000.

האם תוכל להמיר מספר שלם לספרות רומיות בלי לעבור בלולאה על ערכים?

כן. שמור טבלה לכל מקום עשרוני עם המחרוזות של הספרות שלו, כגון "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM עבור המאות. חפש את הערך של כל ספרה ב־num ושרשר את המחרוזות. גם זה O(1), עם 34 מחרוזות שמורות.

למה 3999 הוא המספר הגדול ביותר שמותר?

M היא האות הגדולה ביותר, ואסור שאות תופיע ארבע פעמים ברצף, לכן MMM הוא הגבול של האלפים, ו־3999 הוא MMMCMXCIX. מספרים גדולים יותר נכתבו באמצעות סימנים נוספים, כמו קו מעל אות כדי להכפיל אותה ב־1000.

def intToRoman(num):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

num = 49

הפלט הצפוי

"XLIX"