Square Root (Integer)
تستقبل دالتك عددًا صحيحًا غير سالب x وتُعيد جذره التربيعي الصحيح: أكبر عدد صحيح r بحيث r × r ≤ x. أي إن الجذر يُقرَّب إلى الأسفل، لذا إذا لم يكن العدد مربعًا كاملًا، فستكون النتيجة جذر المربع الكامل الأصغر منه. احسبه بنفسك، دون استخدام دالة جذر تربيعي أو أسّ مدمجة.
الدالة
- xinteger
- العدد الصحيح غير السالب الذي نريد أخذ جذره التربيعي
- تُرجعinteger
- الجذر التربيعي لـ x مقربًا إلى الأسفل لأقرب عدد صحيح
القيود
0 ≤ x ≤ 231 - 1- لا تستدعِ دالة جذر تربيعي أو قوة أو أسّ مضمّنة.
أمثلة
- المدخلات
- x = 17
- المخرجات
- 4
- الشرح
4 × 4 = 16لا يزيد على 17، لكن5 × 5 = 25أكبر، لذا يُقرَّب جذر 17 إلى الأسفل ليصبح 4.
- المدخلات
- x = 49
- المخرجات
- 7
- الشرح
- 49 مربع كامل،
7 × 7 = 49، لذا لا يتم تقريب أي شيء والإجابة هي 7 بالضبط.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف ستجد الجذر التكعيبي الصحيح بدلًا من ذلك، أي أكبر r بحيث r × r × r ≤ x، إذا كان من الممكن أن تكون x سالبة أيضًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
الإجابة هي أكبر عدد صحيح مربعه لا يتجاوز
x. إذا ربّعت عددًا مرشحًاmوقارنته بـx، فماذا تعرف عن الأعداد المرشحة الأصغر منmوالأكبر منه؟تزداد المربعات كلما زادت
m. إذا كانm × m ≤ x، فإن كل مرشح أصغر يناسب أيضًا؛ وإذا كانm × m > x، فإن كل مرشح أكبر لا يناسب. تشكّل المرشحات سلسلة مرتبة من القيم المناسبة تليها القيم غير المناسبة، ويجد البحث الثنائي موضع الانتقال بينها.ابحث عن
mبين 0 وx. عندما يكونm × m ≤ x، احتفظ بـmوابحث إلى يمينه؛ وإلا فابحث إلى يساره. احسب مربعmباستخدام عدد صحيح من 64 بت، لأن قيمةmالأولى قد تكون نحو10^9.
الحل
العدّ تصاعديًا بدءًا من 0 حتى يتجاوز المربع التالي x يعطي الإجابة الصحيحة، لكنه يتطلب خطوة لكل وحدة من الجذر، أي نحو 46000 خطوة قرب الحد الأعلى للنطاق. الأعداد المربعة 0 و1 و4 و9 و16 وما إلى ذلك مرتبة، لذا يمكنك إجراء بحث ثنائي للعثور على آخر قيمة مرشحة يكون مربعها أقل من أو يساوي x، وإنهاء العملية في نحو 31 خطوة. المشكلة في الطريقتين هي تجاوز السعة: فمربع القيمة المرشحة لا يتسع دائمًا في 32 بتًا.
عُدّ تصاعديًا بدءًا من الصفر
الفكرة
الجذر هو أكبر قيمة لـ r تحقق r × r ≤ x. ابدأ من r = 0، إذ إن مربعه يحقق الشرط دائمًا، واستمر في الانتقال إلى r + 1 ما دام مربع العدد التالي يحقق الشرط. تتوقف الحلقة عند أول قيمة لـ r يكون العدد الذي يليها أكبر من اللازم، وهي الجذر بالضبط. عندما تكون x = 17، فإن المربعات 1 و4 و9 و16 تحقق الشرط، أما 25 فلا يحققه، لذا تتوقف الحلقة عند 4.
تُنفَّذ الحلقة مرة واحدة لكل وحدة من الإجابة. أكبر إجابة هنا هي 46340، لذا لن تتجاوز الخطوات 46340 خطوة، وهذا يُنجز بسرعة. لكن التعقيد هو O(√x)، وهو يزداد مع قيمة الإدخال: قد يستغرق x ذو 64 بت نحو 3 × 10^9 خطوة.
انتبه إلى الفحص الأخير. عندما تكون x = 2^31 - 1، تحسب الحلقة مربع 46341 لتعرف أنه أكبر من اللازم، لكن 46341 × 46341 = 2147488281 لا يتسع في عدد صحيح ذي 32 بت. احسب المربع باستخدام 64 بت.
الخوارزمية
- عيّن
root = 0. - ما دام
(root + 1) × (root + 1) ≤ x، زِدrootبمقدار 1. - أعِد
root.
def mySqrt(x):
root = 0
while (root + 1) * (root + 1) <= x:
root += 1
return rootالبحث الثنائي عن الإجابة
الفكرة
رتّب المرشحين من 0 و1 و2 حتى x، واطرح على كلٍّ منهم السؤال نفسه: هل مربعه أصغر من أو يساوي x؟ ستكون الإجابات نعم، نعم، نعم، ثم لا لكل مرشح بعد الجذر، لأن المربعات تزداد فقط. الجذر هو آخر إجابة بنعم. وهذا التسلسل المرتب من إجابات نعم تليها إجابات لا هو ما صُمم البحث الثنائي للتعامل معه.
احتفظ بالنطاق من lo إلى hi للمرشحين الذين لم يُحسم أمرهم بعد، وابدأ من 0 إلى x، واحتفظ بالمتغير best لأكبر مرشح كانت إجابته نعم حتى الآن. اختبر المنتصف mid. إذا كان mid × mid ≤ x، فالجذر يساوي mid أو أكبر منه: خزّنه في best، وانقل lo إلى mid + 1. وإلا فالجذر أصغر: انقل hi إلى mid - 1. عندما يصبح النطاق فارغًا، يكون best هو الجذر.
تتبّع x = 17. يختبر النطاق من 0 إلى 17 العدد 8 (64، كبير جدًا)، ثم يختبر النطاق من 0 إلى 7 العدد 3 (9، مناسب، best = 3)، ثم يختبر النطاق من 4 إلى 7 العدد 5 (25، كبير جدًا)، ثم يختبر النطاق من 4 إلى 4 العدد 4 (16، مناسب، best = 4). يصبح النطاق فارغًا، والإجابة هي 4. في كل خطوة ينقسم النطاق إلى نصفين، لذا يتطلب x = 2^31 - 1 31 خطوة. أجرِ عملية التربيع باستخدام 64 بت: أول mid هناك هو 1073741823.
الخوارزمية
- اضبط
lo = 0وhi = xوbest = 0. - ما دام
lo ≤ hi، احسبmid، منتصف النطاق. - إذا كان
mid × mid ≤ x(باستخدام 64 بت)، فاضبطbest = midوlo = mid + 1. - وإلا، فاضبط
hi = mid - 1. - أعِد
best.
def mySqrt(x):
lo, hi = 0, x
best = 0 # largest candidate seen so far whose square fits
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
best = mid # mid fits, so try a larger root
lo = mid + 1
else:
hi = mid - 1 # mid is too big
return best
أخطاء شائعة وحالات حدّية
البحث نفسه قصير؛ أما الأخطاء فتختبئ في العمليات الحسابية والحالات الحدّية.
- تربيع الأعداد باستخدام 32 بت. عندما تكون
x = 2147483647، يكون أول مرشح للمنتصف هو 1073741823، ومربعه يساوي نحو1.15 × 10^18. فيintذي 32 بت، يلتف الناتج إلى قيمة خاطئة، وقد تبدو حتى صغيرة بما يكفي لتناسب النطاق. أجرِ عملية الضرب باستخدام 64 بت، أو قارِن باستخدامm ≤ x / mبدلًا من ذلك. - تربيع المرشح التالي باستخدام 32 بت في حلقة العد. الجذر التربيعي لـ
2^31 - 1هو 46340، وآخر فحص في الحلقة يربّع 46341، ما يعطي 2147488281، وهي قيمة تتجاوز حد 32 بت. - تجاوز نطاق 32 بت. الحدّ الحصري
hi = x + 1يساوي 2147483648 لأكبر قيمة لـx، أي يتجاوز حد 32 بت بمقدار واحد. عند استخدامhi = xالشامل، تبلغ قيمةlo + hiذروتها عند 2147483647 بالضبط في الخطوة الأولى، لذا فهي تناسب النطاق دون أي هامش. استخدم فهارس 64 بت أوlo + (hi - lo) / 2. - إرجاع آخر قيمة
midاختبرتها بدلًا من آخر قيمة كانت مناسبة. عندما تكونx = 17، ينتهي البحث بعد اختبار 5، وهي قيمة كبيرة أكثر من اللازم؛ والإجابة هي 4 التي احتفظت بها. - إفساد الحالات الصغيرة. البحث الذي يبدأ عند
lo = 1يفوّتx = 0، كما أن فحص القسمةm ≤ x / mيقسم على صفر عندما تكونm = 0. اختبر 0 و1 كلًّا على حدة.
أسئلة شائعة4
كيف تجد الجذر التربيعي دون استخدام دالة مدمجة؟
لإيجاد الجذر التربيعي الصحيح، استخدم البحث الثنائي لإيجاد الإجابة. تنقسم القيم المرشحة من 0 إلى x إلى مجموعة تكون مربعات عناصرها أصغر من أو تساوي x، ومجموعة تكون مربعات عناصرها أكبر منه، ويعثر البحث الثنائي على آخر قيمة مرشحة في المجموعة الأولى. طريقة نيوتن هي الإجابة الشائعة الأخرى: فهي تحسّن التخمين r باستخدام (r + x / r) / 2 حتى يصبح مربعه ملائمًا.
ما هو التعقيد الزمني للبحث الثنائي عن الجذر التربيعي؟
زمن O(log x) ومساحة O(1). تقلّص كل خطوة نطاق المرشحين إلى النصف، لذا يحتاج x = 2^31 - 1 إلى 31 خطوة. أما العد تصاعديًا بدءًا من 0 فيتطلب O(√x) خطوة، أي 46340 خطوة للقيمة نفسها لـ x، وهذا مناسب هنا، لكنه يزداد بسرعة مع مدخلات 64 بت.
كيف تحسب طريقة نيوتن الجذر التربيعي الصحيح؟
ابدأ بـ r = x. ما دام r × r > x، استبدل r بـ (r + x / r) / 2 باستخدام القسمة الصحيحة. في كل خطوة، تقترب قيمة r من الجذر نزولًا دون تجاوزه، وتتوقف الحلقة عند الجزء الصحيح من الجذر التربيعي. عندما يكون x = 2^31 - 1، يحتاج الأمر إلى 19 خطوة، ويتضاعف تقريبًا عدد الأرقام الصحيحة في كل خطوة بعد الاقتراب من الجذر.
لماذا يحتاج الحل إلى أعداد صحيحة ذات 64 بت بينما الإجابة تتسع في 32 بت؟
الإجابة لا تتجاوز 46340، لكن القيم المرشحة التي تختبرها تتجاوز ذلك. يبحث البحث الثنائي بين 0 وx أولًا عن قيمة مرشحة قريبة من 10^9، ومربعها قريب من 10^18، وهو أكبر بكثير من حد 32 بت، البالغ نحو 2.1 × 10^9. يضمن التربيع باستخدام 64 بت دقة المقارنة. وتجنّب المقارنة m ≤ x / m إجراء عملية الضرب الكبيرة تمامًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def mySqrt(x):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
x = 17
المتوقع
4