Thuật toán convert số thập phân sang la mã

[nguyen2812 (Bùi Đình Nguyên)]

Các anh ơi cho em xin thuật toán convert số thập phân sang số la mã đc không ạ.
Đây chỉ là topic hỏi về thuận toán nên mong các sếp không gạch đá em cũng như là không gây war trong phần cmt như các topic trước ạ.
Em xin chân thành cảm ơn.

[HR16 (Gà Coder)]

Hình như em sợ gây war và gạch đá lắm thì phải . Mà giờ có 2 vấn đề. Thứ nhất, nếu số nhập vào là số có phần thập phân phía sau thì sao . Thứ hai, trong số La Mã, đối với những số từ 4000 trở lên, một dấu gạch ngang được đặt trên đầu số gốc để chỉ cho 1000, làm sao để biểu diễn dấu gạch ngang đó lên màn hình được ?

[qloved (Quân)]

về số có phần thập phân thì có thể giải quyết bằng cách bắt người dùng phải nhập số nguyên là ok. Còn việc số lơn hơn 4k thì có thể dùng bảng mã unicode để sử dụng các kí tự số la mã có dấu gạch ngang là ok

[HR16 (Gà Coder)]

Rồi, giả sử như số nhập từ bàn phím là n(n € N*, n <= 4000) thì cách đổi số thập phân n sang thập phân khá đơn giản, chỉ cần tách số n thành tổng các số đơn vị, chục, trăm, nghìn, chuyển sang dạng số La Mã và ghép lại thôi. Ví dụ: 1234 = 1000 + 200 + 30 + 4, chuyển 1000 thành M, 200 thành CC, 30 thành XXX, 4 thành IV, ta ghép lại thì sẽ có được MCCXXXIV. Chi tiết cách convert số thập phân sang số La Mã ở bên dưới:

Đầu tiên, để tách n thành tổng các số đơn vị, chục, trăm, nghìn thì phải tách n thành các số đơn vị, chục, trăm, nghìn rồi nhân chúng với 10, 100, 1000. Cách tách như sau:

• Hàng đơn vị: n mod 10

• Hàng chục: n/10 mod 10(lấy số ở hàng chục bằng cách lấy phần nguyên).10

• Hàng trăm: n/100 mod 10(lấy số ở hàng trăm bằng cách lấy phần nguyên).100

• Hàng nghìn: n/1000 mod 100(lấy số ở hàng nghìn bằng cách lấy phần nguyên).1000

Sau đó thì chuyển mấy số đó sang dạng La Mã, chỗ này thì tự em làm nha . Rồi cuối cùng là ghép các số này lại là xong. Ngoài ra, em cần phải lưu ý một số quy tắc của số La Mã:

1. Nhiều ký hiệu có thể được kết hợp lại với nhau để chỉ các số với các giá trị khác chúng. Thông thường người ta quy định các chữ số I, X, C, M, không được lặp lại quá ba lần liên tiếp; các chữ số V, L, D không được lặp lại liên tiếp.

2. Người ta dùng các chữ số I, V, X, L, C, D, M, và các nhóm chữ số IV, IX, XL, XC, CD, CM để viết số La Mã. Tính từ trái sang phải giá trị của các chữ số và nhóm chữ số giảm dần.

3. I chỉ có thể đứng trước V hoặc X, X chỉ có thể đứng trước L hoặc C, C chỉ có thể đứng trước D hoặc M.

4. Đối với những số lớn hơn (4000 trở lên), một dấu gạch ngang được đặt trên đầu số gốc để chỉ phép nhân cho 1000

Bảng chữ số La Mã:

Ký tự	Giá trị
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Trích từ Wikipedia:

Số La Mã

P/s: Đối với những số trên 4k, có thể biểu diễn số gạch ngang trên đầu bằng kí tự unicode như @qloved đã nói

[nguyen2812 (Bùi Đình Nguyên)]

Vậy là không đc viết số 99 là IC ạ. Em tính hết các case nhưng còn mấy số kiểu 49 hoặc 99 em cứ nghĩ là viết theo kiểu IL hay IC🤦🤦🤦🤦

