Square Root (Integer)

Q: מהי סיבוכיות הזמן של חיפוש בינארי למציאת שורש ריבועי?

זמן O(log x) ומקום O(1) . בכל צעד טווח המועמדים מצטמצם בחצי, לכן עבור x = 2^31 - 1 נדרשים 31 צעדים. ספירה כלפי מעלה מ־0 נמשכת O(√x) צעדים, 46340 עבור אותו x , וזה מתאים כאן, אך גדל במהירות עם קלטים של 64 ביט.

Q: כיצד מחשבת השיטה של ניוטון שורש ריבועי של מספר שלם?

מתחילים עם r = x . כל עוד r × r > x , מחליפים את r ב־ (r + x / r) / 2 באמצעות חילוק שלם. כל צעד מקרב את r כלפי מטה לשורש מבלי לעבור אותו, והלולאה נעצרת בחלק השלם של השורש הריבועי. עבור x = 2^31 - 1 נדרשים 19 צעדים, ומספר הספרות הנכונות בערך מוכפל בכל צעד כשהוא מתקרב.

קלחיפוש בינארי מתמטיקה וסימולציה

+10

הפונקציה שלך מקבלת מספר שלם לא שלילי x ומחזירה את השורש הריבועי השלם שלו: המספר השלם הגדול ביותר r שעבורו r × r ≤ x. כלומר, השורש מעוגל כלפי מטה, כך שמספר שאינו ריבוע מושלם מקבל את השורש של הריבוע המושלם שמתחתיו. חשב אותו בעצמך, בלי להשתמש בפונקציית שורש ריבועי או חזקה מובנית.

פונקציה

mySqrt(x: integer) → integer

xinteger: המספר השלם הלא־שלילי שיש לחשב את השורש הריבועי שלו
מחזירהinteger: השורש הריבועי של x מעוגל כלפי מטה למספר שלם

אילוצים

0 ≤ x ≤ 2³¹ - 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 יכול להיות גם שלילי?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

ספירה כלפי מעלה מ־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

צפוי