Chào mọi người. Mình đang làm bài +, -, *, / số nguyên cực lớn. Mình đã giải được thuật toán: +, -, * rồi.
Làm đến / thì thấy bí quá. Các bạn góp ý giúp mình về ý tưởng và cách làm với. Mình chỉ cần hướng cách để giải thôi chứ không cần code. Xin cảm ơn!
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ử.
3 Likes
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
2 Likes
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) 
1 Like
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
2 Likes
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 ^^
6 Likes
E xin chân thành cảm ơn những chia sẻ của các a ạ <3
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?