Kiến thức

HÀM TÌM ƯỚC CHUNG LỚN NHẤT TRONG C/C++

Bạn đang xem: HÀM TÌM ƯỚC CHUNG LỚN NHẤT TRONG C/C++

HÀM TÌM ƯỚC CHUNG LỚN NHẤT TRONG C/C++

Ngày đăng: 14-12-2016 21:59:27

Trong các bài toán về C, chúng ta thường gặp dạng bài tìm ước chung lớn nhất (UCLN) của 2 số. Bằng cách xây dựng hàm, chúng ta có thể giải bài này một cách dễ dàng. Hôm nay, tinhoc123 gửi đến cách xây dựng hàm UCLN

Trước tiên, ta cần hiểu ước chung của 2 số n và m là gì, ta gọi i là ước của số n, j là ước của số m. i,j là ước chung của n và m khi i,j thỏa:

♥ n chia hết cho i
♥ m chia hết cho j
♥ i=j

Từ đó, UCLN được định nghĩa là  số i=j lớn nhất trong các ước chung của n và m

VD: 12 và 15 có UCLN là 3

* Phân tích bài toán:

-Input: 2 số m và n
-Output: UCLN của m và n
Để tìm UCLN, trước tiên ta cần phải tìm các ước của 2 số m và n một cách đồng thời. Như vậy ta sẽ sử dụng 2 vòng lặp for lồng nhau để tìm ước số

Kết hợp với điều kiện i=j, ta sẽ tìm ra được ước chung của m và n (dùng câu lệnh if)

Cuối cùng, ta sẽ tìm xem trong các giá trị i=j, giá trị nào lớn nhất thì đó là UCLN. Như vậy, ta sẽ dùng một biến “max” tạm thời để gán giá trị i=j sau mỗi vòng lặp. Nếu max<i=j thì max=i=j

* Triển khai thuật toán, viết hàm:

Và đây là hàm UCLN: 

 int UCLN( int n, int m)
 {
     int i,j,max=0;
     for(i=1;i<=n;i++)
     {
         for(j=1;j<=m;j++)
             if(n%i==0 & m%j==0 & i==j)
             if(max<i)
                 max=i;
     }
 printf(“%d”, max);
 return 1;
 }

Trên đây, tinhoc123 đã hướng dẫn các bạn cách xây dựng hàm UCLN. Chúc các bạn thành công,

Xem hàm số nguyên tố tại

đây

Like, share nếu bạn thấy bài viết này có ích. Trân trọng cám ơn

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button