Strona główna » Algorytmy » Artykuły » Zapis rzymski

Zapis rzymski

Wstęp

Rzym istniał już od czasów starożytnych. Rozwój cywilizacji wykształcił własny addytywny system zapisywania liczb. Pomagał on na usprawnienie handlu, ponieważ do tej pory nie było możliwości zapisu cen.

W addytywnym systemie wszystkie oznaczenia mają określone wartości, a wynikiem jest ich suma.

O systemie

Do oznaczeń wprowadzono znaki i przypisane do nich wartości: I (1), V (5), X (10), L (50), C (100), D (500), M (1000). Podczas zapisywania liczb w tym systemie dążymy do użycia jak najmniejszej ilości znaków:

  1. Maksymalnie 3 takie same znaki spośród I, X, C, M
  2. Obok siebie nie mogą stać dwa znaki: V, L, D
  3. Nie może być dwóch znaków zmniejszających większą liczbę po nich
  4. Znakami poprzedzającymi mogą być tylko I, X, C

Implementacja

Przechowywanie danych

(1.) Ze względu na fakt, że znaki rzymskie składają się z pojedynczej litery to znaki można zapisać do zmiennej typu string. Kolejne znaki są przechowywane w zmiennej signsc. Dodatkowo utworzona zostaje tablica signsv, która przechowuje wartości poszczególnych znaków. Numer indeksu danego znaku w zapisie na liście signsc odpowiada numerowi elementu signsv, który wskazuje jaką wartość dany znak ma.

  1. string signsc = "MDCLXVI";
  2. int signsv[] = {1000, 500, 100, 50, 10, 5, 1};

Z zapisu arabskiego na rzymski

  1. int fRoman(string b){
  2.   int w = 0, t = 0;
  3.   for(int i = 0; i < signsc.length(); i++){
  4.     while((t = b.find(signsc[i])) != string::npos){
  5.       w+=signsv[signsc.find(b[t])];
  6.       for(int j =0; j < t; j++){
  7.         w-=signsv[signsc.find(b[j])];
  8.       }
  9.       b=b.substr(t + 1, b.length());
  10.     }
  11.   }
  12.   return w;
  13. }

Funkcja konwertująca (1.) pobiera liczbę w zapisie rzymskim i deklaruje zwrócenie liczby całkowitej. (2.) Deklarujemy dwie zmienne pomocnicze: w odpowiada za przechowywanie wyniku, a t służy do zmniejszenia ilości wykonywanych operacji - raz wyliczamy wartość, a później dowolną ilość razy tylko odczytujemy. W tym rozwiązaniu wykonujemy (3.) iterację na każdym elemencie listy ze znakami. Patrząc od lewej w zapisie rzymskim największe właśnie tam stoją, a jeśli stoją mniejsze to tylko, aby zmniejszyć wartość większej. Następnie (4.) szukamy pozycji znaku. Najpierw dla M potem D itd. Jeśli taki znak istnieje w zapisie to dodajemy jego wartość, a następnie odejmujemy wartość wszystkich symboli znajdujących się przed nim. Następnie obcinamy część wyrazu, którą już przejrzeliśmy. Po zakończeniu iteracji zwracamy wartość liczby.

Warto zauważyć, że funkcja nie sprawdza poprawności wprowadzonego zapisu, dlatego jeśli nawet przed I stanie M to program odejmie 1000 z wyniku.

Z zapisu rzymskiego na arabski

  1. int fRoman(string b){
  2.   int w = 0, t = 0;
  3.   for(int i = 0; i < signsc.length(); i++){
  4.     while((t = b.find(signsc[i])) != string::npos){
  5.       w+=signsv[signsc.find(b[t])];
  6.       for(int j =0; j < t; j++){
  7.         w-=signsv[signsc.find(b[j])];
  8.       }
  9.       b=b.substr(t + 1, b.length());
  10.     }
  11.   }
  12.   return w;
  13. }

Zamiana z systemu arabskiego na rzymski może przysporzyć trochę więcej problemów, ponieważ musimy pamiętać o zasadach przedstawionych na początku artykułu. Analizując przedstawioną propozycję rozwiązania: (24.) funkcja pobiera liczbę całkowitą i deklaruje zwrócenie wartości tekstowej. (25.) Zmienna w będzie przechowywać aktualny wynik konwersji. Ponownie jak w przypadku zamiany z systemu rzymskiego wykonujemy iterację po wszystkich elementach listy signsc. Zaczynamy od jej początku czyli liczb największych. Dodajemy dany symbol, aż wykryjemy, że już nie możemy tj. kolejne dodanie tego symbolu spowoduje, że konwertowana liczba zejdzie poniżej 0.

W prototypie funkcji można pominąć linijki (31. - 36.). Funkcja prawidłowo zakończy działanie i w większości wypisze prawidłowe działanie. Kod zawarty w (31. - 36.) ma za zadanie dodać np. 40, 9 itd. Działa on na tej samej zasadzie co poprzednia część iteracji, ale sprawdza czy jeżeli odejmiemy kolejny element to uzyskamy liczbę, którą damy radę odjąć.

Przykład

Nie możemy dodać już więcej M, więc sprawdzamy czy damy radę wpisać CM, jeśli tak to dopisujemy i zmniejszamy liczbę konwertowaną. Jednak zasada 4. nie pozwala, aby zmnniejszyć M przy użyciu D. (Teoretycznie DM = 500, ale logiczniej jest zapisać D.) , dlatego przy sprawdzeniu, który element sprawdzamy przesuwamy odpowiednio, którą wartość pobieramy. Zakładając, że sprawdzamy aktualnie 10n, a potem 5·10n - 1 to wystarczy, aby dla obu tych znaków pobrana została następne 10n - 1. Rozwiązanie tego typu powoduje, że wspomniane na początku dopisanie dodatkowych znaków specjalnych spowoduje, że funkcja będzie działać prawidłowo.

Testowanie funkcji

Poprawność działania można sprawdzić przy pomocy poniższej funkcji main():

  1. int main(){
  2.   cout << tRoman(493) << endl;
  3.   system("pause");
  4.   return 0;
  5. }

Po uruchomieniu program wypisze na ekran liczbę 493 zapisaną w systemie Rzymskim:

  1. CDXCIII

Zadania

Zadanie 1

Rzymianie posiadali też symbole dla 10000 i 5000, które przyjmijmy, że były oznaczane kolejno jako A i B. Postaraj się zmienić kod tak, aby zamieniał wpisaną liczbę przy pomocy rozszerzonej tablicy symboli i ich wartości.

Przykładowo dla liczby 44444 program powinien wypisać:

  1. AAAAMBCDXLIV