阶乘的强悍溢出技能

2024-03-22 03:12
文章标签 阶乘 溢出 技能 强悍

本文主要是介绍阶乘的强悍溢出技能,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】

输入n,计算S=1!+2!+3!+…+n!的末6位(不含前导0)。,n!表示

前n个正整数之积。

【样例输入】

10

【样例输出】

37913

一、阶乘溢出性能体验

按正常逻辑,本题可以分三步:

①求1-n的阶乘。

②把每项阶乘加起来。像这样一项一项地把各个式子加到一起,就是累加器。

③取和的末6位。

但是别忘了还有一个条件:

一看到这么大的数,又是阶乘,免不了心里一沉,直觉冥冥中指引恐怕long long型也罩不住。

先拿求n的阶乘探探底。

#include<stdio.h>
int main(){for(int n=1; n<=1e6; n++){long long factorial = 1;for(int i=1; i<=n; i++){factorial *= i;}printf("%d %lld\n", n, factorial);}return 0;
}

结果输出一堆0,肯定是鸟鸣山一样,完鸟。

把1e6改成100,仍然是一堆0,看来早就超限了。

没错,21!的已经输出负数,阶乘的溢出能力实在是太强悍了。

也就是说,用long long型只能计算到20!。如果用int型呢,只能计算到12!。

这可咋办?

二、大数取余神药

据说有一味神药:要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数,可以在每步计算之后对n取余,结果不变。

也就是说:

t=(a*b+c-d)%n中t的值可以分步取余求出:

t1=a*b/%n;
t2=(t1+c)%n;
t=(t2-c)%n;

是何道理呢?其实很简单,因为任何整数除以n的余数都是这个数减去n的倍数后余下的数。

如果x%n=y,它的意思是x=kn+y(x、y、k为整数,y<x)。

显然,所有含n的项都能被n整除,不会产生余数,所以可将其去除,变为:

它们分别是a、b、c、d除以n的余数,所以有:

三、代码实现

在神药的帮助下,本题可改为如下两步:

①求1-n的阶乘。用for循环实现累乘,每执行一次乘法都对1e6取余。

②把每项阶乘加起来。用for循环实现累加,每加一次都对1e6取余。

代码如下:

#include<stdio.h>
int main(){const int MOD = 1e6;int n, S = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){int factorial = 1;for(int j = 1; j <= i; j++)factorial = factorial * j % MOD;S = (S + factorial) % MOD;}printf("%d\n", S);return 0;
}

将1e6定义为MOD常量可以改善程序的可读性,也便于修改(代码中有两次用到这个数,使用MOD表示的情况下,如需修改只需改一次MOD的值)。

另一点需要注意的是,两行取余代码千万不要写成下面这种牛皮plus形式:

factorial *= j % MOD;
S += factorial % MOD;

因为*=、+=这种赋值运算符和=一样,优先级是非常低的,而%的优先极和*、/是一样的,所以会先计算取余,再进行乘赋值、加赋值。

比如下面的代码:

#include<stdio.h>
int main(){int i=10;i *=50+2;printf("%d\n", i);return 0;
}

它的结果是520,而不502。

三、代码优化

前面给出的求阶乘之和的代码可以进一步优化,将两层循环减少为一层循环。

如果读到这里,请别急着往下读,先自己思考一下方法。

原理很简单:n!可表示成前n个正整数之积,也可以表示成(n-1)!*n,所以只要保留上一次循环求得的阶乘,就可以通过累乘的方式求得n的阶乘。这时候就要把factorial这个变量放到循环体之外定义。

代码如下:

#include<stdio.h>
int main(){const int MOD = 1e6;int n, factorial=1, S = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){factorial = factorial * i % MOD;S = (S + factorial) % MOD;}printf("%d\n", S);return 0;
}

四、耗时测试

阶乘,最大的阶乘,阶乘之和。这样的豪华的阵容吞噬时间的能力必然很是强悍吧!

如果想了解代码的运行时间,可以用计时函数clock()。它定义在< time.h>头文件中,该函数返回从程序启动到调用 clock() 时的 CPU 时间。从这个描述咱们要明白:

①统计时间从启动程序开始。这意味着,输入数据的时间也是计算在内的。

②返回时间与clock()代码放置位置有关。

③返回的不是秒数。

针对上述特点,如果咱们想获取程序的纯运行时间(不计用户输入时间),可以采用如下对策:

(1) 借助命令行工具刨除数据输入时间。

①同时按下Win+R键,快速打开运行窗口。

②在运行窗口中输入“cmd”并按回车,打开命令行窗口。

③直接在光标处输入编译后的可执行文件所在盘符,如D:。

④输入cd folder1\folder2(表示D:\folder1\folder2,指程序执行文件所在路径,可以通过复制粘贴的方式输入)

⑤确认进入程序所在路径,然后输入:echo 52|u。操作系统会自动把52输入,其中u是程序名。如果要输入多条数据,可以写成echo 52 92|u。

(2) 计时函数clock( )放在程序结束之前。这样就能返回整个程序的执行时间。

(3) 返回秒数:用clock( )/CLOCKS_PER_SEC可以得到秒数。可以想象有个法号叫CPU的和尚在敲钟,clock( )能告诉你它敲了多少下,CLOCKS_PER_SEC指的是敲钟的速度(每秒敲多少下),二者相除就得到敲了多少秒。

