python - Pythonで再帰的な平方根を作成するにはどうすればよいですか?

Question

私はこのコードを持っています：

def root(x,n):    
    if n==0:
        return x
    else:
        return 0.5**(x/root(x,n-1)+root(x,n-1))

しかし：

>>>root(4,2)
>>>2.05

なんで？そして、それは他の平方根では機能しません...

score 2 · Accepted Answer

平方根を計算するために差分分割アルゴリズムを実装しようとしているようです(ただし、実際にはわかりません)。ただし、これで組み込みのべき乗演算子 (**) を使用する理由はわかりませんが、そうすべきではありません。

再帰的な平方根の基本的な戦略は、平方根を推測し、推測の精度をチェックし、古い推測が十分に正確でない場合は新しい推測を作成し、推測が真の根に十分近くなるまで再帰的に続けることです。戻る。

結果の精度 (および再帰の深さ) を制御するために、実際の平方根に対して推測をチェックできる必要があります。これを行うには、それを 2 乗して、平方根を求めている数との差を非常に小さくします。

def goodEnough(guess, x):
    return abs((x - (guess * guess))) <= .01 #change this value to make the function more or less accurate

実際に平方根を見つけるには、より適切な推測に到達する方法が必要です。ここでアルゴリズムの出番です。かなり単純なので、ニュートン法を使用することにしました。

def newGuess(guess, x):
    return (guess + guess/x)/2

これですべてをまとめることができます:

def root(guess, x):
    if goodEnough(guess, x):
        return guess
    else:
        return root(newGuess(guess, x), x)

そして、もう 1 ステップで推測パラメーターを削除できます。

def sqrt(x):
    return root(x/2, x) #x/2 is usually somewhat close to the square root of a number

2 に答える 2