Armstrong Number

+10

يكون العدد الصحيح الموجب عدد أرمسترونغ عندما يساوي مجموع أرقامه، بحيث يُرفع كل رقم إلى قوة عدد أرقامه. يتكوّن 153 من ثلاثة أرقام، و1^3 + 5^3 + 3^3 = 153، لذا فهو عدد أرمسترونغ. اكتب دالة تستقبل n وتُرجع true إذا كان عدد أرمسترونغ، وfalse خلاف ذلك.

الدالة

isArmstrong(n: integer) → boolean

ninteger: العدد الصحيح الموجب المراد اختباره
تُرجعboolean: يكون صحيحًا عندما يساوي n مجموع أرقامه، بحيث يُرفع كل رقم إلى عدد الأرقام.

القيود

1 ≤ n ≤ 10⁹

أمثلة

المدخلات: 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 عددًا من أعداد أرمسترونغ بين 1 و10^9. هل يمكنك سردها جميعًا دون اختبار مليار عدد واحدًا تلو الآخر؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

التعريف هو الخوارزمية: أوجد عدد الأرقام في 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) للتنسيق.

أسئلة شائعة3

ما هو عدد أرمسترونغ؟

يساوي عدد أرمسترونغ، الذي يُسمّى أيضًا عددًا نرجسيًا، مجموع أرقامه، بعد رفع كل رقم إلى قوة عدد الأرقام. يُعدّ 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 بت.

def isArmstrong(n):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

n = 153

الإخراج المتوقع

true