در برنامه‌نویسی، الگوریتم‌های بازگشتی و الگوریتم‌های دینامیک دو روش قدرتمند برای حل مسائل هستند. الگوریتم‌های بازگشتی بر اساس فراخوانی تابع خود با داده‌های کوچکتر از مسئله اصلی عمل می‌کنند، در حالی که الگوریتم‌های دینامیک با استفاده از ذخیره نتایج مراحل قبلی، به صورت پویا و بهینه مسئله را حل می‌کنند. در این مقاله، به بررسی الگوریتم‌های بازگشتی و الگوریتم‌های دینامیک و نحوه پیاده‌سازی آن‌ها در زبان برنامه‌نویسی C# می‌پردازیم. در پایان توصیه می کنیم برای یادگیری هر چه بهتر این مطالب از پکیج کامل آموزش الگوریتم ها و ساختمان داده ها در سی شارپ استفاده کنید.
الگوریتم‌های بازگشتی بر اساس مفهوم بازگشتی یا فراخوانی تابع خود با داده‌های کوچکتر، مسئله را به صورت تکراری حل می‌کنند. این الگوریتم‌ها به صورت زیر عمل می‌کنند:
در زیر یک نمونه از پیاده‌سازی الگوریتم بازگشتی فاکتوریل در زبان سی شارپ آورده شده است:
private static int Factorial(int n)
{
if (n == 0)
return 1;
else
return n * Factorial(n - 1);
}
در این مثال، تابع Factorial را برای محاسبه فاکتوریل یک عدد صحیح تعریف کرده‌ایم. اگر عدد ورودی برابر با صفر باشد، یک برمی‌گردانیم زیرا فاکتوریل صفر برابر با یک است. در غیر این صورت، تابع را با ورودی کوچکتر (یعنی n-1) فراخوانی می‌کنیم و نتیجه را در n ضرب می‌کنیم. در نهایت، نتیجه نهایی را برمی‌گردانیم.
الگوریتم‌های دینامیک بر اساس ذخیره نتایج مراحل قبلی، به صورت پویا و بهینه مسئله را حل می‌کنند. این الگوریتم‌ها به صورت زیر عمل می‌کنند:
در زیر یک نمو نه از پیاده‌سازی الگوریتم دینامیک برای محاسبه برنامه پوششی خطی (Longest Increasing Subsequence) در زبان سی شارپ آورده شده است:
private static int LongestIncreasingSubsequence(int[] arr)
{
int[] lis = new int[arr.Length];
lis[0] = 1;
for (int i = 1; i < arr.Length; i++)
{
lis[i] = 1;
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
int maxLis = 0;
for (int i = 0; i < arr.Length; i++)
{
if (lis[i] > maxLis)
maxLis = lis[i];
}
return maxLis;
}
در این مثال، تابع LongestIncreasingSubsequence را برای محاسبه برنامه پوششی خطی (Longest Increasing Subsequence) برای یک آرایه اعداد صحیح تعریف کرده‌ایم. برای حل این مسئله، از روش دینامیک استفاده می‌کنیم. در ابتدا، یک آرایه lis برای ذخیره نتایج برنامه پوششی خطی را ایجاد می‌کنیم. سپس با استفاده از یک حلقه for، آرایه lis را پر می‌کنیم. در هر مرحله، مقدار lis[i] را برابر با یک قرار داده و از حلقه دیگری برای مقایسه عناصر قبلی با arr[i] و به روزرسانی مقدار lis[i] استفاده می‌کنیم. در انتها، مقدار بزرگترین برنامه پوششی خطی را در maxLis ذخیره کرده و آن را برمی‌گردانیم.
در این مقاله، به بررسی الگوریتم‌های بازگشتی و الگوریتم‌های دینامیک پ رداختیم و نحوه پیاده‌سازی آن‌ها در زبان برنامه‌نویسی C# را بررسی کردیم. الگوریتم‌های بازگشتی بر اساس فراخوانی تابع خود با داده‌های کوچکتر، مسئله را حل می‌کنند، در حالی که الگوریتم‌های دینامیک با استفاده از ذخیره نتایج مراحل قبلی، به صورت پویا و بهینه مسئله را حل می‌کنند. با استفاده از این الگوریتم‌ها می‌توانیم به صورت موثر و بهینه به حل مسائل پیچیده پرداخته و زمان و منابع محاسباتی را صرفه جویی کنیم.
بهترین و جامع ترین آموزش های برنامه نویسی و توسعه نرم افزار از سطح ابتدایی تا سطح میانی و سطح پیشرفته
تمامی حقوقی مادی و معنوی متعلق به گروه آموزشی پرووید است.
