蓝桥杯--阶乘之和

待我称王封你为后i 2021-09-22 12:50 501阅读 0赞

题目描述：

输入n， 计算S＝ 1！ ＋ 2！ ＋ 3！ ＋ …＋ n！ 的末6位（ 不含前导0 ）n≤10^6， n!表示前n个正整数之积。  
样例输入：  
10  
样例输出：

37913

题目分析：

这道题目看似是很简单的一个循环问题，实际上这个题目还是有很多坑的，例如数据溢出、时间效率问题。肯定会有同学上手就用下面的代码来做（这个题是在楼主刚学习没有多久的时候做的），这很正常，经过测试的同学就能知道这个代码就存在着上述我说的那些问题。

这个代码只适用于N的次数较少的做法，并不能满足这个题的需求，放在这就当作是一个反例吧！！！

#include<iostream>
    using namespace std;
    int main()
    {
    	int T,n=1,sum=0;
    	cin>>T;
    	for(int i=1;i<=T;i++)
    	{
    		n=n*i;   //每一次阶乘 
    		sum+=n;  //阶乘加和 
    	}
    	cout<<sum%1000000<<endl;//后六位 
    	return 0;
    }

改进一(解决数据溢出问题)：

让我们重新来看这个问题，这个题最终要求的是N！之和的后六位，我们通常的思维都是求和完成之后再做%运算，其实我们我们可以在每一次加和的时候就直接考虑将%加入，这样就不会出现数据溢出的问题。

代码如下：

#include<iostream>
    using namespace std;
    int main()
    {
    	int T,n=1,sum=0;
    	cin>>T;
    	for(int i=1;i<=T;i++)
    	{
    		n=(n*i)%1000000;   //对每一次阶乘的运算都取模
    		sum+=n;  //阶乘加和
    	}
    	cout<<sum%1000000<<endl;//后六位 
    	return 0;
    }

改进二(解决代码效率问题)：

如果你只是想完成这个题，就不需要看着一部分了

如果你看到了这一行说明你有点兴趣，那么我可能接下来会说很多的废话（关于我看待算法的见解、见仁见智、不喜勿喷）

解决完上面的数据数据溢出，如果有细心的小伙伴肯定会去测试边界数据也就是当N=1000000的时候，这个时候你就会惊喜的发现，这个边界值是能够运行出答案了，那么这个题是不是就意味着做完了呢？实际上如果只是针对这个题来说，这个代码确实已经够了，但是我为什么还要在这个地方提出改进二呢，这是因为这个题实际上还是可以继续优化的，有一点算法知识的同学都是能看出这个算法应该是O(n)的时间复杂度的，这个时间复杂度并不是特别的高（勿杠！！相对来说！！），但是一个好的算法的时间复杂度是什么？应该是O(log n)甚至于是O(1)之类的，所以我们应该尝试着去实现，这样的算法，O(n)不好吗？好，但是对于一个学计算机的人来说，它还不够好，除非它真的已经没有办法再优化了，我们才能说这个算法，已经是当前最优的了。

接下来我们回到这个问题中来，O(n)的算法我们如何区去优化，目前位置的最好办法就是找规律（照规律就不说了大家都懂）、剪枝（剪枝这里我说一下，就是在程序执行的过程中利用一些已知的限制条件去尽可能的减少循环或者递归的次数、想当于把无用的枝桠剔除掉，方便我们去寻找主要的内容）

这个题的话其实照规律就行了

很多同学会测试很多很大的数据：1000000、1000、100000等等，细心的人可能都发现了他们的值竟然都是一样的，都是940313，这个时候，就要提出疑问了，为什么会相同呢？到底有多少相同呢？

带着这个疑问我们将这些数据都打印出来

测试代码：

#include<iostream>
    using namespace std;
    int main()
    {
    	int T,n=1,sum=0;
    	cin>>T;
    	for(int i=1;i<=T;i++)
    	{
    		n=(n*i)%1000000;   //每一次阶乘 
    		sum+=n;  //阶乘加和
    		cout<<sum%1000000<<" "<<i<<endl;//后六位 
    	}
    	return 0;
    }

运行如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70][]

看着这里相比你已经很清楚了吧，图中很清楚的能够看到从N=24开始后面的数据就一直是940313，所以我们成功的发现了这个代码隐藏的规律，那就是N=24之后的数据我们就不用再进行计算了

这样我们的时间复杂度是多少？O(24)对吧？，显而易见这个代码的时间复杂度已经趋近于是O(1)级别的了。

改进代码如下：

#include<iostream>
    using namespace std;
    int main()
    {
    	int T,n=1,sum=0;
    	cin>>T;
    	for(int i=1;i<=T;i++)
    	{
    		if(i>24)
    		break;
    		n=(n*i)%1000000;   //每一次阶乘 
    		sum+=n;  //阶乘加和
    	}
    	cout<<sum%1000000<<endl;//后六位 
    	return 0;
    }

到这里整个题的求解和优化就结束了，

附：可能有的同学不太能理解为什么24之后就不再增长了，我这里给大家放一个图，图中我打印的是1！+....+ N！在每一个阶段%1000000的取值，图中显而易见的在25它的值就为0了，%1000000的值为0说明什么，bingo！没错就是他的尾数至少都有6个0了，这样才会出现x%1000000=0的情况，所以后面不管怎么增加所得到的数据末尾都会大于6个0，所以对再增加对末尾的取值就不会有任何影响了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70 1][]

到此结束！谢谢耐心阅读！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70]: /images/20210920/fe6e0a1375f04af4aa0afef738124eae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70 1]: /images/20210920/edafcb9896734d658a39a8c271fe4d4b.png