PTA 函数题（C语言） |
您所在的位置：网站首页 › 10的阶乘c语言程序俩个for循环做 › PTA 函数题（C语言） |
PTA 函数题（C语言）
|
题目title： 阶乘计算升级版 题目作者： 陈越 浙江大学 本题要求实现一个打印非负整数阶乘的函数。 函数接口定义： void Print_Factorial ( const int N );其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出N!的值，否则打印“Invalid input”。 裁判测试程序样例： #include int Factorial( const int N ); int main() { int N, NF; scanf("%d", &N); NF = Factorial(N); if (NF) printf("%d! = %d\n", N, NF); else printf("Invalid input\n"); return 0; } /* 你的代码将被嵌在这里 */ 输入样例： 15 输出样例： 1307674368000思路：这道题目的最后一个测试点是一个坑，要通过最后一个测试点就不能用普通的int、long long去存放计算出来的阶乘了，因为会越界！ 我们的思路是用一个数组F[N]来存放阶乘（这里数组长度最小设置为N=2568，这个长度是我试出来的刚好能通过最后一个测试点的最小数组长度，多写点也无所谓）。存放的结构是低位在前，即F[0]存放的是个位，依此类推。 计算阶乘的时候我们用外层循环让i从2迭代到N，每次迭代给F"乘以"i。 这里的这个给数组"乘以"一个数，是用里层循环完成的，就按照我们小学学过的整数带进位的乘法。遍历从F[0]到F[N-1]，比如遍历到某个F[j]，我们要做的运算下面3步： （1）给F[j]乘以外层循环当前的i，在加上F[j]前一项进位过来的值carry，然后把结果赋值给F[j]，即F[j]=F[j]*i+carry； （2）计算出要进位给下一位F[j+1]的值，carry = F[j]/10； （3）F[j]只保留个位数字，F[j] = F[j]%10。 举个例子，如下图所示
假设我们已经得到12!=479001600，现在要计算13!。首先我们把479001600按照从低位到高位的次寻排列在数组F中，就是上图中的第一行。然后对数组F的每一位乘以13，例如我们现在计算到F[2]这个位置了，我们F[2]*13得到78，我们去78的个位7，加上这个位置的进位项0（是由前一个位置计算得来的），于是新的F[2]的结果就是7。最后别忘了把78整除10后的商赋值给下一位的进位项。 当里层循环遍历完，就像相当于给当前的阶乘F"乘以"外层循环当前的i， 当外层循环迭代完，F就存储了我们想要的阶乘了，只不过存储的结构是低位在前。 最后，我们要找到数组最后一个不为0的元素，从这个元素开始倒序输出数组即可。 代码： void Print_Factorial ( const int N ) { int i, j, carry = 0; int M = 2568, F[2568] = {1}; // 初始化一个长度为2568的数组,为什么是2568呢？因为刚好能通过最后一个测试点。比2568长，是可以的。 if (N < 0) { printf("Invalid input"); return; } else if (N == 0) { printf("1"); return; } else if (N > 0) { for (i = 2; i = 0; i--) { if (F[i] != 0) { break; } } for (j = i; j >= 0; j--) { printf("%d",F[j]); } return; } } 更多PTA题目的的参考代码，可以在wx小程序里搜“PTA刷题助手”，或扫下面的二维码
|
【本文地址】
今日新闻 |
推荐新闻 |