題目如下：
實作 int sqrt(int x) 函式，
計算并回傳 x 的平方根，其中 x 是非負整數，
由于回傳型別是整數，結果只保留整數的部分，小數部分將被舍去，
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842…,
由于回傳型別是整數，小數部分將被舍去
解題方法1
使用樸素的二分解法，即可解決問題
#include<stdio.h>
int mySqrt(int x)
{
if (x < 2)
{
return x;
}
int left = 1;
int right = x / 2;
while (left <= right)
{
int mid = (left + right) / 2;
if (x / mid > mid)
{
left = mid + 1;
}
else if (x / mid < mid)
{
right = mid - 1;
}
else
{
return mid;
}
}
return right;
}
int main()
{
printf("%d\n",mySqrt(8));
printf("%d\n",mySqrt(4));
printf("%d\n",mySqrt(16));
return 0;
}
運行截圖如下：
解題方法2
牛頓迭代法（Newton’s method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法，
產生背景：
多數方程不存在求根公式，因此求精確根非常困難，甚至不可解，從而尋找方程的近似根就顯得特別重要，方法使用函式 的泰勒級數的前面幾項來尋找方程 的根，牛頓迭代法是求方程根的重要方法之一，其最大優點是在方程 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時線性收斂，但是可通過一些方法變成超線性收斂，另外該方法廣泛用于計算機編程中，
利用迭代演算法解決問題，需要做好以下三個方面的作業：
一、確定迭代變數
在可以用迭代演算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數，
二、建立迭代關系式
所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系），迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成，
三、對迭代程序進行控制
在什么時候結束迭代程序？這是撰寫迭代程式必須考慮的問題，不能讓迭代程序無休止地執行下去，迭代程序的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定，對于前一種情況，可以構建一個固定次數的回圈來實作對迭代程序的控制；對于后一種情況，需要進一步分析得出可用來結束迭代程序的條件，
#include<stdio.h>
int s;//定義全域變數s
double sqrts(double x)
{
double res = (x + s / x) / 2;
if (res == x)
{
return x;
}
else
{
return sqrts(res);
}
}
int mySqrt(int x)
{
s = x;
if (x == 0)
return 0;
return ((int)(sqrts(x)));
}
int main()
{
printf("%d\n",mySqrt(8));
printf("%d\n",mySqrt(4));
printf("%d\n",mySqrt(16));
return 0;
}
運行截圖如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259466.html
標籤：其他
上一篇：高精度除法