এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদমের পাইথন প্রোগ্রাম

এই আর্টিকেলে আমরা নিচের সমস্যা সমাধানের কথা শিখব।

সমস্যা: দুটি সংখ্যা দেওয়া আছে, আমাদের সেগুলোর GCD ক্যালকুলেট করে ডিসপ্লে করতে হবে।

GCD (Greatest Common Divisor) দুটি সংখ্যার সবচেয়ে বড় সেই সংখ্যা যা উভয়কেই ভাগ করতে পারে। এখানে আমরা ইউক্লিডিয়ান পদ্ধতি অনুসরণ করি GCD কম্পিউট করতে অর্থাৎ বারবার ভাগ দিয়ে রিমাইন্ডার শূন্য হয়ার পরোঁত থামি। এখানে আমরা রিকার্সনে পাওয়া পূর্বের ভ্যালুতে বেস করে অ্যালগরিদম এক্সটেন্ড করি।

চলুন নিচের ইমপ্লিমেন্টেশনে সমাধানটি পর্যবেক্ষণ করি।

উদাহরণ

# এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম
def gcdExtended(a, b, x, y):
    # বেস কেস
    if a == 0:
        x = 0
        y = 1
        return b
    x1 = 1
    y1 = 1  # রেজাল্ট স্টোর
    gcd = gcdExtended(b % a, a, x1, y1)
    # x এবং y আপডেট পূর্বের ক্যালকুলেটেড ভ্যালু দিয়ে
    x = y1 - (b / a) * x1
    y = x1
    return gcd

x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of", a, "&", b, "is =", g)

আউটপুট

gcd of 11 & 15 is = 1

সभी ভেরিয়েবল লোকাল স্কোপে ঘোষণা করা হয়েছে এবং তাদের রেফারেন্স উপরের চিত্রে দেখা যাচ্ছে।

উপসংহার

এই আর্টিকেলে আমরা শিখেছি কিভাবে এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদমের পাইথন প্রোগ্রাম লিখতে হয়।