Chuyển số thập phân thành số hữu tỉ ??

Liên hệ QC

Lệnh Hồ Đại Hiệp

Độc cô Cửu kiếm
Tham gia
20/10/08
Bài viết
299
Được thích
524
Nhân có bài này Tìm mối quan hệ giữa 2 nhóm số cho trước

Bài toán là : Có một số thập phân cho trước, ta biết rằng nó có thể được biểu diễn chính xác dưới dạng phân số (Số hữu tỉ), và mẫu số của nó sẽ <=10.000.000 (VD vậy thôi)

Vậy có cách nào tìm được chính xác phân số đó ??

VD :26.813/268.250 = 0,099955265610438
 
Nhân có bài này Tìm mối quan hệ giữa 2 nhóm số cho trước

Bài toán là : Có một số thập phân cho trước, ta biết rằng nó có thể được biểu diễn chính xác dưới dạng phân số (Số hữu tỉ), và mẫu số của nó sẽ <=10.000.000 (VD vậy thôi)

Vậy có cách nào tìm được chính xác phân số đó ??

VD :26.813/268.250 = 0,099955265610438

Tóm tắt lại đề bài
c là số thập phân. Tìm 2 số nguyên ab sao cho a/b=c (b<=10.000.000)

Cách giải :

Để giải quyết triệt để bài này, tôi có hướng giải như sau:
Bước 1

Tìm 2 số aabb sao cho aa/bb=c
dễ dàng tìm được aa, bb. Ví dụ c=0,001234 thì aa=12345bb=1000000
Bước 2
+ So sánh bb với 10.000.000
- Nếu bb<=10.000.000: đáp số a=aab=bb
+ Nếu bb>10.000.000: tìm uớc số chung lớn nhất cc của aabb.
- Nếu có ƯSCLN: đáp số a=aa/ccb=bb/cc
- Nếu không có ƯSCLN: bài toán vô nghiệm

Còn vướn chỗ làm sao tìm được ƯSCLN. Tức là phải giải quyết được vấn đề số nguyên tố. Các bạn có cách nào tìm nhanh dược các số nguyên tố nhỏ hơn a và b?
 
Upvote 0
Tại sao lại có số nguyên tố trong đó vậy thầy? Em có hai cách tình nhanh số nguyên tố (A và B). Và (B nhanh hơn A) nhưng (B chiếm nhiều dung lượng lưu trữ hơn A). Vậy tạm thời em đem cách A lên trước nha:
PHP:
Public Function SoNguyenTo(so As Single) As Boolean     Application.Volatile (False)     Dim i As Single     If so  2 And Int(so) Mod 2 = 0) Then Exit Function       SoNguyenTo = True     If so = 2 Or so = 3 Or so = 5 Or so = 7 Then Exit Function     For i = 3 To Int(Sqr(so)) Step 2         If so Mod i = 0 Then SoNguyenTo = False: Exit Function     Next End Function
Thầy dùng Function này để xác định SNT. Thân.
 
Lần chỉnh sửa cuối:
Upvote 0

Cách giải :

Để giải quyết triệt để bài này, tôi có hướng giải như sau:
Bước 1

Tìm 2 số aabb sao cho aa/bb=c
dễ dàng tìm được aa, bb. Ví dụ c=0,001234 thì aa=12345bb=1000000
Bước 2
+ So sánh bb với 10.000.000
- Nếu bb<=10.000.000: đáp số a=aab=bb
+ Nếu bb>10.000.000: tìm uớc số chung lớn nhất cc của aabb.
- Nếu có ƯSCLN: đáp số a=aa/ccb=bb/cc
- Nếu không có ƯSCLN: bài toán vô nghiệm

Còn vướn chỗ làm sao tìm được ƯSCLN. Tức là phải giải quyết được vấn đề số nguyên tố. Các bạn có cách nào tìm nhanh dược các số nguyên tố nhỏ hơn a và b?
Giải thuật chính xác là như này đây, nhưng theo em thì nếu bb<10.000.000 thì ta vẫn nên tối giản cho đẹp(đương nhiên là nếu tác giả không yêu cầu thì thôi cho nhanh :)). Còn vấn đề tối giản thì thay vì tìm ƯSCLN thì em lặp để chia dần. Đến đây mới lại chợt nhớ ra là mình for từ Số nhỏ - 1 về căn bậc 2 với step là -1 thì số sẽ giảm nhanh hơn. Nhưng thôi xin phép không post lại code nữa, bác nào thử thay lại rồi test xem tốc độ có cải thiện hơn không nhé.
 
Upvote 0
Tại sao lại có số nguyên tố trong đó vậy thầy?
Mình nhớ hồi học số học ở phổ thông, muốn tối giản phân số thì phân tích tử và mẫu số thành tích các số nguyên tố, rồi đơn giản các số nguyên tố giống nhau trên tử và mẫu số.
 
Upvote 0
Mà hổi đó chỉ phân tích thành các SNT nhỏ hơn 20 thôi. Giờ đây thì phải nhỏ SQRT(số) đó lận. Thật là làm khó người quá và quá trình quét sẽ lâu hơn nữa. Vì còn phải xem có phân tích thành cặp số mấy nữa. Lại phải quét! Thật là mệt.... Nếu có thì cho em xin thuật toán đi! thì tốt hơn thầy ơi! Thân.
 
Lần chỉnh sửa cuối:
Upvote 0
Đây là bài toán chính

Thực ra bài toán này chỉ là một phần của bài toán :

Giải phương trình 3 ẩn, nếu nghiệm là phân số thì biểu hiện dưới dạng phân số.

Vì bài của bác BNTT ( Tìm mối quan hệ giữa 2 nhóm số cho trước) có mấy ẩn giải ra bằng các hàm định thức, tuy nhiên đó là số thập phân. Vậy làm cách nào để có thể lấy số chính xác của nghiệm.

Cảm ơn nhiều.

Giải thuật chính xác là như này đây, nhưng theo em thì nếu bb<10.000.000 thì ta vẫn nên tối giản cho đẹp(đương nhiên là nếu tác giả không yêu cầu thì thôi cho nhanh :)). Còn vấn đề tối giản thì thay vì tìm ƯSCLN thì em lặp để chia dần. Đến đây mới lại chợt nhớ ra là mình for từ Số nhỏ - 1 về căn bậc 2 với step là -1 thì số sẽ giảm nhanh hơn. Nhưng thôi xin phép không post lại code nữa, bác nào thử thay lại rồi test xem tốc độ có cải thiện hơn không nhé.

Thực ra ta cũng nên cho giới hạn của mẫu số. Theo như của excel thể hiện thì ta nên cho là (9*10^15)

Cảm ơn mọi người

--CV--
 
Upvote 0
Còn vướn chỗ làm sao tìm được ƯSCLN. Tức là phải giải quyết được vấn đề số nguyên tố. Các bạn có cách nào tìm nhanh dược các số nguyên tố nhỏ hơn a và b?

Mà hổi đó chỉ phân tích thành các SNT nhỏ hơn 20 thôi. Giờ đây thì phải nhỏ SQRT(số) đó lận. Thật là làm khó người quá và quá trình quét sẽ lâu hơn nữa. Vì còn phải xem có phân tích thành cặp số mấy nữa. Lại phải quét!
Thật là mệt....
Nếu có thì cho em xin thuật toán đi! thì tốt hơn thầy ơi!
Thân.

Tìm ƯSCLN của 2 số: dùng hàm này
Thuật Toán Euclid tìm ƯSCLN(a,b) - Tìm Ước Chung Lớn Nhất giữa 2 số a và b:
Gọi số lớn là a, số nhỏ là b

Lấy a chia cho b (số lớn chia cho số nhỏ) được thương = q, số dư = r ( b > r ).
+ Nếu r = 0 => ƯSCLN(a,b) = b
+ Nếu r <> 0, thì lấy b chia cho r (số lớn chia cho số nhỏ)
Và cứ thế tiếp tục ...
PHP:
Function UCLN(a As Long, b As Long) As Long
Dim Sl As Long, Sn As Long, Tmp As Long
If a > b Then
    Sl = a: Sn = b
    Else
        Sl = b: Sn = a
End If
boyxin:
Tmp = Sl Mod Sn
If Tmp > 0 Then
    Sl = Sn: Sn = Tmp: GoTo boyxin
End If
UCLN = Sn
End Function
 
Lần chỉnh sửa cuối:
Upvote 0
Chú ý: Các bác test thì nên test theo hướng xuất phát từ 1 số thập phân thay cho từ 1 phân số. Vì nếu test xuất phát từ 1 phân số thì trong quá trình chia để trả về kết quả có thể excel đã làm tròn mất rồi.

Em làm như sau:
Bước 1: chuyển số thập phân về dạng phân số thập phân (VD: 0.123 = 123/1000 = Tuso/Mauso)
Bước 2: Tìm ƯSCLN(Tuso,Mauso)
Bước 3: Chia cả Tuso, Mauso cho ƯSCLN đã tìm được ở bước 2 => Ta được phân số tối giản


  1. Các bác Test giùm xem cách này thế nào?
  2. Các bác phát triển giúp để có thể test với số có nhiều chữ số hơn
 

File đính kèm

Lần chỉnh sửa cuối:
Upvote 0
Test!

  1. các bác test giùm xem cách này thế nào?
  2. các bác phát triển giúp để có thể test với số có nhiều chữ số hơn
Kết quả test: 0.123456789 = 123456789 / 1000000000
Kết quả dùng hàm của HVL: 0.123456789 = 13566680 / 109890109
 
Upvote 0
Loai hoay cả ngày hôm nay theo hướng phân tích tử số và mẫu số ra thừa số nguyên tố rồi tối giản. Ví dụ:
tử số ts=a*b*c*d
mẫu số ms=a*c*e*f
(với a, b, c, d, e, f là các số nguyên tố)
ts / ms = a*b*c*d / a*c*e*f = b*d / e*f (đơn giản được ac)

Nhưng làm sao phân tích được số ts, ms ra thừa số nguyên tố ? Phải sử dụng vòng lặp duyệt. Tính bỏ cuộc vì cách giải cũng không khác anh em mấy.
Tình cờ phát hiện ra mình đâu cần tìm chi nhiều số nguyên tố, vì các số dạng 10, 100, 1000, ..., 10000000 chỉ là tích của 2 số nguyên tố 2 và 5. Như vậy chỉ cần đơn giản tử số và mẫu số cho 2 và 5 mà thôi, không cần duyệt các số khác.
Bài toán quy về như sau:
1. Chuyển số thập phân về dạng phân số có tử số ts và mẫu số ms=10^n. Ví dụ 0,0123 > 123/10000 (ts=123, ms=10000)
2. Dùng vòng lặp chia tsms cho 2, 5 (nếu cả 2 chia hết). Lặp cho đến khi nào 2, 5 không chia hết cho cả ts, ms thì kết thúc

Mã:
Function SoHuuTy(soThapPhan As Double) As String
Dim soTren As Long, soDuoi As Long, nCham As Long
Dim strNum As String
strNum = Trim(Str(soThapPhan))
nCham = InStr(1, strNum, ".")
If nCham = 0 Then
  SoHuuTy = strNum & "/1"
  Exit Function
ElseIf nCham = 1 Then
  soTren = Val(Mid(strNum, 2))
  soDuoi = 10 ^ (Len(strNum) - 1)
Else
  soTren = Replace(strNum, ".", "")
  soDuoi = 10 ^ (Len(strNum) - InStr(1, strNum, "."))
End If
SoHuuTy = soTren & " / " & soDuoi
If soTren > 1 Then
  Do
    If soTren >= 2 And soTren Mod 2 = 0 Then
      soTren = soTren / 2
      soDuoi = soDuoi / 2
    ElseIf soTren >= 5 And soTren Mod 5 = 0 Then
      soTren = soTren / 5
      soDuoi = soDuoi / 5
    Else
      Exit Do
    End If
  Loop
End If
SoHuuTy = soTren & "/" & soDuoi
End Function
 
Upvote 0
Kết quả test: 0.123456789 = 123456789 / 1000000000
Kết quả dùng hàm của HVL: 0.123456789 = 13566680 / 109890109

Trong thực tế, dễ thấy

attachment.php
 

File đính kèm

  • Problems.JPG
    Problems.JPG
    10.8 KB · Đọc: 83
