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

Przykład

Spróbujmy przeliczyć liczbą 1493 na system Rzymski. W tym celu należy najpierw sprawdzić czy są wielkrotności 1000. Są, więc zapisujemy M. Następne jest 400, które można zapisać jako CD, ponieważ to oznacza od wartości D odejmij C czyli 500 - 100 = 400. Pozostało już do zapisania tylko 93. W podobny sposób zapisujemy 90 jako XC. Ostatnie 3 zapisujemy jako III. Zbierając wszystko razem otrzymujemy MCDXCIII.

Przeliczmy teraz w drugą stronę liczbę MMXV. Patrząc od lewej stoją dwa znaki M czyli 1000 + 1000 = 2000. Nastę jest X przez nic niezmniejszane, więc do wyniku dodajemy X. I tak samo postępujemy z V. Otrzymana suma to 2015.

Implementacja

Przechowywanie danych

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

(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.

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() - 1);
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 (5.) dodajemy jego wartość, a następnie (6. - 8.) odejmujemy wartość wszystkich symboli znajdujących się przed nim. (9.) 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 arabskiego na rzymski

1. string tRoman(int a) {
2.   string w = "";
3.   for (int i = 0; i < signsc.length(); i++) {
4.     while (a >= signsv[i]) {
5.       w += signsc[i];
6.       a -= signsv[i];
7.     }
8.     int j = (i % 2 == 0) ? 2 : 1;
9.     while (i + 1 < signsc.length() && a >= (signsv[i] - signsv[i + j])) {
10.       w += signsc[i + j];
11.       w += signsc[i];
12.       a -= (signsv[i] - signsv[i + j]);
13.     }
14.   }
15.   return w;
16. }

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: (1.) funkcja pobiera liczbę całkowitą i deklaruje zwrócenie wartości tekstowej. (2.) 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.

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 10ⁿ, a potem 5·10^{n - 1} to wystarczy, aby dla obu tych znaków pobrana została następne 10^{n - 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ższego fragmentu kodu. Program wczytuje od użytkownika pewną liczbę arabską i wypisuje na ekran skonwertowaną na system rzymski, a później ponownie liczbę rzymską konwertuje na arabską.

1. int main() {
2.   int a;
3.   cout << "Podaj liczbe Arabska:" << endl;
4.   cin >> a;
5.   string t = tRoman(a);
6.   cout << "Zapis Rzymski " << t << endl;
7.   cout << "Zapis Arabski " << fRoman(t) << endl;
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja

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ć AAAAMBCDXLIV.

• Kod źródłowy Implementacja