この記事では、「a」を「n」のべき乗にする計算をいくつかの異なる方法で行います。
それでは、1つの方法を順を追って見ていきましょう。
こちらもお読みください。
方法1：基本的な考え方
a^n` を計算する最も基本的な方法は、数 a と n を何度も何度も掛け合わせることです。
この方法はかなり遅く、全く効率的ではありません。
それでも、この方法のコードは以下の通りです。
|
1
2
3
4
5
6
7
|
def basic_approach(a,n):
ans = 1
for i in range(n):
ans *= a
return ans
print(basic_approach(2,5))
|
上記のコードから得られる出力は32であり、これは正しい出力です。
さて、次のアプローチに移ろう。
方法2：通常の再帰的アプローチ
このメソッドでは、Recursion を使ってアプローチします。
もし、Recursionについてもっと知りたい場合は、以下のチュートリアルをご覧ください。
Recursionについてもっと読む。
fun(a,n) = a * fun(a,n-1)というのが基本的な考え方です。
したがって、再帰はaのn乗を計算するのに使うことができます。
コードは以下の通りです。
参考のため、コメントをつけた。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def normal_recursion(a,n):
# If power is 0 : a^0 = 1
if(n==0):
return 1
# If power is 1 : a^1 = a
elif(n==1):
return a
# For n>=2 : a^n = a* (a^(n-1))
term = normal_recursion(a,n-1)
term = a * term
# Return the answer
return term
print(normal_recursion(2,5))
|
上記のコードから得られた出力は 32 であり、これは正確で正しい出力です。
次に、再帰を利用した、より良い方法を考えてみましょう。
方法3：高速な再帰的アプローチ
先ほどは線形再帰的な方法を使いましたが、nの累乗を計算するには、nの値（べき乗値）に基づいて計算することも可能です。
-
- nが偶数なら fun(a,n) = [ fun(a,n/2) ] ^ 2
- nが奇数の場合 fun(a,n) = a * ( [ fun(a,n/2) ] ^ 2)
これはより効率的な方法で、プログラムにかかる時間を大幅に短縮することができます。
同じ方法のコードを以下に示す。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
def fast_recursion(a,n):
# If power is 0 : a^0 = 1
if(n==0):
return 1
# If power is 1 : a^1 = a
elif(n==1):
return a
# For n>=2 : n can be even or odd
# If n is even : a^n = (a^(n/2))^2
# if n is odd : a^n = a * ((a^(n/2))^2)
# In both the cases we have the calculate the n/2 term
term = fast_recursion(a,int(n/2))
term *= term
# Now lets check if n is even or odd
if(n%2==0):
return term
else:
return a*term
print(fast_recursion(2,5))
|
このコードの出力は32であり、これは正しい。
この方法は、以前の方法と比較して、半分の時間を要します。
まとめ
この記事では、再帰を含む方法と含まない方法を用いて、n乗を計算する方法を学びました。
どの方法を使っても構いませんが、最も効率の良い方法を選ぶと良いでしょう。
お読みいただきありがとうございました。