Lần chỉnh sửa cuối:
Upvote 0
Loai hoay cả ngày hôm nay theo hướng phân tích tử số và mẫu số ra thừa số nguyên tố rồi tối giản. Ví dụ: tử số ts=a*b*c*d mẫu số ms=a*c*e*f (với a, b, c, d, e, f là các số nguyên tố) ts / ms = a*b*c*d / a*c*e*f = b*d / e*f (đơn giản được ac) Nhưng làm sao phân tích được số ts, ms ra thừa số nguyên tố ? Phải sử dụng vòng lặp duyệt. Tính bỏ cuộc vì cách giải cũng không khác anh em mấy. Tình cờ phát hiện ra mình đâu cần tìm chi nhiều số nguyên tố, vì các số dạng 10, 100, 1000, ..., 10000000 chỉ là tích của 2 số nguyên tố 2 và 5. Như vậy chỉ cần đơn giản tử số và mẫu số cho 2 và 5 mà thôi, không cần duyệt các số khác. Bài toán quy về như sau: 1. Chuyển số thập phân về dạng phân số có tử số ts và mẫu số ms=10^n. Ví dụ 0,0123 > 123/10000 (ts=123, ms=10000) 2. Dùng vòng lặp chia tsms cho 2, 5 (nếu cả 2 chia hết). Lặp cho đến khi nào 2, 5 không chia hết cho cả ts, ms thì kết thúc
Cảm ơn thầy nhiều nhưng theo em thầy nên nghĩ ngơi thì hơn. Cần gì bận tâm quá vậy. Mà nói thật cách của thầy có nhiều giới hạn và chỉ giải được cho số thập phân có 11 chữ số thôi. Nhiều hơn là #Value! rồi. Và chỉ chia cho 2 và cho 5 thôi vậy cũng không ổn lắm. Em cung cấp thêm 1000 SNT đầu tiên cho thầy làm ví dụ cho vui nha! Nếu rãnh thầy xét giùm em những số lớn hơn. Còn không thì những code ở bài trên cũng đủ rồi và tương đối không sai gì mấy. Ví dụ như code này:
PHP:
Function PhanSo(So As Double) As String     Application.Volatile (False)     Dim i As Double, Temp As String     For i = 1 To 10 ^ Val(Len(So))         If Round(So * i, 10) = Round(So * i, 0) Then             PhanSo = Format(Round(So * i, 0), "#,##0") & "/" & Format(i, "#,##0")             Exit Function         End If     Next End Function
Có thể tính được cho số =121/14641 và kết quả là 1/121. Hoặc =169/17303 và kết quả là 13/1331. Vậy cũng đúng chứ nhỉ? Mặc dù những số quá lớn thì nó quét lâu nhưng kết quả đúng cho các số nhỏ cũng đủ dùng chứ không đến nỗi đâu bác. Thân.
 

File đính kèm

Lần chỉnh sửa cuối:
Upvote 0
Trong thực tế, dễ thấy

attachment.php
Đây chẳng qua là boyxin bị bác Bill lừa thôi, thực tế thì khi tính bởi excel nó đã bị làm tròn nên bác nghĩ 13566680/109890109=0.123456789 thôi, bác thử dùng Calculator của window tính thử xem nó ra bao nhiêu. Em tính thì nó ra thế này này 0.12345678899999999089999992629.
- To Po_Pi: Dùng vòng lặp từ đầu đến cuối thì quá lâu, và khi bác dùng Round thì vẫn bị giới hạn bởi sai số người dùng. Với con số 0.123456789 của bác HVL đưa ra thì code của bác chạy lâu quá nên không rõ đưa ra kết quả thế nào.
 
Upvote 0
Chuyển số thập phân thành phân số tối giản

Theo em, chủ đề này đến đây có thể coi là tạm ổn

Bước 1: chuyển số thập phân về dạng phân số thập phân (VD: 0.123 = 123/1000 = Tuso/Mauso)
  1. Số thập phân = x
  2. Tử số = Replace(x, ".", "")
  3. Mẫu số = Tử số / x
Bước 2: Tìm ƯSCLN(Tử số,Mẫu số)
Thuật Toán Euclid tìm ƯSCLN(a,b) - Tìm Ước Chung Lớn Nhất giữa 2 số a và b:
Gọi số lớn là a, số nhỏ là b

