Steps to Reduce a Number to Zero
ابدأ بعدد صحيح غير سالب n، وكرّر قاعدة واحدة حتى يصل إلى 0: إذا كان العدد زوجيًا، فاقسمه على 2؛ وإذا كان فرديًا، فاطرح منه 1. يُعدّ كل تطبيق للقاعدة خطوة واحدة. أرجِع عدد الخطوات اللازمة.
الدالة
- ninteger
- العدد الابتدائي
- تُرجعinteger
- عدد الخطوات حتى يصل العدد إلى 0
القيود
0 ≤ n ≤ 231 - 1
أمثلة
- المدخلات
- n = 14
- المخرجات
- 6
- الشرح
- يتناقص العدد على النحو التالي
14 → 7 → 6 → 3 → 2 → 1 → 0: ثلاث عمليات قسمة على 2 وثلاث عمليات طرح،6خطوات.
- المدخلات
- n = 8
- المخرجات
- 4
- الشرح
8 → 4 → 2 → 1 → 0. تنقسم قوة العدد اثنين إلى النصف ثلاث مرات، وتحتاج إلى عملية طرح واحدة في النهاية، أي4خطوات.
- المدخلات
- n = 123
- المخرجات
- 12
- الشرح
123في النظام الثنائي هو1111011: سبعة أرقام وستة آحاد. تتطلب الآحاد الستة ست عمليات طرح، وتتطلب الأرقام الستة التي تلي الواحد الأول ست عمليات قسمة على اثنين، أي12خطوة.
+12 اختبارات مخفية عند الإرسال
سؤال إضافي
افترض أن العدد الفردي يمكن أن يزيد بمقدار 1 بدلًا من أن ينقص. ما أقل عدد من الخطوات اللازمة للوصول إلى 0، وما الخيار الصحيح للعدد 15؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
طبّق القاعدة يدويًا على
14وأحصِ. كم مرة يمكن تنصيف عدد ذي 32 بت؟اكتب الأعداد بالنظام الثنائي. ماذا يحدث للأرقام عند القسمة على النصف، وماذا يحدث عند طرح
1من عدد فردي؟كل بت بقيمة 1 يتطلب عملية طرح واحدة، وكل رقم ثنائي باستثناء الرقم الأول يتطلب عملية تنصيف واحدة. تعامل مع
n == 0بشكل منفصل.
الحل
تنفيذ القاعدة سريع بالفعل: كل عملية قسمة إلى النصف تقسم العدد إلى النصف، لذا فإن 2^31 - 1 يحتاج إلى 61 خطوة فقط. الجزء المثير للاهتمام هو ملاحظة ما تفعله القاعدة بالأرقام الثنائية. تؤدي القسمة إلى النصف إلى حذف الرقم الأخير، وطرح 1 من عدد فردي يحوّل آخر 1 فيه إلى 0. لذا فالإجابة هي عدد الأرقام زائد عدد الواحدات، ناقص واحد.
شغّل العملية
الفكرة
نفّذ ما تقوله العبارة. ما دام n أكبر من 0، اقسمه على اثنين إذا كان زوجيًا، واطرح 1 إذا كان فرديًا، ثم احسب الخطوة. بالنسبة إلى 14، تزور الحلقة القيم 7 و6 و3 و2 و1 و0، أي ست خطوات.
الحلقة قصيرة لأن الطرح يجعل العدد الفردي زوجيًا دائمًا، لذا تكون هناك عملية قسمة على اثنين كل خطوتين على الأقل. العدد الأصغر من 2^31 يُقسم على اثنين بحد أقصى 30 مرة قبل أن يصل إلى 1، ومع عملية طرح واحدة قبل كل قسمة على اثنين وعملية طرح واحدة في النهاية، تُنفَّذ الحلقة بحد أقصى 61 مرة.
لا يحتاج الإدخال 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عُدّ الأرقام الثنائية
الفكرة
تابع العملية بالنظام الثنائي. 14 هو 1110. القسمة على 2 تحذف الرقم الأخير: 111. طرح 1 من عدد فردي يمحو رقمه الأخير، وهو 1: 110. إذن، كل خطوة إما أن تحذف الرقم الأخير أو تحوّل 1 في النهاية إلى 0.
والآن احسب. يجب محو كل 1 في العدد مرة واحدة، وهذا يتطلب عملية طرح واحدة لكل 1. ويجب حذف كل رقم، وهذا يتطلب عملية قسمة على 2 واحدة لكل رقم، باستثناء الرقم الأول: عندما لا يتبقى سوى 1، فإن عملية الطرح التي تمحوه تعطي 0 بالفعل. إذن الإجابة هي length - 1 + ones. بالنسبة إلى 14 = 1110، تكون النتيجة 4 - 1 + 3 = 6.
تحتوي Java وC وC++ وGo وRust وSwift على دوال مدمجة لإجراء كلا العدّين (عدّ الأصفار البادئة وعدّ البتات ذات القيمة 1)، وتُترجم إلى تعليمة واحدة على معظم المعالجات. أما اللغات الأخرى فتكتب n بالنظام الثنائي وتعدّ المحارف، أو تقرأ الأرقام باستخدام % 2؛ وهذا يتطلب حلقة لا تتجاوز 31 دورة. أعد 0 أولًا عندما يكون 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). - احتساب خطوة قسمة على 2 للرقم الأول. تتحول
1إلى0بالطرح، لذا فإن8 = 1000تحتاج إلى4 - 1 + 1 = 4خطوات، لا5. - دمج خطوتين في خطوة واحدة. كتابة
n = (n-1) / 2لعدد فردي تنفّذ الطرح والقسمة على 2 معًا، لذا يجب إضافة2إلى العدد، لا1. وإلا فستكون نتيجة14هي4بدلًا من6. - تكرار الحلقة ما دام
n > 1. يتوقف ذلك قبل أوانه بخطوة واحدة، لأن الخطوة الأخيرة تحوّل1إلى0. يجب أن تستمر الحلقة حتى تصبحnمساويةً لـ0.
أسئلة شائعة4
ما هو التعقيد الزمني لاختزال عدد إلى الصفر؟
يستغرق تنفيذ العملية زمنًا O(log n)، لأن العدد ينخفض إلى النصف على الأقل كل خطوتين. بالنسبة إلى n = 2^31 - 1، يكون ذلك 61 خطوة. ويستغرق عدّ الأرقام الثنائية باستخدام تعليمات البت المضمّنة زمنًا O(1).
ما صيغة عدد الخطوات؟
بالنسبة إلى n > 0، الإجابة هي طول n بالثنائي، ناقص واحد، زائد عدد البتات التي قيمتها 1. كل بت قيمته 1 يتطلب عملية طرح واحدة، وكل خانة بعد الخانة الأولى تتطلب عملية تنصيف واحدة. بالنسبة إلى n = 0، الإجابة هي 0.
أيُّ عددٍ أقل من 2^31 يتطلب أكبر عدد من الخطوات؟
2^31 - 1، وهو واحد وثلاثون رقمًا 1 بالنظام الثنائي. يتطلب 31 عملية طرح و30 عملية تنصيف، أي 61 خطوة إجمالًا. لا يوجد عدد أصغر يحتوي على هذا العدد من الخانات وهذا العدد من الأرقام 1 في الوقت نفسه.
لماذا يُعادل التنصيف الإزاحة إلى اليمين؟
العدد الثنائي هو مجموع قوى العدد اثنين. قسمة عدد زوجي على 2 تُنقص كل قوة بمقدار واحد، ما ينقل كل رقم خانة واحدة إلى اليمين ويحذف 0 الأخيرة. وهذا بالضبط ما تفعله n >> 1، لذا يمكنك كتابة عملية التنصيف بأي من الطريقتين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def numberOfSteps(n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 14
المتوقع
6