algorytm.org

Zamiana z i na system rzymski

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Zamiana z i na system rzymski
Ocena użytkowników:***** / 53
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 09 lutego 2007 12:32

Rzymski system liczbowy jest systemem addtywnym - oznacza to, że wartość danej liczby uzyskujemy po dodaniu do siebie wszystkich reprenetujących ją składników. System ten jest pochodzenia etruskiego i został przejęty przez Rzymian około roku 500 p.n.e.

Do zapisu liczb rzymskich używa się 7 liter:

SymbolWartość
I1
V5
X10
L50
C100
D500
M1000


W systemie rzymskim zapisujemy liczby od strony lewej do prawej poczynając od znaków liczb o największej wartości. Kilkakrotnie napisany ten sam znak oznacza wielokrotność liczby wyrażonej tym znakiem. Na przykład: II = 1 + 1 = 2, z kolei XV = 10 + 5 = 15. Zapis powinien być jak najkrótszy, liczby 6 nie zapiszemy zatem jako IIIIII, tylko jako VI.
Nieco inaczej zapisuje się liczby 4xx (4, 40, ...) oraz 9xx (9, 90, ...), powstają one poprzez zapisanie znaku 1xx (1, 10, ...) przed odpowiednio znakiem 5xx (5, 50, ...) lub 10xx (1, 10, 100, ...). Zatem 4 zapiszemy jako IV, 40 jako XL a 400 jako CD, podobnie 9 zapiszemy jako IX, 90 jako XC a 900 jako CM. Liczba 1xx może stać wyłącznie przed liczbą 5xx lub 10xx o tej samej liczbie zer wyrażonych przez xx. Nie dozwolony jest zatem zapis liczby 99 w postaci: IC, prawidłowy zapis to XCIX = XC + IX = 90 + 9. Wiemy więc już jak zapisywane są liczby w systemie rzymskim zajmijmy się teraz więc algorytmami konwersji z i na liczby rzymskie.

Konwersja liczby rzymskie -> liczby arabskie
Posuwamy się od lewej strony i dodajemy do siebie wszystkie kolejne składniki, przy czym zwrócić uwagę musimy na miejsca, w których liczba 1xx poprzedza liczbę 5xx lub 10xx.
Sprawdzamy zgodność badanego znaku i symbolu rzymskiego poczynając od największej wartości.
Dopóki nie przeanalizowaliśmy wszystkich znaków liczby do przekonwertowania.
  • Jeżeli aktualnie badany znak zgodny jest z aktualnym symbolem to dodaj do wyniku wartość tego symbolu, przejdź do analizy kolejnego znaku w liczbie do przekonwertowania.
  • W przeciwnym razie, jeżeli aktualnie rozpatrywany symbol jest postaci 10xx i w liczbie do przekonwertowania pozostało więcej niż jeden znak do analizy to sprawdź czy dwa kolejne znaki pasują do wzorca postaci 9xx. Jeżeli tak, to dodaj wartość wzorca postaci 9xx do wyniku, przejdź do analizy kolejnego znaku po wzorcu 9xx. Przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej).
  • W przeciwnym razie, jeżeli aktualnie rozpatrywany symbol jest postaci 5xx i w liczbie do przekonwertowania pozostało więcej niż jeden znak do analizy to sprawdź czy dwa kolejne znaki pasują do wzorca postaci 4xx. Jeżeli tak, to dodaj wartość wzorca postaci 4xx do wyniku, przejdź do analizy kolejnego znaku po wzorcu 4xx. Przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej).
  • W przeciwnym wypadku przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej).


Przykład:

Zamienimy na postać arabską liczbę MCCIX.
Aktualnie rozpatrywanym symbolem jest M, bierzemy pierwszy znak naszej liczby. Zgadza się zatem do wyniku dodajemy 1000. Wynik = 0 + 1000 = 1000.
Sprawdzamy czy kolejny znak, w liczbie którą mamy przekonwetować równy jest M? Nie, ale M jest postaci 10xx i liczba znaków pozostałych do sprawdzenia jest większa od 1. Sprawdzamy więc czy dwa kolejne znaki pasują do wzorca postaci 9xx. Dla M będzie to 900 czyli CM. Nie pasują, a więc porównywać będziemy z kolejnym symbolem.
Kolejny symbol to D, Nie jest on równy rozpatrywanemu znakowi z liczby do przekonwertowania. Jest on postaci 5xx, a liczba znaków pozostalych do sprawdzenia jest większa od 1. Sprawdzamy więc czy dwa kolejne symbole nie psaują do wzorca postaci 4xx. Dla D będzie to 400 czyli CD. Nie pasują, a więc porównywać będziemy kolejny symbol.
Kolejny symbol to C, którego wartość wynosi 100. Zgadza się on z aktualnie rozpatrywanym (drugim) znakiem liczby, którą konwertujemy. Dodajemy zatem 100 do wyniku i przechodzimy do analizy kolejnego (trzeciego) znaku w liczbie do przekonwertowania. Wynik = 1000 + 100 = 1100.
Kolejny symbol to znów C, tak więc znów dodajemy 100 do wyniku. Wynik = 1100 + 100 = 1200. Przechodzimy do analizy kolejnego znaku w liczbie wejściowej.
Kolejny znak, jest różny od aktualnie rozpatrywanego symbolu C. Liczba znaków pozostałych do sprawdzenia jest większa od 1, zatem sprawdzimy jeszcze symbole postaci 9xx, dla C będzie to XC czyli 90. Nie zgadza się. A więc przechodzimy do analizy kolejnego symbolu.
Kolejnym symbolem jest X, wartość aktualnie rozpatrywanego znaku to I, tak więc nie zgadzają się. Pozostało do przeanalizowania jeszcze więcej jak 1 znak więc sprawdzamy, czy kolejne dwa znaki pasują do wzorca 9xx. Dla X będzie to IX, czyli 9. Dwa kolejne znaki pasują do tego wzorca. Tak więc do wyniku dodajemy 9, wynik = 1200 + 9 = 1209. Przesuwamy się z analizą o dwa znaki.
Doszliśmy do końca analizy wejściowej liczby rzymsiej, zatem zakończyliśmy konwersje. MCCIX = 1209.

