Để trình bày thuật toán tìm ucln theo cách tối ưu nhất ta làm chi tiết như thế nào? câu hỏi 60188 - hoctapsgk.com
Để trình bày thuật toán tìm ucln theo cách tối ưu nhất ta làm chi tiết như thế nào?
Lời giải 1 :
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 nhất sử dụng phép trừ
Thuật toán tìm ước chung lớn nhất 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 https://nguyenvanhieu.vn
int gcd(int a, int b){
// Nếu a = 0 => ucln(a,b) = b
// Nếu b = 0 => ucln(a,b) = a
if (a == 0 || 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, bởi vì lúc này a và b bằng nhau
}
Giải thích:
0
1
2
3
4
5
6
7
8
9
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 = 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à 1
Xem thêm: Các chia sẻ hay được đúc kết từ kinh nghiệm 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
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Code from https://nguyenvanhieu.vn
int gcd(int a, int 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;
}
}
return a + b; // return a + b, bởi vì 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 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ó:
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.
0
1
2
3
4
5
6
7
// Code from https://nguyenvanhieu.vn
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
Cài đặt khử đệ quy
0
1
2
3
4
5
6
7
8
9
10
11
12
// Code from https://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ố 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++
Để 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:
0
1
2
3
4
5
6
7
8
// Code from https://nguyenvanhieu.vn
#include
#include
int main(){
int a = 5, b = 9;
printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b));
}
Tổng kết tất cả cách cách trên trong 1 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 https://nguyenvanhieu.vn
#include
#include
int gcd1(int a, int b){
// Nếu a = 0 => ucln(a,b) = b
// Nếu b = 0 => ucln(a,b) = a
if (a == 0 || 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, bởi vì lúc này a và b bằng nhau
}
int gcd2(int a, int b){
// Nếu a = 0 => ucln(a,b) = b
// Nếu b = 0 => ucln(a,b) = a
if (a == 0 || b == 0){
return a + 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;
}
}
return a + b; // return a + b, bởi vì lúc này 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ử
0
1
2
3
4
5
6
gcd1(5, 9) = 1
gcd2(5, 9) = 1
gcd3(5, 9) = 1
gcd4(5, 9) = 1
gcd5(5, 9) = 1
CHÚC BN HỌC TỐT
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 10
Lớp 10 - Năm thứ nhất ở cấp trung học phổ thông, năm đầu tiên nên có nhiều bạn bè mới đến từ những nơi xa hơn vì ngôi trường mới lại mỗi lúc lại xa nhà mình hơn. Được biết bên ngoài kia là một thế giới mới to và nhiều điều thú vị, một trang mới đang chò đợi chúng ta.
Nguồn : ADMIN :))Copyright © 2021 HOCTAP247