Các thuật toán tìm ước chung lớn nhất cài đặt với C

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 .

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ó :

Thuật toán tìm ước chung lớn nhất của hai số nguyên sử dụng 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ì

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments