最新消息:

2019年海淀区青少年程序设计挑战活动复赛小学组C++试题第2题题解

C++ 少儿编程 1909浏览 0评论
2019年海淀区青少年程序设计题解

2

阶乘

    分析:利用模拟过程法,根据题目的意思,利用循环先求出n!和n!!,在求n!!的时候,先判断n的奇偶性,如果为偶数,循环从2到n,步长为2;如果为奇数,循环从1到n,步长为2。然后再循环求n!和n!!的值的末尾0的个数。代码如下:

#include <iostream>

using namespace std;

int main(){

    longlong n,f1=1,f2 =1,ans1 =0,ans2 =0;

    cin >> n;

    for(int i =1;i <= n;i++){

        f1 = f1*i;

    }

    if(n%2==0){

        for(int i =2;i <= n;i=i+2){

            f2 = f2*i;

        }

    }else{

        for(int i =1;i <= n;i=i+1){

            f2 = f2*i;

        }

    }

    cout << f1 <<” “<< f2 << endl;

    while(f1){

        if(f1%10==0){

            ans1++;

            f1 = f1/10;

        }else{

            break;

        }

    }

    while(f2){

        if(f2%10==0){

            ans2++;

            f2 = f2/10;

        }else{

            break;

        }

    }

    cout << ans1 <<” “<< ans2 << endl;

    return 0;

}

运行结果:

2019年海淀区青少年程序设计挑战活动复赛小学组C++试题第2题题解

2019年海淀区青少年程序设计挑战活动复赛小学组C++试题第2题题解

       这种方法思考起来简单,但n一旦大于20,阶乘的结果就会特别大,数据将会发生异常。   

       具体观察每种情况,把特殊情况特殊处理掉省去不必要的时间以及寻找n与阶乘和双阶乘末尾0的个数的关系,这样可以避免计算n!和n!!的大数。

       观察n!发现,阶乘末尾的0的个数跟n中5的个数有关系,有几个5阶乘末尾就有几个0。因为0的出现的根本原因就是5*偶数的存在。

       在求n!!的时候,如果n为奇数,则都是奇数相乘,而奇数相乘的结果必然为奇数,奇数的末尾不可能有0,所以这种情况下输出0即可。如果n为偶数,则都是偶数相乘,那结果必然为偶数,末尾就可能有0,需要进行计算判断。其中双阶乘的末尾的0的出现通过两种方式,第一种当n<50时,主要是通过10的倍数,第二种当n>=50时,这个时候数字当中出现5,有10的倍数的原因,也有5*偶数的原因。代码如下:

#include <iostream>

using namespace std;

int main(){

    int n,f1=1,f2 =1,ans1 =0,ans2 =0;

    cin >> n;

    int t1 = n,t2 = n;

    while(t1){

        t1 = t1 /5;

        ans1= ans1 + t1;

    }

    if(n%2==0){

        t2 = t2 /10;

        ans2 = ans2 + t2;

        while(t2){

            t2 = t2/5;

            ans2 = ans2 + t2;

        }

    }else{

        ans2 =0;

    }

    cout << ans1 <<” “<< ans2 << endl;

    return 0;

}

转自公众号:
noip案例讲解

您必须 登录 才能发表评论!