محاسبه دستی فاکتوریل آسان است، اما چگونه می توان این کار را به صورت برنامه ای و به تمیزترین شکل ممکن انجام داد؟
فاکتوریل یک عدد یک مفهوم ریاضی مهم است. می توانید از آن برای انجام جایگشت ها و ترکیب ها، نوشتن عبارات نمایی و لگاریتمی و محاسبه احتمال استفاده کنید.
شما از آن برای پیدا کردن روش‌های مختلف استفاده می‌کنید که می‌توانید چیدمان صندلی را طراحی کنید، یا تی‌شرت‌هایی را برای تعطیلات خود به مالدیو انتخاب کنید. اما چگونه می توان فاکتوریل یک عدد را محاسبه کرد؟
فاکتوریل یک عدد چیست؟
فاکتوریل یک عدد مثبت حاصل ضرب تمام اعداد صحیح مثبت کوچکتر یا مساوی مقدار خود عدد است. عددی که با علامت تعجب (!) به دنبال آن فاکتوریل یک عدد است. شما فاکتوریل پنج را 5 نشان می دهید! و آن را به صورت زیر محاسبه کنید:
5 = 5 * 4 * 3 * 2 * 1 = 120
راه دیگری برای تجسم آن این است:
5 = 5 * 4! کجا 4! = 4 * 3!، 3! = 3 * 2! و به همین ترتیب تا زمانی که 1 بگیرید! = 1 * 0! که 1 است.
شما از این مفهوم برای ساختن برنامه فاکتوریل ما با استفاده از یک مفهوم محبوب به نام بازگشت استفاده خواهید کرد.
بازگشت چیست؟
بازگشت فرآیندی است که در آن یک تابع خود را فراخوانی می کند. یکی از مزایای اصلی این فرآیند این است که یک مشکل بزرگتر را به قطعات کوچکتر تقسیم می کند. این باعث می شود مشکل حل شود.
شما می توانید از بازگشت برای حل مسائل مناسب در سه مرحله آسان استفاده کنید:
- حالت پایه را پیدا کنید: اگر تابعی همیشه خودش را فراخوانی کند، فرآیند بی نهایت خواهد بود. برای جلوگیری از این اتفاق، یک مورد پایه تعریف کنید که به نقطه توقف منطقی برای عملکرد شما تبدیل شود. برای مثال، در یک برنامه فاکتوریل، محاسبه را روی صفر متوقف کنید. این مورد اصلی برای مشکل می شود.
- رابطه بین مسئله و زیرمسئله را بیابید: مسئله بزرگتر را به یک مشکل فرعی تقسیم کنید. به عنوان مثال، مشکل پیدا کردن فاکتوریل پنج است. فرض کنید پاسخ فاکتوریل چهار را دارید، یعنی 24. چگونه فاکتوریل پنج را با استفاده از 24 به دست خواهید آورد؟ با ضرب پنج خود در آن. این رابطه بین مشکل و مشکل فرعی است.
- رابطه موجود در مرحله 2 را تعمیم دهید: اکنون که رابطه را دارید، آن را بر حسب n تعمیم دهید. بنابراین، فاکتوریل یک عدد n حاصلضرب n و فاکتوریل n-1 است.
می توانید از این مفهوم برای یافتن مجموع n عدد طبیعی، محاسبه GCD، LCM، سری فیبوناچی و بررسی اعداد اول استفاده کنید.
کد شبه برای تابع فاکتوریال با استفاده از بازگشت
به این صورت است که از بازگشت استفاده می کنید و کد شبه را برای ساخت برنامه خود به هر زبانی می نویسید. با زبان های مختلف، نحو و اجرا تغییر می کند، اما منطق دست نخورده باقی می ماند.
function Fact(n)
If n == 0 then // base case
Return 1
Return n * Call Fact(n - 1) // generalized relation
برنامه فاکتوریال در C
C اولین زبان برنامه نویسی سطح بالا و مستقل از پلتفرم بود. این سینتکس دقیق دارد، به حروف بزرگ و کوچک حساس است و کد را با سریع ترین سرعت اجرا می کند. این یک زبان برنامه نویسی رویه ای است و از این رو شما هر تابعی را در بالای تابع اصلی اعلام می کنید. در اینجا نحوه ساخت برنامه فاکتوریل با استفاده از بازگشت در زبان C آمده است:
شما می توانید کل کد منبع برنامه فاکتوریل را با استفاده از بازگشت در C، جاوا و پایتون در اینجا پیدا کنید
مخزن GitHub
.
- فایل هدر خروجی ورودی استاندارد را برای نمایش خروجی به صفحه وارد کنید.#include
- تابع واقعیت را تعریف کنید و عدد صحیح n را به عنوان آرگومان بگیرید.int fact(int n) {
- حالت پایه تابع را با دستور if بنویسید و برابری آن را با استفاده از == بررسی کنید. اگر n برابر با صفر باشد، یک را برگردانید. اگر (n == 0) برگرداند 1؛
- معادله تعمیم یافته را بنویسید و حاصل ضرب n را با فراخوانی تابع زیرمسئله n-1 برگردانید. بازگشت n * fact(n – 1);}
- تابع main را اعلام کنید و یک متغیر از نوع عدد صحیح را مقداردهی کنید تا عدد فاکتوریل آن را ذخیره کنید.int main() { int num = 5;
- فاکتوریل عدد را با استفاده از تابع printf() نمایش دهید. %d مشخص کننده قالب اعشاری است. از هر یک از مشخص کننده های قالب استفاده کنید تا آن را با شماره ای که می خواهید فاکتوریل آن پیدا کنید جایگزین کنید و با فراخوانی تابع نتیجه را دریافت کنید. printf(“فاکتوریل %d %d است”، num، fact(num)); بازگشت 0;}
#include <stdio.h>
int fact(int n) {
if (n == 0)
return 1;
return n * fact(n - 1);
}
int main() {
int num = 5;
printf("Factorial of %d is %d", num, fact(num));
return 0;
}
برنامه فاکتوریال در جاوا
جاوا یک زبان برنامه نویسی کامپایل شده و مستقل از پلتفرم است. شما تمام کدها را در یک کلاس ذخیره می کنید و اجرا از تابع اصلی شروع می شود. حساس به حروف بزرگ و نحو است. کد کمی طولانی تر اما سریعتر از پایتون است. در اینجا نحوه ساخت برنامه فاکتوریل با استفاده از بازگشت در جاوا آمده است:
- Main class.class Main { را تعریف کنید
- یک تابع ثابت با نوع بازگشتی int تعریف کنید که متغیر n از نوع عدد صحیح را می پذیرد. شما یک متد استاتیک را اعلام کردید زیرا متد اصلی در جاوا نیز به عنوان استاتیک اعلام شده است. علاوه بر این، نمی توانید یک روش غیر استاتیک را از یک نمونه استاتیک فراخوانی کنید. static int fact(int n) {
- حالت پایه تابع را با دستور if بنویسید و برابری آن را با استفاده از == بررسی کنید. اگر n برابر با صفر باشد، یک را برگردانید. اگر (n == 0) برگردانید 1؛
- معادله تعمیم یافته را بنویسید و حاصل ضرب n را با فراخوانی تابع زیرمسئله n-1 برگردانید. return n * fact(n – 1); }
- تابع اصلی را در جاوا اعلام کنید. اصلاح کننده دسترسی را به عنوان عمومی اعلام کنید، بنابراین می تواند توسط تمام کلاس ها و روش های دیگر قابل دسترسی باشد. شما تابع اصلی را ثابت اعلام می کنید تا کامپایلر بتواند آن را بدون نمونه سازی کلاس فراخوانی کند. نوع برگشتی باطل است و آرگومان هایی از نوع String را می پذیرد. شماره ای که می خواهید فاکتوریل آن را پیدا کنید ذخیره کنید. public static void main (String[] args) { int num = 5;
- از متد println() که نمونه ای از کلاس PrintStream است که در کلاس System تعریف شده است برای نمایش فاکتوریل عدد استفاده کنید. System.out.println(“عامل ” + num + ” است ” + fact(num)); }}
class Main {
static int fact(int n) {
if (n == 0)
return 1;
return n * fact(n - 1);
}
public static void main(String[] args) {
int num = 5;
System.out.println("Factorial of " + num + " is " + fact(num));
}
}
برنامه فاکتوریال در پایتون
نوشتن کد در پایتون بسیار آسان و سرگرم کننده است. از آنجایی که این یک زبان مستقل از پلتفرم تفسیر شده است، لازم نیست نوع داده متغیرها را اعلام کنید. شما همچنین از اعلام کلاس ها و وارد کردن کتابخانه ها برای چنین برنامه ساده ای اجتناب می کنید. زمین بازی برای شروع کدنویسی آماده است.
نحو ساده‌تر است، با طول کد کمی، اما اجرای آن کمی بیشتر از زبان‌های دیگر طول می‌کشد. در اینجا نحوه ساخت برنامه فاکتوریل با استفاده از بازگشت در پایتون آمده است:
- واقعیت تابع را تعریف کنید که n.def fact(n) را به عنوان آرگومان می‌پذیرد:
- حالت پایه تابع را با دستور if بنویسید و برابری آن را با استفاده از == بررسی کنید. اگر n برابر با صفر باشد، یک را برگردانید. اگر n == 0: برگردانید 1
- معادله تعمیم یافته را بنویسید و حاصل ضرب n را با فراخوانی تابع زیرمسئله n-1 برگردانید. بازگشت n * واقعیت (n-1)
- عددی را که می‌خواهید فاکتوریل آن را پیدا کنید ذخیره کنید و با استفاده از عبارت print نمایش دهید.num = 5;print(“Factorial of”, num, “is”, fact(num))
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
num = 5;
print("Factorial of", num, "is", fact(num))
کاربردهای زیادی از بازگشت وجود دارد
بازگشت یک راه موثر برای حل مشکلات است. این هسته اصلی هوش مصنوعی است و در دنیای واقعی در بازی های پازل مانند شطرنج یا سودوکو کاربرد دارد.
همچنین یک روش قدرتمند برای مرتب‌سازی ساختارهای داده مانند درخت یا مرتب‌سازی الگوریتم‌هایی مانند مرتب‌سازی سریع و مرتب‌سازی ادغام است. همچنین می‌توانید از بازگشت در الگوریتم‌های جستجو مانند جستجوی باینری، عبارات ریاضی مانند سری فیبوناچی و موارد دیگر استفاده کنید.