Mẹo về Tìm ƯCLN của 2 số nguyên dương M và N trong C Mới Nhất
Pro đang tìm kiếm từ khóa Tìm ƯCLN của 2 số nguyên dương M và N trong C được Update vào lúc : 2022-06-26 00:20:05 . Với phương châm chia sẻ Bí quyết về trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi Read tài liệu vẫn ko hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Ad lý giải và hướng dẫn lại nha.
86
/ 100
Nội dung chính
- Các thuật toán tìm ước chung lớn số 1
- Cách 1. Tìm UCLN sử dụng phép trừ
- Cách 2. Tìm UCLN sử dụng phép chia dư
- Cách 3. Tìm UCLN sử dụng giải thuật Euclid
- Cách 4. Tìm UCLN sử dụng hàm có sẵn của C++
Trong nội dung bài viết này tôi sẽ cùng những bạn tìm hiểu về những thuật toán tìm ước chung lớn số 1 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 số 1
Ước chung lớn số 1 [GCD – Greatest Common Divisor] của 2 số nguyên a và b là số nguyên lớn số 1 d thỏa mãn nhu cầu tính chất cả a và b đều chia hết cho d.
Các thuật toán tìm ước chung lớn số 1
Dưới đấy là một số trong những cách thường được sử dụng để xử lý và xử lý bài toán tìm ước chung lớn số 1 của hai số.
Cách 1. Tìm UCLN sử dụng phép trừ
Đây là sơ đồ của thuật toán này
Thuật toán tìm ước chung lớn số 1 sử dụng phép trừ
Code minh họa
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code from //nguyenvanhieu.vn
int gcd[int a, int b]
Giải thích:
Tại từng 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 to nhiều hơn.
Ví dụ với hai số a = 7, b = 5
L1: a > b => a = 2, b = 5
L2: b > a => a = 2, b = 3
L3: b > a => a = 2, b = 1
L4: a > b => a = 1, b = 1
L5: a == b => trả về a hoặc b đều được => KQ là một trong
Xem thêm: Các chia 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ư cách 1. Chỉ thay đổi phép trừ sang phép chia dư.
Code minh họa
// Code from //nguyenvanhieu.vn
int gcd[int a, int b]
// Lặp tới khi một trong 2 số bằng 0
while [a*b != 0]
if [a > b]
a %= b; // a = a % b
else
b %= a;
return a + b; // return a + b, chính bới thời gian hiện nay 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 số 1 của hai số a và b ta cần thực thi 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.
// Code from //nguyenvanhieu.vn
int gcd[int a, int b]
if [b == 0] return a;
return gcd[b, a % b];
Cài đặt khử đệ quy
// Code from //nguyenvanhieu.vn
int gcd[int a, int b]
int tmp;
while[b != 0]
tmp = a % b;
a = b;
b = tmp;
return a;
Gợi ý: Một số nội dung bài viết về giải thuật tương tự
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:
// Code from //nguyenvanhieu.vn
#include <algorithm>
#include <stdio.h>
int main[]
int a = 5, b = 9;
printf[“ngcd[%d, %d] = %d”, a, b, std::__gcd[a,b]];
Tổng kết toàn bộ cách cách trên trong một chương trình.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// Code from //nguyenvanhieu.vn
#include <stdio.h>
#include <algorithm>
int gcd1[int a, int b] b == 0]
return a + b;
while [a != b]
if [a > b]
a -= b; // a = a – b
else
b -= a;
return a; // return a or b, chính bới thời gian hiện nay a và b bằng nhau
int gcd2[int a, int b] b == 0]
return a + b;
// Lặp tới khi một trong 2 số bằng 0
while [a*b != 0]
if [a > b]
a %= b; // a = a % b
else
b %= a;
return a + b; // return a + b, chính bới thời gian hiện nay hoặc a hoặc b đã bằng 0.
int gcd3[int a, int b]
if [b == 0] return a;
return gcd3[b, a % b];
int gcd4[int a, int b]
int tmp;
while[b != 0]
tmp = a % b;
a = b;
b = tmp;
return a;
int main[]
int a = 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ử
gcd1[5, 9] = 1
gcd2[5, 9] = 1
gcd3[5, 9] = 1
gcd4[5, 9] = 1
gcd5[5, 9] = 1
Trên đây tôi đã trình diễn rõ ràng về những thuật toán tìm ước chung lớn số 1 của hai số. Nếu bạn đọc quan tâm hay có vướng mắc gì. Vui lòng để lại ở phản hồi phía cuối nội dung bài viết.
Nếu bạn quan tâm đến tìm BCNN của 2 số, vui lòng chuyển qua nội dung bài viết tìm BCNN của 2 số nhé.
Reply
8
0
Chia sẻ
Chia Sẻ Link Download Tìm ƯCLN của 2 số nguyên dương M và N trong C miễn phí
Bạn vừa Read Post Với Một số hướng dẫn một cách rõ ràng hơn về Review Tìm ƯCLN của 2 số nguyên dương M và N trong C tiên tiến và phát triển nhất và Chia Sẻ Link Cập nhật Tìm ƯCLN của 2 số nguyên dương M và N trong C Free.
Hỏi đáp vướng mắc về Tìm ƯCLN của 2 số nguyên dương M và N trong C
Nếu sau khi đọc nội dung bài viết Tìm ƯCLN của 2 số nguyên dương M và N trong C vẫn chưa hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Ad lý giải và hướng dẫn lại nha
#Tìm #ƯCLN #của #số #nguyên #dương #và #trong