2から100までの階乗を計算するプログラム

はじめに

　最近大学のプログラミングの講義で、「2から100までの階乗を計算するプログラム」を作るという課題が出たのですが割と難しかったので、自分用の備忘録としてプログラムを残したいと思います。

プログラム

2019/01/09に更新(更新内容:コメントの追加)

public class Report5_2_30114020{
    public static void main(String[] args) {

        //①
        int [] answerArray = new int [200];     //階乗の計算結果を格納する配列
        int [] copyArray = new int [200];       //配列の内容を一時的にコピーする配列

        //②
        //配列の値を初期化
        for(int i=0; i<answerArray.length; i++){
            answerArray[i] = 0;
        }
        answerArray[0] = 1;

        //③
        for(int i=2; i<=100; i++){
            //④
            //配列をコピー
            for(int j=0; j<answerArray.length; j++){
                copyArray[j] = answerArray[j];
            }
            //⑤
            //演算
            int upNumber1 = 0;
            int upNumber2 = 0;
            int first = 0;
            int second = 0;
            int third = 0;
            if(i<10){
                first = i;
            }else if(i<100){
                first = i%10;
                second = i/10;
            }else{
                third = 1;
            }
            //⑥
            for(int j=0; j<answerArray.length; j++){
                int firstPlus = 0;
                int secondPlus = 0;
                int thirdPlus = 0;
                firstPlus = first * copyArray[j];
                if(j-1>=0){
                    secondPlus = second * copyArray[j-1];
                }
                if(j-2>=0){
                    thirdPlus = third * copyArray[j-2];
                }

                int sum = firstPlus + secondPlus + thirdPlus + upNumber1;

                answerArray[j] = sum % 10;

                //⑦
                //桁上がりの準備
                if(sum <10){
                    upNumber1 = upNumber2;
                    upNumber2 = 0;
                }else if(sum < 100){
                    upNumber1 = upNumber2 + (sum)/10;
                    upNumber2 = 0;
                }else{
                    upNumber1 = upNumber2 + ((sum)/10)%10;
                    upNumber2 = (sum)/100;
                }
            }

            //⑧
            //結果を表示
            int counter = 0;
            for(int j=0; j<answerArray.length; j++){
                if(answerArray[answerArray.length-1-j] != 0){
                    break;
                }
                counter++;
            }
            System.out.print(i + "の階乗：");
            for(int j=0; j<answerArray.length; j++){
                if(j<counter){
                    continue;
                }
                System.out.print(answerArray[answerArray.length-1-j]);
            }
            System.out.println();
        }
    }
}

プログラムの解説

2019/01/09に更新(更新内容:「プログラムの解説」の追加)
丸数字(①など)はプログラムに書かれた丸数字に対応します。

プログラムの概要

　このプログラムは2の階乗から100の階乗までを計算するプログラムです。普通のint型では、100の階乗(158桁)という大きな数字を格納することができないので、十分に多くの要素数を持つint型の配列に、100の階乗の計算結果を1桁ずつ格納するというのが基本的な方針です。その際繰り上がりなどが起こるので、そのあたりの処理が少し複雑になります。

①配列を用意

階乗の計算結果を格納する配列です。階乗の計算結果を一桁づつ配列の要素に保存するので、100!が158桁であることを踏まえると、それより大きい要素数の配列を準備することが必要です。copyArrayは⑥で計算を行う時に必要になります。

②配列の値を初期化

answerArray[n]は階乗の計算結果のn+1桁目に対応します。初めの計算結果は1にしておきたいので、初めの要素だけを1にして、それ以外の要素は0にして初期化します。

③実際の処理

このfor文が一番外側の処理になります。このfor文内で有効な変数iは、その時計算している階乗の数字に対応します。(例:i=10のループではi!を計算しているということ。)

④配列のコピーをとる

iが更新されてループするたびに、直前までに計算した階乗の結果をコピーします。(i=10のループの④では、直前までに計算した9!をコピーしているということ。)このコピーした配列は後で⑥で使います。

⑤階乗の答えを更新するのに必要な変数の準備

変数upNumber1は桁が1つ上がる繰り上がりの数字を格納する変数です。変数upNumber2は桁が2つ上がる繰り上がりの数字を格納する変数です。firstはiの値の1桁目、secondはiの値の2桁目、thirdはiの値の3桁目になります。この後に、first、second、thirdのそれぞれについて直前までの計算結果との積を求めます。

⑥注目している桁の値を求める

firstとcopyArray[j]の値の積をfirstPlusという新しい変数に入れます。secondとcopyArray[j-1]の積の値をsecondPlusという新しい変数に入れます。thirdとcopyArray[j-2]の積の値をthirdPlusという新しい変数に入れます。ここで、firstにかけるのはインデックスがjなのに、second、 thirdではj-1、j-2とずれているのはsecondとthirdはそれぞれ変数iの十の位を表した数と百の位を表した数だからです。このあたりは複数桁の数字と3桁の数字の掛け算の筆算をイメージしていただくとわかりやすいと思います。なお、secondPlusとthirdPlusを出す処理でif文を使っているのは、配列の存在しないインデックスを参照しないようにするためです。変数sumはfirstPlus、secondPlus、thirdPlusの値と前のループで生じた繰り上がりを足したものです。これの1桁目がi!のj+1桁目の値になるのでsumを10で割った余りをanswerArrayに代入します。

⑦次のループで使う桁上がりを保存した変数を準備する

この段階でsumが求まるので、この値を使って、次のループで使う桁上がりを保存した変数を準備します。

⑧計算結果を表示

その時点での計算結果(i!)を表示します。変数counterで、空()の配列の数を数えます。次に配列に格納された数字を1桁ずつ順番に表示します。インデックスが大きい方から表示することで、i!の数値を出力することができます。この時に前に求めたcounterの回数だけ処理をスルーすることで、はじめに余計な0を表示しないようにすることができます。

まとめ

　久しぶりにプログラムを書くのに手間取ってしまいました。個人的なハマりポイントは、自分のやり方では配列のコピーを取ることが必須だということになかなか気がつかなかったことです。近いうちに気が向いたら解説も載せたいと思います。