Categories: Tổng hợp

[C]. Ước Chung Lớn Nhất – Bội Chung Nhỏ Nhất

Published by
Video ước chung lớn nhất và bội chung nhỏ nhất

ucln bcnn

1. Thuật Toán Ngây Thơ

Ước Chung Lớn Nhất (UCLN) của 2 số a, b là số lớn nhất mà 2 số a và b cùng chia hết

Thuật toán tự nhiên mà bạn dùng để tìm UCLN đó là duyệt từ số nhỏ hơn trong 2 số về tới 1, số nào mà cả a và b chia hết đầu tiên sẽ là UCLN

Chú ý rằng UCLN(a, 0) = a

Code :

#include “stdio.h” #include “math.h” int ucln(int a, int b){ if(a == 0 || b == 0){ return a + b; } int min = a < b ? a : b; for(int i = min; i >= 1; i-){ if(a % i == 0 && b % i == 0){ return i; } } return 1; } int main(){ printf(“%d”, ucln(28, 20)); return 0; }

Bội Chung Nhỏ Nhất (BCNN) của 2 số a, b là số nhỏ nhất mà chia hết đồng thời cho cả a và b

Thuật toán tự nhiên mà bạn dùng để tìm BCNN đó là duyệt từ số lớn hơn trong 2 số và tăng dần cho tới khi gặp số đầu tiên chia hết cho cả a và b.

Code :

#include “stdio.h” #include “math.h” int bcnn(int a, int b){ int max = a > b ? a : b; int kq = max; while(1){ if(max % a == 0 && max % b == 0){ kq = max; break; } ++max; } return kq; } int main(){ printf(“%d”, bcnn(28, 20)); return 0; }

2. Thuật Toán Euclid

Thuật toán Euclid phát biểu như sau : UCLN của hai số nguyên không thay đổi khi thay số lớn hơn bằng hiệu của nó với số nhỏ hơn

Quá trình thay thế này được lặp đi lặp lại cho tới khi 2 số bằng nhau, khi đó UCLN chính là 1 trong 2 số.

Ví dụ

UCLN(20, 15) = UCLN (15, 5) = UCLN(5, 10) = UCLN(5, 5) => UCLN(20, 15) = 5

UCLN(16, 10) = UCLN(10, 6) = UCLN(6, 4) = UCLN(4, 2) = UCLN(2, 2) => UCLN(16, 10) = 2

Code :

#include “stdio.h” #include “math.h” int ucln(int a, int b){ //neu a hoac b = 0 thi ucln la so con lai if(a == 0 || b == 0){ return a + b; } while(a != b){ if(a > b){ a = a – b; //Thay thế số lớn hơn bằng hiệu 2 số } else{ b = b – a; //Thay thế số lớn hơn bằng hiệu 2 số } } return a; // b } int main(){ printf(“%d”, ucln(28, 20)); return 0; }

Output :

4

Giải thích :

  1. a = 28, b = 20, a != b vòng lặp lặp lần 1 : vì a > b nên a = a – b = 28 – 20 = 8
  2. a = 8, b = 20, a != b vòng lặp lặp lần 2 : vì b > a nên b = b – a = 20 – 8 = 12
  3. a = 8, b = 12, a != b vòng lặp lặp lần 3 : vì b > a nên b = b – a = 12 – 8 = 4
  4. a = 8, b = 4, a != b vòng lặp lặp lần 3 : vì a > b nên a = a – b = 8 – 4 = 4
  5. a = 4, b = 4, a == b => Vòng lặp kết thúc và hàm trả về 4

Để tìm BCNN bạn có thể dựa vào kiến thức : BCNN(a, b) = a * b / UCLN(a, b).

Ví dụ BCNN(28, 20) = 28 * 20 / UCLN(28, 20) = 560 / 4 = 140

Code :

#include “stdio.h” #include “math.h” int ucln(int a, int b){ //neu a hoac b = 0 thi ucln la so con lai if(a == 0 || b == 0){ return a + b; } while(a != b){ if(a > b){ a = a – b; //Thay thế số lớn hơn bằng hiệu 2 số } else{ b = b – a; //Thay thế số lớn hơn bằng hiệu 2 số } } return a; // b } int bcnn(int a, int b){ return a * b / ucln(a, b); // a / ucln(a, b) * b } int main(){ printf(“%d”, bcnn(28, 20)); return 0; }

Output :

140

3. Cải Tiến Thuật Toán Euclid

