Programowanie w języku Delphi » Gotowce

Rzymskie na dziesiętne

Jak chyba większość maniaków programowania najlepiej odpoczywam po tej pięknej i fascynującej pracy... programując różne pierdoły ;) Natknąłem się na kilka sposobów przekodowywania liczby dziesiętnej na rzymską, ale jakoś nie wpadł mi w oko algorytm przeciwny. Tymczasem potrzeba takiej konwersji zachodzi częściej - choćby, jak w moim przypadku - do zamiany roku produkcji podanego w czołówce filmu w systemie, a jakże, rzymskim, na jakiś przyswajalny mojej wyobraźni, czyli dziesiętny :) Oto owoc kilku chwil mojego relaksu. Dla tych, którzy zrzynają gotowce mechanicznie podaję najpierw źródło :D


unit Roman2Dec;
 
{ 'private' }
 
interface
 
function RomanToDec( const roman: string ): integer;
 
 
 
implementation
 
uses
  Sysutils, { funkcja UpperCase }
  Strutils; { funkcje AnsiEndsStr, LeftStr }
 
 
const
  numbers_max = 21;
 
type
  liczby = record
    rom: string;
    dec: integer;
  end;
 
function RomanToDecRec( const roman: string ): integer;
const
  numbers: array[ 1..numbers_max ] of liczby =
  ( ( rom: 'III'; dec: 3 ),
    ( rom: 'II'; dec: 2 ),
    ( rom: 'IV'; dec: 4 ),
    ( rom: 'IX'; dec: 9 ),
    ( rom: 'I'; dec: 1 ),
    ( rom: 'V'; dec: 5 ),
    ( rom: 'XXX'; dec: 30 ),
    ( rom: 'XX'; dec: 20 ),
    ( rom: 'XL'; dec: 40 ),
    ( rom: 'XC'; dec: 90 ),
    ( rom: 'X'; dec: 10 ),
    ( rom: 'L'; dec: 50 ),
    ( rom: 'CCC'; dec: 300 ),
    ( rom: 'CC'; dec: 200 ),
    ( rom: 'CD'; dec: 400 ),
    ( rom: 'CM'; dec: 900 ),
    ( rom: 'C'; dec: 100 ),
    ( rom: 'D'; dec: 500 ),
    ( rom: 'MMM'; dec: 3000 ),
    ( rom: 'MM'; dec: 2000 ),
    ( rom: 'M'; dec: 1000 ) );
 
var
  roman_temp: string;
  i: integer;
  decimal_temp: integer;
  success: boolean;
 
begin
  { Przypisanie wartosci poczatkowych }
  result := 0; { Wazne przypisanie, pozwala uproscic obsluge ew. bledow! }
  decimal_temp := 0; { zmienna sluzaca do przechowywania sumy czastkowej }
 
  { Przepisanie liczby rzymskiej do zmiennej tymczasowej, zmiana na duze litery }
  roman_temp := UpperCase( roman );
 
  { Wlasciwa analiza }
  while Length( roman_temp ) > 0 do
  begin
    { Zmienna success bedzie ustawiona na true jesli ktorys z elementow tablicy
      numbers bedzie KONCZYL lancuch roman_temp. Na razie ustawiamy ja na false,
      co pozwala wylapac blad w przypadku liczb zawierajacych znaki inne niz
      cyfry rzymskie, na przyklad 'A'. }
    success := false;
 
    { przeszukiwanie tablicy numbers }
    for i := 1 to numbers_max do
    begin
      if AnsiEndsStr( numbers[ i ].rom, roman_temp ) then
        { jeden z elementow numbers znajduje sie na koncu lancucha roman_temp }
      begin
        { kontrola poprawnosci - dziesietny odpowiednik nie moze byc mniejszy
          niz uzyskana juz suma tymczasowa. Poniewaz result jest na razie
          ustawiony na 0 - mozemy spokojnie opuscic funkcje bez dodatkowych
          czynnosci }
        if ( numbers[ i ].dec <= decimal_temp ) then
          exit;
 
        { Zwiekszamy sume tymczasowa }
        decimal_temp := decimal_temp + numbers[ i ].dec;
 
        { Obcinamy lancuch tymczasowy od konca o dlugosc znalezionego wlasnie
          elementu liczby rzymskiej }
        roman_temp := LeftStr( roman_temp, Length( roman_temp ) - Length( numbers[ i ].rom ) );
 
        { Ustawiamy zmienna success i konczymy przeszukiwanie }
        success := true;
        break;
      end;
    end;
 
    if not success then
    begin
      { jesli liczba rzymska konczy sie elementem, ktorego nie znaleziono
        w tablicy numbers - na przyklad zawiera 'A' - opuszczamy funkcje.
        Result dalej jest ustawiony na zero :) }
      exit;
    end;
  end; { lancuch roman_temp pusty, koniec przeszukiwania }
 
  result := decimal_temp;
