فرادرسبرنامه محاسبه ضریب دو جمله ای – راهنمای کاربردی
در این مطلب، روش نوشتن برنامه محاسبه ضریب دو جمله ای یا در واقع، تابعی که دو پارامتر n و k را از ورودی بگیرد و مقدار ضریب دو جمله‌ای C(n, k) را بازگرداند، بیان شده است. همچنین، پیاده‌سازی روش مذکور در زبان‌های برنامه‌نویسی ++C و C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و PHP انجام شده است. در ادامه، تعاریف متداول ضریب دو جمله ای آمده است:
- ضریب دو جمله ای C(n, k) را می‌توان به عنوان ضریب X^k در بسط تعریف کرد.
- یک ضریب دو جمله‌ای C(n, k)، تعداد راه‌هایی که k شی را می‌توان از بین n شی، صرف‌نظر از ترتیب آن‌ها، انتخاب کرد به دست می‌دهد. به بیان رسمی، تعداد زیرمجموعه‌های k-عنصر (یا k ترکیب) از یک مجموعه n عنصری را به دست می‌دهد.
اکنون، هدف نوشتن تابعی است که دو پارامتر n و k را از ورودی بگیرد و مقدار ضریب دو جمله‌ای C(n, k) را بازگرداند. برای مثال، تابع باید 6 را برای n = 4 و k = 2 و ۱۰ را برای n = 5 و k = 2 بازگرداند.
محاسبه ضریب دو جمله ای با روش بازگشتی
مقدار C(n, k) را می‌توان به صورت بازگشتی، با استفاده از رابطه استانداردی که در ادامه آمده است برای ضریب دو جمله‌ای محاسبه کرد.
C(n, k) = C(n-1, k-1) + C(n-1, k) C(n, 0) = C(n, n) = 1
در ادامه، پیاده‌سازی بازگشتی ساده (Naive Recursive) که به سادگی ساختار بازگشتی بیان شده در بالا را اعمال کند، ارائه شده است.
پیاده‌سازی روش ساده در ++C
پیاده‌سازی روش بازگشتی در C
پیاده‌سازی روش بازگشتی در جاوا
پیاده‌سازی روش بازگشتی در پایتون
پیاده‌سازی روش بازگشتی در #C
پیاده‌سازی روش بازگشتی در PHP
خروجی قطعه کدهای بالا، به صورت زیر است.
Value of C(52) is 10
محاسبه ضریب دو جمله ای با برنامه‌نویسی پویا
لازم به ذکر است که تابع بالا، زیرمسائل مشابهی را دوباره و دوباره محاسبه می‌کند. درخت بازگشتی زیر با n = 5 و k = 2 در این راستا قابل توجه است. تابع C(3, 1) دو بار فراخوانی می‌شود. برای مقادیر n بزرگ، فراخوانی‌های تکراری زیادی برای زیرمسائل مشابه متعددی وجود خواهد داشت.
C(5, 2)
/ \
C(4, 1) C(4, 2)
/ \ / \
C(3, 0) C(3, 1) C(3, 1) C(3, 2)
/ \ / \ / \
C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)
از آنجا که زیرمسائل تکراری مجددا فراخوانی می‌شوند، این مساله دارای خصوصیت هم‌پوشانی است. بنابراین، مسئله ضریب چند جمله‌ای دارای هر دو خصوصیت مسائل برنامه‌نویسی پویا است. (همچون دیگر مسائل برنامه‌نویسی پویا، محاسبه مجدد زیرمسائل مشابه با ساخت یک آرایه موقت C[][] در حالت پایین به بالا است). در ادامه، پیاده‌سازی راهکار این مسئله با استفاده از برنامه‌نویسی پویا، در زبان‌های برنامه‌نویسی گوناگون انجام شده است.
پیاده‌سازی روش برنامه‌نویسی پویا در ++C
پیاده‌سازی روش برنامه‌نویسی پویا در C
پیاده‌سازی روش برنامه‌نویسی پویا در جاوا
پیاده‌سازی روش برنامه‌نویسی پویا در پایتون
پیاده‌سازی روش برنامه‌نویسی پویا در #C
پیاده‌سازی روش برنامه‌نویسی پویا در PHP
خروجی قطعه کدهای بالا، به صورت زیر است.
Value of C[5][2] is 10
پیچیدگی زمانی از درجه O(n*k) و فضای کمکی از درجه O(n*k) است. در ادامه، نسخه بهینه شده فضایی از رویکرد بالا، پیاده‌سازی شده است.
پیاده‌سازی نسخه بهینه در C و ++C
پیاده‌سازی نسخه بهینه در جاوا
پیاده‌سازی نسخه بهینه در پایتون
پیاده‌سازی نسخه بهینه در #C
پیاده‌سازی نسخه بهینه در PHP
خروجی قطعه کدهای بالا، به صورت زیر است.
Value of C[5][2] is 10
پیچیدگی زمانی این روش از درجه O(n*k) و پیچیدگی فضایی آن از درجه O(k) است. در ادامه، توصیف دقیق‌تری از آنچه در حال وقوع است را مشاهده می‌کنید.
1==========>> n = 0, C(0,0) = 1 1–1========>> n = 1, C(1,0) = 1, C(1,1) = 1 1–2–1======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1 1–3–3–1====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1 1–4–6–4–1==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1
بنابراین، در اینجا هر حلقه‌ای روی i، در واقع iاُمین سطر از مثلث خیام پاسکال را با استفاده از سطر (i-1)اُم می‌سازد.
در هر زمان، هر عنصری از آرایه C مقداری خواهد داشت (صفر یا بیشتر) و در تکرار بعدی، مقدار برای آن عناصر بر اساس تکرار قبلی به دست می‌آید. در عبارت C[j] = C[j] + C[j-1]، قسمت سمت راست معادله مقداری را نشان می‌دهد که از تکرار پیشین به دست می‌آید (یک سطر از مثلث خیام پاسکال، به سطرهای پیشین بستگی دارد). سمت راست، نشانگر مقدار تکرار کنونی است که به وسیله این عبارت به دست می‌آید. فرض می‌شود که هدف، محاسبه C(4, 3) است. این یعنی: n=4 و k=3. در همین راستا، داریم: همه عناصر آرایه C با اندازه ۴ (k+1) با صفر مقداردهی اولیه می‌شوند. یعنی:
C[0] = C[1] = C[2] = C[3] = C[4] = 0 Then C[0] is set to 1 For i = 1: C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1 For i = 2: C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1 C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2 For i=3: C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1 C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3 C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3 For i=4: C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1 C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4 C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6 C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4
C(4,3) = 4، پاسخ مثال بیان شده در بالا است. اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^
