C++ প্রোগ্রাম: এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম বাস্তবায়ন

এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম কেবল দুটি নম্বরের GCD বের করার আরেকটি পদ্ধতি। এতে এক্সট্রা ভেরিয়েবল থাকে ax + by = gcd(a, b) কম্পিউট করার জন্য। কম্পিউটার প্রোগ্রামে ব্যবহার করার জন্য এটি আরও ইফিশিয়েন্ট।

অ্যালগরিদম

শুরু
  a, b, x এবং y ভেরিয়েবল ডিক্লেয়ার করুন
  gcdExtended(int a, int b, int *x, int *y)
  if (a == 0)
    *x = 0; *y = 1; return b;
  রিকারসিভ কলের রেজাল্ট স্টোর করার জন্য দুটি ভেরিয়েবল নিন
  রিকারসিভ কলের রেজাল্ট ব্যবহার করে x এবং y আপডেট করুন
শেষ

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

int gcdExtended(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}

int main() {
    int x, y;
    int a = 35, b = 15;
    cout << "gcd " << gcdExtended(a, b, &x, &y);
    return 0;
}

আউটপুট

gcd 5