Trong mục 2 khi a và b cách xa nhau thì thuật toán Euclid hoạt động không hiệu quả, ví dụ bạn tìm ULCN(1000000000, 1) thì thuật toán cần lặp 999999999 lần.

Ta cải tiến thuật toán Euclid bằng nhận xét sau : UCLN của hai số nguyên không thay đổi khi thay 1 trong 2 số thành số dư của nó với số còn lại. Có nghĩa là UCLN(a, b) = UCLN(b, a % b)

Quá trình thay thế này được lặp đi lặp lại cho tới khi 1 trong 2 số bằng 0, khi đó UCLN chính là số còn lại

Ví dụ

UCLN(20, 15) = UCLN(15, 20 % 15) = UCLN(15, 5) = UCLN(5, 15 % 5) = UCLN(5, 0) => UCLN(20, 15) = 5

UCLN(16, 28) = UCLN(28, 16 % 28) = UCLN(28, 16) = UCLN(16, 28 % 16) = UCLN(16, 12) = UCLN(12, 16 % 12) = UCLN(12, 4) = UCLN(4, 12 % 4) = UCLN(4, 0) => UCLN(16, 28) = 4

UCLN(1000000000, 1) = UCLN(1, 1000000000 % 1) = UCLN(1, 0) = 1 => UCLN(1000000000, 1) = 1 (Bạn chỉ cần 1 vòng lặp thay vì 999999999)

Code :

#include “stdio.h” #include “math.h” int ucln(int a, int b){ while(b != 0){ int r = a % b; a = b; b = r; } return a; } int main(){ printf(“%d”, ucln(28, 20)); return 0; }

Giải thích :

  1. a = 28, b = 20, b != 0 nên vòng lặp lặp lần 1 : r = a % b = 8, a = b = 20, b = r = 8
  2. a = 20, b = 8, b != 0 nên vòng lặp lặp lần 2 : r = a % b = 4, a = b = 8, b = r = 4
  3. a = 8, b = 4, b != 0 nên vòng lặp lặp lần 3 : r = a % b = 0, a = b = 4, b = r = 0
  4. a = 4, b = 0, b == 0 nên vòng lặp dừng, hàm trả về a = 4

Cải tiến này giúp bạn có thể code hàm tìm UCLN nhanh hơn rất nhiều so với thuật toán Euclid ban đầu từ đó thuật toán tìm BCNN cũng hiệu quả hơn.

Nó giúp code của bạn chỉ tốn số bước nhiều nhất là năm lần số chữ số của số nhỏ hơn, điều này được Gabriel Lamé chứng minh vào năm 1844.

Bổ sung kiến thức : 2 số đồng nguyên tố hay nguyên tố cùng nhau là 2 số có UCLN là 1, vì dụ (5, 12) là nguyên tố cùng nhau

Xem thêm bài giảng của mình về UCLN, BCNN :

aw0c4kJpoEU

This post was last modified on %s = human-readable time difference 22:56

Published by

Bài đăng mới nhất

Con số may mắn hôm nay 3/11/2024 theo tuổi: Xem số MAY MẮN giúp bạn ĐÓN LỘC

Con số may mắn hôm nay 3/11/2024 theo tuổi: Xem con số MAY MẮN giúp…

11 giờ ago

Tử vi Chủ nhật ngày 3/11/2024 của 12 con giáp: Thìn khôn ngoan, Dần may mắn

Tử vi Chủ nhật ngày 3/11/2024 của 12 con giáp: Rồng khôn, Hổ may mắn

12 giờ ago

Cảnh báo 4 con giáp đối diện với nguy cơ mất tiền hao của, tháng 11/2024 chớ vội đầu tư

Cảnh báo 4 con giáp đối mặt nguy cơ mất tiền, đừng vội đầu tư…

14 giờ ago

4 con giáp VƯỢT chông gai để LỘI NGƯỢC dòng xuất sắc cuối năm 2024, TIỀN của tràn vào nhà

4 con giáp VƯỢT gai để lội ngược dòng xuất sắc cuối năm 2024, tiền…

14 giờ ago

Tuần mới (4 – 10/11) ôm trọn may mắn, 3 con giáp mở mày mở mặt khi thăng hoa vượt kỳ vọng

Tuần mới (4 - 10/11) đón nhận may mắn, 3 con giáp mở mang tầm…

19 giờ ago

Cách giúp 12 con giáp đạp gió rẽ sóng, chinh phục đỉnh cao trong tháng 11/2024

Cách giúp 12 con giáp cưỡi sóng vượt gió chinh phục đỉnh cao tháng 11/2024

20 giờ ago