【ニュートン反復法&ユークリッドアルゴリズム】

文書ディレクトリ

ニュートン反復法の開平方根

ニュートン反復法の簡単な紹介

ユークリッドの最大公約数

ニュートン反復法の開平方根
leetcodeには平方根を解くアルゴリズムの問題があるので、ニュートン反復法で解きたいと思っています.
ニュートン反復法の簡単な紹介
rをf(x)=0のルートとし、現在x 0をrの初期近似値として選択し、過点(x 0,f(x 0))を曲線y=f(x)の接線L,L:y=f(x 0 f’(x 0)(x-x 0))とすると、LとX軸の交点の横座標X 1=x 0-f(x 0/f’(x 0))となり、x 1をrの一次近似値と呼ぶ.過点(x 1,f(x 1))は曲線y=f(x)の接線とし、この接線とx軸の交点の横座標x 2=x 1-f(x 1/f’(x 1))を求め、x 2をrの二次近似値と呼ぶ.以上の手順を繰り返して、rの近似値シーケンスを得、xn+1=xn−f(xn/f’(xn))をrのn+1次近似値と呼び、これがニュートン反復式である.
アルゴリズムの問題を見てみましょうSince the return type is an integer, the decimal digits are truncated and only integer part ofthe result is returned Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
ニュートン反復法に基づいて,まずこの問題の反復式を求め,aの平方根xを求めると,f(x)=x 2−aがこの問題を導出したニュートン反復式は,xn+1=1/2(xn+a/xn)が反復を必要とするたびに得られる式であり,アルゴリズムを書くことができる.

int mySqrt(int x)
{
    if (x < 0)
    {
        return -1;
    }
    double e = 1e-15;
    double xn = x;
    double xn1 = (xn + x / xn) / 2;
    while (abs(xn - xn1) > e)
    {
        xn = xn1;
        xn1 = (xn + x / xn) / 2;
    }
    return (int)xn;
}

ユークリッドの最大公約数
ユークリッドアルゴリズムは転がり相除法とも呼ばれ、2つの数の最大公約数を求めるために使用される.定理:2つの整数の最大公約数はその中の小さいその数と2つの数を除いた残りの数の最大公約数に等しい.最大公約数(Greatest Common Divisor)はGCDと略され、gcd(a,b)=gcd(b,a mod b)(a>bかつr=a mod bとしてもよいが、rは0ではない)は、aがa=kb+rとして表すことができる定理を証明する過程である.(a,b,k,rはいずれも正の整数であり、rはdがa,bの1つの公約数であると仮定し、d|a,d|bと表記する.すなわち、aとbはいずれもdで除算できる.一方、r=a-kbは、両側が同時にdで除算され、r/d=a/d-kb/d=mであり、等式右側からmは整数であることが分かるため、d|rはしたがってdであり、a mod bの公約数はdがbであり、a mod bの公約数はdがbであると仮定し、d|b,d|(a-k*b)、kは整数である.さらにd|a.したがってdもaであり、bの公約数は(a,b)と(b,a mod b)の公約数が同じであり、その最大公約数も必然的に等しく、証明される.したがって、最大公約数を求めるコードは、

int GCD(int a, int b)
{
    if (a < b)
    {
        std::swap(a, b);
    }
    if (b == 0)
    {
        return a;
    }
    int iterValue = 0;
    while(b > 0)
    {
        iterValue = a % b;
        a = b
        b = iterValue;
    }
    return a;
}