Armstrong Number
يكون العدد الصحيح الموجب عدد أرمسترونغ عندما يساوي مجموع أرقامه، بحيث يُرفع كل رقم إلى قوة عدد أرقامه. يتكوّن 153 من ثلاثة أرقام، و1^3 + 5^3 + 3^3 = 153، لذا فهو عدد أرمسترونغ. اكتب دالة تستقبل n وتُرجع true إذا كان عدد أرمسترونغ، وfalse خلاف ذلك.
الدالة
- ninteger
- العدد الصحيح الموجب المراد اختباره
- تُرجعboolean
- يكون صحيحًا عندما يساوي n مجموع أرقامه، بحيث يُرفع كل رقم إلى عدد الأرقام.
القيود
1 ≤ n ≤ 109
أمثلة
- المدخلات
- n = 153
- المخرجات
- true
- الشرح
- يتكوّن
153من 3 أرقام، لذا يُكعَّب كل رقم:1 + 125 + 27 = 153. يعيد المجموع العدد نفسه، لذا تكون الإجابةtrue.
- المدخلات
- n = 10
- المخرجات
- false
- الشرح
10يتكون من رقمين، لذا نربّع كل رقم:1 + 0 = 1، وهذا لا يساوي10. الإجابة هيfalse.
- المدخلات
- n = 9474
- المخرجات
- true
- الشرح
- مع 4 أرقام، تكون القوة 4:
6561 + 256 + 2401 + 256 = 9474، وهو العدد نفسه، لذا تكون الإجابةtrue.
+31 اختبارات مخفية عند الإرسال
سؤال إضافي
يوجد 31 عددًا من أعداد أرمسترونغ بين 1 و10^9. هل يمكنك سردها جميعًا دون اختبار مليار عدد واحدًا تلو الآخر؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قبل أن تتمكن من رفع رقم إلى قوة، تحتاج إلى معرفة الأس. كم عدد الخانات في
n، وكيف يمكنك معرفة ذلك باستخدام الحساب؟n % 10هو الرقم الأخير، والقسمة الصحيحة على 10 تزيله. كرر ذلك حتى لا يتبقى شيء: بهذا تزور كل رقم، ويكون عدد الخطوات هو الأسk.احسب عدد الخانات في مرور واحد. ثم استخرجها مجددًا، وأضف كل خانة مرفوعة إلى القوة
kإلى مجموع ذي 64 بت، وأعِد ما إذا كان المجموع يساويnالأصلي.
الحل
التعريف هو الخوارزمية: أوجد عدد الأرقام في n، وارفع كل رقم إلى تلك القوة، واجمع النتائج ثم قارنها بـ n. تكمن المزالق في الأعداد. الأس هو عدد الأرقام في قيمة n هذه تحديدًا، وليس 3 ثابتًا، وقد يتجاوز المجموع عددًا صحيحًا من 32 بت: بالنسبة إلى 999999999، يكون 9 × 9^9 = 3486784401.
اقرأ الأرقام من السلسلة النصية
الفكرة
السلسلة العشرية لـ n تمنحك الأمرين اللذين تحتاج إليهما. طولها هو الأس k، ومحارفها هي الأرقام. بالنسبة إلى 9474، تتكون السلسلة من 4 محارف، لذا تجمع 9^4 + 4^4 + 7^4 + 4^4.
حوّل كل محرف إلى رقمه، وارفعه إلى القوة k، ثم أضفه إلى مجموع جارٍ. يكون n عددًا من أعداد أرمسترونغ بالضبط عندما يساوي المجموع النهائي n.
احتفظ بالمجموع في عدد صحيح ذي 64 بتًا. يتسع n في 32 بتًا، لكن ليس بالضرورة أن يتسع المجموع: فالقيمة 999999999 تعطي 3486784401، وهي أعلى من حد 32 بتًا البالغ 2147483647. ويستغرق حساب قوة باستخدام حلقة من k عملية ضرب k خطوة لكل رقم، لذا يكون فحص التعقيد O(k²)، حيث k تساوي تقريبًا log n. في هذه الحالة، لا يتجاوز ذلك 100 عملية ضرب، وتستهلك السلسلة k محرفًا من الذاكرة.
الخوارزمية
- حوِّل
nإلى سلسلة عشرية، واجعلkيساوي طولها. - اضبط
totalذي 64 بت على0. - لكل محرف، حوِّله إلى رقمه
dوأضفd^kإلىtotal، مع ضرب الأعداد الصحيحة بدلًا من استدعاء دالة أسّية بالأعداد العائمة. - أعِد ما إذا كانت قيمة
totalتساويn.
def isArmstrong(n):
digits = str(n)
k = len(digits)
total = 0
for ch in digits:
total += int(ch) ** k
return total == nافصل الأرقام وابحث عن قواها
الفكرة
تؤدي العمليات الحسابية المهمة نفسها من دون سلسلة. m % 10 هو الرقم الأخير من m، والقسمة الصحيحة على 10 تحذفه؛ لذا فإن حلقة تقسم على 10 حتى لا يتبقى شيء تحسب عدد الأرقام. تصبح 9474 947، ثم 94، ثم 9، ثم 0: أربع خطوات، لذا k = 4.
لا يوجد سوى عشرة أرقام، لذا أنشئ جدولًا powers[d] = d^k للقيم d من 0 إلى 9 قبل أن تجمع أي شيء. عندئذٍ لا يتطلب كل رقم سوى عملية بحث واحدة بدلًا من k عمليات ضرب. ينخفض زمن التحقق إلى O(log n)، ويكون حجم الجدول ثابتًا ويساوي عشرة، أي إن المساحة O(1).
تستخرج الحلقة الثانية الأرقام مجددًا وتضيف powers[m % 10] إلى المجموع. كل حد إما صفر أو موجب، لذا لا يتناقص المجموع أبدًا، وبمجرد أن يتجاوز n تكون الإجابة false. بالنسبة إلى 999999999، يحدث ذلك بعد ثلاثة أرقام، عند 3 × 387420489 = 1162261467. يظل الجدول بحاجة إلى 64 بتًا، لأن n = 10^9 يتكون من عشرة أرقام، و9^10 = 3486784401.
الخوارزمية
- احسب عدد أرقام
nبقسمة نسخة منه على 10 حتى تصل إلى 0؛ وسمِّ العددk. - املأ
powers[d] = d^kلكل رقمdمن 0 إلى 9، باستخدام أعداد صحيحة من 64 بت. - اقسم نسخة جديدة من
nعلى 10 مرة أخرى، مع إضافةpowers[m % 10]إلىtotalفي كل خطوة. - إذا تجاوزت
totalقيمةn، فأعِدfalseفورًا. - بعد الرقم الأخير، أَعِد ما إذا كانت
totalتساويn.
def isArmstrong(n):
# Count the digits: k is the exponent.
k = 0
m = n
while m > 0:
k += 1
m //= 10
# powers[d] = d^k for the ten possible digits.
powers = [d ** k for d in range(10)]
total = 0
m = n
while m > 0:
total += powers[m % 10]
if total > n:
return False # the total only grows
m //= 10
return total == n
أخطاء شائعة وحالات حدّية
الصيغة قصيرة، لذا تأتي الأخطاء من الأعداد المحيطة بها.
- أسّ ثابت مقداره 3. يقبل
153و370لكنه يرفض9474، ويرفض كل عدد أحادي الرقم أكبر من 1، لأن7^3 = 343. - مجموع من 32 بتًا. مجموع
999999999هو3486784401، ومدخل الجدول9^10هو العدد نفسه. في C، يكون هذا التجاوز سلوكًا غير معرّف، بينما تلتف Java وC# إلى عدد سالب، ويحدث انهيار في إصدار تصحيح الأخطاء من Rust. استخدمlongأوlong longأوi64. - الأسس ذات الفاصلة العائمة. تُرجع
powفي C وMath.powفي Java قيمة من النوعdouble. أعادت بعض بيئات تشغيل C قيمة أقل بقليل من عدد صحيح، مثل24.999...للقيمة5^2، ويقتطع التحويل القيمة إلى24. اضرب أعدادًا صحيحة في حلقة بدلًا من ذلك. - المقارنة مع القيمة الخاطئة. تقسم حلقات الأرقام
nحتى تصل إلى 0، لذا اعمل على نسخة وقارن المجموع بالقيمة الأصلية. - الترميز العلمي. في R، تكون نتيجة
as.character(1e9)هي"1e+09"، أي خمسة أحرف، لذا يستخدم حل R القائم على السلاسلsprintf("%.0f", n)للتنسيق.
أسئلة شائعة4
ما هو عدد أرمسترونغ؟
يساوي عدد أرمسترونغ، الذي يُسمّى أيضًا عددًا نرجسيًا، مجموع أرقامه، بعد رفع كل رقم إلى قوة عدد الأرقام. يُعدّ 153 عددًا من هذا النوع لأن 1^3 + 5^3 + 3^3 = 153، ويُعدّ 9474 كذلك لأن 9^4 + 4^4 + 7^4 + 4^4 = 9474. كل عدد مكوّن من رقم واحد يحقق هذا الشرط، لأن d^1 = d.
كم عدد أعداد أرمسترونغ؟
في النظام العشري، يوجد بالضبط 88 عددًا موجبًا من الأعداد ذات مجموع الأرقام مساويًا لقوة عدد أرقامها، وأكبرها مكوّن من 39 رقمًا. القائمة منتهية لأن عددًا مكوّنًا من k أرقام يكون على الأقل 10^(k-1)، بينما لا يتجاوز مجموع قوى أرقامه k × 9^k، وابتداءً من 61 رقمًا لا يمكن للمجموع أن يلحق به أبدًا. بين 1 و10^9 يوجد 31 عددًا منها.
لماذا يحتاج التحقق من عدد أرمسترونغ إلى عدد صحيح ذي 64 بت؟
المدخل يقع ضمن 32 بت، لكن مجموع الأرقام المرفوعة إلى قوى قد يكون أكبر من العدد بعدة مرات. يعطي 999999999 القيمة 9 × 9^9 = 3486784401، وهي أكبر من 2^31-1 = 2147483647. سيفيض المجموع ذو 32 بت عندها، لذا احتفظ بالمجموع والقوى في نوع ذي 64 بت.
ما هو التعقيد الزمني للتحقق مما إذا كان العدد من أعداد أرمسترونغ؟
يتكوّن n من نحو log n أرقام، وبحد أقصى 10 أرقام هنا. استخراج الأرقام والبحث عن كل قوة في جدول من عشرة عناصر يستغرق وقتًا O(log n) ومساحة O(1). أما إعادة حساب d^k باستخدام حلقة لكل رقم، فيجعل التعقيد O(log² n)، لكنه يظل سريعًا لهذا الحجم.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isArmstrong(n):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 153
المتوقع
true