代码如下:

#include<stdio.h>
#include<time.h>
int main(){const int MOD = 1e6;int n, S = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){int factorial = 1;for(int j = 1; j <= i; j++)factorial = (factorial * j % MOD);S = (S + factorial) % MOD;}printf("%d\n", S);printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);return 0;
}

将优化前后的代码分别测试结果如下:

n

18

19

20

21

22

23

24

25

26

答案

348313

180313

820313

260313

940313

580313

940313

940313

940313

n

1600

3200

6400

12800

25600

51200

102400

204800

409600

答案

940313

940313

940313

940313

940313

940313

940313

940313

940313

优化前

时间

0.03

0.05

0.12

0.38

1.44

5.74

23.28

93.43

381.62

优化后

时间

0.03

0.03

0.03

0.03

0.03

0.03

0.03

0.03

0.03

从表中数据可得出:

(1) 优化后的一层循环都是瞬间运行完毕,而优化前的两层循环随着n的变大,运行时间越来越长,呈指数上升。

(2) 程序的运行时间大致和n的平方成正比(因为n每翻一番,运行时间近似翻两番)。据此可估计n=1e6时,程序大致需要37分钟才能执行完。

这涉及到一个估算时间复杂度的技巧:很多程序的运行时间与规模n存在着近似的简单关系,这种关系可以通过计时函数来估测。比如上表通过对比每次将n翻倍的运行时间来验证这一关系。

(3) 从24开始,答案始终不变。这是因为25!末尾有6个0,所以从第5项开始,后面的所有项都不会影响和的末6位数字。所以,对于优化前的代码,只需要在程序的最前面加一条语句“if(n>25)n=25;”,你就不用等几十分钟才能看到n=1e6时的结果了。

这篇关于阶乘的强悍溢出技能的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/834419

相关文章

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

c++习题30-求10000以内N的阶乘

目录 一,题目  二,思路 三,代码    一,题目  描述 求10000以内n的阶乘。 输入描述 只有一行输入,整数n(0≤n≤10000)。 输出描述 一行,即n!的值。 用例输入 1  4 用例输出 1  24   二,思路 n    n!           0    1 1    1*1=1 2    1*2=2 3    2*3=6 4

CTFHub技能树-Git泄漏-Index

目录 一、Git索引(Index)的基本概念 二、解题过程 主旨:使用git泄漏恢复源代码 方法一:使用GitHack手动恢复 方法二:直接使用Git_Extract获取网站源代码拿去flag   当前大量开发人员使用git进行版本控制,对站点自动部署。如果配置不当,可能会将.git文件夹直接部署到线上环境。这就引起了git泄露漏洞。请尝试使用BugScanTeam的Gi

作为刚从事Java开发的小白,需要掌握哪些技能

作为一个刚踏入Java开发世界的小白,面对各种技术和工具,你可能会觉得有点不知所措。但是别担心,我会给你一个简单清晰的路线图,让你可以有条不紊地掌握基本技能,逐步成长为一名Java开发者。 1. 扎实的Java基础 Java的基础是你迈向高级开发的重要基石,建议从以下几个方面着手: 语法和基础概念:比如变量、条件语句、循环、方法、数组、面向对象编程(OOP)等等。这些基础如同建房子的地基,越

高精度加法,乘法,阶乘

#include <iostream>#include <map>#include <string>#include <algorithm>using namespace std;const int Max = 50000;string str1,str2;/***********乘法***********/void chenfa(){cin >> str1>>str2;int a

堆内存溢出的测试类——JVM学习笔记

记个笔记,手写一个测试类,模拟堆内存溢出。 /*** 堆内存溢出测试类* VM Agrs: -Xms10m -Xmx10m -XX:+HeapDumpOnOutOfMemoryError* @author lixiang* @date 2019年04月12日 - 14:44* @history 2019年04月12日 - 14:44 lixiang create.*/public class

COI实验室技能:图像到图像的深度学习开发框架(pytorch版)

Basic deep learning framework for image-to-image 这个开发框架旨在帮助科研人员快速地实现图像到图像之间的模型开发。 github连接:https://github.com/SituLab/Basic-deep-learning-framework-for-image-to-image 目录 1模型开发 1-1克隆项目到本地1-2深度学习开发

【LeetCode】:面试题 16.05. 阶乘尾数

🎁个人主页:我们的五年 🔍系列专栏:C++课程学习 🎉欢迎大家点赞👍评论📝收藏⭐文章   好久没有写文章了,今天碰见了一道有趣的题目,写下来分享一下。 🏆1.问题描述:  🏆2.问题分析: 🎲优化一: 首先看到这道题的时候,暴力肯定是不行的,n的阶乘可能会是一个很大的数,肯定是会超过int,long long的范围的。 然后再去想其他的方法优

C/C++的阶乘求和以及变量存储数据大小

目录 1. 前言 2. 正文 2.1 问题 2.2 解决办法 2.2.1 思路 2.2.2 代码实现 2.2.3 测试结果 3. 备注 1. 前言 其实刚学C语言的时候,打击都会先认识,类型,像int,double之类的存储类型。在这篇文章中,就需要大家对这个大小有了解。 2. 正文 2.1 问题 题目描述: 一个正整数如果等于组成它的各位数字的阶乘之和,该整数