3 thuật toán tìm ước chung lớn nhất C/C++ – https://final-blade.com

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Bài viết chia sẻ 3 thuật toán tìm ước chung lớn nhất của 2 số nguyên a b trong lập trình C/C++. UCLN là bài toán rất hay cho việc rèn tư duy logic với C/C++, java, c#.. .

1. Giới thiệu bài toán UCLN

Bài toán tìm ước chung lớn nhất C/C++ là một bài toán rất hay trong lập trình cơ bản, hầu hết các bạn mới học lập trình đều rất hứng thú với nó.

Bài toán có thể được nêu lên dưới nhiều dạng khác nhau, nhưng tóm tắt lại là: Tìm ước chung lớn nhất của hai số nguyên A, B.

Ước của một số ít là số mà số đó hoàn toàn có thể chia hết, ví dụ 2 là ước của 4. .. UCLN của hai số A, B là ước lớn nhất của cả hai số đó. UCLN hoàn toàn có thể là chính số đó, 1 hay bất kể số nguyên nào khác .
Có 3 cách để tìm UCLN trong lập trình :

  • Cách 1: Tìm UCLN sử dụng vòng lặp
  • Cách 2: Tìm UCLN sử dụng phép trừ
  • Cách 3: Tìm UCLN sử dụng phép chia

Ngoài ra còn có rất nhiều cách khác như sử dụng thư viện. .. Trong bài viết này mình chỉ đề cập tới 3 cách thông dụng nhất .

Tham khảo 6 thuật toán sắp xếp thông dụng trong lập trình.

tim uoc chung lon nhat c

2. Tìm ước chung lớn nhất sử dụng vòng lặp

Ý tưởng tìm UCLN sử dụng vòng lặp như sau: Duyệt i từ phần tử nhỏ hơn về 1, nếu cả hai số A, B đều chia hết cho i thì kết thúc vòng lặp. i chính là ucln của hai số đó.

Với ý tưởng sáng tạo này bạn hoàn toàn có thể sử dụng vòng lặp for hoặc while đều được. Ở đây mình dùng vòng lặp while cho dễ tưởng tượng .

Code C/C++ hàm tìm ucln1:

int ucln1(int a, int b){
	int temp;
	if(b > a) {   // Dùng để chuyển b thành a
		temp = b;
		b = a;
		a = temp;
	}     // sau khối lệnh, ta có a >= b
	
	int i = b;  // i chạy từ b
	while(i >= 1) {
		if(a%i == 0 && b%i == 0)  // nếu a và b cùng chia hết cho i
			break;          // thoát vòng lặp
		i--;
	}
	return i;   // Trả về i, i là UCLN của A, B
}

3. Tìm UCLN sử dụng phép trừ

Thuật toán này có ý tưởng sáng tạo như sau : Khi nào a ! = b thì lấy số lớn hơn trừ cho số bé hơn sau đó gán lại giá trị bằng đúng thương hiệu vừa tính được. Khi hai số bằng nhau thì đó chính là ước chung lớn nhất .
Nói thì hơi khó hiểu, bạn chỉ cần nhớ thuật toán là được, cùng tìm hiểu thêm code C / C + + phía dưới :

int ucln2(int a, int b){
	while(a != b){  // Khi a còn khác b
		if(a > b)  // nếu a > b
			a = a - b;   // gán lại a
		else    // Trường hợp b > a
			b = b - a;   // Gán lại b
	}
	return a; // return b;
}

4. Thuật toán tìm UCLN sử dụng phép chia

Có một công thức toán học được nêu ra như sau: a = b*x + r
tức là: số a chia số b sẽ được x lần và dư r.

Lúc này tác dụng bài toán tìm ucln của a, b chính là bài toán tìm UCLN của b và r. Cho tới khi r = 0 thì b chính là hiệu quả ta cần tìm .
Thuật toán này có độ phức tạp thấp hơn 2 thuật toán nêu bên trên ( vận tốc nhanh hơn 1 tí ) .

Code C/C++:

int ucln3(int a, int b ){
	int r = a % b; 		// a = b*x + r;
	while (r!=0) {
                // Gán lại a = b, quay về bài toán tìm ucln của b và r
		a = b;  
		b = r;
		r = a % b;   // r là phần dư của phép chia a/b
	}
	
	return b;
}

Lời kết

Bài viết về UCLN trong lập trình của mình đến đây là hết. Hi vọng rằng bạn sẽ làm chủ được cả 3 thuật toán này. Tưởng chừng bài toán này rất đơn thuần nhưng bạn sẽ học đc nhiều từ nó đấy. Chúc bạn thành công xuất sắc !

Xem thêm các bài viết về lập trình C/C++ tại đây

admin