[問題] a的b次方實作時間logb之遞迴寫法

[conan77420 (人生就是不停的戰鬥)]

a的b次方計算時間在logb內完成

這題好像之前有在板上看過，但好像沒有遞迴版的

非遞迴的寫法我自己寫的如下：

#include<iostream.h>
using namespace std;
int fastpow(int ,int );
int main()
{
    int num=0, pow=0;
    cout<<"Enter num:";
    cin>>num;
    cout<<"Enter pow:";
    cin>>pow;
    cout<<fastpow(num,pow);


system("pause");
}
int fastpow(int a,int b)
{
int temp=1;
while(b!=0)
{
 if(b&1)
 {temp=temp*a;}
 a=a*a;
 b=b>>1;
}
return temp;
}
=================================

造裡說非遞迴出的來〝遞迴〞應該就出的來

無奈可能非遞迴沒寫得很好，遞迴我實在想不出來要怎麼寫才漂亮

請教大家

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.69.46
→ ilway25:我想問的是，乘法運算該視為常數嗎？
> -------------------------------------------------------------------------- <

作者: ledia (下班後才下棋) 看板: C_and_CPP
標題: Re: [問題] a的b次方實作時間logb之遞迴寫法
時間: Wed Mar 24 23:42:16 2010

※ 引述《conan77420 (人生就是不停的戰鬥)》之銘言：
: a的b次方計算時間在logb內完成
: 這題好像之前有在板上看過，但好像沒有遞迴版的
: 非遞迴的寫法我自己寫的如下：
: #include<iostream.h>
: using namespace std;
: int fastpow(int ,int );
: int main()
: {
:     int num=0, pow=0;
:     cout<<"Enter num:";
:     cin>>num;
:     cout<<"Enter pow:";
:     cin>>pow;
:     cout<<fastpow(num,pow);
: system("pause");
: }
: int fastpow(int a,int b)
: {
: int temp=1;
: while(b!=0)
: {
:  if(b&1)
:  {temp=temp*a;}
:  a=a*a;
:  b=b>>1;
: }
: return temp;
: }
: =================================
: 造裡說非遞迴出的來〝遞迴〞應該就出的來
: 無奈可能非遞迴沒寫得很好，遞迴我實在想不出來要怎麼寫才漂亮
: 請教大家
  示意一下就好

  my_pow(int a, int b)

    half <- my_pow(a, ceil(b/2))

    if(b&1)
       return half * half * a;
    else
       return half * half;

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.49

> -------------------------------------------------------------------------- <

作者: etrexetrex (moonet) 看板: C_and_CPP
標題: Re: [問題] a的b次方實作時間logb之遞迴寫法
時間: Wed Mar 24 23:53:50 2010

http://nopaste.csie.org/b7518

完全只是把原po的非遞迴改成遞迴 = =

int fastpow_initial(int a, int b)
{
        return fastpow_recursive(a,b,1);
}

int fastpow_recursive(int a, int b, int temp)
{
        if(b == 0)
                return temp;
        else if(b&1)
                return fastpow_recursive(a*a,b>>1,temp*a);
        else
                return fastpow_recursive(a*a,b>>1,temp);
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.169.77
推 ledia:很有 LISP 的感覺 XD
> -------------------------------------------------------------------------- <

作者: Benedy (小Ben) 看板: C_and_CPP
標題: Re: [問題] a的b次方實作時間logb之遞迴寫法
時間: Wed Mar 24 23:43:11 2010

原理其實差不多，而且我也沒有寫得挺漂亮

int power (int x, int y) {
   if (y == 1) return x;
   if (y == 2) return (x * x);

   int k = power (x, y / 2);
   return (y % 2) ? (k * k * x) : (k * k);
}

※ 引述《conan77420 (人生就是不停的戰鬥)》之銘言：
: a的b次方計算時間在logb內完成
: 這題好像之前有在板上看過，但好像沒有遞迴版的
: 非遞迴的寫法我自己寫的如下：
: #include<iostream.h>
: using namespace std;
: int fastpow(int ,int );
: int main()
: {
:     int num=0, pow=0;
:     cout<<"Enter num:";
:     cin>>num;
:     cout<<"Enter pow:";
:     cin>>pow;
:     cout<<fastpow(num,pow);
: system("pause");
: }
: int fastpow(int a,int b)
: {
: int temp=1;
: while(b!=0)
: {
:  if(b&1)
:  {temp=temp*a;}
:  a=a*a;
:  b=b>>1;
: }
: return temp;
: }
: =================================
: 造裡說非遞迴出的來〝遞迴〞應該就出的來
: 無奈可能非遞迴沒寫得很好，遞迴我實在想不出來要怎麼寫才漂亮
: 請教大家

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.227.132
→ Benedy:沒想到樓上有人早先一步了
推 ledia:我偷懶只寫示意, 沒處理細節 XD  你比較勤勞
→ sbrhsieh:return statement 的 (?:) operator 有筆誤
→ Benedy:已修正, 謝謝眼睛很尖的樓上
※ 編輯: Benedy          來自: 220.136.227.132      (03/25 00:09)