Yêu cầu:
– Nhập 2 số nguyên a,b.
a. Tìm USC lớn nhất của 2 số đó
b. Tìm bội số chung nhỏ nhất của 2 số đó
Phân tích:
– Dùng thuật toán Euclid để tìm USC lớn nhất
– BSC nhỏ nhất = a*b / USCLN(a, b)
Code:
/************************************************************ * Author: VNCODING * History * 2014/04/03 first create VNCODING *************************************************************/ #include "stdio.h" #include "conio.h" int uscln(int a, int b); int bscnn(int a, int b); void main() { int a = 6, b = 18; printf("USCLN(%d,%d) = %d\n", a, b, uscln(a, b)); printf("BSCNN(%d,%d) = %d\n", a, b, bscnn(a, b)); getch(); } // dung thuat toan Euclid int uscln(int a, int b) { if(a == 0 && b == 0) return -1; else return (b == 0)? a : uscln(b, a%b); } int bscnn(int a, int b) { if(a == 0 || b == 0) return -1; else return (a*b/uscln(a, b)); }
Kết quả:
USCLN(6,18) = 6 BSCNN(6,18) = 18
return (b == 0)? a : uscln(b, a%b);
Giải thích vì sao lại a%b ???
>return (b == 0)? a : uscln(b, a%b);
Đây là thuật toán Euclid tìm USCLN. Bạn tham khảo thêm ở đây:
https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid
Nên có thêm điều kiện trả về khi cả a và b bằng 0. Và cả trường hợp số âm nữa. Tốt nhất là nên lấy abs trước khi chạy hàm uscln
#include “stdafx.h”
#include
#include
using namespace std;
int ucln(int a, int b)
{
if (a == 0 || b == 0)
return a + b;
else
if (a <= b)
return ucln(a, b%a);
else
return ucln(b, a%b); //Có thể viết trong 1 dòng: return (a==0 || b==0) ? (a+b) : (a<=b) ? ucln(a, b%a) : ucln(b, a%b);
}
int main()
{
int num1, num2, temp;
cout <> num1 >> num2;
temp = ucln(abs(num1), abs(num2));
if (temp == 0)
cout << "Khong the tim UCLN(0,0)" << endl;
else
cout << "UCLN(" << num1 << "," << num2 << ") = " << temp << endl;
return 1;
}
Cho mình hỏi sao những lệnh “cin” trong code của mình khi post lên đều bị mất đi vậy -.-
Hi Hoang, cảm ơn bạn đã quan tâm đến blog.
Khi post code bạn sử dụng cho mình tag sau
các anh chị cho em hỏi, return -1 để làm gì ạ ? em cám ơn ạ