[C] Nhập vào một số nguyên, xuất ra số La Mã

[hirikarate]

Nếu ai đã từng xài Word chắc hẳn biết chức năng Bullets and Numbering dùng để viết danh sách có thứ tự. Bi giờ mình hãy viết 1 hàm như sau:
Nhập vào một số nguyên N (0<N<10 000), xuất ra số đó dưới dạng số La Mã, với giả thiết sau:

IV: 4
V:  5
XL: 40
L:  50
XC: 90
C:  100
CD: 400
D:  500
M:  1000 //Max
MMMMM: 5000

Ví dụ: Nếu nhập N=1459 thì xuất ra M CD L IX
Để thử xem chương trình mình chạy đúng hay sai, hãy mở Word ra, rồi vào Format -> Bullets and Numbering -> Chọn thẻ Numbered -> Nhấp vào Customize... -> Trong ô Number style hãy chọn kiểu 1,2,3... -> Trong ô Start at gõ 1 số cần thử nghiệm, ví dụ 1459 -> Vào lại ô Number style, chọn kiểu là I, II, III… -> Nhìn vào ô Start at: sẽ thấy kết quả.
Cố gắng nghiên cứu bài này để sau này lỡ có được triệu tập viết code cho Office thì còn xoay sở được

[hirikarate]

Em đã viết được code và chạy ra kết quả đúng, nhưng không biết thuật giải có tối ưu chưa. Mong mấy huynh xem giúp ạ !

/*
IV: 4
V:  5
XL: 40
L:  50
XC: 90
C:  100
CD: 400
D:  500       1459 M CD L IX
M:  1000 //Max
MMMMM: 5000
*/


#include <stdio.h>
#include <conio.h>

void LaMa(int n);

void main()
{
    int n=0;
    clrscr();
    do
      {
         printf("n= ");
         scanf("%d",&n);
       }
    while(n<1);
    printf("So La Ma: ");
    LaMa(n);
    getch();
}

void LaMa(int n)
{
    switch(n)
         {
	case 40 : printf("IL "); break;
	case 50 : printf("L ");  break;
	case 90 : printf("XC "); break;
	case 100 : printf("C "); break;
	case 400 : printf("CD ");break;
	case 500 : printf("D "); break;
	case 900 : printf("CM ");break;
	default  :
		switch(n)
		   {
		        case 0 :                 break;
		        case 1 : printf("I");    break;
		        case 2 : printf("II");   break;
		        case 3 : printf("III");  break;
		        case 4 : printf("IV");   break;
		        case 5 : printf("V");    break;
		        case 6 : printf("VI");   break;
		        case 7 : printf("VII");  break;
		        case 8 : printf("VIII"); break;
		        case 9 : printf("IX");   break;
		        default:
			 if(n>1000 && n%1000!=0)
			    { LaMa((n/1000)*1000); LaMa(n%1000); return;}
			 else if(n%1000==0)
			           for(int i=1; i<=n/1000; i++) printf("M ");
			 else if(n<1000 && n>900)
			     { printf("CM "); LaMa(n-500); return;}
			 else if(n<900 && n>500)
			     { printf("D "); LaMa(n-500); return;}
			 else if(n<500 && n>400)
			     { printf("CD "); LaMa(n-400); return;}
			 else if(n<400 && n>100)
			     { printf("C "); LaMa(n-100); return;}
			 else if(n<100 && n>50 && n!=90)
			     { printf("L "); LaMa(n-50); return;}
			 else if(n<50 && n>10 && n!=40)
			     { printf("X "); LaMa(n-10); return;}
		   }
         }

}

[rox_rook]

Cố gắng nghiên cứu bài này để sau này lỡ có được triệu tập viết code cho Office thì còn xoay sở được

Kinh quá ^^ !
Cái này thì giải thuật tối ưu gì nhỉ ? Cứ switch mà làm tới thôi

[huynguyen]

Bài này khá thú vị và cũng khá đơn giản, giống như bài chia tiền vậy:

#include <iostream>
#include <cstring>
using namespace std;
int main(){
    cout <<"Nhap n: "; int n; cin >>n;
    string s;
    while (n >= 1000) {s += "M"; n -= 1000;}
    if (n >= 900) {s += "CM"; n -= 900;}
    if (n >= 500) {s += "D"; n -= 500;}
    if (n >= 400) {s += "CD"; n -= 400;}
    while (n >= 100) {s += "C"; n -= 100;}
    if (n >= 90) {s += "XC"; n -= 90;}
    if (n >= 50) {s += "L"; n -= 50;}
    if (n >= 40) {s += "XL"; n -= 40;}
    while (n >= 10) {s += "X"; n -= 10;}
    if (n >= 9) {s += "IX"; n -= 9;}
    if (n >= 5) {s += "V"; n -= 5;}
    if (n >= 4) {s += "IV"; n -= 4;}
    while (n >= 1) {s += "I"; n -= 1;}
    cout <<"Chuyen sang so la ma: " <<s <<endl;
    system("pause");
    return 0;
}

Trong giải thiết của bạn chia ko đủ các trường hợp xảy ra, bài của mình đã thiết kế đủ trường hợp rồi, nếu các bạn thấy thiếu thì bổ sung giúp nhé.

[kidkid]

uh giống bài chia tiền nè , không khó lắm vấn đề là thuật giải sao cho tối ưu thôi ,

[neverland87]

Hi,như vậy là tối ưu rồi, cái chính là không bỏ xót trường hợp thôi, còn thuật toán thì đa số dùng cấu trúc lựa chọn, do đó độ phức tạp của thuật toán luôn là 1 hằng số O(1).