tim uoc chung lon nhat va boi chung nho nhat trong c

Trong nội dung bài viết này tôi tiếp tục nằm trong chúng ta dò la hiểu về những thuật toán dò la ước cộng đồng lớn số 1 của nhì số nguyên vẹn và minh họa code vày ngữ điệu C/C++.

Bạn đang xem: tim uoc chung lon nhat va boi chung nho nhat trong c

Định nghĩa ước cộng đồng rộng lớn nhất

Ước cộng đồng lớn số 1 (GCD – Greatest Common Divisor) của 2 số nguyên $a$ và $b$ là số nguyên vẹn rộng lớn nhất $d$ thỏa mãn đặc thù cả a và b đều phân tách không còn mang đến d.

Các thuật toán dò la ước cộng đồng rộng lớn nhất

Dưới đấy là một trong những cơ hội thông thường được dùng nhằm giải quyết và xử lý Việc dò la ước cộng đồng lớn số 1 của nhì số.

Cách 1. Tìm UCLN dùng quy tắc trừ

Đây là sơ vật của thuật toán này

Code minh họa

// Code from https://emtc2.edu.vn int gcd(int a, int b){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if (a == 0 || b == 0){ return a + b; } while (a != b){ if (a > b){ a -= b; // a = a - b }else{ b -= a; } } return a; // return a or b, chính vì thời điểm hiện tại a và b vày nhau }

Giải thích:

Tại từng bước một lặp nó sẽ bị đánh giá độ quý hiếm lúc này của a và b coi thằng nào là to hơn. Ví dụ với nhì số a = 7, b = 5 L1: a > b => a = 2, b = 5 L2: b > a => a = 2, b = 3 L3: b > a => a = 2, b = 1 L4: a > b => a = 1, b = 1 L5: a == b => trả về a hoặc b đều được => KQ là 1

Xem thêm: Các share hoặc được đúc rút kể từ tay nghề của tác giả

Cách 2. Tìm UCLN dùng quy tắc phân tách dư

Sơ vật thuật toán tương tự động như cơ hội 1. Chỉ thay cho thay đổi quy tắc trừ sang trọng quy tắc phân tách dư.

Code minh họa

// Code from https://emtc2.edu.vn int gcd(int a, int b){ // Lặp cho tới Lúc 1 trong các 2 số vày 0 while (a*b != 0){ if (a > b){ a %= b; // a = a % b }else{ b %= a; } } return a + b; // return a + b, chính vì thời điểm hiện tại hoặc a hoặc b đang được vày 0. }

Cách 3. Tìm UCLN dùng giải thuật Euclid

Cho a, b là nhì số nguyên vẹn (giả sử a ≥ b), nhằm dò la ước cộng đồng lớn số 1 của nhì số a và b tớ cần thiết triển khai phân tách a mang đến b được thương q và số dư r (r ≥ 0) tức là a = b*q + r, Lúc cơ tớ có:

Xem thêm: trường thpt hoa sen

Cài bịa thuật toán dùng đệ quy.

// Code from https://emtc2.edu.vn int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

Cài bịa khử đệ quy

// Code from https://emtc2.edu.vn int gcd(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; }

Gợi ý: Một số nội dung bài viết về giải thuật tương tự

Cách 4. Tìm UCLN dùng hàm có trước của C++

Để hoàn toàn có thể sử người sử dụng hàm dò la ucln vô C++ tớ cần thiết thêm thắt thư viện algorithm.

Ví dụ minh họa:

// Code from https://emtc2.edu.vn #include <algorithm> #include <stdio.h> int main(){ int a = 5, b = 9; printf("ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); }

Tổng kết toàn bộ cơ hội phương pháp bên trên trong một công tác.

// Code from https://emtc2.edu.vn #include <stdio.h> #include <algorithm> int gcd1(int a, int b){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if (a == 0 || b == 0){ return a + b; } while (a != b){ if (a > b){ a -= b; // a = a - b }else{ b -= a; } } return a; // return a or b, chính vì thời điểm hiện tại a và b vày nhau } int gcd2(int a, int b){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if (a == 0 || b == 0){ return a + b; } // Lặp cho tới Lúc 1 trong các 2 số vày 0 while (a*b != 0){ if (a > b){ a %= b; // a = a % b }else{ b %= a; } } return a + b; // return a + b, chính vì thời điểm hiện tại hoặc a hoặc b đang được vày 0. } int gcd3(int a, int b) { if (b == 0) return a; return gcd3(b, a % b); } int gcd4(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; } int main(){ int a = 5, b = 9; printf("ngcd1(%d, %d) = %d", a, b, gcd1(a,b)); printf("ngcd2(%d, %d) = %d", a, b, gcd2(a,b)); printf("ngcd3(%d, %d) = %d", a, b, gcd3(a,b)); printf("ngcd4(%d, %d) = %d", a, b, gcd4(a,b)); printf("ngcd5(%d, %d) = %d", a, b, std::__gcd(a,b)); }

Kết trái khoáy chạy thử

gcd1(5, 9) = 1 gcd2(5, 9) = 1 gcd3(5, 9) = 1 gcd4(5, 9) = 1 gcd5(5, 9) = 1

Trên trên đây tôi đang được trình diễn cụ thể về những thuật toán dò la ước cộng đồng lớn số 1 của nhì số. Nếu độc giả quan hoài hoặc đem vướng mắc gì. Vui lòng nhằm lại ở comment phía cuối nội dung bài viết.

Nếu các bạn quan hoài cho tới dò la BCNN của 2 số, hí hửng lòng chuyển sang nội dung bài viết dò la BCNN của 2 số nhé.

Xem thêm: với n là số nguyên dương công thức nào dưới đây đúng