---
# System prepended metadata

title: 求平方根(整數部分)
tags: [week 10]

---

# 求平方根(整數部分)
###### tags: `week 10`

## Solution 1
> [name=子恩]
Main Idea:十分逼近法
從高的位數開始找"平方後剛好等於或小於x"的數字，一路找到個位數
```python1
# recursion version
x = int(input())
root = 0
f = open('result.txt','a')
n = len(str(x))//2

def root(t ,n):
    if 10**n > x:return root(t ,n-1)        # 如果10的n次比x大，把n減1。這行用來確認開始時的數字一定比x小
    for i in range(10):
        if ((t+i)*10**n)**2 > x:            # 如果找到一個數的平方比x大，找它前一個數whose平方比x小
            if n == 0:return t+i-1          # 如果找到個位就停
            return root((t+i-1)*10 ,n-1)    # 找下一位數
    return root((t+9)*10 ,n-1)              # 如果1~9都小於x，就是9

root = root(0 ,n)
# print(root ,file = f ,flush = True)
print(root)
```

## Solution 2
> [name=Jason Lin]

### Main Idea: 二分逼近

- 參考助教提供的hint:
	1. 1^2 ≤ n ≤ n^2
	2. If a^2 ≤ n ≤ b^2 holds for positive integers a and b, and c = ⌊(a + b)/2⌋, then either a^2 ≤ n ≤ c^2 or c^2 ≤ n ≤ b^2 (or both).

- 類似binary search
```python=
#The recursive version(will exceed recursive limit)
'''
def root(down,N,up):
    if up-down==1 or up==down: return down
    mid = (down+up)//2
    if mid**2 == N: return mid
    elif down**2<=N<=mid**2:
        return root(down,N,mid)
    elif mid**2<=N<=up**2:
        return root(mid,N,up)
'''

#The loop version
def root(N):
    down = 1
    up = N
    while True:
        if up-down==1 or up==down: break
        mid = (down+up)//2
        if mid**2 == N: down = mid
        elif down**2<=N<=mid**2: up = mid
        elif mid**2<=N<=up**2: down = mid
    return down


n = eval(input())
val = root(n)
print(val)
```


### The orgin and intuitive sol. but errs when n too large(exceed float limit)
```python=
import math
n=eval(input())
print(int(math.sqrt(n)//1))
```