end; { function RomanToDec }
 
end.




Teraz kilka słów o użytym algorytmie:

Konwersja oparta jest na prostym fakcie: zapis cyfr rzymskich jest skomplikowany jedynie dlatego, że najstarsi Rzymianie nie znali... SPACJI :) Oraz nie pofatygowali się wprowadzić jednoznakowych odpowiedników dla wszystkich cyfr z zakresu 0..9, co również nie dziwi zważywszy że zera też nie znali :) Tak więc jakaś liczba rzymska, na przykład

MMCCCLXXXVIII (2388 dziesiętnie)

co wygląda dość koszmarnie - rozbiera się jako:

MM CCC L XXX V III

Czyli 2000 + 300 + 50 + 30 + 5 + 3.

Można było stosować logiczny rozbiór liczby, sprawdzając czy 'I' to jedynka czy część 'II', 'III', 'IV', 'VI' lub 'IX', ale powstałby logiczny potworek :) . Można było zapisać odpowiedniki cyfr rzymskich 1..9, 10..90, 100..900, 1000..3000 - ale wtedy tablica numbers miałaby 30 elementów. Wybrałem metodę IMHO najprostszą, polegającą na wyliczeniu listy możliwych tokenów (patrz tablica numbers) i wyszukiwaniu jej elementów w liczbie rzymskiej. Wyjaśnienia wymaga jedynie jej (tablicy :P) uporządkowanie. Jest tak posortowana, żeby podczas przeszukiwania liczby rzymskiej najpierw wychwytywać 'III' a potem 'II'. Zauważcie, że w przypadku wystąpienia niedozwolonej sekwencji 'XXXX' najpierw zostanie odnaleziony token 'XXX', a następnie 'X', co spowoduje wyjście z funkcji z wynikiem zero :) Wyjaśnia się tu dlaczego nie redukowałem rozmiarów tablicy numbers poprzez usunięcie tokenów 'III', 'II' i pozwolenie programowi by zliczał to jako odpowiednią ilość jedynek. Otóż... musiałbym wtedy znacznie rozbudować kontrolę poprawności wprowadzanych liczb rzymskich! Obecnie opiera się ona na prostym fakcie: wartość żadnego kolejnego tokenu nie może być mniejsza niż już obliczona suma cząstkowa (ret_val). Zapis 'VII' jest poprawny, zapis 'IIV' - już nie. Gdybym zostawił tylko 'I', przy konwersji liczby 'III' funkcja zwróciłaby zero :) Dla szczególnie dociekliwych - podpowiem, że kontrola nie jest zupełnie szczelna i mimo wszystko można przemycić niewłaściwy zapis ;)

Konwersja wyłącznie dla liczb z przedziału 1..3999. Na moje potrzeby (zmiana roku filmu) - to aż nadto.

