Tìm ý tưởng để thực hiện phép chia trên số lớn?

Anh down cuốn Tài liệu giáo khoa chuyên tin quyển 1 trang 24 trở đi có nói về xử lý số nguyên lớn, anh xem thử.

Chia như hồi học cấp 1 ấy bạn. VD: 475 / 5
4 / 5 ko đc, lấy tiếp chữ số sau nó được 47
47 / 5 = 9 dư 2
2 / 5 ko được, lấy tiếp chữ số sau nó
25 / 5 = 5
vậy kết quả là 95

Bạn có thể tham khảo code của mình bigint divmod. Dùng thuật toán recrusive để chia( hình như chậm hơn cả naive)

Một bạn trả lời trên page

a1a2…an/b1…bm( Số bị chia và số chia có n và m chữ số)

B1. Dùng 2 chuỗia a và b chứa các chữ số của số bị chia và số chia, các mảng có số pt tương ứng là n và m
B2. Lấy m phần tử đầu của chuỗi a được số a1, đem số này chia b, vì 2 số đều lớn nên có thể dùng vòng for để lặp từ 1 đến 9, nếu i = 1…9, mà ib > a1 thì được thương bằng i-1 và số dư là t1 = a1 -b(i-1)

B3. Có số dư t1 từ bước 2, tiếp túc lấy t1*10+ số thứ m+1 trong chuỗi a ban đầu để được số chia a2, lại dùng vòng for để lăp và lai tính đc số dư t2, tiếp tục như vậy đến khi nào đến phần tử n trong chuỗi a thì dừng. Có thể tiếp tục nếu muốn lấy số thập phân

Cách này khả thi khi số bị chia nhỏ thôi

Cách đơn giản dễ code (chắc là vậy )
a/b = số lần a=a-b đến khi nào a < b
Với trg hợp a < b thì nhớ thêm 1 và trừ.
Ví dụ nhé:

5/2
kq =0;
5-=2 = 3; kq=1;
3-=2 = 1; kq=2;
-> 5 /2 = 2 dư 1.

Nhưng nếu muốn thập phân ta làm tiếp

do 1 < 2 -> nhớ 1 -> thành 10/2
-> kq = 2.[kq của 10/2]
10 -=2 = 8 kq' = 1;
8 -=2 = 8 kq' = 2;
6-= 2 = 4 kq' = 3;
4-= 2 = 2 kq' = 4;
2-=2 = 0 kq'=5; dừng. (do 0/2 = 0)

Ví dụ 1/3

1 < 3 nên ta mượn 1 -> 10/3
10 -=3 = 7 kq = 1;
7-=3 = 4 kq=2;
4-=3 = 1 kq=3;
-> kq 10/3 = 3 dư 1.

Tiếp tục phần thập phân:

1 < 3 nên mượn 1 = 10
10 / 3 = 3 dư 1 như đã tính.

Nhưng lúc này dó chúng ta ở phần thập phân rồi nên khỏi cần dấu “chấm”
Nên tiếp tục mượn 1 và chia.
Thì trục trặc ở đây là 10/3 = 3,(3)
Nên kết hợp với thuật toán tìm chu kỳ nữa là xong ^^

E xin chân thành cảm ơn những chia sẻ của các a ạ <3