Integer to Roman

Q: Tam sayıdan Roma rakamına dönüştürmenin zaman karmaşıklığı nedir?

O(1) . Girdi en fazla 3999 olduğundan, açgözlü döngü tablonun 13 satırını kontrol eder ve en fazla 15 sembol ekler. Daha büyük sayılara izin verilseydi ve tekrarlanan M ile yazılsaydı, süre num / 1000 ile birlikte artardı.

Q: İzin verilen en büyük sayı neden 3999?

M en büyük harftir ve hiçbir harf art arda dört kez görünemez; bu yüzden binler basamağında en fazla MMM yazılır ve 3999, MMMCMXCIX şeklindedir. Daha büyük sayılar, bir harfin üzerine çizgi koyarak o harfi 1000 ile çarpmak gibi ek işaretlerle yazılırdı.

OrtaMatematik ve simülasyon Açgözlü

+10

Roma rakamlarının yedi harfi vardır: M 1000, D 500, C 100, L 50, X 10, V 5 ve I 1. Harfler büyükten küçüğe doğru sıralanır ve toplanır; bu nedenle 7, VII şeklinde yazılır. Hiçbir harf arka arkaya dört kez tekrarlanmaz: 4, 9, 40, 90, 400 ve 900; IV, IX, XL, XC, CD ve CM şeklinde yazılır; bu gösterimlerde küçük harf, kendisinden sonra gelen büyük harften çıkarılır. Yalnızca bu altı çiftte küçük harf önce gelir.

Bir tam sayı olan num verildiğinde, Roma rakamı karşılığını döndür.

Fonksiyon

intToRoman(num: integer) → string

numinteger: 1 ile 3999 arasında bir tam sayı
Döndürürstring: num sayısının büyük harflerle yazılmış Roma rakamı

Kısıtlar

1 ≤ num ≤ 3999

Örnekler

Girdi: num = 49
Çıktı: "XLIX"
Açıklama: 49, 40 + 9'dur, bu yüzden sayı XL ardından IX şeklindedir: XLIX. IL kullanılamaz, çünkü I yalnızca IV ve IX içinde çıkarma yapar.

Girdi: num = 2026
Çıktı: "MMXXVI"
Açıklama: 2026'da 4 veya 9 rakamı yok, bu yüzden çift gerekmiyor ve harflerin değerlerini topluyoruz: 1000 + 1000 + 10 + 10 + 5 + 1, MMXXVI eder.

Girdi: num = 944
Çıktı: "CMXLIV"
Açıklama: 944, 900 + 40 + 4’tür ve her parça çıkarma yöntemiyle oluşturulmuş bir çifttir: CM, XL ve IV birleşerek CMXLIV olur.

Ek soru

Bir dizenin standart biçimde bir Roma rakamı olup olmadığını kontrol edebilir misin? XLIX kabul edilmeli; IIII, IL ve VX ise reddedilmeli.

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Altı çıkarma çiftini alfabeye kendi sembolleri olarak ekleyin; böylece bir sayı yazmak para üstü vermeye dönüşür: hâlâ sığan en büyük değeri her zaman alın. Girdi en fazla 3999’dur, bu nedenle işlem miktarı küçük ve sabittir.

Önce toplama işlemiyle yaz, ardından uzun biçimleri kısalt.

Sezgi

Önce çiftleri göz ardı et: sığdığı kadar M, ardından D yaz ve bu şekilde I'ye kadar devam et. 944 için bu, DCCCCXXXXIIII sonucunu verir. Bu toplamsal biçim, yalnızca bir basamak 4 veya 9 olduğunda standart biçimden farklıdır ve bu konumlarda kısa biçimi olan altı dizgeden biri bulunur: DCCCC, CM; CCCC, CD; LXXXX, XC; XXXX, XL; VIIII, IX ve IIII, IV olur.

