c++ - C++での整数の累乗

Question

pow(a,b)結果を整数として取得する必要があります（aとbは両方とも整数です）。現在、含まれている計算(int) pow( (double)a, (double)b)は間違っています。たぶん誰かが整数でpow（a、b）を実行し、整数も返す関数を手伝ってくれるでしょうか？

しかし、ここに奇妙な部分があります。私はLinuxでGeany（およびg ++ / gccコンパイラ）を使用してpow(a,b)スクリプトを作成し、スクリプトだけをコンパイルして正常に動作させました。しかし、大学にはDev-C ++（およびMS Windows）があります。[Warning] converting toDev-C ++では、スクリプトはエラーint'でコンパイルされませんでした。double'

このscrpitをWindows（およびMingwコンパイラ）でも動作させる必要があります。

score 68 · Accepted Answer

Zedよりも優れた再帰的アプローチ。

int myPow(int x, unsigned int p)
{
  if (p == 0) return 1;
  if (p == 1) return x;
  
  int tmp = myPow(x, p/2);
  if (p%2 == 0) return tmp * tmp;
  else return x * tmp * tmp;
}

O（p）の代わりにO（log²（p））の方がはるかに複雑です。

または、constexprc++17を使用する関数として。

template <unsigned int p>
int constexpr IntPower(const int x)
{
  if constexpr (p == 0) return 1;
  if constexpr (p == 1) return x;

  int tmp = IntPower<p / 2>(x);
  if constexpr ((p % 2) == 0) { return tmp * tmp; }
  else { return x * tmp * tmp; }
}

score 15 · Accepted Answer

ほとんどの場合、Zeds の単純な再帰に対応しています...

再帰が反復よりも優れていると想定されるのはなぜですか? 特に C++ では。どうしたの...

int myPow (int x, int p) {
  int i = 1;
  for (int j = 1; j <= p; j++)  i *= x;
  return i;
}

あなたの答えが間違っている、または悪いと言っているのではありません。再帰的であるために良いと思うという印象を受けただけです。IMO、特に C++ では、そのバイアスにより、プログラムが遅くなったり、プログラムが壊れたりする可能性があります。巨大なスタックを増やしているためにプログラムが遅くなり、キャッシュと仮想メモリのページングが発生します。反復ソリューションが機能する場所でスタックオーバーフローが発生するため、壊れたプログラム。

あなたの答えを見て、それが末尾再帰的であり、とにかく反復に最適化されると考える人もいます。もちろん、それは真実ではありません - 各再帰呼び出しが終了した後、まだ実行すべき乗算があるため、末尾再帰ではありません。問題は、C++ では、末尾再帰の最適化を妨げるより微妙なことがたくさんあるということです。たとえコンパイラがそれらを実行したとしてもです。例えば...

void myrecurse (plan *p)
{
  plan i;
  i.prev = p;
  //  more plan setup, checks, and special case handling

  myrecurse (&i);
}

この場合、すべての「プラン」インスタンスがスタックに残る必要があります。したがって、スタックフレームを破棄することはできません。したがって、再帰呼び出しの後に実行される操作が正確にゼロであっても、これは反復に最適化できません。plan は POD 構造体であると想定されるため、デストラクタのクリーンアップなどの非表示の操作でさえありません。

ちなみに、これは私が実際のコードで行ったことに基づいています-再帰中に計画されたデータ構造操作ですが、再帰がルート/リーフに到達するまで元のノードでは何も変更されず、必要なすべての新しいノードが正常に実行されました割り当てられ、すべてのロックが取得され、さらに悪化する中断はありません。その時点で、計画インスタンスのリンクされたリストを介して反復が行われ、変更がコミットされます。ロジックは、再帰呼び出しの巻き戻しに関連するフラグメントに分割されるよりも、反復として明確でした。

ここでのポイントは、再帰が自動的に悪いと主張することではありません。デフォルトでは再帰の方が反復よりも優れていると人々が想定しているように見えると、ただ緊張します。

score 5 · Accepted Answer

あなたの宿題は、積分指数関数を書くことだと思います。まず、指数とは何かを見てみましょう。

http://en.wikipedia.org/wiki/Exponent

次に、教科書でCで数字を掛ける方法を調べますfor。ループを使用することをお勧めします。

score 3 · Accepted Answer

末尾再帰関数が最適ではないでしょうか? 何かのようなもの：

int myPow_helper(int x, int p, int result) {
   if (p == 0) {
      return result;
   } else {
      return myPow_helper(x, p-1, result*x);
   }
}

int myPow(int x, int p) {
   return myPow_helper(x, p, 1);
}

score 2 · Accepted Answer

ダブルを(int) pow((double)a, (double)b)行のintにキャストする代わりに、powの結果を丸めてみて、必要に応じてintにキャストします。

特に結果が1つずれている場合は、切り捨てるときに浮動小数点の問題の1つになる可能性があります。

score 2 · Accepted Answer

C++標準にはありませんint pow(int, int)（double pow(double, int)、がありfloat ...ます）。Microsoft の cmath は、ipow を持たない C math.h を使用します。一部の cmath ヘッダーは、のテンプレートバージョンを定義しますpow。

$ cat main.cpp
#include <cmath>

int main() {
  std::pow(2,2);
}

$ gcc main.cpp # this cmath has template pow
...snip... std::pow<int, int>(int, int)]+0x16): undefined reference to `pow'
collect2: ld returned 1 exit status
1 ;( user@host:
$ gcc main.cpp -lm

Google Codeでfunction:ipow lang:c++を検索します。

最初のリンクの例を次に示します。

template <typename Type1, typename Type2>
Type1 ipow(Type1 a, Type2 ex)
// Return a**ex
{
    if ( 0==ex )  return 1;
    else
    {
        Type1 z = a;
        Type1 y = 1;
        while ( 1 )
        {
            if ( ex & 1 )  y *= z;
            ex /= 2;
            if ( 0==ex )  break;
            z *= z;
        }
        return y;
    }
}

C++ コードでの整数の累乗 (平方、立方など) の計算を参照してください。

score -10 · Accepted Answer

あなたが自慢できる素晴らしい再帰的アプローチ：

int myPow(int x, int p) {
  if (p == 0) return 1;
  if (p == 1) return x;
  return x * myPow(x, p-1);
}

c++ - C++での整数の累乗

11 に答える 11

Related

Reference