2

私は初心者ですが、インターネットのどこかで入手したこの C プログラム (クレジット: http://www.geeksforgeeks.org/archives/28 ) が適切に動作することを知っています。

#include<stdio.h>

float power(float x, int y)
{
    float temp;
    if( y == 0)
       return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
    {
        if(y > 0)
            return x*temp*temp;
        else
            return (temp*temp)/x;
    }
}

/* Program to test function power */
int main()
{
    float x=2;
    int y=5;
    printf("%f", power(x, y));
    getchar();
    return 0;
}


私はちょうどどのように、なぜだろうと思っています。この関数のコードの行の後に、質問/コメントをコメントにしました...

float temp;
if( y == 0)
   return 1; 
       //this I understand because for instance 2^0 is 1
temp = power(x, y/2);
if (y%2 == 0)
    return temp*temp; 
        //if y is even, eg. 2^4 then 2^2 * 2^2 is still equal to 16
else
{
    if(y > 0) 
        //this part I don't get anymore. eg. 2^5, then temp=2^(5/2)
        return x*temp*temp; 
            //2 * 2^(5/2) * 2^(5/2) how? this will become 64 but the answer is 32.
            //but when I run the program it halts the right answer ie, 32
    else
        return (temp*temp)/x;
}


何が起こったのか、親切に説明してください。多分私は何かを逃しただけです。また、どのようにしてO(lg n)実行時間になったのか。どうもありがとうございました！

4

5 に答える 5

4

y/2温度の計算に使用されるのは整数除算であることに注意してください。したがって、コメントした質問では、5/2の結果は2.5ではなく2になります。

于 2012-06-29T03:44:07.740 に答える
3

2 乗によるべき乗のウィキペディアの説明と競合するのは難しいですが、ここに私の見解があります。

答えの鍵は次の式にあります。

a^(b*c) == ((a^b)^c)

これは、「累乗が偶数の場合に何をすべきか」という質問にすぐに答えy=2*kます。xk

奇数べき乗の場合はもう少し複雑です: 書き直しましょう

x ^ (2*k+1)

なので

(x ^ 2*k) * x

これで、そのブランチで何が起こるかがわかります。else奇数から 1 を引いて偶数にし、 を取得し、最後にx ^ (y-1)を掛けます。*x

ここで、時間の計算量について説明します。各ステップでyが半分になるため、再帰呼び出しが行われる回数は になりますO(Log2(N))。

*実装は明示的に減算1しません。yむしろ、 の整数除算を実行し、除算y/2の余りを破棄します。

于 2012-06-29T03:45:36.020 に答える
0 
/* if y is even and positive, e.g., 5, then floor of y/2 is (y-1)/2, e.g. 4/2
   then x^((y-1)/2 + (y-1)/2 + 1) = x^y, e.g., x * x^2 * x^2 = x^(1+2+2) = x^5) */
if(y > 0) 
    return x*temp*temp; 

/* if y is even and negative, e.g., -5, then floor of y/2 is (y+1)/2, e.g. -4/2
   then x^((y+1)/2 - (y+1)/2 - 1) = x^y, e.g., x^-1 * x^-2 * x^-2 = x^(-1-2-2) = x^-5) */

else
    return (temp*temp)/x;

複雑さO（lgn）については、再帰的なパワー呼び出しの前に2で割っているので、最大でlg（n）呼び出しを実行します。

于 2012-06-29T03:44:56.453 に答える
0

これは、nを半分にしながら x を繰り返し 2 乗する通常の x nアルゴリズムのやや不格好な実装です。Oddnには余分な処理が必要です。すべてのステップで、n が奇数かどうかを確認し、別の係数を掛けます。

アレクサンダー・ステパノフのジェネリック/テンプレート化されたアルゴリズムに関する1つの非常に素晴らしい講義シリーズは、この起源を説明しています:

これは、半分にしながら足し算を繰り返す古代エジプトのアルゴリズムに由来しnます。

最初の講義はかなり簡単なことから始まりますが、上手になります。彼には楽しい余談と物語があります。彼は繰り返し加算による乗算の再帰的アルゴリズムから始め、さまざまな方法でそれを改良します。彼は+ を * に置き換えて、この累乗アルゴリズムをレクチャー 2 (of 4) の終わり近くに作成します。

1: Stepanov は、C++ の STL の多くを設計および実装しました。彼は、ジェネリック プログラミングの非常に初期の発明者/パイオニアの 1 人でした。私は彼の講義を楽しんだので、それらをお勧めします。

この特定の実装は、私には見栄えがよくありません。

私はそれについて考えたことはありませんが、確かにn除算よりも負の奇数を処理するためのより良い方法があります. これは、C の整数除算の丸め方向の癖でしょうか? (これは、符号付きオペランドに対して算術シフトを行う C 実装であっても、算術右シフトとは異なります>>。C 標準はそれを必要としませんが、一部の特定の C 実装では動作が定義されています。)

また、変数名は誤解を招きます: 通常y、 と同じ型を持つと予想されxます。整数変数と FP 変数を混在させる場合はn、整数のような名前を使用してください。

于 2016-03-04T07:03:11.427 に答える
-1 
private int nthPower(int num, int power)
    {
        int [] arr = new int[power+1];
        arr[0] = 1; // Any number to the power '0' is '1'
        arr[1] = num; // Any number to the power '1' is num itself.
        int i =2;
        //Now in the for loop you just fill the next element in the array 
        // by multiplying the num with its previous result. Once you are out 
        // of loop you have the desired answer in 'i-1' th index.
        for (i =2; i<=power;i++)
        {
            arr[i] = num*arr[i-1];
        }
        return arr[i-1]; //This is your answer
    }
于 2016-03-03T15:14:26.200 に答える