الگوریتم اقلیدسی (Euclidean Algorithm)

الگوریتم اقلیدسی یکی از مهم‌ترین و پرکاربردترین الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد های علم رایانه و ریاضیات است که به محاسبهٔ بزرگترین مقسوم علیه مشترک (GCD) دو عدد صحیح می‌پردازد. این الگوریتم از اهمیت بسزایی برخوردار بوده و در مسائل مختلفی از جمله رمزنگاری، تئوری اعداد و حل مسائل عددی به کار می‌رود.

اهمیت الگوریتم اقلیدسی

یکی از دلایل اهمیت الگوریتم اقلیدسی این است که به سادگی و با کارایی بالا می‌تواند GCD دو عدد را محاسبه کند؛ این مفهوم محاسبه GCD به طور وسیع در ریاضیات و علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است. به کار می‌رود. برای مثال، در رمزنگاری RSA، محاسبهٔ GCD از اهمیت حیاتی برخوردار است.

کاربرد در علوم کامپیوتر

در علوم کامپیوتر، الگوریتم اقلیدسی در مسائل تقسیم و حاکمیت اعداد به کار می‌رود؛ همچنین در رمزنگاری و تولید اعداد تصادفی نیز از این الگوریتم استفاده می‌شود. اهمیت این الگوریتم در سرعت و کارایی بالا و امکان پیاده‌سازی آسان آن در بسیاری از برنامه‌های کامپیوتری نهفته است.

الگوریتم اقلیدسی پایه‌ ای (Basic) برای بدست اوردن ب م م (GCD)

الگوریتم اقلیدسی پایه‌ای یکی از ساده‌ترین و پرکاربردترین الگوریتم‌های محاسبه بزرگترین مشترک مقسومین (GCD) دو عدد است. این الگوریتم بر اساس اصل اقلیدسی که توسط دانشمند یونانی باستان اقلیدس در قرن سوم پیش از میلاد ارائه شد، کار می‌کند. اصل اقلیدسی می‌گوید که بزرگترین مشترک مقسومین دو عدد، بزرگترین مشترک مقسومین دومین عدد و باقی‌مانده تقسیم اولیه این دو عدد است و این اصل به تعداد دفعات تکراری اعمال می‌شود تا باقی‌مانده برابر با صفر شود.

حالا به توضیح الگوریتم اقلیدسی پایه‌ ای برای محاسبهٔ بزرگترین مشترک مقسومین (GCD) می‌پردازیم:

الگوریتم اقلیدسی پایه‌ ای برای محاسبه بزرگترین مشترک مقسومین (GCD)

الگوریتم اقلیدسی پایه‌ ای به روش بازگشتی کار می‌کند و برای محاسبه بزرگترین مشترک مقسومین (GCD) دو عدد a و b، به صورت زیر عمل می‌کند:

• اگر b برابر صفر باشد، جواب a خواهد بود و الگوریتم متوقف می‌شود.
• در غیر این صورت، a را به a برقرار b تقسیم می‌کنیم.
• سپس الگوریتم را با b به عنوان a و با باقی‌مانده قسمت a بر b به عنوان b فراخوانی می‌کنیم و به مرحله 1 باز می‌گردیم.
• این الگوریتم به صورت بازگشتی و با تقسیم مکرر اعداد ورودی، بزرگترین مشترک مقسومین را به دست می‌آورد.

پیاده‌سازی الگوریتم اقلیدسی پایه‌ ای در Pytho

def gcd_basic(a, b):
    if b == 0:
        return a
    else:
        return gcd_basic(b, a % b)

# مثال استفاده:
a = 48
b = 18
result = gcd_basic(a, b)
print(f"GCD({a}, {b}) = {result}")

def gcd_basic(a, b):
    if b == 0:
        return a
    else:
        return gcd_basic(b, a % b)

# مثال استفاده:
a = 48
b = 18
result = gcd_basic(a, b)
print(f"GCD({a}, {b}) = {result}")

کپی کردن کد

پیاده‌سازی الگوریتم اقلیدسی پایه‌ ای در ++C

#include 
int gcd_basic(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd_basic(b, a % b);
    }
}

int main() {
    int a = 48;
    int b = 18;
    int result = gcd_basic(a, b);
    std::cout  "GCD("  a  ", "  b

	#include 
int gcd_basic(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd_basic(b, a % b);
    }
}

