C++で数値の5乗根の床値を求める方法【線形探索と二分探索】

この問題では、数値 N が与えられ、その5乗根の床値（小数点以下を切り捨てた整数値）を求めることが課題となります。

ある数の5乗根とは、その数自身を5回掛け合わせると元の数になる値のことです。

つまり、N^1/5 = a であるとき、a × a × a × a × a = N が成り立ちます。

例で問題を理解しよう

入力：N = 325

出力：3

説明：

325 の5乗根は約 3.179 であり、その床値は 3 になります。

解法アプローチ1：線形探索

最もシンプルな解決策は、1 から n まで順番に走査し、自分自身を5回掛けると n になる（または n を超える直前の）数を見つける方法です。

ただし、与えられる数が必ずしも完全な5乗数であるとは限らないため、正確な値は得られません。そこで、5乗した結果が初めて n を超える値を見つけ、その値から 1 を引くことで、5乗根の床値を求めます。

実装例1：線形探索による解法

#include<iostream>
using namespace std;

int calcFifthRoot(int n) {
   
   if (n == 0 || n == 1)
      return n;

   int a = 0;
   for(a = 1; a*a*a*a*a < n ; a++){
     
   }
   return (a - 1);
}

int main() {
   
   int n = 325;
   cout<<"The Floor of fifth root of "<<n<<" is "<<calcFifthRoot(n);
   return 0;
}

出力

The Floor of fifth root of 325 is 3

このアルゴリズムは正しく動作しますが、計算量が O(n) となるため、大きな n に対しては非効率です。より優れた解決策として、探索アルゴリズムを改良し、二分探索（バイナリサーチ）を使って5乗根を効率的に求める方法があります。これにより計算量を O(log n) まで削減できます。

二分探索では、探索範囲の中央値 a の5乗と n を比較し、a の5乗が n より小さければ探索範囲を上半分に、大きければ下半分に絞り込んでいきます。見つかった最大の候補値を記録しておき、ループ終了後にそれを返すことで床値が得られます。

実装例2：二分探索による解法

#include<iostream>
using namespace std;

int calcFifthRoot(int n)
{
   if (n == 0 || n == 1)
   return n;

   int start = 1, end = n, root = 0;
   while (start <= end)
   {
      int a = (start + end) / 2;
      long int apowfive = a*a*a*a*a;

      if (apowfive == n)
         return a;
      if (apowfive < n) {
         
         start = a + 1;
         root = a;
      }
      else
         end = a - 1;
   }
   return root;
}

int main() {
   
   int n = 250;
   cout<<"The floor of fifth root of "<<n<<" is "<<calcFifthRoot(n);
   return 0;
}

出力

The floor of fifth root of 250 is 3

まとめ

本記事では、C++ で数値の5乗根の床値を求める2つの方法を紹介しました。単純な線形探索は理解しやすいものの O(n) の計算量が必要であり、二分探索を用いることで O(log n) に大幅に高速化できます。大きな数値を扱う場合は、二分探索版の実装を採用することをおすすめします。