Implement thuật toán cộng trừ nhân chia số nguyên lớn

PHP hay JS cho nhanh nhỉ?
Thôi chả code đâu, trình bày lại ý tưởng thôi. Cũng đơn giản mà, chỉ có cái chia hai số nguyên lớn là loằng ngoằng một chút thôi à.

Cộng:
aaaaaaaaaaaaaaaaaaaa
bbb

Bước 1: thêm 0 vào bên trái cho dài bằng nhau
aaaaaaaaaaaaaaaaaaaa
00000000000000000bbb

Bước 2: Khởi tạo 1 biến nhớ n = 0, xâu r rỗng. Cộng từ phải qua trái, các cặp chữ số với thêm cả biến nhớ n. Nếu tổng c (a+b+n) lớn hơn 9 thì lấy nó trừ đi 10 thu được c và gán lại biến nhớ n = 1 (không bao giờ nhớ được lên tận 2 vì 9 + 9 + 1 cũng chỉ là 19 ^^). Nếu tổng c nhỏ hơn 10 thì thu được c và gán biến nhớ n = 0. Lưu giá trị c, nhét vào sau r. Sau khi cộng đến cặp chữ số bên trái nhất, nếu nhớ còn là 1 thì thêm 1 vào sau r.

Bước 3: Đảo ngược xâu r, ta có tổng.

Thuật toán chia hai số nguyên lớn:

Chia 12415 cho 23

1 2 4 1 5 chia 2 3 0 0
0 0

23 có 2 chữ số. Lấy 12 chia cho 23, được 0, dư 12. Hạ 4 xuống

1 2 4 1 5 chia 2 3 0 0
0 0 0
1 2 4 0 0

124 chia cho 23 được thương là 5, dư là 9. Hạ 1 xuống

Làm sao tính 124 chia cho 23 được thương và dư là bao nhiêu?

Bước 1. Gán thương t = 0; a = 124; b = 023

Bước 2. Nếu a nhỏ hơn b thì thương là t và dư là a

Bước 3. Gán a = a – b và tăng t lên 1

Quay lại bước 2.

1 2 4 1 5 chia 2 3 0 0
0 5
1 2 4
9 1

Làm tương tự cho đến khi không còn chữ số nào để hạ xuống thì thương là dãy số bên trái (cắt bỏ 0 ở bên trái), số dư là dãy số bên phải.

1 2 4 1 5 chia 2 3
0 5 3 9
1 2 4
9 1
2 2 5
1 8

20 thoughts on “Implement thuật toán cộng trừ nhân chia số nguyên lớn”

  2. huypv

    Đúng “thuật toán” cộng trừ nhân chia này được học từ tiểu học, được thầy cô/dạy hướng dẫn thực hiện tính thế nào thì chỉ cần code theo đúng như thế là ok.

Comments are closed.