読者です 読者をやめる 読者になる 読者になる

にわとりプログラマーの備忘録

覚えたことをすぐ忘れてしまう、自分のための備忘録ブログです。

100の階乗を計算するプログラムを書いてみた

scala Java プログラミング

現在scalaの勉強をしているので、何かコードを書いてみようと思い大学1年生の頃に課題であった「100!を計算するプログラム」をJavascalaでそれぞれ書いてみました。

以下がそのコードです。

Java

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;
    }

}

scala

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)));
    }
    
}

基本的なことすら全く知らないな ...