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)، في تمريرة واحدة.

الخوارزمية

اسرد القيم الثلاث عشرة مع رموزها، من 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 في الجدول. عندها ينتج عن 900 DCD.
استخدام 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"