Steps to Reduce a Number to Zero

Q: ما هو التعقيد الزمني لاختزال عدد إلى الصفر؟

يستغرق تشغيل العملية زمنًا قدره O(log n) ، لأن كل خطوة ثانية على الأقل تقسم العدد إلى النصف: 61 خطوة عندما تكون n = 2^31 - 1 . ويستغرق عدّ الأرقام الثنائية باستخدام تعليمات البت المضمّنة زمنًا قدره O(1) .

Q: أي عدد أقل من 2^31 يحتاج إلى أكبر عدد من الخطوات؟

2^31 - 1 ، وهو عدد يتكوّن من واحد وثلاثين رقمًا 1 في النظام الثنائي. يحتاج إلى 31 عملية طرح و 30 عملية تنصيف، أي 61 خطوة إجمالًا. لا يوجد عدد أصغر يحتوي على هذا العدد من الخانات ومن أرقام 1 في الوقت نفسه.

Q: لماذا يُعادل التنصيف الإزاحة إلى اليمين؟

العدد الثنائي هو مجموع قوى العدد اثنين. قسمة عدد زوجي على 2 تخفّض كل قوة بمقدار واحد، ما يحرّك كل رقم منزلة واحدة إلى اليمين ويحذف 0 الأخيرة. وهذا ما تفعله n >> 1 ، لذا يمكنك كتابة عملية التنصيف بأي من الطريقتين.

مبتدئمعالجة البتات رياضيات ومحاكاة

+10

ابدأ بعدد صحيح غير سالب n وكرّر قاعدة واحدة حتى يصل إلى 0: إذا كان العدد زوجيًا، فاقسمه على 2؛ وإذا كان فرديًا، فاطرح 1. يُعدّ كل تطبيق للقاعدة خطوة واحدة. أعد عدد الخطوات اللازمة.

الدالة

numberOfSteps(n: integer) → integer

ninteger: العدد الابتدائي
تُرجعinteger: عدد الخطوات حتى يصل العدد إلى 0

القيود

0 ≤ n ≤ 2³¹ - 1

أمثلة

المدخلات: n = 14
المخرجات: 6
الشرح: يتناقص العدد هكذا: 14 → 7 → 6 → 3 → 2 → 1 → 0: ثلاث عمليات تنصيف وثلاث عمليات طرح، 6 خطوات.

المدخلات: n = 8
المخرجات: 4
الشرح: 8 → 4 → 2 → 1 → 0. تتنصّف قوة العدد 2 ثلاث مرات، وتحتاج إلى عملية طرح واحدة في النهاية، أي 4 خطوات.

المدخلات: n = 123
المخرجات: 12
الشرح: 123 بالنظام الثنائي هو 1111011: سبعة أرقام وستة أرقام 1. تتطلب أرقام 1 الستة ست عمليات طرح، وتتطلب الأرقام الستة التي تأتي بعد الرقم 1 الأول ست عمليات تنصيف، أي 12 خطوة.

سؤال إضافي

افترض أن العدد الفردي يمكنه أيضًا أن يزداد بمقدار 1. ما أقل عدد من الخطوات اللازمة للوصول إلى 0، وأي اختيار هو الصحيح للعدد 15؟

تلميحات

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

فُتح 0 من 3

الحل

في النظام الثنائي، يؤدي التنصيف إلى إسقاط الرقم الأخير، ويحوّل طرح 1 من عدد فردي آخرَ 1 فيه إلى 0. لذا، عندما يكون n > 0، تكون الإجابة هي عدد الأرقام الثنائية زائد عدد مرات ظهور الرقم 1، ناقص واحد. كما أن تطبيق القاعدة مباشرةً سريع: بحد أقصى 61 خطوة.

شغّل العملية

الفكرة

طبّق القاعدة وعدّ الخطوات. بالنسبة إلى 14، تزور الحلقة القيم 7 و6 و3 و2 و1 و0: ست خطوات.

الطرح يجعل العدد الفردي زوجيًا دائمًا، لذا تكون كل خطوة ثانية على الأقل عملية تنصيف. يُنصَّف العدد الأصغر من 2^31 بحد أقصى 30 مرة قبل أن يصل إلى 1. ومع طرح واحد قبل كل عملية تنصيف وطرح واحد في النهاية، تُنفَّذ الحلقة بحد أقصى 61 مرة. عندما يكون n = 0، لا تُنفَّذ الحلقة مطلقًا وتكون الإجابة 0.

