Factorial
مضروب العدد الصحيح n، ويُكتب n!، هو حاصل ضرب كل عدد صحيح من 1 حتى n. على سبيل المثال، 4! = 1 × 2 × 3 × 4 = 24. وبالتعريف 0! = 1. تستقبل دالتك n وتُعيد n!.
الدالة
- ninteger
- العدد الصحيح الذي تحسب مضروبه
- تُرجعinteger
- حاصل ضرب كل عدد صحيح من 1 إلى n، وهو 1 عندما تكون n تساوي 0
القيود
0 ≤ n ≤ 12- الإجابة تقع ضمن نطاق عدد صحيح موقّع من 32 بت: أكبرها هو
12! = 479001600.
أمثلة
- المدخلات
- n = 5
- المخرجات
- 120
- الشرح
- اضرب
1 × 2 × 3 × 4 × 5. يكون حاصل الضرب التراكمي 1، ثم 2، ثم 6، ثم 24، وينتهي عند 120.
- المدخلات
- n = 0
- المخرجات
- 1
- الشرح
- لا يوجد شيء لضربه، وحاصل الضرب الذي لا يحتوي على عوامل يساوي
1. ولهذا السبب0! = 1.
سؤال إضافي
100! يتكوّن من 158 رقمًا. هل يمكنك حساب عدد الأصفار التي ينتهي بها دون حسابه؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب
4!و5!على هيئة حاصل ضرب. ما علاقة5!بـ4!؟5! = 5 × 4!. وبشكل عامn! = n × (n-1)!، وتنتهي السلسلة عند0! = 1.احتفظ بحاصل ضرب متراكم يبدأ عند
1واضربه في كل عدد من2إلىn. والبدء من 1 يعطي الإجابة الصحيحة أيضًا عند0و1.
الحل
للعاملي وصفان متكافئان، ويتحول كل منهما إلى كود. كحاصل ضرب، n! = 1 × 2 × ... × n، وهذا عبارة عن حلقة. وكتعريف递ي، 0! = 1 وn! = n × (n-1)!، وهذا عبارة عن دالة تستدعي نفسها. يتطلب كلاهما إجراء نحو n عملية ضرب. والحلقة هي الخيار الذي ينبغي إنهاء الدرس به، لأنها لا تحتاج إلى مكدس استدعاءات.
الاستدعاء الذاتي انطلاقًا من التعريف
الفكرة
يُعرَّف المضروب باستخدام مضروب أصغر: n! = n × (n-1)!. إذا كنت تعرف بالفعل 4! = 24، فحينها 5! = 5 × 24 = 120. تكتب الدالة العودية هذه الجملة على هيئة شيفرة. للحصول على factorial(n)، تطلب factorial(n-1) وتضرب الإجابة في n.
تحتاج الاستدعاءات إلى نقطة تتوقف عندها، وهي الحالة الأساسية: تُرجع factorial(0) القيمة 1 من دون استدعاء أي شيء. يُنقص كل استدعاء n بمقدار واحد، لذا تنطلق الاستدعاءات من 5 بهذا الترتيب: 5، 4، 3، 2، 1، 0. ثم تعود الإجابات عبر سلسلة الاستدعاءات: 1، 1، 2، 6، 24، 120.
هناك n + 1 استدعاء وn عملية ضرب، لذا فإن الزمن هو O(n). ينتظر كل استدعاء على المكدس إلى أن يعود الاستدعاء الذي تحته، لذا يحتفظ المكدس بـ n + 1 إطارًا، ما يعني أن المساحة هي O(n). عندما تكون n ≤ 12، يكون ذلك ضئيلًا، لكن النمط نفسه مع مدخل كبير يؤدي إلى تجاوز سعة المكدس.
الخوارزمية
- إذا كانت
nتساوي0، فأعِد1. هذه هي الحالة الأساسية. - وإلا، فاستدعِ الدالة باستخدام
n-1. - اضرب تلك النتيجة في
nوأعِدها.
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)الضرب في حلقة تكرار
الفكرة
فكّ الاستدعاء الذاتي، وستحصل على حاصل ضرب تراكمي. ابدأ بـ result = 1 واضربه في 2، ثم في 3، وهكذا حتى n. عندما تكون n = 5، تكون النتائج 1، 2، 6، 24، 120.
البدء من 1 يغطي أيضًا أصغر المدخلات. عندما تكون n = 0 وn = 1، تُنفَّذ الحلقة من 2 إلى n صفر مرة، وتُعيد الدالة القيمة الابتدائية 1، وهي الإجابة الصحيحة لكلتا الحالتين.
تنفّذ الحلقة n-1 عملية ضرب، بزمن O(n)، وتحتفظ برقم واحد، بمساحة O(1). لا يوجد مكدس استدعاءات قد يفيض، وهذا هو سبب توقّع المحاوِرين لهذه النسخة بعد أن تكون قد عرضت النسخة递ّية.
الخوارزمية
- عيّن
result = 1. - كرّر
kمن2إلىn، شاملًا الطرفين. - اضرب
resultفيkفي كل خطوة. - أعِد
result.
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
أخطاء شائعة وحالات حدّية
شفرة المضروب قصيرة، لذا تظهر الأخطاء عند الحالات الحدّية.
- بدء حاصل الضرب بـ
0. كل عملية ضرب تُبقيه عند 0. القيمة الابتدائية لحاصل الضرب هي1. - إيقاف الاستدعاء التعاودي عند
n == 1فقط. إذا استُدعيت الدالة بالقيمة0، فلن تصل أبدًا إلى الحالة الأساسية: ستتابع إلى -1 و-2 وما إلى ذلك حتى يفيض المكدس. اجعلn == 0هي الحالة الأساسية. - استخدام حلقة بشرط
k < nبدلًا منk ≤ n. يؤدي ذلك إلى إسقاط العامل الأخير وإرجاع(n-1)!، لذا تعطي5الناتج 24 بدلًا من 120. - تجاهل تجاوز السعة. لا تتسع القيمة
13! = 6227020800في عدد صحيح موقّع من 32 بت. في Java وC# يلتف حاصل الضرب بصمت إلى عدد خاطئ، وفي C يكون تجاوز السعة الموقّع سلوكًا غير معرّف، أما إصدار تصحيح الأخطاء في Rust فيؤدي إلى ذعر. يتسع عدد صحيح من 64 بت حتى20!؛ وبعد ذلك تحتاج إلى أعداد صحيحة كبيرة. - في Swift، كتابة
for k in 2...n. النطاق المغلق الذي تكون نهايته أصغر من بدايته يؤدي إلى انهيار وقت التشغيل عندما تكون قيمةnهي 0 أو 1.
أسئلة شائعة3
ما هو التعقيد الزمني لحساب مضروب عدد؟
تنفّذ كلٌّ من الحلقة والاستدعاء الذاتي عملية ضرب واحدة لكل عدد حتى n، لذا يكون الزمن O(n). تحتاج الحلقة إلى مساحة إضافية O(1). يحتفظ الاستدعاء الذاتي بإطار مكدس واحد لكل استدعاء حتى تُرجع الحالة الأساسية، لذا يستخدم مساحة O(n).
لماذا يساوي 0! العدد 1؟
0! هو حاصل ضرب لا شيء من الأعداد، وحاصل ضرب بلا عوامل يساوي 1، تمامًا كما أن مجموعًا بلا حدود يساوي 0. كما أنه يُبقي القاعدة n! = n × (n-1)! صحيحة عند n = 1: 1! = 1 × 0! = 1. ويتفق ذلك مع العدّ: توجد طريقة واحدة بالضبط لترتيب صفر من العناصر.
هل العودية أم الحلقة أفضل لحساب المضروب؟
إنهما يجريان عمليات الضرب نفسها ويُرجعان الإجابة نفسها. تبدو النسخة العودية كالتعريف الرياضي، ولهذا تُعدّ تمرينًا كلاسيكيًا أوليًا على الاستدعاء الذاتي. تستخدم الحلقة ذاكرة ثابتة ولا يمكن أن تتسبب في تجاوز سعة مكدس الاستدعاءات، لذا فهي الخيار الأفضل في الشيفرة الفعلية.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def factorial(n):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
n = 5
الإخراج المتوقع
120