Na koniec (o ile ktoś do tego miejsca doczytał :P) kilka ogólnych uwag o sposobie napisania funkcji. Miałem do wyboru użycie dwóch tablic, jednej na tokeny rzymskie i drugiej na odpowiedniki dziesiętne - lub tablicy rekordów. Pierwszy wariant mimo iż teoretycznie upraszczał strukturę programu - MÓGŁ spowodować problemy i przy pisaniu (łatwo się pomylić w odpowiednikach rom-dec) i przy EWENTUALNYM późniejszym rozszerzaniu funkcji na przykład poprzez zwiększanie zakresu konwertowanych liczb. Z tych samych względów zamiast kodować rozmiar tablicy numbers "na sztywno" - użyłem stałej numbers_max. A życie szybko uczy każdego programistę, że jedynie małą część kodu pisze się raz-na-zawsze :)

Ale sposoby pisania przejrzystego i łatwego do modyfikacji kodu - to już temat na zupełnie inne opowiadanie... :)

10 komentarzy

Sopelek 2014-06-25 10:19

Trochę może nie wczas, ale można to rozwiązać dużo prościej w C.

int rzymskieArabskie(const char* r)
{
    static int wartosci[256] = {['I'] = 1, ['V'] = 5, ['X'] = 10, ['L'] = 50, ['C'] = 100, ['D'] = 500, ['M'] = 1000};
    int wynik = 0;
    int i = 0;
    while(r[++i])
    {
        int wartosc = wartosci[r[i-1]];
        if(wartosc >= wartosci[r[i]]) wynik += wartosc;
        else wynik -= wartosc;
    }
    return wynik + wartosci[r[i-1]];
}

mati66688 2010-05-06 10:24

Wystarczą 2 Edity i 1 Button i można też np. tak:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  i:integer;
  roman:string;
  dzies:integer;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
roman:='';
dzies:=0;
roman:=Edit1.Text;
i:=length(roman);

// Można dodać jeszcze zamianą znaków małych na duże ale to kwestia estetyki i poprawnego działania programu w każdych warunkach.

For i:=1 to i do
Begin
if (roman[i]='i') then roman[i]:='I';
if (roman[i]='v') then roman[i]:='V';
if (roman[i]='x') then roman[i]:='X';
if (roman[i]='l') then roman[i]:='L';
if (roman[i]='c') then roman[i]:='C';
if (roman[i]='d') then roman[i]:='D';
if (roman[i]='m') then roman[i]:='M';
end;
// -> zamiana z małych na duże :P
Edit1.Text:=roman; // Podmiana textu w Edit1 by zlikwidować w nim małe i dać duże. Czysta estetyka :)


for i:=1 to i do
Begin
if (roman[i]='I') then dzies:=dzies+1;
if (roman[i]='I')and(roman[i+1]='V') then dzies:=dzies-2;
if (roman[i]='V') then dzies:=dzies+5;
if (roman[i]='I')and(roman[i+1]='X') then dzies:=dzies-2;
if (roman[i]='X') then dzies:=dzies+10;
if (roman[i]='X')and(roman[i+1]='L') then dzies:=dzies-20;
if (roman[i]='L') then dzies:=dzies+50;
if (roman[i]='X')and(roman[i+1]='C') then dzies:=dzies-20;
if (roman[i]='C') then dzies:=dzies+100;
if (roman[i]='C')and(roman[i+1]='D') then dzies:=dzies-200;
if (roman[i]='D') then dzies:=dzies+500;
if (roman[i]='C')and(roman[i+1]='M') then dzies:=dzies-200;
if (roman[i]='M') then dzies:=dzies+1000;
end;
Edit2.Text:=inttostr(dzies);
end;

end.

Sposób myślę w miarę prosty i zrozumiały :) Myślę że rozważyłem wszystkie opcje w razie czego pisać a poprawię :)

Booboo 2004-12-16 11:11

   po pierwsze piwo widziałem o wiele prostszy algorytm podobny do przedstawionego przez Tomuslaw'a (pierwszy komentaż)
   po drugi piwo rosjanie zapisują rzymska 4 jako IIII a nie IV