الخوارزمية

عيّن steps إلى 0.
طالما أن n > 0: إذا كان n زوجيًا، فعيّن n إلى n / 2، وإلا فعيّنه إلى n-1.
أضف 1 إلى steps في كل مرة.
أعِد steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

عُدّ الأرقام الثنائية

الفكرة

كل خطوة إما تحذف الرقم الثنائي الأخير أو تحوّل 1 الأخيرة إلى 0. العدد 14 هو 1110: القسمة على اثنين تعطي 111، والطرح من 111 يعطي 110. يجب تصفير كل 1 مرة واحدة، وهذا يتطلب عملية طرح واحدة لكل 1. ويجب حذف كل رقم، بعملية قسمة على اثنين واحدة لكل رقم، باستثناء الواحد المتصدر: عندما لا يتبقى سوى 1، فإن طرحه يعطي 0 بالفعل. لذا تكون الإجابة length - 1 + ones، وبالنسبة إلى 14 تكون 4 - 1 + 3 = 6.

تتضمن Java وC وC++ وGo وRust وSwift دوالًا مضمّنة لحساب كلا العددين (الأصفار المتصدرة والبتات المضبوطة)، وتُترجم إلى تعليمة واحدة على معظم المعالجات. أما اللغات الأخرى فتقرأ الأرقام باستخدام % 2 ضمن حلقة لا تتجاوز 31 دورة. تعامل مع n = 0 أولًا: إذ لا يحتوي على أي بت بقيمة 1 يستند إليه القانون.

الخوارزمية

إذا كان n == 0، فأعِد 0.
أوجد length، وهو عدد الأرقام الثنائية في n.
أوجد ones، وهو عدد البتات التي قيمتها 1.
أعِد length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

أخطاء شائعة وحالات حدّية

نسيان n = 0 في صيغة البتات. تعطي length - 1 + ones القيمة -1، وقد يكون عدد الأصفار البادئة 0 غير معرّف (__builtin_clz(0) في C).
احتساب عملية تنصيف للرقم الأول. تتحول 1 إلى 0 بعملية طرح، لذا تحتاج 8 = 1000 إلى 4 - 1 + 1 = 4 خطوات، وليس 5.
كتابة n = (n-1) / 2 لعدد فردي واحتساب خطوة واحدة. هذا السطر ينفّذ خطوتين، لذا تكون النتيجة للعدد 14 هي 4 بدلًا من 6.
التكرار ما دام n > 1. يتوقف ذلك قبل الخطوة الأخيرة، التي تحوّل 1 إلى 0.

أسئلة شائعة3

ما هو التعقيد الزمني لاختزال عدد إلى الصفر؟

يستغرق تشغيل العملية زمنًا قدره O(log n)، لأن كل خطوة ثانية على الأقل تقسم العدد إلى النصف: 61 خطوة عندما تكون n = 2^31 - 1. ويستغرق عدّ الأرقام الثنائية باستخدام تعليمات البت المضمّنة زمنًا قدره O(1).

أي عدد أقل من 2^31 يحتاج إلى أكبر عدد من الخطوات؟

2^31 - 1، وهو عدد يتكوّن من واحد وثلاثين رقمًا 1 في النظام الثنائي. يحتاج إلى 31 عملية طرح و30 عملية تنصيف، أي 61 خطوة إجمالًا. لا يوجد عدد أصغر يحتوي على هذا العدد من الخانات ومن أرقام 1 في الوقت نفسه.

لماذا يُعادل التنصيف الإزاحة إلى اليمين؟

العدد الثنائي هو مجموع قوى العدد اثنين. قسمة عدد زوجي على 2 تخفّض كل قوة بمقدار واحد، ما يحرّك كل رقم منزلة واحدة إلى اليمين ويحذف 0 الأخيرة. وهذا ما تفعله n >> 1، لذا يمكنك كتابة عملية التنصيف بأي من الطريقتين.

def numberOfSteps(n):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

n = 14

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