100の階乗を計算するプログラムを書いてみた
現在scalaの勉強をしているので、何かコードを書いてみようと思い大学1年生の頃に課題であった「100!を計算するプログラム」をJavaとscalaでそれぞれ書いてみました。
以下がそのコードです。
import java.math.BigInteger; /* * 100の階乗を計算するプログラム(配列を利用した筆算方式) */ public class Main { public static void main(String[] args) throws Exception { int[] answer = kaijou(100); int digit = answer[0]; System.out.println("100! = "); for(int i=digit; i>0; i--){ System.out.print(answer[i]); } } private static int[] kaijou(int n){ int[] answer = new int[160]; int carry = 0; // 桁上がり int digit = 1; // 現在の桁数 answer[1] = 1; for(int i=1; i<=n; i++){ for(int j=1; j<=digit; j++){ int num = answer[j] * i + carry; // i倍し、下位の桁からの桁上がりを加える carry = num/10; // 上位桁への桁上がりを保持 answer[j] = num%10; // 配列に1の位の値を格納 if(carry > 0 && (j+1) > digit){ // 桁の最高位が繰り上がる digit++; } } carry = 0; } answer[0] = digit; // 最初の要素に答えの桁数を保持 return answer; } }
object Main extends App{ val answer = kaijou(100); val digit = answer(0); println("100! = ") for(i <- digit to 1 by -1){ System.out.print(answer(i)); } def kaijou(n: Int): Array[Int] = { var answer = new Array[Int](160); var carry = 0; // 桁上がり var digit = 1; // 現在の桁数 answer(1) = 1; for(i <- 1 to n){ var j=1 while(j<=digit){ var num = answer(j) * i + carry; // i倍し、下位の桁からの桁上がりを加える carry = num/10; // 上位桁への桁上がりを保持 answer(j) = num%10; // 配列に1の位の値を格納 if(carry > 0 && (j+1) > digit){ // 桁の最高位が繰り上がる digit+=1; } j+=1 } carry = 0; } answer(0) = digit; // 最初の要素に答えの桁数を保持 return answer; } }
実行結果
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Long型で値を代入してもオーバーフローを起こすので、せいぜい15!(?)までしか計算できません。
そのため各桁を配列で管理し、筆算を計算しています。
因みに、友達に「多倍長整数使えばいいじゃん!」Σ(・ω・ノ)ノ!と言われて実装したら何の苦労も無く実装できました。(ノД`)・゜・。
Java
import java.math.BigInteger; /* * 100の階乗を計算するプログラム(BigInteger[多倍長整数:32bit,64bitを超えた巨大な整数]を利用) */ public class Main { public static void main(String[] args) throws Exception { BigInteger answer = kaijou(new BigInteger("100")); System.out.println(answer); } private static BigInteger kaijou(BigInteger n){ if(n.equals(BigInteger.ONE)){ return BigInteger.ONE; } return n.multiply(kaijou(n.subtract(BigInteger.ONE))); } }
基本的なことすら全く知らないな ...