Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

SPOJ.COM – Thuật toán bài GGD – Mr Toothless and His GCD Operation

Đề bài:

Bạn được cho một số N và bạn phải tìm ra hai số a và b sao cho GCD(a, b) (ước chung lớn nhất của a và b) là lớn nhất có thể. Trong đó 1<=a<b<=N.

Đầu vào:

Bắt đầu với số T (<= 100) – là số lượng test case. Mỗi test case sẽ bao gồm một số N duy nhất (2 ≤ N ≤ 106).

Đầu ra:

Với mỗi test case, in ra hai số a và b thỏa mãn. Nếu có nhiều test case thỏa mãn thì in ra cặp a và b thỏa mãn a + b là lớn nhất.

Ví dụ:

Đầu vào:

1

2

Đầu ra:

Case 1: 1 2

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/GGD/

Problem Setter: Md Abdul Alim, Department of CSE, Bangladesh University of Business & Technology

Phân tích:

+ Trước tiên tôi áp dụng thuật toán tham lam Greedy để tìm ra chìa khóa của bài toán. Tôi nhận ra rằng để ước chung lớn nhất của 2 số a và b là lớn nhất thì 2 số đó phải thỏa mãn là b = 2*a. Lúc này thực chất là tôi phải tìm ra số a lớn nhất thỏa mãn b = 2*a.

+ Để làm được điều này một cách nhanh nhất tôi sẽ áp dụng thuật toán chia để trị Divide and Conquer để giải quyết được nhanh hơn. Đối với việc áp dụng phương pháp chia để trị này thì việc đầu tiên phải xác định biên của kết quả. Rõ ràng giá trị của số a sẽ là từ 1 đến N. Việc tiếp theo chỉ là triển khai thuật toán chia để trị. Xin mời bạn theo dõi cách triển khải của tôi ở dưới đây.

Lời giải:

(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)

Code C/C++:

#include <iostream>
using namespace std;

int N;                    // Lưu số N đầu vào
int Num1, Num2;            // Lần lượt là 2 số được chọn    

bool IsValid(int mid)
{
    int a = mid, b = mid*2;
    if(b <= N)
    {
        Num1 = a;
        Num2 = b;
        return true;
    }
    return false;
}

int main()
{
    // freopen("input.txt","r",stdin);
    int T;
    cin >> T;
    for(int tc = 0; tc < T; tc++)
    {
        cin >> N;
        if(N == 2) cout << "Case " << tc + 1 << ": 1 2" << endl;
        else if(N == 3) cout << "Case " << tc + 1 << ": 2 3" << endl;
        else
        {
            // Dùng phương pháp chia đôi để tìm ra giá trị lớn nhất của UCLN
            // UCLN sẽ nằm trong khoảng từ 1 đến N
            int Left = 1, Right = N, Mid = 0;
            while(Left < Right - 1)
            {
                Mid = (Left + Right) / 2;
                if(IsValid(Mid)) Left = Mid;
                else Right = Mid - 1;
            }
        if(IsValid(Right)) cout << "Case " << tc + 1 << ": " << Num1 << " " << Num2 << endl;
        else if(IsValid(Left)) cout << "Case " << tc + 1 << ": " << Num1 << " " << Num2 << endl;
        }
    }
    return 0;
}

Code by Phạm Văn Lâm.

295 views

3 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài GGD – Mr Toothless and His GCD Operation trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

  2. Bùi Minh Bách

    Anh có thể hướng dẫn em chi tiết cách tìm ra hoặc chứng minh b=2*a thì b và a sẽ có ucln không ạ? Em cảm ơn

    1. Phạm Văn Lâm (Post author)

      Như mình đã nói ở trên, bài này mình sử dụng thuật toán Tham Lam, mà tham lam nghĩa là chưa có chứng minh. Tuy nhiên, suy luận của mình là như sau (bạn xem như vậy đã hợp lý chưa):
      1. UCLN của a và b lớn nhất có thể sẽ là số a (chú ý là b > a).
      2. Khi UCLN của số b và a là a, tức là b = N * a. Mà ta muốn tìm số a lớn nhất => N = 2. Vì khi N càng lớn thì a sẽ càng nhỏ.

      Đây chỉ là suy luận của mình thôi, còn chứng minh theo toán học thì hiện tại mình chưa chứng minh được.
      Không biết có bạn nào có thể chứng minh được điều trên là đúng không?

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *