01/10/2018, 15:27

Hỏi về thuật toán tìm nghiệm của phương trình bậc nhất 2 ẩn bằng đệ quy

Mình đang làm 1 bài toán tìm nghiệm của pt 2 ẩn bằng đệ quy.
Mà cụ thể là tìm x, y: UCLN(a,b) = ay + by

Ngồi gần 2 tiếng rồi mà code vẫn chạy sai
Mn góp ý giúp mình với ạ.
Chỉ tìm 1 cặp thôi nhé mn

明玉 viết 17:35 ngày 01/10/2018

Bạn cho mình nguyên văn cái đề bài nào?

rogp10 viết 17:33 ngày 01/10/2018

Như trên

Với lại bạn code ntn nữa.

Hello World viết 17:42 ngày 01/10/2018

Đề là tìm cặp x, y : UCLN(a,b) = a * x + b * y.
Mình code đếm số bị trừ của mỗi cái rồi xuất ra, nhưng lỗi mỗi khi chuyên a > b sang b >a …

明玉 viết 17:30 ngày 01/10/2018

a, b là có sẵn phải không. Vậy bạn cho đại một x rồi tìm y thôi

viết 17:39 ngày 01/10/2018

~.~

en.wikipedia.org

Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by t...

Hello World viết 17:31 ngày 01/10/2018

hì hì, sr bạn. Mình thiếu sót quá ^^

viết 17:41 ngày 01/10/2018

chém gió cái, code C++ như pseudo code

#include <iostream>
#include <utility>

std::pair<int,int> bezoutCoefficients(int a, int b)
{
    int s = 0, old_s = 1;
    int t = 1, old_t = 0;
    int r = b, old_r = a;
    while (r)
    {
        int quotient = old_r / r;
        old_r = std::exchange(r, old_r - quotient * r);
        old_s = std::exchange(s, old_s - quotient * s);
        old_t = std::exchange(t, old_t - quotient * t);
    }
    return {old_s, old_t};
}

int main()
{
    auto [x, y] = bezoutCoefficients(66, 242);
    std::cout << "x = " << x << ", y = " << y << "\n";
}
Văn Dương viết 17:36 ngày 01/10/2018

Bậc nhất mà có 2 ẩn à anh em @@.

rogp10 viết 17:37 ngày 01/10/2018

Sao lại không mà đây là phương trình nghiệm nguyên.

Văn Dương viết 17:33 ngày 01/10/2018

Bị nhầm ẩn với nghiệm
2 ẩn nhưng chỉ có 1 nghiệm ( trừ trường hợp đặc biệt).

rogp10 viết 17:38 ngày 01/10/2018

1 họ nghiệm số nghiệm nguyên là 0 hoặc vô số.

Bài liên quan
0