Output Của Bài Toán Tìm ước Chung Lớn Nhất Của Hai Số Nguyên ...
Có thể bạn quan tâm
Nội dung chính Show
- Example2 Input: 2 20 Output: 14
- Example3 Input: 3 5 Output: -1 Giải thích ví dụ: - Ở ví dụ thứ nhất: Chỉ có cặp (2, 10) thỏa mãn ƯCLN(2,10) = 2, BCNN(2,10) = 10. Nên tổng là 12. - Ở ví dụ thứ hai: Có hai cặp (2, 20) và (4, 10) thỏa mãn, tổng nhỏ nhất là 14. - Ở ví dụ thứ ba: Không tìm được cặp nào thỏa mãn ƯCLN là 3 và BCNN là 5.
- Các thuật toán tìm ước chung lớn nhất
- 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++
- Video liên quan
Với hai số nguyên dương A, B cho trước. Ta dễ dàng tìm được ước chung lớn nhất G và bội chung nhỏ nhất L của hai số A và B.
Bây giờ chúng ta hãy xét bài toán ngược của bài toán trên:
“Cho biết trước ước chung lớn nhất G và bội chung nhỏ nhất L của hai số nguyên dương A và B.
Rõ ràng, sẽ có rất nhiều cặp (A, B) nguyên dương có ước chung lớn nhất là G và bội chung nhỏ nhất là L, tuy nhiên cũng có trường hợp chúng ta không thể tìm được giá trị A, B thỏa mãn. Hãy xác định giá trị nhỏ nhất của tổng A + B, hoặc đưa ra -1 nếu không tìm được cặp (A, B)”.
Input
- Hai số nguyên dương G và L (1 ≤ G ≤ L ≤ 109).
Output
- Số nguyên dương là tổng nhỏ nhất có thể. Trong trường hợp không tìm được hai số A và B thì đưa ra kết quả là -1.
Example1
Input: 2 10 Output: 12Example2 Input: 2 20 Output: 14
Example3 Input: 3 5 Output: -1 Giải thích ví dụ: - Ở ví dụ thứ nhất: Chỉ có cặp (2, 10) thỏa mãn ƯCLN(2,10) = 2, BCNN(2,10) = 10. Nên tổng là 12. - Ở ví dụ thứ hai: Có hai cặp (2, 20) và (4, 10) thỏa mãn, tổng nhỏ nhất là 14. - Ở ví dụ thứ ba: Không tìm được cặp nào thỏa mãn ƯCLN là 3 và BCNN là 5.
86 / 100
Trong bài viết này tôi sẽ cùng các bạn tìm hiểu về các thuật toán tìm ước chung lớn nhất của hai số nguyên và minh họa code bằng ngôn ngữ C/C++.
Định nghĩa ước chung lớn nhất
Ước chung lớn nhất (GCD – Greatest Common Divisor) của 2 số nguyên a và b là số nguyên lớn nhất d thỏa mãn 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 nhất
Dưới đây là một số cách thường được sử dụng để giải quyết bài toán tìm ước chung lớn nhất 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 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 intgcd(inta,intb){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if(a==0||b==0){ returna+b; } while(a!=b){ if(a>b){ a-=b;// a = a - b }else{ b-=a; } } returna;// return a or b, bởi vì lúc này a và b bằng nhau } |
Giải thích:
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
// Code from https://nguyenvanhieu.vn intgcd(inta,intb){ // 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; } } returna+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ó:
Cài đặt thuật toán sử dụng đệ quy.
// Code from https://nguyenvanhieu.vn intgcd(inta,intb){ if(b==0)returna; returngcd(b,a%b); } |
Cài đặt khử đệ quy
// Code from https://nguyenvanhieu.vn intgcd(inta,intb){ inttmp; while(b!=0){ tmp=a%b; a=b; b=tmp; } returna; } |
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:
// Code from https://nguyenvanhieu.vn #include #include intmain(){ inta=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 intgcd1(inta,intb){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if(a==0||b==0){ returna+b; } while(a!=b){ if(a>b){ a-=b;// a = a - b }else{ b-=a; } } returna;// return a or b, bởi vì lúc này a và b bằng nhau } intgcd2(inta,intb){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if(a==0||b==0){ returna+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; } } returna+b;// return a + b, bởi vì lúc này hoặc a hoặc b đã bằng 0. } intgcd3(inta,intb){ if(b==0)returna; returngcd3(b,a%b); } intgcd4(inta,intb){ inttmp; while(b!=0){ tmp=a%b; a=b; b=tmp; } returna; } intmain(){ inta=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 bày chi tiết về các thuật toán tìm ước chung lớn nhất của hai số. Nếu bạn đọc quan tâm hay có thắc mắc gì. Vui lòng để lại ở bình luận phía cuối 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 bài viết tìm BCNN của 2 số nhé.
Từ khóa » Trình Bày Input Và Output Giải Bài Toán Tìm ước Chung Lớn Nhất Của Hai Số Nguyên Dương
-
Xác định Bài Toán Và Xây Dựng Thuật Toán 1. Tìm ước Chung Lớn Nhất ...
-
Bài Toán đặt Vấn đề Tìm ước Số Chung Lớn Nhất (ưcln) Của Hai Số ...
-
Xác định Input Và Output Của Bài Toán " Tìm ước Chung Lớn ...
-
Tìm ước Số Chung Lớn Nhất Và Bội Số Chung Nhỏ Nhất Của A Và B
-
Hay Xác định Input Của Bài Toán Tìm ước Chung Lớn Nhất Của 2 Số ...
-
Output Của Bài Toán Tìm ước Chung Lớn Nhất Của 2 Số Nguyên Dương ...
-
Viết Thuật Toán Tìm ước Chung Lớn Nhất Của 2 Số Nguyên Dương ...
-
Giáo án Tin Học 10 Bài 6 | Xemtailieu
-
Tiết 20 Bài 6_Giải Bài Toán Trên Máy Tính - Tài Liệu Text - 123doc
-
Bài 6. Giải Bài Toán Trên Máy Tính - Tài Liệu Text - 123doc
-
Viết Thuật Toán Tìm ước Chung Lớn Nhất Của 2 Số Nguyên Dương A Và B.
-
Giáo án Môn Tin Học 10 - Tiết 9 - Bài 4: Bài Toán Và Thuật Toán
-
4. BÀI TOÁN VÀ THUẬT TOÁN - SGK Tin Học 10 - MarvelVietnam