int main() {
    int a = 48;
    int b = 18;
    int result = gcd_basic(a, b);
    std::cout  "GCD("  a  ", "  b 

کپی کردن کد

الگوریتم اقلیدسی توسعه یافته

الگوریتم اقلیدسی توسعه یافته یک نسخه بهبود یافته از الگوریتم اقلیدسی برای محاسبه بزرگترین مشترک مقسومین (GCD) دو عدد است. این الگوریتم توسعه‌یافته برای محاسبه GCD با استفاده از ضرب و تقسیم‌ نرمال عدد‌ها کمترین تعداد مراحل را نیاز دارد و کارآیی بهتری دارد تا الگوریتم اقلیدسی پایه‌ ای.

مثال الگوریتم اقلیدسی توسعه یافته

فرض کنید می‌خواهیم بزرگترین مشترک مقسومین (GCD) عدد 48 و 18 را محاسبه کنیم. 

1. ما m1 را برابر با 48 و m2 را برابر با 18 قرار می‌دهیم.
2. x1 = 1، x2 = 0، y1 = 0، و y2 = 1 را تنظیم می‌کنیم.
3. باقی‌ماندهٔ m1 بر m2 معادل 12 است (48 % 18 = 12).
4. ما m1 و m2 را به ترتیب با 18 و 12 جایگزین می‌کنیم.
5. همچنین، x1 و x2 را به ترتیب با 0 و 1 جایگزین می‌کنیم.
6. همچنین، y1 و y2 را به ترتیب با 1 و 1- جایگزین می‌کنیم.
7. الگوریتم به مرحله 3 باز می‌گردد.
8. باقی‌ماندهٔ m1 بر m2 معادل 6 است (18 % 12 = 6).
9. ما m1 و m2 را به ترتیب با 12 و 6 جایگزین می‌کنیم.
10. همچنین، x1 و x2 را به ترتیب با 1 و 1- جایگزین می‌کنیم.
11. همچنین، y1 و y2 را به ترتیب با 1- و 2 جایگزین می‌کنیم.
12. الگوریتم به مرحله 3 باز می‌گردد.
13. باقی‌ماندهٔ m1 بر m2 معادل 0 است (12 % 6 = 0).
14. بنابراین، جواب m2 یعنی 6 است که بزرگترین مشترک مقسومین (GCD) عدد 48 و 18 می‌باشد.

پیاده‌سازی الگوریتم اقلیدسی توسعه یافته در Python

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1

    return gcd, x, y

a = 48
b = 18

result, x, y = extended_gcd(a, b)

print(f"GCD({a}, {b}) = {result}")
print(f"x = {x}, y = {y}")

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1

    return gcd, x, y

a = 48
b = 18

result, x, y = extended_gcd(a, b)

print(f"GCD({a}, {b}) = {result}")
print(f"x = {x}, y = {y}")

کپی کردن کد

پیاده‌سازی الگوریتم اقلیدسی توسعه یافته در C++

#include 
int extended_gcd(int a, int b, int &x, int &y)
{ if (b == 0) 
{ x = 1; y = 0; return a; } 
int x1, y1; 
int gcd = extended_gcd(b, a % b, x1, y1);
x = y1; y = x1 - (a / b) * y1; return gcd; }
int main() { // ورودی‌ها int a = 48; int b = 18;
int x, y; 
int result = extended_gcd(a, b, x, y); 
std::cout "GCD(" a ", " b ") = " 
result std::endl; std::cout "x = " x 

#include 
#include 
int extended_gcd(int a, int b, int &x, int &y)
{ if (b == 0) 
{ x = 1; y = 0; return a; } 
int x1, y1; 
int gcd = extended_gcd(b, a % b, x1, y1);
x = y1; y = x1 - (a / b) * y1; return gcd; }
int main() { // ورودی‌ها int a = 48; int b = 18;
int x, y; 
int result = extended_gcd(a, b, x, y); 
std::cout "GCD(" a ", " b ") = " 
result std::endl; std::cout "x = " x 

کپی کردن کد

در این دو نمونه کد (Python و C++)، تابع extended_gcd برای محاسبه بزرگترین مشترک مقسومین (GCD) و مقادیر x و y با استفاده از الگوریتم اقلیدسی توسعه یافته استفاده می‌شود. ورودی‌های مورد نیاز را تعریف کرده و نتیجه محاسبه GCD و مقادیر x و y را نمایش می‌دهد.

الگوریتم اقلیدسی توسعه یافته چگونه کار می کند؟

الگوریتم اقلیدسی توسعه یافته به صورت بازگشتی کار می‌کند و دارای مراحل زیر است:

تعیین ورودی‌ها: این الگوریتم با دو عدد ورودی a و b شروع می‌شود.

مرحله اول: در این مرحله، مقدار a را به عنوان m1 و مقدار b را به عنوان m2 قرار می‌دهیم. همچنین، مقدار x1 را برابر با 1 و مقدار x2 را برابر با 0 قرار می‌دهیم.

مرحله دوم: در این مرحله، مقدار y1 را برابر با 0 و مقدار y2 را برابر با 1 قرار می‌دهیم.

مرحله سه: در این مرحله، باقی‌ماندهٔ m1 بر m2 را محاسبه کرده و نتیجه را در m3 قرار می‌دهیم.

مرحله چهارم: اگر مقدار m3 برابر با صفر باشد، جواب برابر با m2 خواهد بود و الگوریتم متوقف می‌شود.

مرحله پنجم: اگر مقدار m3 برابر با صفر نباشد، مقادیر m1 و m2 را به ترتیب با m2 و m3 جایگزین می‌کنیم.

مرحله ششم: همچنین، مقادیر x1 و x2 را به ترتیب با x2 و (x1 - q * x2) جایگزین می‌کنیم، که در اینجا q نتیجهٔ تقسیم m1 به m2 است.

مرحله هفتم: همچنین، مقادیر y1 و y2 را به ترتیب با y2 و (y1 - q * y2) جایگزین می‌کنیم.

مرحله هشتم: الگوریتم به مرحله چهارم باز می‌گردد و این مراحل تا زمانی ادامه می‌یابد که مقدار m3 برابر با صفر شود.

محاسبه مقادیر x و y: یکی از ویژگی‌های مهم الگوریتم اقلیدسی توسعه یافته این است که می‌تواند مقادیر x و y را نیز محاسبه کند. این مقادیر به عنوان ضرایب معادله دیافرانسیلی خطی مرتبط با a و b شناخته می‌شوند و از اهمیت بسیاری در مسائل رمزنگاری و تئوری اعداد برخوردارند. در نتیجه، الگوریتم اقلیدسی توسعه یافته به عنوان یک ابزار قدرتمند برای محاسبات عددی و رمزنگاری در علوم کامپیوتر و ریاضیات شناخته می‌شود.

جمع بندی

در این مقاله به معرفی و توضیح الگوریتم اقلیدسی توسعه یافته پرداختیم. الگوریتم اقلیدسی توسعه یافته یک نسخه بهبود یافته از الگوریتم اقلیدسی برای محاسبه بزرگترین مشترک مقسومین (GCD) دو عدد است. در این الگوریتم، علاوه بر محاسبه GCD، می‌توان مقادیر x و y را نیز محاسبه کرد که به عنوان ضرایب معادله دیافرانسیلی خطی مرتبط با a وb شناخته می‌شوند.

مراحل کار الگوریتم اقلیدسی توسعه یافته شامل تعیین ورودی‌ها، مقداردهی اولیه، محاسبه باقی‌مانده تقسیم و انجام مراحل بازگشتی تا رسیدن به جواب GCD می‌باشد. این الگوریتم به صورت بازگشتی کار می‌کند و به صورت مؤثر برای محاسبات عددی و رمزنگاری در علوم کامپیوتر و ریاضیات استفاده می‌شود. الگوریتم اقلیدسی توسعه یافته به عنوان یک ابزار قدرتمند برای محاسبات مرتبط با GCD و معادلات دیافرانسیلی خطی شناخته می‌شود و در مسائل مختلفی از جمله رمزنگاری و تئوری اعداد به کار می‌رود.

مطالب مرتبط

همه مقالات

طراحی الگوریتم چیست؟ آموزش طراحی الگوریتم به زبان ساده

پادکست بررسی درس ساختمان داده

ترند های طراحی رابط کاربری

چرا برنامه نویسی بهترین شغل دنیاست؟