蓝桥杯vip题阶乘计算

蓝桥杯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;
}

蓝桥杯vip题阶乘计算

原文：https://www.cnblogs.com/xiaoxiaodaining/p/12394523.html