Konwersja liczby arabskie -> liczby rzymskie
Sprawdzamy możliwość dodania symbolu rzymskiego poczynając od największej wartości.
Dopóki zadana liczba jest większa od zera:
  • Jeżeli zadana liczba jest większa bądź równa, wartości aktualnie rozpatrywanego symbolu to dodaj ten symbol do wyniku, a od liczby odejmij jego wartość.
  • W przeciwnym wypadku jeżeli aktualnie rozpatrywany symbol jest postaci 10xx, to rozpatrz możliwość dodania symbolu 9xx - jeżeli liczba jest większa bądź równa 9xx, to dodaj reprezentację 9xx do wyniku, a jego wartość odejmij od liczby, którą konwertujemy. Przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej)
  • W przeciwnym wypadku jeżeli aktualnie rozpatrywany symbol jest postaci 5xx, to rozpatrz możliwość dodania symbolu 4xx - jeżeli liczba jest większa bądź równa 4xx, to dodaj reprezentację 4xx do wyniku, a jego wartość odejmij od liczby, którą konwertujemy. Przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej)
  • W przeciwnym wypadku przejdź do rozpatrywania kolejnego symbolu (o wartości mniejszej).


Przykład:

Zamienimy na liczbę rzymską liczbę 2945.
A więc na początek bierzemy M, którego wartość wynosi tysiąc, sprawdzamy czy liczba która zamieniamy jest od niej większa bądź równa? Tak, a więc do wyniku dopisujemy M, a od naszej liczby odejmujemy 1000. Otrzymujemy wynik = 'M', liczba = 2945 - 1000 = 1945.
Dalej sprawdzamy, czy nasza liczba jest większa bądź równa M, tak a więc dopisujemy do wyniku kolejne 'M' i odejmujemy znów 1000. Wynik = 'MM', liczba = 1945 - 1000 = 945.
Znów sprawdzamy, czy nasza liczba jest większa, bądź równa M. Nie, bieżącym symbolem jest w tej chwili M, które jest postaci 10xx, a więc sprawdzamy czy nasza liczba jest większa bądź równa liczbie postaci 9xx. Tak 945 jest większe od 900, a więc do wyniku dopisujemy 'CM' a od liczby odejmujemy 900. Zatem wynik = 'MMCM', liczba 945 - 900 = 45.
Wartość M mamy już sprawdzoną, przechodzimy zatem do D, którego wartość wynosi, 500. Nasza liczba, której wartość obecnie wynosi 45 nie jest większa bądź równa 500. Aktualny symbol jest postaci 5xx, sprawdzimy zatem czy nasza liczba jest większa bądź równa liczbie postaci 4xx. 45 nie jest większe bądź równe 400 zatem, przechodzimy do sprawdzenia kolejnego symbolu.
C ma wartość 100, nasza liczba nie jest większa bądź równa 100, C jest postaci 10xx, zatem sprawdzimy jeszcze wartość 9xx, czyli 90. Nasza liczba nie jest większa bądź równa 90, tak więc znów przechodzimy do kolejnej wartości.
L, ma wartość 50, nasza liczba nie jest więszka bądź równa jemu, ale sprawdzamy jeszcze wartość postaci 4xx - nasza liczba jest większa od 40, tak więc do wyniku dopisujemy 'XL', a od liczby odejmujemy 40. Wynik= 'MMCMXL', liczba = 45 - 40 = 5. Przechodzimy do sprawdzania kolejnego wymbolu.
X, ma wartość 10, 5 jest mniejsze od 10, więc sprawdzimy jeszcze wartość postaci 9xx, 5 jest mniejsze również od 9, tak więc przechodzimy do kolejnego symbolu.
V, ma wartość 5. Nasza liczba jest równa 5, a więc do wyniku dopisujemy 'V'i odejmujemy 5. Wynik = 'MMCMXLV', liczba = 5 - 5 = 0.
Doszliśmy do zera, a więc uzyskaliśmy już ostateczny wynik: 2945 = 'MMCMXLV'.

Przedstawione sposoby konwersji pozwalają na zapis liczb do 3999 włącznie. Co jeżeli liczba, którą chcemy zapisać jest większa? Musimy wówczas użyć zapisu z kreską nad liczbą. Oznacza ona pomnożenie przez 1000. I tak na przykład V oznacza 5 * 1000 = 5000. Czyli wówczas do naszych konwersji użylibyśmy następującej tableki:

SymbolWartość
I1
V5
X10
L50
C100
D500
M1000
V5000
X10000
L50000
C100000
D500000
M1000000


Innym sposobem jest zapisanie liczby wewnątrz pionowych kresek, oznacza to wówczas pomnożenie raz 100. Czyli |V| oznacza 5 * 100 = 500.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 3
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 4
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 9
Kamil DębowskiC/C++konwersja tylko rzymskie->arabskie
.cpp
.cpp
***** / 6
golabowC/C++C++ - dodawanie dwóch liczb rzymskich
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 5
Tomasz LubińskiJava
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 października 2012 15:19
Komentarze
photo
0 # Emili 2009-11-24 20:24
Ta stronka jest super można poznać wiele rzymskich liczb B)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz