4

本当に恥ずかしい!!再帰を使用して数値「a」(「a」の累乗「b」)のべき乗を計算する次の小さなプログラムの動作を理解できません。この背後で使用されているロジックを親切に説明してください。 "x*x" パラメータ、n/2 パラメータ、および "n modulo 2" 部分の使用法がわかりません。分析してください。

    #include<stdio.h>

    int foo(int,int);

    int main() {
      int a,b;

      printf("Enter number a and its power b\n");
      scanf("%d%d",&a,&b);

      printf("a raised to b is %d", foo(a,b));
      return 0;
    }


    int foo ( int x , int n) {
      int val=1;

      if(n>0) {
        if (n%2 == 1) 
          val = val *x;
        val = val * foo(x*x , n/2);
      }

      return val;
    }
4

3 に答える 3

4

これは、 のようなべき乗が次のx^23ように書き換えられるという事実を利用します。x^16 * x^4 * x^2 * x^1

を計算する代わりに 4 つの乗算x^16だけを実行するだけなので、計算はかなり簡単です。(((x^2)^2)^2)^2x * x * x * ... 16 times ... * x

x^16ここで、計算中に出くわしたことx^4、およびx^2数値を計算するために必要だったことに注意してください。したがって、最終x^23的には、22 回ではなく 7 回の乗算だけで計算できます。

ここで、n % 2とn / 2が関係するのは、2 のべき乗が n にあるかどうかを判断することです (この例では、23 の 2 進表現で 8 ですか? いいえ)。

したがって、n のビットを繰り返すだけです。毎回 x を 2 乗し、現在見ている n ビットに 1 があれば、2 乗した数値を結果に掛けます。

アップデート：

このように数値を書き出すコツはn、バイナリで見ることです。23 は 10111 2です。または、位の値を書き出すことができます23 = 1*16 + 0*8 + 1*4 + 1*2 + 1*1。

これは、私たちが始めx^23 = x^(16 + 4 + 2 + 1)た指数法則のおかげです。= x^16 * x^4 * x^2 * x^1

別の簡単な例として、 を取り上げx^44ます。バイナリで 101100 2と書くので、

44  =  1*32 + 0*16 + 1*8 + 1*4 + 0*2 + 0*1  =  32 + 8 + 4

それで

x^44 = x^(32 + 8 + 4) = x^32 * x^8 * x^4

次に、以下を計算します

1:   x^2  = (x)^2                     (from the x we are given)
2:   x^4  = (x^2)^2                   (x^2 from step 1)
3:   x^8  = (x^4)^2                   (x^4 from step 2)
4:   x^16 = (x^8)^2                   (x^8 from step 3)
5:   x^32 = (x^16)^2                  (x^16 from step 4)
6:   x^44 = (x^32) * (x^8) * (x^4)    (using results of steps 2, 3, and 5)
于 2013-04-03T06:30:39.180 に答える
1

あなたが述べたように、foo再帰的に動作します。一歩一歩進んでみませんか？と を仮定するa==2とb==3、

1手目

int foo ( int x , int n) // x == 2, n==3
{
int val=1;

if(n>0) // n == 3, true!
{
    if (n%2 == 1) //true!
    val = val *x; // val = 1 * 2;
    val = val * foo(x*x , n/2); // next step
}

return val;
}

2手目

int foo ( int x , int n) // x == 4, n==1
{
int val=1;

if(n>0) // n == 1, true!
{
    if (n%2 == 1) //true
    val = val *x; val = 1 * 4;
    val = val * foo(x*x , n/2); // next step -> 4 * ...
}

return val;
}

2 番目のステップでは、最初のステップで得られる 4 を返します。

val = val * foo(x*x , n/2); // 2 * 4 in the first step and this equals 8
于 2013-04-03T06:30:18.437 に答える