Dạng thập phân của phân số | Giải đề HSG tin học 12 | năm 2012-2013

Thứ hai - 08/05/2023 03:47 1.975 0

Tiếp theo câu 3 của đề học sinh giỏi tin học 12 của tỉnh Nghệ An năm 2012-2013. Đây là một bài xử lý khi chia tử với mẫu của một phân số thì nó là số thập phân hữu hạn hay vô hạn tuần hoàn. Dây cũng là một trong những bài xử lý số học khá thú vị. Mời các bạn cùng tham khảo nhé.

Đề bài

Câu 3. Dạng thập phân của phân số.
Ngày nghỉ cuối tuần Nam rất muốn đi chơi công viên. Mẹ ra điều kiện nếu Nam biết cách chuyển một phân số sang dạng thập phân (hữu hạn hoặc vô hạn tuần hoàn) thì sẽ được đi chơi. Bạn hãy giúp bé Nam nhé.
Yêu cầu: Cho 2 số nguyên dương P và Q (P, Q £ 10⁵). Hãy đưa ra dạng thập phân (hữu hạn hoặc vô hạn tuần hoàn) của phân số $\frac{P}{Q}$ .
Dữ liệu: Vào từ file văn bản Bai3.inp: Chỉ một dòng duy nhất chứa 2 số nguyên dương P và Q.
Kết quả: Ghi ra file văn bản Bai3.out: Chỉ một dòng duy nhất là dạng thập phân của phân số $\frac{P}{Q}$ theo quy cách như các ví dụ dưới đây:

Bai3.inp	Bai3.out	Bai3.inp	Bai3.out	Bai3.inp	Bai3.out	Bai3.inp	Bai3.out
32567 125	260.536	367 12	30.58(3)	67 737	0.(09)	200 5	40

Code mẫu bằng pascal

const   fi      =       'Bai3.inp';
        fo      =       'Bai3.out';
        max  	= 100000;
type   	m1		= array[0..max] of longint;
var             t,m     : longint;
                l1,l2   : longint;
        	a,d	: m1;
        	vhth  	: boolean;
                f       : text;
procedure nhap;
begin
  assign(f,fi);
  reset(f);
  readln(f,t, m);
  close(f);
end;
procedure chia;
var r: longint;
begin
  fillchar(a,sizeof(a),0);
  fillchar(d,sizeof(d),0);
  l1:= 0; {vi tri chu so thap phan bat dau cua chu ky}
  l2:= 0; {so chu so o phan thap phan ke ca truoc chu ky va trong chu ky}
  vhth:= true; {xac nhan co vo han tuan hoan hay khong}
  a[0]:= t div m; {phan nguyen cua phan so  t/m}
  t   := t mod m; {phan du dau tien de tao ra phan thap phan}
  if t=0 then vhth:= false {neu phan du bang 0 thi phan so la so nguyen}
  else
  if t>0 then {neu phan du khac khong thi tiep tuc chia tao ra phan thap phan}
  repeat
    inc(l2);
    d[t]:= l2;{ d danh dau: khi du la t,  chia tiep duoc chu so thap phan thu  l2}
    t   := t * 10;
    a[l2]:= t div m; {mang ket qua A:  Tu A[i]  la chu so  thap phan thu  i }
    t   := t mod m; {du moi}
     if t=0 then begin {du moi bang 0, thi phan so la thap phan huu han}
 	 vhth:= false; {xac nhan la thap phan huu han}
	 break;
     end;
     if d[t]>0 then l1:= d[t]; {da gap so du cu tao ra chu so thap phan o}
     	{vi tri d[t],  vay co chu ki va suy ra  vi tri chu so bat dau cua chu ki la L1=d[t] }
  until d[t]>0;
end;
procedure ghi;
var f: text;i: longint;
begin
  assign(f,fo);  rewrite(f);
  write(f,a[0]); {ghi phan nguyen}
  if l2<>0 then write(f,'.'); {neu co phan thap phan thi ghi dau cham}
  if not vhth then begin {neu khong co chu ki}
    for i:=1 to l2 do write(f,a[i]);
  end
  else begin {neu co chu ki}
    for i:=1 to l1-1 do
      write(f,a[i]); {phan thap phan truoc chu ki}
    if l1<>0 then begin
      write(f,'(');
      for i:=l1 to l2 do write(f,a[i]); {phan chu ki}
      write(f,')');
    end;
  end;
  close(f);
end;
BEGIN
  nhap;
  chia;
  ghi;
END.

Giải thích

Chúng ta chia như thời đi học tiểu học thôi. Trong code đã chú thích rõ rồi ha.

Giải quyết bằng Python

Để chuyển một phân số thành dạng thập phân, ta có thể sử dụng thuật toán chia. Đầu tiên, ta tính phần nguyên của thương bằng cách lấy phần nguyên của `P/Q`. Sau đó, ta tính phần dư của `P/Q` và nhân nó với 10 để có được số tiếp theo của phần thập phân. Lặp lại quá trình trên với phần dư mới để tính các số phần thập phân tiếp theo cho đến khi phần dư bằng 0 hoặc đến khi ta đã tính được đủ số thập phân tối đa cho phép.

Tuy nhiên, nếu phần dư của thương `P/Q` xuất hiện lặp lại, tức là nếu ta đã tính được mãi mãi vẫn chỉ ra phần thập phân giống với một mẫu lặp, thì phân số đó sẽ là một số tuần hoàn vô hạn. Trong trường hợp này, ta cần phải lưu trữ lại số lần xuất hiện của mẫu lặp và lặp lại quá trình trên cho đến khi tìm được một mẫu tương tự như trước đó. Để xác định các số hữu hạn và tuần hoàn, ta cần sử dụng 3 biến: `integerPart` (phần nguyên), `decimalPart` (phần thập phân) và `loopPart` (phần tuần hoàn).

Đầu tiên ta xây dựng hàm chia xử lý chuyển đổi phân số thành số thập phân như sau:

Hàm chuyển đồi phân số thành số thập phân

def fraction_to_decimal(P, Q):
    if P == 0:
        return "0"
    integerPart = "" if P * Q > 0 else "-"  # Phần nguyên của kết quả (có thể là số âm)
    P, Q = abs(P), abs(Q)  # Chuyển đổi số âm thành số dương
    integerPart += str(P // Q)  # Tính phần nguyên
    decimalPart = ""  # Phần thập phân
    loopPart = ""  # Phần tuần hoàn
    modDict = {}  # Dictionary lưu trữ phần dư và vị trí của nó
    mod = P % Q  # Tính phần dư ban đầu
    while mod != 0 and mod not in modDict:
        modDict[mod] = len(decimalPart)  # Lưu trữ phần dư và vị trí của nó
        mod *= 10  # Đưa phần dư lên hàng đơn vị để tính phần thập phân tiếp theo
        decimalPart += str(mod // Q)  # Tính phần thập phân
        mod %= Q  # Tính phần dư tiếp theo
    if mod != 0:
        loopStartIndex = modDict[mod]  # Lấy vị trí bắt đầu của phần tuần hoàn
        loopPart = "(" + decimalPart[loopStartIndex:] + ")"  # Lấy phần tuần hoàn
        decimalPart = decimalPart[:loopStartIndex]  # Lấy phần hữu hạn
    else:
        decimalPart = decimalPart  # Không có phần thập phân tuần hoàn
    return integerPart + (("."+decimalPart) if decimalPart != "" else "") + loopPart  # Trả về kết quả cuối cùng

Hàm `fraction_to_decimal(P, Q)` nhận vào hai số nguyên dương `P` và `Q` biểu diễn phân số cần chuyển đổi. Hàm trả về dạng thập phân tương ứng, có thể là một số hữu hạn hoặc tuần hoàn.

Lưu ý rằng đối với số âm, ta cần xác định phần âm trong dạng thập.

Code đầy đủ bằng Python

def fraction_to_decimal(P, Q):
    if P == 0:
        return "0"
    integerPart = "" if P * Q > 0 else "-"  # Phần nguyên của kết quả (có thể là số âm)
    P, Q = abs(P), abs(Q)  # Chuyển đổi số âm thành số dương
    integerPart += str(P // Q)  # Tính phần nguyên
    decimalPart = ""  # Phần thập phân
    loopPart = ""  # Phần tuần hoàn
    modDict = {}  # Dictionary lưu trữ phần dư và vị trí của nó
    mod = P % Q  # Tính phần dư ban đầu
    while mod != 0 and mod not in modDict:
        modDict[mod] = len(decimalPart)  # Lưu trữ phần dư và vị trí của nó
        mod *= 10  # Đưa phần dư lên hàng đơn vị để tính phần thập phân tiếp theo
        decimalPart += str(mod // Q)  # Tính phần thập phân
        mod %= Q  # Tính phần dư tiếp theo
    if mod != 0:
        loopStartIndex = modDict[mod]  # Lấy vị trí bắt đầu của phần tuần hoàn
        loopPart = "(" + decimalPart[loopStartIndex:] + ")"  # Lấy phần tuần hoàn
        decimalPart = decimalPart[:loopStartIndex]  # Lấy phần hữu hạn
    else:
        decimalPart = decimalPart  # Không có phần thập phân tuần hoàn
    return integerPart + (("."+decimalPart) if decimalPart != "" else "") + loopPart  # Trả về kết quả cuối cùng
# Đọc dữ liệu vào
with open('Bai3.inp', 'r') as f:
    P, Q = map(int, f.readline().strip().split())

# Chuyển đổi phân số thành dạng thập phân
result = fraction_to_decimal(P, Q)

# Ghi kết quả vào file
with open('Bai3.out', 'w') as f:
    f.write(result)