Zanurkuj w Pythonie/Analiza przypadku: Liczby rzymskie

Analiza przypadku: Liczby rzymskie

edytuj

Najprawdopodobniej spotkaliśmy się już gdzieś z liczbami rzymskimi. Można je spotkać w starszych filmach oglądanych w telewizji (np. "Copyright MCMXLVI" zamiast "Copyright 1946") lub na ścianach bibliotek, czy uniwersytetów (napisy typu "założone w MDCCCLXXXVIII" zamiast "założone w 1888 roku"). Mogliśmy je także zobaczyć na przykład w referencjach bibliograficznych. Ten system reprezentowania liczb sięga czasów starożytnego Rzymu (stąd nazwa).

W liczbach rzymskich wykorzystuje się siedem znaków, które na różne sposoby się powtarza i łączy, aby zapisać pewną liczbę:

  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1000

Poniżej znajdują się podstawowe zasady konstruowania liczb rzymskich:

  • Znaki są addytywne. I to 1, II to 2, a III to 3. VI to 6 (dosłownie, „5 i 1”), VII to 7, a VIII to 8.
  • Znaki dziesiątek (I, X, C i M) mogą się powtarzać do trzech razy. Za czwartym należy odjąć od następnego większego znaku piątek. Nie można zapisać liczby 4 jako IIII. Zamiast tego napiszemy IV ("o 1 mniej niż 5"). Liczba 40 zapisujemy jako XL (o 10 mniej niż 50), 41 jako XLI, 42 jako XLII, 43 jako XLIII, a potem 44 jako XLIV (o 10 mniej niż 50, a potem o 1 mniej niż 5).
  • Podobnie w przypadku 9. Musimy odejmować od wyższego znaku dziesiątek: 8 to VIII, lecz 9 zapiszemy jako IX (o 1 mniej niż 10), a nie jako VIIII (ponieważ znak nie może się powtarzać cztery razy). Liczba 90 to XC, a 900 zapiszemy jako CM.
  • Znaki piątek nie mogą się powtarzać. Liczba 10 jest zawsze reprezentowana przez X, nigdy przez VV. Liczba 100 to zawsze C, nigdy LL.
  • Liczby rzymskie są zawsze pisane od najwyższych do najniższych i czytane od lewej do prawej, więc porządek znaków jest bardzo ważny. DC to 600, jednak CD jest kompletnie inną liczbą (400, ponieważ o 100 mniej niż 500). CI to 101, jednak IC nie jest żadną poprawną liczbą rzymską (nie możemy bezpośrednio odejmować 1 od 100, musimy to zapisać jako XCIX, o 10 mniej niż 100, dodać 1 mniej niż 10).

Sprawdzamy tysiące

edytuj

Jak sprawdzić, czy jakiś łańcuch znaków jest liczbą rzymską? Spróbujmy sprawdzać cyfra po cyfrze. Jako, że liczby rzymskie są zapisywane zawsze od najwyższych do najniższych, zacznijmy od tych najwyższych: tysięcy. Dla liczby 1000 i większych, tysiące zapisywane są przez serię liter M.

Przykład. Sprawdzamy tysiące
>>> import re
>>> pattern = '^M?M?M?$'         #(1)
>>> re.search(pattern, 'M')      #(2)
<SRE_Match object at 0106FB58>
>>> re.search(pattern, 'MM')     #(3)
<SRE_Match object at 0106C290>
>>> re.search(pattern, 'MMM')    #(4)
<SRE_Match object at 0106AA38>
>>> re.search(pattern, 'MMMM')   #(5)
>>> re.search(pattern, "")       #(6)
<SRE_Match object at 0106F4A8>
  1. Ten wzorzec składa się z 3 części:
    • ^, które umieszczone jest w celu dopasowania jedynie początku łańcucha. Gdybyśmy go nie umieścili, wzorzec pasowałby do każdego wystąpienia znaków M, czego przecież nie chcemy. Chcemy, aby dopasowane zostały jedynie znaki M znajdujące się na początku łańcucha, o ile w ogóle istnieją.
    • M?, które ma wykryć, czy istnieje pojedyncza litera M. Jako, że powtarzamy to trzykrotnie, dopasujemy od zera do trzech liter M w szeregu.
    • $, w celu dopasowania wzorca do końca łańcucha. Gdy połączymy to ze znakiem ^ na początku, otrzymamy wzorzec, który musi pasować do całego łańcucha, bez żadnych znaków przed czy po serii znaków M.
  2. Sednem modułu re jest funkcja search, która jako argumenty przyjmuje wyrażenie regularne (wzorzec) i łańcuch znaków ('M'), a następnie próbuje go dopasować do wzorca. Gdy zostanie dopasowany, search zwraca obiekt który posiada wiele metod, które opisują dopasowanie. Jeśli nie uda się dopasować, search zwraca None, co jest Pythonową pustą wartością i nic nie oznacza. Na razie jedyne, co nas interesuje, to czy wzorzec został dopasowany, czy nie, a co możemy stwierdzić przez sprawdzenie, co zwróciła funkcja search. 'M' pasuje do wzorca, gdyż pierwsze opcjonalne M zostało dopasowane, a drugie i trzecie zostało zignorowane.
  3. 'MM' pasuje, gdyż pierwsze i drugie opcjonalne M zostało dopasowane, a trzecie zignorowane.
  4. 'MMM' również pasuje do wzorca, gdyż wszystkie trzy opcjonalne wystąpienia M we wzorcu zostały dopasowane.
  5. 'MMMM' nie pasuje, gdyż pomimo dopasowania pierwszych trzech opcjonalnych znaków M, za trzecim wzorzec wymaga, aby łańcuch się skończył, a w naszym łańcuchu znaków znajduje się kolejna litera M. Tak więc search zwraca wartość None.
  6. Co ciekawe, pusty łańcuch też pasuje do wzorca, gdyż wszystkie wystąpienia M są opcjonalne.

