蓝桥杯vip题阶乘计算

时间:2023-12-16 23:45:56

蓝桥杯vip题阶乘计算

详细题目


输入一个正整数n,输出n!的值。

其中n!=123n。

算法描述

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