|
题目来源：校软件班第二周作业第一题 参考：阶乘，递归函数，C语言常见数据类型范围，算术溢出，高精度算法
阶乘： 一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。 亦即n!=1×2×3×...×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。 递归函数： 一个函数可以调用其他函数，而当它调用自己的时候，就称其为递归（注意：递归函数必须要有终止条件） C语言常见数据类型范围：
signed 和 unsigned 分别对应 有符文 和 无符号
字节数： 用sizeof()来求，例如 sizeof(int)==4
位数 即bit数 ： 一个字节是8位，所以 sizeof(int)的位数是32位
取值范围： 2进制下的最大取值 转换成的 10进制数
例如：sizeof(int)的位数是32位，二进制下除最高位符号位为0(表示正数)，剩下31位取1，相加得 2147483647
 注意：剩下31位下标是0-30，最高位是2^30。
算术溢出：算术溢出（arithmetic overflow）是指计算机进行算术运算产生的结果超出机器所能表示的范围。
深入理解：https://www.jianshu.com/p/ffc97c4d2306
https://blog.csdn.net/itworld123/article/details/78914969
高精度算法：计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。---重点是模拟！
模拟谁呢？。。当然是模拟人啊，你想想人是怎么计算加减乘除的。
入门详解：https://blog.csdn.net/zsjzliziyang/article/details/82050337?utm_source=blogxgwz0
一种寻常的思路是直接递归：
#include<stdio.h>
int fac(int n){
if(n<=1) return 1;
return n*fac(n-1);
}
int main(){
int n;
scanf("%d",&n);
printf("%d",fac(n));
return 0;
}
但会出现一个问题，在20！的时候，出现了负数？（算术溢出）
事实上，在第13！的时候，int就不够储存了，int的最大值是 2147483647 13！正确的答案是 6 227 020 800
而这段代码的错误答案是：
一种简单的解决方式是，是用取值范围比int还大的数据类型来储存 比如：long long ,double,long double etc.... 例如 long long
但是，在21！的时候。。。
这算是基本满足了题目的要求吧，但对于进阶的数据范围200<n<1000，还是远远不够， 也许你想到了用其他类型，比如最大的long double，4932位 但是。。mingw使用windows的C运行库，里面的printf不支持long double的输出（你可以在linux环境下试试） 也许你试了试就会发现，看似4932位计算的如此之多，但long double的有效位只有18-19位，所以后面的4000多位，全部是0。 那怎么办呢？？
用模拟的思想， 我们人是怎么进行加减乘除运算的？。 相信聪明的你已经想到了幼儿园老师交的办法 竖式计算： 指在计算过程中列一道竖式计算，使计算简便。加法计算时相同数位对齐，若和超过10，则向前进1。 减法计算时相同数位对齐，若不够减，则向前一位借1当10。
很简单易懂的思想对吧，那怎么实现呢？，如何把每一位数都存起来呢？ 当然是用数组啦。。。。 1 #include<stdio.h>
2 const int N=10000;// 定义一个不可改变的常数N
3 int a[N];
4 int main(){
5 int n;
6 scanf("%d",&n);
7 int s=0;
8 a[0]=1;
9 int ans=0;
10 for(int i=1;i<=n;i ){
11 int t=0;//进位
12 for(int j=0;j<N;j ){//模拟计算
13 s=a[j]*i t;//每一位乘以i,再加上t
14 a[j]=s;//余数
15 t=s/10;
16 }
17 }
18 int k=N-1;
19 while(a[k]==0) k--;//删除前导0
20 for(int i=k;i>-1;i--) printf("%d",a[i]);
21 printf("\n\n%d\n",k);//计算位数
22 return 0;
23 }
这是定义了10000位，假如需要计算更大的数，可以改变N的值。 来源：http://www./content-4-71951.html |
|
|
