python正整數平方根_Python3算法之四：x的平方根

關注微信公衆号“酸痛魚”，獲得更多最新最全的文章。

本文中所涉及的代碼，在未特殊聲明的情況下，都是基于Python3程式設計語言編寫的。

建議您在PC浏覽器中閱讀本文。

如果您未掌握知識提要中的内容，建議您先掌握這些内容之後再閱讀本文。

知識提要

1、math庫

2、int取整操作

3、牛頓疊代（未掌握不影響對本文的了解）

4、二分查找（未掌握不影響對本方的了解）

問題描述

給定一個非負整數x，求x的正數平方根r。要求：隻保留正數根的整數部分。

例如：

當x = 2時，r = 1。（2的平方根約為1.414）

當x = 4時，r = 2。（4的平方根為2）

當x = 8時，r = 2。（8的平方根約為2.828）

為了表述友善，在本文中，我們直接将“正數平方根”稱為“平方根”，在無歧義的情況下，會直接稱為r。

1

系統函數法

大部分程式設計語言都提供了豐富的數值操作的系統函數，例如向上取整ceil，向下取整floor，求平方根sqrt，等等。Python當然也不例外。對于本章題目，最簡單和最高效的解法，就是利用系統函數，先求x的平方根，再向下取整。

import math

def mySqrt(x):

# 求x的根，并向下取整，相當于math.floor(math.sqrt(x))

return int(math.sqrt(x))

如果這是一個競賽題目，而沒有禁止使用系統函數，那麼如上的代碼絕對是最優解。出于“學術”讨論和拓展學習的目的，我們将在本文中重點讨論其它的解題思路。

2

暴力破解法

對于任意大于1的正整數x，它的平方根一定不大于x的一半。利用這個特點，我們可以從x/2開始，不停地向左探索，直到到第一次找到一個數r，滿足r的平方不大于x，此時，r就是我們的解。

def mySqrt(x):

if x <= 1: return x

r = x // 2

while r > 1:

if r * r <= x:

return r

else:

r -= 1

return 1

不得不提的是，這種解法是存在嚴重的效率問題。當x值為1億的時候，在我的計算機上，大概花了4秒鐘的運作時間。如果你在比賽中使用這種解法，極有可能因為運作時間過長而被判定為解題失敗。

3

牛頓疊代法

在這裡，我将假設你知道什麼是牛頓疊代。不過如果你隻是專注于題目本身的求解，你隻需要知道牛頓疊代怎麼用就行了，可以不必了解它的原理。

假設r{n}表示第n次疊代的值，那麼疊代公式為：

r{n+1}= (r{n} + x/r{n})/2

由于我們求解的精度為保留小數點0位，即取整，是以我們隻需要疊代到r{n+1}和r{n}的整數部分相等時即可。此時r{n+1}的整數部分就是我們的解。

def mySqrt(x):

r = 1

n = 0

while int(r) != int(n):

n = r

r = (n + x / n) / 2

return int(r)

4

二分查找法

給定一個整數q，在升序的有序整數數列A中，找到q的位置。我們用A(i)表示A的第i個元素，用A(i, j)表示A中第i個到第個j的元素集合。假如A的長度為len，則A的最大下标e＝len－1。如果q是A中元素，那麼q一定落在A(0,e)中。我們可以通以下的步驟進行有限次的疊代，得到結果：

A、令s = 0，e = len - 1

B、如果s > e；跳轉到G

C、令m = (s + e) / 2

D、如果A(m) < q，q的範圍縮小為A(m + 1, e)；可令s = m + 1，跳轉到B；

E、如果A(m) > q，q的範圍縮小為A(s, m - 1)；可令e = m - 1，跳轉到B；

F、如果A(m) == q，那麼m就是q在A中的位置；查找結束

G、q不在數組A中。查找結束

對于我們的題目，也就是求解x平方根r的題目來說，模型退化了，A相當于整數數組[1，2，3，……，x]，而且一定有解。我們還需要稍微改造一下，就是在A(1, x)中，找到A(m)，滿足A(m)^2 <= x < A(m+1)^2。事實上，就是在1到x中，找到m，滿足m^2 <= x < (m+1)^2。

def mySqrt(x):

if x <= 1: return x

s, e = 1, x # A

while s <= e: # B

m = (s + e) // 2 # C

val1, val2 = m * m, (m + 1) * (m + 1)

if val1 <= x < val2: # F

return m

if val1 < x: # D

s = m + 1

else: # E

e = m - 1

return -1 # G●微信 掃碼關注會變帥哦

酸痛魚，與你分享快樂的代碼