(pewnie czepicie się ze rosjanie wszystko inaczej robia X-( ale jesteś programista i musisz przewidzieć wszystkie ruchy użytkownika)

Dryobates 2004-11-07 21:14

To chyba jest troszke prostsze: http://4programmers.net/article.php?id=197 Warto czasem poczytać co już jest w gotowacach :)

Gynvael Coldwind 2004-07-21 09:48

kod bedzie w c, sorx ;>

/* konwersja rzymskie -> arabskie
 */
int
rzym2arab( char *what )
{
  static int conv[ 20 ];
  int ret = 0;
  int s = 0, i;
  char *wh = what;
 
  while( *wh )
  {
    switch( *wh )
    {
      case 'I': conv[ s ] =    1; break;
      case 'V': conv[ s ] =    5; break;
      case 'X': conv[ s ] =   10; break;
      case 'L': conv[ s ] =   50; break;
      case 'C': conv[ s ] =  100; break;
      case 'D': conv[ s ] =  500; break;
      case 'M': conv[ s ] = 1000; break;
    }
 
    wh++; s++;
  }
 
  conv[ s ] = 0;
 
  for( i = 1; i <= s; i++ )
  {
    /* ie. II, adds 1 (the second 1 will be added later) */
    if( conv[ i ] == conv[ i - 1 ] )
    {
      ret += conv[ i - 1 ];
    }
 
    /* ie. IX, adds 9 */
    else if( conv[ i - 1 ] < conv[ i ] )
    {
      ret += conv[ i ] - conv[ i - 1 ];
      i++;
    }
 
    /* ie. XI, adds 10 (the I will be added later) */
    else
    {
      ret += conv[ i - 1 ];
    }
  }
 
 
  return ret;
}

moze na delphi tez da sie przelozyc...

Shreq 2004-07-18 23:21

Pewnie że prostszy, tylko robi konwersję w drugą stronę, z arabskich na rzymskie, nieprawdaż? :D

Tomuslaw 2004-07-18 22:43

1. prostszy *
2. edit2.text // miejsce, gdzie będzie wypisywana liczba rzymska

Tomuslaw 2004-07-18 22:41

A nie lepiej zrobić program, który będzie odejmował? :) Tzn.:

...
 rz[1]:='I';
   rz[2]:='IV';
   rz[3]:='V';
   rz[4]:='IX';
   rz[5]:='X';
   rz[6]:='XL';
   rz[7]:='L';
   rz[8]:='XC';
   rz[9]:='C';
   rz[10]:='CD';
   rz[11]:='D';
   rz[12]:='CM';
   rz[13]:='M';
   ar[1]:=1;
   ar[2]:=4;
   ar[3]:=5;
   ar[4]:=9;
   ar[5]:=10;
   ar[6]:=40;
   ar[7]:=50;
   ar[8]:=90;
   ar[9]:=100;
   ar[10]:=400;
   ar[11]:=500;
   ar[12]:=900;
   ar[13]:=1000;
...
x:=StrToInt(edit1.text); // liczba arabska
      i:=13;
      repeat
         if x>=ar[i] then
            begin
            x:=x-ar[i];
            edit2.text:=edit2.text+rz[i];
            end
         else
            Dec(i);
     until x=0;

Prostrzy, nieprawdaż ? :)

Shreq 2004-07-24 06:27

-> Gynvael Coldwind

Wbrew pozorom - po wycięciu komentarzy mój kod jest tylko o kilka (dwie?) linijki dłuższy, co wziąwszy pod uwagę iż to Delphi vs C - nie jest złym wynikiem :) Natomiast mój nie przepuści potworków typu:
"IIIIIII"
"IXIXIXIXIX"
"XCAAACX"
że już o "iiiiii" nie wspomnę :)

Idea mi się podoba jako _zaczątek_ logicznego rozbioru zapisu, ale dorzuć jeszcze jakieś sprawdzanie poprawności danych :)

Pozdrawiam

Tomuslaw 2004-07-23 07:55

Shreq - rzeczywiście :)