Trong bài viết này tôi sẽ cùng những bạn tìm hiểu và khám phá về những thuật toán tìm ước chung lớn nhất của hai số nguyên và minh họa code bằng ngôn từ C / C + + .Định nghĩa ước chung lớn nhất
Ước chung lớn nhất ( GCD – Greatest Common Divisor ) của 2 số nguyên a và b là số nguyên lớn nhất d thỏa mãn nhu cầu đặc thù cả a và b đều chia hết cho d .
Mục lục nội dung
Các thuật toán tìm ước chung lớn nhất
Dưới đây là một số cách thường được sử dụng để giải quyết bài toán tìm ước chung lớn nhất của hai số.
Bạn đang đọc: Các thuật toán tìm ước chung lớn nhất cài đặt với C
Cách 1. Tìm UCLN sử dụng phép trừ
Đây là sơ đồ của thuật toán này
Code minh họa
0123456789101112131415161718
/ / Code from https://mindovermetal.org
intgcd(inta,intb){
/ / Nếu a = 0 => ucln ( a, b ) = b
/ / Nếu b = 0 => ucln ( a, b ) = a
if(a==0||b==0){
returna+b;
}
while(a!=b){
if(a>b){
a-=b;/ / a = a – b
}else{
b-=a;
}
}
returna;/ / return a or b, chính do lúc này a và b bằng nhau
}
Giải thích:
0123456789
Tại mỗi bước lặp nó sẽ kiểm tra giá trị hiện tại của a và b xem thằng nào lớn hơn .Ví dụ với hai số a = 7, b = 5L1 : a > b => a = 2, b = 5L2 : b > a => a = 2, b = 3L3 : b > a => a = 2, b = 1L4 : a > b => a = 1, b = 1L5 : a = = b => trả về a hoặc b đều được => KQ là 1
Xem thêm : Các san sẻ hay được đúc rút từ kinh nghiệm tay nghề của tác giả
Cách 2. Tìm UCLN sử dụng phép chia dư
Sơ đồ thuật toán tương tự như như cách 1. Chỉ biến hóa phép trừ sang phép chia dư .
Code minh họa
01234567891011121314
/ / Code from https://mindovermetal.org
intgcd(inta,intb){
/ / Lặp tới khi 1 trong 2 số bằng 0
while(a *b!=0){
if(a>b){
a%=b;/ / a = a % b
}else{
b%=a;
}
}
returna+b;/ / return a + b, do tại lúc này hoặc a hoặc b đã bằng 0 .
}
Cách 3. Tìm UCLN sử dụng giải thuật Euclid
Cho a, b là hai số nguyên ( giả sử a ≥ b ), để tìm ước chung lớn nhất của hai số a và b ta cần triển khai chia a cho b được thương q và số dư r ( r ≥ 0 ) tức là a = b * q + r, khi đó ta có :
Cài đặt thuật toán sử dụng đệ quy .
01234567
/ / Code from https://mindovermetal.org
intgcd(inta,intb){
if(b==0)returna;
returngcd(b,a%b);
}
Cài đặt khử đệ quy
0123456789101112
/ / Code from https://mindovermetal.org
intgcd(inta,intb){
inttmp;
while(b!=0){
tmp=a%b;
a=b;
b=tmp;
}
returna;
}
Gợi ý : Một số bài viết về giải thuật tựa như
Cách 4. Tìm UCLN sử dụng hàm có sẵn của C++
Để hoàn toàn có thể sử dùng hàm tìm ucln trong C + + ta cần thêm thư viện algorithm .
Ví dụ minh họa :
012345678
/ / Code from https://mindovermetal.org
#include
#include
intmain(){
inta=5,b=9;
printf(” \ ngcd ( % d, % d ) = % d “,a,b,std::__gcd(a,b));
}
Tổng kết tổng thể cách cách trên trong 1 chương trình .
Xem thêm: Tứ niệm xứ – Wikipedia tiếng Việt
/ / Code from https://mindovermetal.org
#include
#include
intgcd1(inta,intb){
/ / Nếu a = 0 => ucln ( a, b ) = b
/ / Nếu b = 0 => ucln ( a, b ) = a
if(a==0||b==0){
returna+b;
}
while(a!=b){
if(a>b){
a-=b;/ / a = a – b
}else{
b-=a;
}
}
returna;/ / return a or b, chính bới lúc này a và b bằng nhau
}
intgcd2(inta,intb){
/ / Nếu a = 0 => ucln ( a, b ) = b
/ / Nếu b = 0 => ucln ( a, b ) = a
if(a==0||b==0){
returna+b;
}
/ / Lặp tới khi 1 trong 2 số bằng 0
while(a*b!=0){
if(a>b){
a%=b;/ / a = a % b
}else{
b%=a;
}
}
returna+b;/ / return a + b, chính bới lúc này hoặc a hoặc b đã bằng 0 .
}
intgcd3(inta,intb){
if(b==0)returna;
returngcd3(b,a%b);
}
intgcd4(inta,intb){
inttmp;
while(b!=0){
tmp=a%b;
a=b;
b=tmp;
}
returna;
}
intmain(){
inta=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 quả chạy thử
0123456
gcd1(5,9)=1
gcd2(5,9)=1
gcd3(5,9)=1
gcd4(5,9)=1
gcd5(5,9)=
1
Xem thêm: PWA là gì? Bạn có cần xây dựng PWA cho website của mình không?
Trên đây tôi đã trình diễn chi tiết cụ thể về những thuật toán tìm ước chung lớn nhất của hai số. Nếu bạn đọc chăm sóc hay có vướng mắc gì. Vui lòng để lại ở phản hồi phía cuối bài viết .
Nếu bạn chăm sóc đến tìm BCNN của 2 số, vui mừng chuyển qua bài viết tìm BCNN của 2 số nhé .
Source: https://mindovermetal.org
Category: Wiki là gì
