Phép Chia Lấy Dư Trong C - Toán Tử Chia Lấy Phần Dư Trong C++

Tóm Tắt

1. Chút kiến thức căn bản cần chuẩn bị

1.1) Một vài định nghĩa cơ bản về số học

Khi ta nói rằng chia hết cho (, là các số nguyên) thì ta viết một cách ngắn gọn như sau: . Nghĩa là . = ( là số nguyên). Một số nguyên là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó. Một số nguyên nếu không phải là số nguyên tố thì được gọi là hợp số.

Bạn đang xem:

1.2) Định lý

Nội dung 1. Chút kiến thức căn bản cần chuẩn bịKhi ta nói rằng chia hết cho (, là các số nguyên) thì ta viết một cách ngắn gọn như sau: . Nghĩa là . = ( là số nguyên). Một số nguyên là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó. Một số nguyên nếu không phải là số nguyên tố thì được gọi là hợp số.Bạn đang xem: Phép chia lấy dư trong c

Với a, b, c, x, y là các số nguyên, thì:

Nếu và thì . Nếu và thì . Nếu và thì .

Việc chứng minh các định lý trên không quá phức tạp, mình sẽ nhường công việc thú vị này cho bạn đọc. Nếu bạn có thắc mắc gì hãy thoải mái comment xuống bên dưới bài viết nhé!

Mình bonus 2 vấn đề nho nhỏ sau với bạn đọc hiếu kỳ

1) Hãy chứng minh nếu một số nguyên là một số lẻ thì luôn chia hết cho 8.

2) Liệu rằng là số nguyên tố với mọi số nguyên ?

1.3) Một vài tính chất của phép chia lấy dư

Phép chia lấy dư có lẽ đã rất quen thuộc với nhiều người, chúng ta đã được học nó từ cấp 1, ví dụ như 9 chia 8 dư 1. Người ta ký hiệu phép chia lấy dư là mod, trong nhiều ngôn ngữ lập trình chúng ta có ký hiệu % với ý nghĩa tương đương. Ví dụ: 9 mod 8 = 1 hay 9%8 = 1

1.3.1) Định nghĩa

Với và là các số nguyên, ta định nghĩa phép chia lấy dư như sau:

Trong đó là phép chia lấy phần nguyên. Ví dụ, nên .Bạn có thể thử vài số bất kỳ để kiểm chứng định nghĩa trên. Có nhiều ứng dụng khá hay của phép chia lấy dư nhưng mình sẽ không đề cập ở bài viết này để tránh lan man.

1.4) Ước chung lớn nhất (greatest common divisor)

1.4.1) Định nghĩa Một số nguyên được gọi là ước chung của và nếu và cùng chia hết cho , hay nói cách khác, khi và . Ước chung lớn nhất của và , hai số nguyên khác 0, được định nghĩa là số nguyên lớn nhất trong các ước chung của và . Ta ký hiệu là như sau:1.4.2) Định lý Nếu và là các số nguyên thì . Nếu và là các số nguyên thì . Nếu , và là các số nguyên thì

Định lý 1 và 2 mình sẽ để cho bạn đọc tự chứng minh, mình chỉ chứng minh định lý 3, đây cũng chính là định lý nền tảng cho giải thuật Euclid.

Chứng minh Định lý 3:

Ta cần chứng minh rằng ước chung của và giống với ước chung của và .Giả sử rằng và thì và (, là các số nguyên). Khi đó ta có:

Từ đó suy ra là ước của . Vậy là ước chung của và .Ngược lại, ta giả sử là ước chung của và thì và với , là các số nguyên. Khi đó ta có:

Từ đó suy ra là ước chung của và .

Từ hai chứng minh trên ta suy ra tập ước chung của giống với tập ước chung của . Do vậy .

Xem thêm: Tìm Hiểu Cấu Tạo Máy Ảnh Cơ Là Gì? Có Gì Khác Nhau? Máy Ảnh Kỹ Thuật Số, Máy Ảnh Cơ Là Gì

Từ định lý 3 ta rút ra 1 hệ quả quan trọng là nền tảng cho giải thuật Euclid.

1.4.3) Hệ quả Định lý 3Hệ quả:

Với và là các số nguyên, thì

Chứng minh:

Nhớ lại chút về định nghĩa của phép chia lấy dư: , suy ra với . Do đó hệ quả là đúng.

Áp dụng hệ quả:

Bây giờ chúng ta sẽ sử dụng hệ quả trên kết hợp với Định lý 2 mục 1.4.2) để tính ước chung lớn nhất của 2 số nguyên bất kỳ. Ví dụ, ta muốn tính , quy trình như sau:

gcd(64, 24) = gcd(64 mod 24, 24) = gcd(16, 24) = gcd(24 mod 16, 16) = gcd(8, 16) = gcd(16 mod 8, 8) = gcd(0, 8) = 8
Như vậy . Bạn có thể thử với các số khác nếu muốn.

2. Giải thuật Euclid

Thực ra khi thực hiện ví dụ trên là bạn đang chạy giải thuật Euclid rồi đấy. :))

Giải thuật Euclid thực chất là giải thuật giúp bạn tính được ước chung lớn nhất của 2 số nguyên bất kỳ, dựa trên cơ sở toán học mà chúng ta đã đề cập và chứng minh ở trên.Có thể bạn đang cảm thấy giải thuật này cũng chẳng giúp ích được gì lắm đúng không ? Điểm thú vị của giải thuật Euclid ở chỗ nó giúp chúng thực hiện việc tính với các số lớn khá nhanh. Bài viết sau mình sẽ demo việc này cũng như thử xem xét độ phức tạp của giải thuật này.

Bây giờ chúng ta sẽ implement giải thuật Euclid bằng code C++ nhé. Ta làm đúng theo các bước như khi ta thực hiện ví dụ trước thôi.

1234567891011int gcd(int a, int b) { int c = b; a = abs(a); b = abs(b); while(b > 0) { c = b; b = a%b; a = c; } return a;}Kiến thức có vẻ nhiều mà khi code có mấy dòng nhỉ. :))

Kiến thức có vẻ nhiều mà khi code có mấy dòng nhỉ. :))

Ta nhận thấy ở đây có sự lặp lại của chính hàm , do vậy ta có thể đệ quy đến khi nào một trong hai số hoặc bằng 0. Sau đây là implement giải thuật Euclid theo kiểu đệ quy.

12345678910int gcdRecursion(int a, int b) { int c; a = abs(a); b = abs(b);if(b > 0) { c = gcdRecursion(b,a%b); } else c = a; return c;}Mình tạm kết phần 1 tại đây, trong bài viết sau mình sẽ phân tích độ phức tạp của giải thuật Euclid và đề cập giải thuật Euclid mở rộng.Bạn đọc nếu có gì muốn góp ý gì về bài viết thoải mái comment và nếu cảm thấy bài viết bổ ích thì hãy share để bạn bè cùng đọc nhé!
Chuyên mục:

Mình tạm kết phần 1 tại đây, trong bài viết sau mình sẽ phân tích độ phức tạp của giải thuật Euclid và đề cập giải thuật Euclid mở rộng.Bạn đọc nếu có gì muốn góp ý gì về bài viết thoải mái comment và nếu cảm thấy bài viết bổ ích thì hãy share để bạn bè cùng đọc nhé!Chuyên mục: Tổng hợp

Phép Chia Lấy Dư Trong C – Toán Tử Chia Lấy Phần Dư Trong C++