蓝桥杯vip题阶乘计算
详细题目
输入一个正整数n，输出n!的值。
其中n!=123…n。
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
测试输入
10
测试输出
3628800
解题方案一
一开始比较呆逼，直接模拟的，主要是太拘泥于传统纸上的计算方式。
#include<iostream>
using namespace std;
const int MAXN = 30000;
typedef struct save {
int data[MAXN];
int length;
string t_name;
}Save;
Save T1, T_1, T_2,T_3;
long long test_num = 1;
//存储初始值
void save_to_T1(int n) {
T1.length = 0;
while(n>0){
T1.data[T1.length++] = n % 10;
n /= 10;
}
/*测试*/
//cout << "T1目前的长度为" << T1.length << endl;
//cout << "T1内部的数据为" << endl;
//for (int i = 0; i < T1.length; ++i) {
// cout << T1.data[i];
//}
//cout << endl;
}
//切片得k值
void kill_to_k(int& k1, int& k2, int& k3, int n ) {
k1 = n % 10;
n /= 10;
k2 = n % 10;
n /= 10;
k3 = n % 10;
/*测试*/
//cout << "k1:" << k1<<" " << "k2:" << k2 <<" "<< "k3:" << k3<<" " << endl;
}
//求 T_1, T_2,T_3
void how_to_T(int k,Save& T) {
int temp = 0; //紧致数
for (int i = 0; i < T1.length; ++i) {
int t = T1.data[i] * k + temp;
temp = t / 10;
T.data[T.length++] = t % 10;
}
if (temp != 0) {
T.data[T.length++] = temp ;
}
/*测试*/
//cout << "临时"<<T.t_name<<"的数据为：" << endl;
//for (int i = 0; i < T.length; ++i) {
// cout << T.data[i];
//}
//
//cout << endl;
}
//求length 最长的值
int chose_max_long(int k1,int k2 ,int k3){
if (k3 >0) {
//cout << "最大值是t3.吗" << T_3.t_name;
return T_3.length;
}
else if (k2 > 0) {
//cout << "最大值是t2吗" << T_2.t_name;
return T_2.length;
}
else {
//cout << "最大值是t1吗" << T_1.t_name;
return T_1.length;
}
}
//完成累加到T1
void sum_to_T(int max_long) {
T1.length = 0;
int temp = 0;
for (int i = 0; i < max_long; ++i) {
int t = T_1.data[i] + T_2.data[i] + T_3.data[i] + temp;
temp = t / 10;
T1.data[T1.length++] = t % 10;
}
if (temp != 0) {
T1.data[T1.length++] = temp;
}
}
/*结果测试*/
void show_result() {
//cout << endl;
for (int i = T1.length - 1; i >= 0; --i) {
cout << T1.data[i];
}
}
int main() {
T1.length = 0;
T1.data[0] = 0;
T_1.t_name = "T1";
T_2.t_name = "T2";
T_3.t_name = "T3";
int n;
cin >> n;
save_to_T1(n);
//从n-1乘到2就行了
for (int i = n - 1; i >= 2; --i) {
int k1 = 0, k2 =0 , k3 = 0;
kill_to_k(k1, k2, k3, i);
T_1.length = 0;
T_2.length = 1;
T_3.length = 2;
how_to_T(k1,T_1);
how_to_T(k2,T_2);
how_to_T(k3,T_3);
int z =chose_max_long(k1,k2,k3);
/*测试*/
//cout << "最大长度为:" << z << endl;
sum_to_T(z);
//show_result();
}
show_result();
return 0;
}
写的又长又烂虽然ac了
方案二
参考网友的，整体方案还是模拟但是，向前进位的时候直接进就好了。
#include <iostream>
using namespace std;
const int maxn = 10000;
int T1[maxn] = { 1 };
int temp = 1,k = 0 ; //T1的存储长度
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <temp; ++j) {
T1[j] = T1[j] * i + k;
k = T1[j] / 10;
T1[j] = T1[j] % 10;
if (j == temp-1 && k != 0) {
++temp;
}
}
}
//逆序输出
for (int i = temp-1; i >= 0; --i) {
cout << T1[i];
}
return 0;
}
