Recently, in a university programming lecture, I had the task of creating a "program that calculates factorials from 2 to 100", but it was rather difficult, so I would like to leave the program as a memorandum for myself.
Updated on 2019/01/09 (Updated content: Add comment)
public class Report5_2_30114020{
public static void main(String[] args) {
//①
int [] answerArray = new int [200]; //An array that stores the calculation result of factorial
int [] copyArray = new int [200]; //An array that temporarily copies the contents of the array
//②
//Initialize array values
for(int i=0; i<answerArray.length; i++){
answerArray[i] = 0;
}
answerArray[0] = 1;
//③
for(int i=2; i<=100; i++){
//④
//Copy array
for(int j=0; j<answerArray.length; j++){
copyArray[j] = answerArray[j];
}
//⑤
//Calculation
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;
//⑦
//Preparing for carry
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;
}
}
//⑧
//View results
int counter = 0;
for(int j=0; j<answerArray.length; j++){
if(answerArray[answerArray.length-1-j] != 0){
break;
}
counter++;
}
System.out.print(i + "Factorial:");
for(int j=0; j<answerArray.length; j++){
if(j<counter){
continue;
}
System.out.print(answerArray[answerArray.length-1-j]);
}
System.out.println();
}
}
}
Updated on 2019/01/09 (Updated content: "Program description" added) Circled numbers (such as ①) correspond to the circled numbers written in the program.
This program is a program that calculates from factorial 2 to factorial 100. Since an ordinary int type cannot store a large number of factorial 100 (158 digits), the calculation result of factorial 100 is calculated one digit at a time in an int type array with a sufficiently large number of elements. The basic policy is to store it. At that time, carry-up etc. will occur, so the processing around that will be a little complicated.
An array that stores the calculation result of factorial. Since the factorial calculation result is saved in the elements of the array digit by digit, it is necessary to prepare an array with a larger number of elements, considering that 100! Is 158 digits. copyArray is required when performing the calculation in ⑥.
answerArray [n] corresponds to the n + 1th digit of the factorial calculation result. Since we want to set the initial calculation result to 1, only the first element is set to 1 and the other elements are set to 0 for initialization.
This for statement is the outermost process. The variable i that is valid in this for statement corresponds to the factorial number that is being calculated at that time. (Example: In the loop of i = 10, i! Is calculated.)
Each time i is updated and loops, it copies the result of the factorial calculated just before. (In ④ of the loop of i = 10, it means that 9! Calculated just before is copied.) This copied array will be used later in ⑥.
The variable upNumber1 is a variable that stores the carry number that goes up one digit. The variable upNumber2 is a variable that stores a carry number that goes up two digits. first is the first digit of the i value, second is the second digit of the i value, and third is the third digit of the i value. After this, the product of the calculation results up to the last time is calculated for each of first, second, and third.
Put the product of the values of first and copyArray [j] in a new variable called firstPlus. Put the value of the product of second and copyArray [j-1] in a new variable called secondPlus. Put the value of the product of third and copyArray [j-2] in a new variable called thirdPlus. Here, the index is j for first, but j-1 and j-2 are different for second and third. Second and third are the numbers and hundreds that represent the tens digit of the variable i, respectively. Because it is the number represented. I think it's easier to understand this area if you imagine the multiplication of multiple-digit numbers and three-digit numbers. The reason that the if statement is used in the process of issuing secondPlus and thirdPlus is to avoid referencing the index where the array does not exist. The variable sum is the sum of the values of firstPlus, secondPlus, thirdPlus and the carry that occurred in the previous loop. Since the first digit of this is the value of the j + 1th digit of i !, the remainder of sum divided by 10 is assigned to answerArray.
At this stage, sum is obtained, so use this value to prepare a variable that stores the carry to be used in the next loop.
The calculation result (i!) At that time is displayed. In the variable counter, count the number of empty () arrays. Next, the numbers stored in the array are displayed one digit at a time. By displaying from the one with the largest index, the numerical value of i! Can be output. At this time, it is possible to prevent the unnecessary 0 from being displayed at the beginning by passing through the processing for the number of counters obtained before.
It took me a long time to write a program for the first time in a long time. My personal addiction was that I didn't realize that it was imperative to make a copy of the array in my own way. I would like to post a commentary if I feel like it in the near future.
Recommended Posts