[HR16 (Gà Coder)]

Tách 49 thành 49 = 40 + 9, chuyển 40 thành XL, chuyển 9 thành IX, ghép lại thành XLIX. Còn đối với 99 thì 99 = 90 + 9, chuyển 90 thành XC, chuyển 9 thành IX, ghép lại thành XCIX thôi.

[tntxtnt]

có cách dễ hơn là trừ tham lam như thối tiền ấy

v = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
tương ứng với
s = [“M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”]
rồi duyệt 1 vòng lặp nếu giá trị n hiện tại >= v[i] thì in ra s[i] và trừ v[i] cho n tới khi n < v[i], tiếp tục tới khi n = 0 thì dừng

ví dụ 1234:
1234 > 1000, in ra M, trừ 1000 còn 234
234 < 900, ko in ko trừ
234 < 500, ko in ko trừ
234 < 400, ko in ko trừ
234 > 100, in ra C, trừ 100 còn 134; 134 > 100, in ra C, trừ 100 còn 34
34 < 90, ko in ko trừ
34 < 50, ko in ko trừ
34 < 40, ko in ko trừ
34 > 10, in ra X, trừ 10 còn 24; 24 > 100, in ra X, trừ 10 còn 14; 14 > 100, in ra X, trừ 10 còn 4
4 >= 4, in ra IV, trừ 4 còn 0, kết thúc
vậy 1234 = MCCXXXIV

[HR16 (Gà Coder)]

Đúng là cách này đơn giản hơn thật .

[Lovemagic]

đoạn code rome-golf mình đọc đc ở pagedout Code javascript
Cách dùng rome(1234)

function rome(N,s,b,a,o){
     for(s=b='',a=5;N;b++,a^=7)
        for(o=N%a,N=N/a^0;o--;)
          s='IVXLCDM'.charAt(o>2?b+N-(N&=~1)+(o=1):b)+s;
    return s
}

Ai hứng thú đọc thêm thì vào trang 33 nha https://pagedout.institute/download/PagedOut_001_beta1.pdf

[HR16 (Gà Coder)]

Không nên dùng đoạn code này để tham khảo . Chạy vẫn đúng nhưng quá khó hiểu

[rogp10]

Như đoạn này:

b+N-(N&=~1)

[noname00 (HK boy)]

@nguyen2812

mấy số kiểu 49 hoặc 99 em cứ nghĩ là viết theo kiểu IL hay IC

Hàng nào ra hàng đó, hàng chục chuyển riêng, hàng đơn vị chuyển riêng.

@Lovemagic

for(s=b=’’,a=5;N;b++,a^=7)

Đáng ra có thể viết

for (s="", b=0, a=5; N; b++, a^=7)

nhưng hình như tác giả thích troll :v

[HR16 (Gà Coder)]

Tác giả bảo là đoạn code trên là từ một người nào đó tham gia thử thách golf code nhỏ mà. Mà chính tác giả cũng bị “nổ não”(mind-boggling) khi đọc đoạn code trên

[rogp10]

Dùng charAt thì chắc là lâu lắm rồi.

[HR16 (Gà Coder)]

Theo cuốn sách mà @Lovemagic đã đề cập thì cái thử thách trên có từ hồi 2003 rồi

[nguyen2812 (Bùi Đình Nguyên)]

Ngoài việc chia ra nhiều case còn cách nào tối ưu hơn không nhỉ các bác

[HR16 (Gà Coder)]

Hmmm… Chẳng biết nữa ?

[rogp10]

Đọc từng chữ số rồi thay số bằng chữ là xong https://en.wikipedia.org/wiki/Roman_numerals#"Standard"_form

[HR16 (Gà Coder)]

À thấy code của @Lovemagic nói đến cũng dùng cách này, mà đúng là cách này đơn giản nhất rồi

Mà khoan… Ví dụ như 1234 thì bạn thay kiểu gì ?

[noname00 (HK boy)]

Đơn giản thôi mà

1 -> M
2 -> CC
3 -> XXX
4 -> IV

1234 -> MCCXXXIV