Lấy a chia cho b (số lớn chia cho số nhỏ) được thương = q, số dư = r ( b > r ).
+ Nếu r = 0 => ƯSCLN(a,b) = b
+ Nếu r <> 0, thì lấy b chia cho r (số lớn chia cho số nhỏ)
Và cứ thế tiếp tục ...

Bước 3
: Chia cả Tử số, Mẫu số cho ƯSCLN đã tìm được ở bước 2 => Ta được phân số tối giản
-----------------------------------------------------------------------------------

Toàn bộ code chuyển từ số thập phân về dạng phân số (tối giản) như sau:

(NGẮN GỌN, ĐƠN GIẢN, TÍNH TOÁN ÍT, CHÍNH XÁC => TỐC ĐỘ CỰC NHANH)
Còn hạn chế: chuyển đổi được số thập phân có số chữ số <11 (kể cả trước và sau dấu thập phân)
PHP:
Function STP_PS(x As Double) As String
    Dim Tu As Long, Mau As Long
    Tu = Replace(x, ".", ""): Mau = Tu / x
    STP_PS = Tu / UCLN(Tu, Mau) & " / " & Mau / UCLN(Tu, Mau)
End Function
Function UCLN(a As Long, b As Long) As Long
Dim r As Long
If a > b Then
    r = a Mod b
    Else: r = b Mod a
End If
If r = 0 Then
    UCLN = Application.Min(a, b)
    Else: UCLN = UCLN(Application.Min(a, b), r)
End If
End Function
 
Lần chỉnh sửa cuối:
Upvote 0
Mình xin gửi thêm một cách :
PHP:
Function SoSangPhanso(So As Double) As String
Dim Tu As Double, Mau As Double, Tuso As Double, Mauso As Double
Dim Pos As Byte, Digit As Byte, Temp As Double
Pos = InStr(1, So, ".", 1) + InStr(1, So, ",", 1)
Digit = Len(Mid(So, Pos + 1, 15))
Mau = 10 ^ Digit: Mauso = Mau
Tu = So * Mauso: Tuso = Tu
Do
    If Tu < Mau Then
        Temp = Tu: Tu = Mau: Mau = Temp
    End If
    Tu = Tu Mod Mau
Loop While Tu * Mau <> 0
SoSangPhanso = Tuso / (Tu + Mau) & "/" & Mauso / (Tu + Mau)
End Function

Theo mình nghĩ, rất ít khi người ta chuyển từ số thập phân sang phân số một cách chính xác. Mà chỉ chuyển thành phân số tương đối với một giới hạn sai số cho phép nhất định.

Bản thân số thập phân trước khi chuyển, nó đã là một số chưa chính xác vì đã được làm tròn từ kết quả của một phép chia dư nào đó. Nếu như ta dùng số này để chuyển thành phân số chính xác thì phân số này cũng không chính xác.

Như vậy, việc chuyển từ số thập phân sang phân số cho kết quả tương đối với một sai số nào đó (do ta chọn) có lẽ sẽ thực tiễn hơn.

VD : 1/3=0.333333333333333

dùng phép chuyển đổi chính xác : 0.333333333=333333333/1000000000

(ta không thể có nhiều hơn nữa số 3 sau phẩy vì giới hạn của biến )

Ở đây số ta cần lại là 1/3 chứ không phải là 333333333/1000000000

Vậy, ta sẽ giải quyết bài toán này với điều kiện : Tìm số hữu tỷ từ một phân số cho trước với một sai số cho phép :
PHP:
Function SoSangPhanso(So As Double, Optional Saiso As Double = 0) As String
 
Upvote 0
Và đây là kết quả :
Kết quả trả về rất gần với kết quả mong muốn, tốc độ lại nhanh.
Nếu như muốn kết quả trả về chính xác thì tùy theo trường hợp mà ta chon sai số nhỏ một tí.
VD

Cfract(370.333333333333)=1111/3
Cfract(0.333333333333333,0.00001)=1/3
Cfract(3.14285714285714,0.00001)=22/7

