2019.07.29
整数の累乗
累乗とは
累乗は、同じ数を何回か掛け合わせることです。
基数をa、指数をnとすると、
累乗=an
です。
例えばa=3でn=5であれば、
累乗=35=3×3×3×3×3=243
となります。これは3を5回掛け合わせる計算を意味しています。
Javaソースコード - for文で繰り返し掛け算を行う
Power1.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035
public class Power1 { // aのn乗を戻すメソッド static int power( int a, int n ) { // 結果の初期値 int result = 1; // nが１の場合に計算 if ( 1 <= n ) { // aをn回掛ける for ( int i = 0; i < n; ++ i ) { result = result * a; } } // 結果を戻す return result; } // メイン public static void main( String[] args ) { // 変数の宣言 int a, n; int ans; // べき乗の計算 a = 5; n = 7; ans = power( a, n ); // 結果表示 System.out.println( a + "の" + n + "乗は、" + ans ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis Power1.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac Power1.java
実行
C:\talavax\javasample>java Power1
実行結果
5の7乗は、78125
002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018
// aのn乗を戻すメソッド static int power( int a, int n ) { // 結果の初期値 int result = 1; // nが１の場合に計算 if ( 1 <= n ) { // aをn回掛ける for ( int i = 0; i < n; ++ i ) { result = result * a; } } // 結果を戻す return result; }
for文を使って、aをn回掛けています。
nが0以下の値のとき、1を戻すようにしています。
Javaソースコード - 再帰
Power2.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053
public class Power2 { // aのn乗を戻すメソッド static int power( int a, int n ) { // 結果の初期化 int result; // nが0以下の場合、１を戻す if ( 0 >= n ) result = 1; else { // nが1場の場合 switch ( n ) { case 1: // n=1の場合、aを戻す result = a; break; case 2: // n=2の場合、a*aを戻す result = a * a; break; default: int pow = power( a, n / 2 ); result = pow * pow; // nが奇数の場合 if ( 1 == ( n % 2 ) ) { result *= a; } break; } } return result; } // メイン public static void main( String[] args ) { // 変数の宣言 int a, n; int ans; // べき乗の計算 a = 5; n = 7; ans = power( a, n ); // 結果表示 System.out.println( a + "の" + n + "乗は、" + ans ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis Power2.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac Power2.java
実行
C:\talavax\javasample>java Power2
出力結果
5の7乗は、78125
002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036
// aのn乗を戻すメソッド static int power( int a, int n ) { // 結果の初期化 int result; // nが0以下の場合、１を戻す if ( 0 >= n ) result = 1; else { // nが1場の場合 switch ( n ) { case 1: // n=1の場合、aを戻す result = a; break; case 2: // n=2の場合、a*aを戻す result = a * a; break; default: int pow = power( a, n / 2 ); result = pow * pow; // nが奇数の場合 if ( 1 == ( n % 2 ) ) { result *= a; } break; } } return result; }
nが0以下の値のとき、1を戻すようにしています。
例えば、累乗=35の場合を見ていきましょう。
3を5回掛けて3×3×3×3×3=243の結果を得ます。
この式を少しだけ変形すると
(3×3)×(3×3)×3
となります。さらに(3×3)をpowとおくと
pow×pow×3
となります。
よって、powを計算した値で、pow×pow×3を計算すると掛け算４回で結果を得ることができます。
次に、累乗=39の場合を見ていきましょう。
(3×3×3×3)をpowとおくと
39=pow×pow×3
となります。
さらにpow'=3×3とおくと
pow=3×3×3×3=(3×3)×(3×3)=pow'×pow'
となり、powは掛け算２回で結果を得ることができます。
よって、pow×pow×3を計算すると掛け算４回で結果を得ることができます。
Javaソースコード - 乗算の回数を取得
PowerN.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048
public class PowerN { // aのn乗の掛け算の回数を戻すメソッド static int power_n( int a, int n ) { // 結果の初期化 int result = 0; // nが2以上の場合 if ( 2 <= n ) { // nが1場の場合 switch ( n ) { case 2: // n=2の場合、a*aを戻す result += 1; break; default: int pow_num = power_n( a, n / 2); result += pow_num; result += 1; // nが奇数の場合 if ( 1 == ( n % 2 ) ) { result += 1; } break; } } return result; } // メイン public static void main( String[] args ) { // 変数の宣言 int a, n; int ans; // べき乗の計算 a = 3; n = 19; ans = power_n( a, n ); // 結果表示 System.out.println( a + "の" + n + "乗に使う掛け算の回数は、" + ans ); } }
実行
C:\talavax\javasample>java PowerN
出力結果
3の19乗に使う掛け算の回数は、6
指数（掛ける回数）に対して、実際に掛け算を行う回数が少なくなることが確認できます。
以上です。
関連コンテンツ
広告
