Tìm ước Chung Lớn Nhất Của Hai Số Trong C - Lập Trình Từ Đầu

1. Bài tập tìm ước chung lớn nhất của hai số a và b trong C

Bài tập cơ bản này ta có thể có hướng giải quyết là sử dụng giải thuật Euclid, sử dụng phép trừ, sử dụng phép chia dư trong ngôn ngữ lập trình C.

Đầu vào sẽ là một biến nguyên dương a và b,  yêu cầu của bài toán là tìm ước chung lớn nhất của hai số a và b.

2. Lời giải

Đầu tiên chúng ta cần phải biết ước chung lớn nhất của hai số là gì?

Ước chung lớn nhất (ƯCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất là ước số chung của các số đó

Ví dụ hai số 8 và 12 có ước chung là 4 và 2 trong đó ước chung lớn nhất của hai số đó là 4.

2.1 Cách sử dụng giải thuật Euclid

Giải thuật Euclid (hay thuật toán Euclid) là một giải thuật để tính ước chung lớn nhất (ƯCLN) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không.

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 thực hiện 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ác bước thực hiện giải thuật Euclid như sau:

Bước 1: Chúng ta khai báo int a , int b để gán giá trị của a và b , khai báo biến int tg.

Bước 2: Nhập dữ liệu từ bàn phím gán giá trị vào biến a và b.

Bước 3: Sử dụng vòng lặp while với điều kiện miễn là khi b!=0 thì vòng lặp tiếp tục, gán biến tg = a%b, gán biến a = b, biến b = tg.

Bước 4: In ra màn hình giá trị của ước chung lớn nhất là a.

Chương trình như sau:

#include<stdio.h> int main() { //khai bao a, b, tg int a, b, tg; //nhap a printf("nhap a:"); scanf("%d",&a); //nhap b printf("nhap b:"); scanf("%d",&b); while(b!=0) { tg = a % b; a = b; b = tg; } //in UCLN ra man hinh printf("UCLN là :%d",a); }

Ví dụ tôi nhập a=10 và b=20

Kết quả:

nhap a:10 nhap b:20 UCLN lα :10

2.2 Cách sử dung phép trừ

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

Các bước thực hiện phép trừ như sau:

Bước 1: Chúng ta khai báo int a , int b để gán giá trị của a và b.

Bước 2: Nhập dữ liệu từ bàn phím gán giá trị vào biến a và b.

Bước 3: Sử dụng if với điều kiện a=0 hoặc b=0 thì in ra màn hình UCLN là a+b.

Bước 4: Sử dụng vòng lặp while với điều kiện miễn là khi a!=b thì vòng lặp tiếp tục, sử dụng if nếu a>b thì a-=b ngược lại b-=a.

Bước 5: In ra màn hình giá trị của ước chung lớn nhất là a.

Chương trình như sau:

#include<stdio.h> int main() { //khai bao a, b int a, b; //nhap a printf("nhap a:"); scanf("%d",&a); //nhap b printf("nhap b:"); scanf("%d",&b); if(a==0||b==0){//neu a=0 hoac b=0 printf("UCLN la: %d", a+b); } while(a!=b) { if (a > b){//neu a>b a -= b; // a = a - b }else{// a<b b -= a;// b = b - a } } //in UCLN ra man hinh printf("UCLN là :%d",a); }

Ví dụ tôi nhập a=8 và b=24

Kết quả:

nhap a:8 nhap b:24 UCLN lα :8

2.3 Cách sử dụng phép chia dư

Bước 1: Chúng ta khai báo int a , int b để gán giá trị của a và b.

Bước 2: Nhập dữ liệu từ bàn phím gán giá trị vào biến a và b.

Bước 4: Sử dụng vòng lặp while với điều kiện miễn là khi a*b!=0 thì vòng lặp tiếp tục, sử dụng if nếu a>b thì a%=b ngược lại b%=a.

Bước 5: In ra màn hình giá trị của ước chung lớn nhất là a+b.

Chương trình như sau:

#include<stdio.h> int main() { //khai bao a, b int a, b; //nhap a printf("nhap a:"); scanf("%d",&a); //nhap b printf("nhap b:"); scanf("%d",&b); // Lap t0i khi 1 trong 2 so a hoac b bang 0 while (a*b != 0){ if (a > b){ a %= b; // a = a % b }else{ b %= a; } } //in UCLN ra man hinh printf("UCLN là :%d",a+b); }

Ví dụ tôi nhập a=9 và b=6

Kết quả:

nhap a:9 nhap b:6 UCLN lα :3

3. Tổng kết

Để thực hiện giải bài tập tìm ước chung lớn nhất của hai số trong C bạn đọc cần phải có kiến thức cơ bản về ngôn ngữ lập trình C, bạn cần nắm vững cách nhập xuất căn bản và các cách sử dụng vòng lặp trong C và các phép toán học cơ bản.