Thuật toán tìm ước chung lớn nhất của 2 số

Nằm vào series học tập thuật tân oán – cấu tạo tài liệu cùng lời giải, bọn họ cùng nhau mày mò những cách thức để kiếm tìm ước chung lớn nhất, code được minch họa bằng Java.

Bạn đang xem: Thuật toán tìm ước chung lớn nhất của 2 số

Trước hết, bọn họ cùng mọi người trong nhà tìm hiểu kim chỉ nan trước đã nhé.

Định nghĩa ước bình thường Khủng nhất

Trước khi hiểu ước thông thường lớn số 1, bạn cần phải biết ước số là gì? Đơn giản lắm, ước số của một trong những ngulặng a là số nguim b Khi và chỉ còn lúc số a phân chia hết mang đến số b.

Ước tầm thường to nhất (GCD – Greatest Comtháng Divisor) của hai xuất xắc những số ngulặng là số lớn nhất vào tập phù hợp ước tầm thường.

Ngược cùng với ước chung lớn nhất là bội số tầm thường nhỏ tuổi độc nhất vô nhị. Mình vẫn dành riêng bài viết sau nhằm lí giải thực hiện thuật tân oán để tìm bội số phổ biến nhỏ độc nhất vô nhị. Các bạn đón phát âm nhé.

Ứng dụng thực tiễn của ước phổ biến lớn nhất (UCLN)

Với nhiều áp dụng thực tiễn, ước tầm thường lớn số 1 không chỉ là dùng trong lĩnh vực toán thù học tập, mà cả những nghành khác nữa, liên quan cho những sự thứ, hiện tượng kỳ lạ trong cuộc sống.

Mình đem ví dụ minh họa nhé:

Tôi ngán làm dev, bỏ về quê chăn thỏ làm nhiều. Đố các bạn biết tôi đang nuôi bao nhiêu bé thỏ? Dữ liệu cho bạn đây: Hàng này tôi luôn ném ra 6 cây súp lơ, 8 củ củ cà rốt làm thức ăn uống cho cái đó. Mỗi bé thỏ những được trải nghiệm cả súp lơ cùng củ cà rốt. Trong số đó, con số súp lơ cùng cà rốt ăn được cần đều nhau. Tất nhiên, không được bỏ thừa ngẫu nhiên đồ ăn nào cả. Thế bắt đầu khó chứ đọng.

Với bài bác toán thù thực tiễn này, các bạn chỉ cần áp dụng UCLN là giải được (Gợi ý đáp án: 2 con thỏ).

Các thuật toán tìm ước phổ biến phệ nhất

Để minch họa mang đến thuật toán kiếm tìm UCLN, chúng ta đang sử dụng ngôn ngữ Java mang đến thân thuộc.

Dưới đó là một trong những thuật tân oán tra cứu UCLN.

Xem thêm: Sinh Viên Việt Nam Tham Gia Chương Trình Tình Nguyện Viên Quốc Tế Ở Nga

#1 – Sử dụng thuật toán thù vét cạn

Trong những thuật toán thù, có lẽ thuật toán vét cạn là thuật toán thù “nông dân” duy nhất, bằng tay thủ công độc nhất vô nhị. Mọi người xuất xắc chơi nhau, thuật tân oán vét cạn là thuật toán thù cđọng tay lớn là chiến hạ, ngoài đề xuất cân nhắc gì cả, kiểu dáng “cần mẫn bù siêng năng”.

Với bài toán này, đưa sử tìm kiếm UCLN của nhì số nguyên ổn (a, b). chúng ta sẽ triển khai lặp từ 1 tới số nhỏ hơn vào hai số (a,b) với kiểm soát xem những số nguim (a, b) bao gồm phân tách hết mang đến chỉ số index không? Chỉ số lớn nhất cơ mà (a,b) chia hết đó là UCLN.

Cài đặt thuật toán bởi Java.

public static int gcdByBruteForce(int a, int b) { int gcd = 1; for (int i = 1; i Độ phức tạp của thuật toán thù là: O(min(a, b))

#2 – Tìm UCLN thực hiện thuật tân oán Euclid

Tìm UCLN của nhì số ngulặng (X,Y), đưa sử x > y. Để kiếm tìm UCLN, chúng ta thực hiện chia x mang lại y, được phần ngulặng a cùng số dư b (b>= 0). Ta bao gồm sơ thiết bị mang đến thuật tân oán Euclid nlỗi sau:

Sơ thứ thuật toán Euclid

Cài đặt giải mã bằng Java theo cách đệ quy.

/* * Java method khổng lồ find GCD of two number using Euclid"s method *
return GDC of two numbers in Java */ private static int findGCD(int x, int y) //base case if(y== 0) return x; return findGCD(y, x%y); Nếu các bạn ko ưa thích đệ quy, có thể cần sử dụng vòng lặp while như sau:

// Code from https://cheohanoi.vnpublic static int findGCD(int x, int y) int temp; while(y!= 0) temp = x % y; x= y; y= temp; return x;Độ tinh vi thuật toán: O(Log min(x, y))

#3 – Thuật toán thù Stein (Binary GCD)

Cuối cùng, mình muốn reviews thêm thuật toán thù stein xuất xắc còn được gọi là thuật toán Binary GCD nhằm tra cứu ước phổ biến lớn số 1 của nhị số ngulặng dương.

Thuật tân oán này thực hiện phnghiền tân oán số học đơn giản dễ dàng nlỗi chuyển số, đối chiếu với phép trừ.

Các bước của thuật toán:

gcd(0, 0) = 0, gcd(n1, 0) = n1, gcd(0, n2) = n2Lúc cả n1 với n2 gần như là số nguim chẵn thì gcd(n1, n2) = 2 * gcd(n1/2, n2/2) do số chẵn luôn luôn phân chia không còn cho 2.Nếu nmột là số ngulặng chẵn, còn n2 là số lẻ thì gcd(n1, n2) = gcd(nmột nửa, n2)Nếu cả n1 với n2 là số lẻ, và n1 >= n2 thì gcd(n1, n2) = gcd((n1-n2)/2, n2).

Sau đó là cài đặt thuật toán thù bằng Java.

public static int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) return n2; if (n2 == 0) return n1; int n; for (n = 0; ((n1 | n2) và 1) == 0; n++) n1 >>= 1; n2 >>= 1; while ((n1 & 1) == 0) n1 >>= 1; bởi while ((n2 & 1) == 0) n2 >>= 1; if (n1 > n2) int temp = n1; n1 = n2; n2 = temp; n2 = (n2 - n1); while (n2 != 0); return n1 Độ phức tạp thuật toán: O((log2n1)2) hoặc O((log2n2)2) tùy theo n1> n2 tuyệt ngược trở lại.

Lời kết

Trên trên đây, tôi đã giới thiệu 3 thuật toán thù phổ biến tốt nhất nhằm tìm kiếm UCLN của hai số nguyên ổn. Trong đó, bản thân có minc họa bởi Java, nếu như mình muốn C++ thì để lại phản hồi dưới để mình đưa sang trọng C++ nhé.

Những thuật tân oán trên cũng khá thường được sử dụng trong số bài bác tân oán tìm kiếm tìm. Rất ý muốn nội dung bài viết này có ích với bạn!

Xem tiếp các bài trong SeriesPhần trước: Thuật toán trong lập trình sẵn – Đôi điều tản mạnPhần kế tiếp: Thuật toán Quichồng Sort – Java Example