PHP:
Function CFract(So As Double, Optional Saiso As Double = 0) As String
Dim Tuso As Double, Mauso As Double
Do
    Tuso = Tuso + 1
    Mauso = Round(Tuso / Left(So, 15), 0)
    If Mauso = 0 Then Mauso = 1
Loop While Mauso = 1 Or Abs(Left(Tuso / Mauso, 15) - Left(So, 15)) > Saiso
CFract = Tuso & "/" & Mauso
End Function
 

File đính kèm

Lần chỉnh sửa cuối:
Upvote 0
Mấy bác còn nghiên cứu vấn đề này nữa à!
Em tìm mãi nhưng vẫn chưa có đáp số như ý muốn được.
Với code của bác hoangdanh282vn thì Tử số 11, mẫu số 121 thì nó toàn ra 100/11 không hà! Hiện chưa biết làm sao để ra được kết quả 1/11.
Bác thử test lại xem.
Thân.
 
Upvote 0
Mấy bác còn nghiên cứu vấn đề này nữa à!
Em tìm mãi nhưng vẫn chưa có đáp số như ý muốn được.
Với code của bác hoangdanh282vn thì Tử số 11, mẫu số 121 thì nó toàn ra 100/11 không hà! Hiện chưa biết làm sao để ra được kết quả 1/11.
Bác thử test lại xem.
Thân.

Cám ơn Po_Pikachu!

Minh đã test lại và nhận thấy rằng, do chức năng AutoFormat Number của excel nên dùng hàm Left sẽ bị sai, chỉnh lại một tí :

Với Hàm CFract ngắn gọn này, chuyển đổi số cực kỳ nhanh, chính xác và không bị giới hạn số lẻ (Với một sai số hợp lý)

Cfract(0.333333333333333,0.0000000001) = 1/3
Cfract(0.666666666666667,0.0000000001) = 2/3
Cfract(0.0909090909090909,0.0000000001) = 1/11
Cfract(1.01801801801802,0.0000000001) = 113/111
Cfract(1091.83826838268,0.0000000001) = 12131415/11111

PHP:
Function CFract(So As Double, Optional Saiso As Double = 0) As String
Dim Tuso As Double, Mauso As Double
Do
Tuso = Tuso + 1
Mauso = Round(Tuso / So, 0)
If Mauso = 0 Then Mauso = 1
Loop While Mauso = 1 Or Abs(Tuso / Mauso - So) > Saiso
CFract = Tuso & "/" & Mauso
End Function
 

File đính kèm

Upvote 0
Xin được sửa code của boyxin 1 chút để không bị giới hạn bởi 11 chữ số.
Mã:
Function STP_PS(x As Double) As String
    Dim Tu As Double, Mau As Double
    Tu = Replace(x, ".", ""): Mau = Tu / x
    STP_PS = Tu / UCLN(Tu, Mau) & " / " & Mau / UCLN(Tu, Mau)
End Function
Function UCLN(a As Double, b As Double) As Long
Dim r As Double
If a > b Then
    r = a - WorksheetFunction.Floor(a, b)
Else
    r = b - WorksheetFunction.Floor(b, a)
End If
If r = 0 Then
    UCLN = Application.Min(a, b)
    Else: UCLN = UCLN(Application.Min(a, b), r)
End If
End Function
Có lẽ đây là cách ổn nhất rồi, cách của hoangdanh vẫn duyệt toàn bộ, không đảm bảo về mặt tốc độ. Nếu với số 0.123456789 mà không có sai số thì treo ngay.
 
Upvote 0
@hoangdanh282vn: Code của bác chạy rất tốt. Mặt dù có lúc nó rút gọn chẳng đúng gì hết. Ví dụ như: =10/542694 KQ: 2/108539. Đúng ra nó nên chia 2 thì lại chia cho 5. Chẳng hiểu nữa.

@rollover79: Code của bác thì chỉ áp dụng cho các số thập phân thôi còn thập phân của một phép chia thì nó toàn báo lỗi #Value!.

Và đáp số cũng không chính xác gì hết. Ví dụ:
Số|hoangdanh282vn|rollover79
0.222273|7782/35011|222273 / 1000000
Thân.
 
Lần chỉnh sửa cuối:
Upvote 0
Web KT

Bài viết mới nhất

Back
Top Bottom