Tìm Bội Chung Nhỏ Nhất Của Hai Số Trong C | Lập Trình Từ Đầu

1. Bài tập tìm bội chung nhỏ 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 vòng lặp for hoặc dựa trên ước chung lớn nhất 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 bội chung nhỏ 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 bội chung nhỏ nhất của hai số là gì?

bội số chung nhỏ nhất (hay còn gọi tắt là bội chung nhỏ nhất, được viết tắt là BCNN) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b. Tức là nó có thể chia cho a và b mà không để lại số dư. Nếu a hoặc b là 0, thì không tồn tại số nguyên dương chia hết cho a và b.

Ví dụ hai số 4 và 8 có bội số chung nhỏ nhất là 8.

2.1 Cách sử vòng lặp for tăng dần cho tới khi tìm được BCNN

BCNN của 2 số a và b phải chia hết cho cả 2 số này. Do đó, ta có thể chỉ cần duyệt qua các số chia hết cho 1 số(hoặc a, hoặc b). Nhưng để tối ưu, bạn hãy duyệt qua các số chia hết cho số lớn nhất giũa a và b.

Các bước thực hiện 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 kq để gán giá trị của bội chung nhỏ nhất, biến int step để tính bước nhảy mỗi khi lặp.

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 nếu a>b thì gán giá trị step = a ngược lại step = b.

Bước 3: Sử dụng vòng lặp for bắt đầu tại i = step, kết thúc khi i<=a*b và mỗi lần i tăng lên step; trong vòng lặp ta sử dụng if với điều kiện nếu i % a == 0 và i % b == 0 thì kq = i kết thúc lặp.

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

Chương trình như sau:

#include<stdio.h> int main() { //khai bao a, b, kq int a, b, kq, step; //nhap a printf("nhap a:"); scanf("%d",&a); //nhap b printf("nhap b:"); scanf("%d",&b); //t́m step la so lon nhat giua a và b if(a>b)//neu a>b { step = a; }else//neu a<b { step = b; } for(int i = step; i <= a*b; i+= step){ if(i % a == 0 && i % b == 0)//neu i chia het cho ca a va b { kq = i; break; } } //in ket qua ra man hinh printf("BCNN(%d, %d) = %d", a, b, kq); }

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

Kết quả:

nhap a:16 nhap b:8 BCNN(16, 8) = 16

2.2 Tìm BCNN của 2 số dựa vào UCLN

Ta có mối quan hệ của BCNN và UCLN của hai số a và b như sau:

Các bước thực hiện như sau:

Bước 1: Ta tạo một hàm int UCLN(int a, int b) dùng để tính UCLN của a và b bạn có thể tìm hiểu về cách tìm UCLN của chúng tôi tại đây.

Bước 2: Trong hàm main, chúng ta khai báo int a , int b để gán giá trị của a và b.

Bước 3: Ta khai báo biến int gan = UCLN(a, b).

Bước 4: Ta in ra màn hình BCNN là : (a*b)/gan.

Chương trình như sau:

#include <stdio.h> // tinh uoc chung lon nhat int UCLN(int a, int b) { while ( a != b) { if (a > b) a = a - b; else b = b - a; } return a; } 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); //khai bao gan = UCLN int gan = UCLN(a, b); printf("BCNN la: %d", (a*b)/gan); }

Ví dụ tôi nhập a=13 và b=12

Kết quả:

nhap a:13 nhap b:12 BCNN la: 156

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, cách gọi hàm trong C và các phép toán học cơ bản.