试题 基础练习 阶乘计算
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
输入一个正整数n，输出n!的值。
其中n!=123*…*n。
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
输入格式
输入包含一个正整数n，n<=1000。
输出格式
输出n!的准确值。
样例输入
10
样例输出
3628800
要点
-
JAVA为什么不建议在for循环中使用"+"进行字符串拼接,而是建议使用StringBuilder 的 append 方法？idea提示string concatenation ‘+=’in loop
JAVA为什么不建议在for循环中使用"+"进行字符串拼接,而是建议使用StringBuilder 的 append 方法？idea提示string concatenation ‘+=’in loop
思路
题目给出的算法描述就很好，按这个做就行，代码其实没多少，就是很绕，需要静下心好好想想
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
代码（无注释）
为了让你们看到代码有多么少，所以专门把注释删了
import java.util.ArrayList;
import java.util.Scanner;
public class FactorialCalculation2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
ArrayList A = calculating(n);
StringBuilder str = new StringBuilder();
for (int i = A.size() - 1; i >= 0; i--) {
str.append(A.get(i));
}
System.out.print(str);
}
public static ArrayList calculating(int n) {
ArrayList<Integer> A = new ArrayList<Integer>();
A.add(1);//首先将a设为1
int highest = 1;//最高位数,比如999的最高位数为3
for (int i = 2; i <= n; i++) {
int carry = 0; //进位数，比如9+9，进位数为1
int temp;
for (int j = 0; j < highest; j++) {
temp = A.get(j) * i + carry;
A.set(j, temp % 10);
carry = temp / 10;
}
while (carry != 0) {
A.add(carry % 10);
carry = carry / 10;
highest++;
}
}
return A;
}
}
代码（含有注释）
import java.util.ArrayList;
import java.util.Scanner;
public class FactorialCalculation {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
ArrayList A = calculating(n);
StringBuilder str = new StringBuilder();
for (int i = A.size() - 1; i >= 0; i--) {
str.append(A.get(i));
}
System.out.print(str);
}
public static ArrayList calculating(int n) {
ArrayList<Integer> A = new ArrayList<Integer>();
A.add(1);//首先将a设为1
int highest = 1;//最高位数,比如999的最高位数为3
for (int i = 2; i <= n; i++) {
int carry = 0; //进位数，比如9+9，进位数为1
int temp;
for (int j = 0; j < highest; j++) {
// 题目算法描述中说，将a乘以一个整数k变为将数组A的每一个元素都乘以k
// A.get(j)是A数组位置为j的原有的数，你在乘以i之后，需要加上下一位的进位carry
// 比如十位乘以i之后，得加上个位乘以i的进位
// 例如987*3=2961，A=【7，8，9】，A.get(1)为位置为1的原有的数，它乘以3之后，需要加上7乘以3的进位2
temp = A.get(j) * i + carry;
// 取余数覆盖A数组中位置为j的元素
// 例如987*3=2961，个位7乘以3之后，将1变为A数组新的个位，也就是覆盖0位置
A.set(j, temp % 10);
// 进位
// 例如987*3=2961，个位7乘以3之后，进位carry为2
carry = temp / 10;
}
// 当位数增加时，比如999*3=2997，它的最高位数就从3变成4，A数组就得增加新元素，长度增加
while (carry != 0) {
// 以999*3=2997为例，这里carry等于2，如果你奇怪这里为啥取余，
// 那你想999*99=98901，这里的carry=98
A.add(carry % 10);
// 位数可能不只是增加了1，可能大于1，比如这里进位carry=98，
// 位数就在999三位的基础上增加了两位，所以你得对carry进行整除，
// 98/10等于9 8已经增加到A数组中了，9在下一次循环增加到A数组中
carry = carry / 10;
// 更新最高位数
highest++;
}
}
return A;
}
}
代码二，运行超时，内存也超了某位同学提出的是使用java的大数类BigInteger
import java.math.BigInteger;
import java.util.Scanner;
public class FactorialCalculation3 {
public static void main(String[] args) {
// long startTime = System.currentTimeMillis(); //获取开始时间
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
BigInteger a = new BigInteger("1"); //首先将a设为1
for (int i = 2; i < n; n++) {
a = a.multiply(BigInteger.valueOf(i));
}
System.out.println(a);
// long endTime = System.currentTimeMillis(); //获取结束时间
// System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
}
}