CCCC'den önce DCCCC'ü değiştir; yoksa 900, DCD'ye dönüşür. Aynı durum onlar ve birler basamağı için de geçerlidir. Toplamsal biçim en fazla 18 harften oluşur (3999), dolayısıyla işlem O(1)'dir; bunun bedeli ikinci bir geçiş ve birkaç geçici dizgedir.

Algoritma

M'den I'ye kadar olan yedi harfin her biri için, num değerine eşit veya bu değerden büyük olduğu sürece harfi ekleyin ve her seferinde değeri çıkarın.
Önce DCCCC ifadesini CM ile, ardından CCCC ifadesini CD ile değiştirin.
Önce LXXXX ifadesini XC ile, ardından XXXX ifadesini XL ile değiştirin.
Önce VIIII ifadesini IX ile, ardından IIII ifadesini IV ile değiştirin.
Dizeyi döndürün.

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 değer üzerinde açgözlü

Sezgi

Yedi harfi ve altı çifti değerlerine göre sırala: 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. Sığan en büyük değeri almak her zaman doğrudur. Daha düşük bir ondalık basamağın tüm değerleri, bir üst basamağın en küçük değerinden küçüktür; bu nedenle döngü bir sonraki basamağa geçmeden önce biter. Bir basamağın içinde 9, 5, 4 ve 1 değerleri her rakamı standart biçimde yazar: 9, 9 simgesidir; 5 ile 8, 5 simgesinin ardından en fazla üç 1 simgesinden oluşur; 4, 4 simgesidir ve 1 ile 3, 1 simgelerinden oluşur.

3746 için döngü MMM, D, CC, XL, V, I yazar: MMMDCCXLVI. Tabloda 13 satır ve yanıtta en fazla 15 harf olduğundan, işlem tek geçişte O(1) olur.

Algoritma

1000'den 1'e kadar olan 13 değeri sembolleriyle birlikte, çiftler dâhil, listele.
Boş bir dizeyle başla.
Her satır için, num değere eşit veya daha büyük olduğu sürece sembolü ekle ve değeri çıkar.
Tüm satırlar tamamlandığında dizeyi döndür.

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)

Tuzaklar ve uç durumlar

Tabloda CM'den önce D koymak. Böylece 900, DCD olarak çıkar.
Her satır için while yerine if kullanmak. 3000 için M üç kez gerekir; if ile sonuç MCMDCDCXCX olur.
Başka çiftler uydurmak. 99, IC değil XCIX'tir ve 45, VL değil XLV'dir.
C'de, yetersiz büyüklükte bir arabellek kullanmak. 3888 için en uzun yanıt 15 harften oluşur; bu nedenle sonlandırıcı sıfırla birlikte 16 bayt gerekir. Toplamalı biçim için 19 bayt gerekir.

Sıkça sorulan sorular3

Tam sayıdan Roma rakamına dönüştürmenin zaman karmaşıklığı nedir?

O(1). Girdi en fazla 3999 olduğundan, açgözlü döngü tablonun 13 satırını kontrol eder ve en fazla 15 sembol ekler. Daha büyük sayılara izin verilseydi ve tekrarlanan M ile yazılsaydı, süre num / 1000 ile birlikte artardı.

Bir tam sayıyı değerler üzerinde döngü kullanmadan Roma rakamlarına dönüştürebilir misin?

Evet. Her ondalık basamak için, yüzler basamağında olduğu gibi, rakamlarına karşılık gelen dizeleri içeren bir tablo tut: "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM. num değerinin her basamağına karşılık gelen diziyi bul ve dizeleri birleştir. Bu yöntem ayrıca O(1) zaman karmaşıklığına sahiptir ve 34 dize saklar.

İzin verilen en büyük sayı neden 3999?

M en büyük harftir ve hiçbir harf art arda dört kez görünemez; bu yüzden binler basamağında en fazla MMM yazılır ve 3999, MMMCMXCIX şeklindedir. Daha büyük sayılar, bir harfin üzerine çizgi koyarak o harfi 1000 ile çarpmak gibi ek işaretlerle yazılırdı.

def intToRoman(num):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

num = 49

Beklenen Çıktı

"XLIX"