Sprawdzamy setki

edytuj

Setki są nieco trudniejsze, ponieważ schemat zapisu nie jest aż tak prosty jak w wypadku tysięcy. Mamy więc następujące możliwości:

  • 100 = C
  • 200 = CC
  • 300 = CCC
  • 400 = CD
  • 500 = D
  • 600 = DC
  • 700 = DCC
  • 800 = DCCC
  • 900 = CM

Wynika z tego, że mamy 4 wzorce:

  • CM
  • CD
  • Zero do trzech wystąpień C (zero, gdyż może nie być żadnej setki)
  • D, po którym następuje zero do trzech C

Ostatnie dwa wzorce możemy połączyć w opcjonalne D, a za nim od zera do trzech C.

Poniższy przykład ilustruje jak sprawdzać setki w liczbach Rzymskich.

Przykład. Sprawdzamy setki
>>> import re
>>> pattern = '^M?M?M?(CM|CD|D?C?C?C?)$'  #(1)
>>> re.search(pattern, 'MCM')             #(2)
<SRE_Match object at 01070390>
>>> re.search(pattern, 'MD')              #(3)
<SRE_Match object at 01073A50>
>>> re.search(pattern, 'MMMCCC')          #(4)
<SRE_Match object at 010748A8>
>>> re.search(pattern, 'MCMC')            #(5)
>>> re.search(pattern, "")                #(6)
<SRE_Match object at 01071D98>
  1. Ten wzorzec zaczyna się tak samo jak poprzedni, rozpoczynając sprawdzanie od początku łańcucha (^), potem sprawdzając tysiące (M?M?M?). Tutaj zaczyna się nowa część, która definiuje 3 alternatywne wzorce rozdzielone pionową kreską (|): CM, CD, i D?C?C?C? (opcjonalne D, po którym następuje od zera do trzech opcjonalnych znaków C). Analizator wyrażeń regularnych sprawdza każdy ze wzorców w kolejności od lewej do prawej, wybiera pierwszy pasujący i ignoruje resztę.
  2. 'MCM' pasuje, gdyż pierwsza litera M pasuje, drugie i trzecie M jest ignorowane, i CM pasuje (gdyż CD oraz D?C?C?C? nie są nawet sprawdzane). MCM to rzymska liczba 1900.
  3. 'MD' pasuje, ponieważ pierwsze M pasuje, drugie i trzecie M z wzorca jest ignorowane, oraz D pasuje do wzorca D?C?C?C? (wystąpienia znaku C jest opcjonalne, więc analizator je ignoruje). MD to rzymska liczba 1500.
  4. 'MMMCCC' pasuje, gdyż pasują wszystkie trzy pierwsze znaki M, a fragment D?C?C?C? we wzorcu pasuje do CCC (D jest opcjonalne). MMMCCC to 3300.
  5. 'MCMC' nie pasuje, Pierwsze M pasuje, CM również, ale $ już nie, gdyż nasz łańcuch zamiast się skończyć, ma kolejną literę C. Nie została ona dopasowana do wzorca D?C?C?C?, gdyż został on wykluczony przez wystąpienie wzorca CM.
  6. Co ciekawe, pusty łańcuch znaków dalej pasuje do naszego wzorca, gdyż wszystkie znaki M są opcjonalne, tak jak każdy ze znaków we wzorcu D?C?C?C?.

Uff! Widzimy, jak szybko wyrażenia regularne stają się brzydkie? A jak na razie wprowadziliśmy do niego tylko tysiące i setki. Ale jeśli dokładnie śledziliśmy cały ten rozdział, dziesiątki i jednostki nie powinny stanowić dla Ciebie problemu, ponieważ wzór jest identyczny. A teraz zajmiemy się inną metodą wyrażania wzorca.