首页 > 代码库 > HDU1042（N!）题解
HDU1042（N!）题解
HDU1042（N!）题解
以防万一，题目原文和链接均附在文末。那么先是题目分析：
【一句话题意】
计算N的阶乘并输出。
【题目分析】
题给范围上限是10000，那么毫无疑问是大数题。之前我整理过各种大数的代码并且改了改然后所谓封装了一下，于是这道题就直接用了个类似的代码修改了一下，然后。。。交上去就对了（喂。。）。
但是作为题解，怎么着也得把做法解释清楚吧。。
以下为c语言代码（虽然是cpp提交的，也带了一堆cpp头文件），也附带了代码解释。代码很好懂，看看解释应该看得明白。还有...如果你是写java代码的。。现成的BigInteger再见慢走不送~
【算法流程】
大数乘小数：
这里的小数指的是int范围内的小数。不管你知道不知道，我们假设你知道，大数应当用一个数组来存储，下标对应每一位的数字（下标和位数的关系可能会是或者说经常是相反的）。而大数运算则是相当于模拟小学的列式计算。那么，我们只需要按照小学那样，让大数的每一位和小数相乘，然后记录进位并加在下一位即可。
为了方便计算，我们用int数组a存储大数，常整i存储小数（这个变量名称改改看着就舒坦了，这里不改是因为...因为....因为爱情XD），为了方便，我们采取下标从小到大对应个，十，百，千，万...的存数方式。为了方便管理位数和输出，我们另外使用一个变量digit存储管理大数现有位数。我们用变量j作为迭代器来扫位数进行模拟每一位的乘法，并用carry存储进位。（注：temp类型是int。）
于是，顺应上面的解释，我们有了这样的代码：
for(carry = 0, j = 1; j <= digit; ++j) { temp = a[j - 1] * i + carry; a[j - 1] = temp % 10; carry = temp / 10; } while(carry) { //处理完毕仍需进位时，需要注意变动digit a[++digit - 1] = carry % 10; carry /= 10; }
我们可以这样测试上面的代码
int a[455000] = {5,4,3,2,1};//初始化为12345，想改自己改= =
digit = 5;//如上，五位
i = n;//n为你要乘的数
自己封装个函数测试吧。。。。。。当然测试结果应该很科学。
修改代码：
大数乘小数有了，那么我们循环从1乘到你要的数（最大1w）就是了。明显，我们需要：
int a[455000] = {1};//初始化为1 digit = 1;//1位（废话 for(i = 2; i <= n; i++) { //这里放大数乘小数的代码，i为小数，a数组为大数。n为要阶乘到的数 //由于是循环，于是每次乘的结果就是大数*2*3*4*...*n了 }
这下明白了吧。。
上代码。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 #include <math.h> 7 8 using namespace std; 9 10 void echoFactorial(int n);11 12 int main() {13 14 int n;15 while(scanf("%d",&n) != EOF) {16 echoFactorial(n);17 }18 return 0;19 }20 21 void echoFactorial(int n){22 int carry, j;23 int digit;24 int temp, i;25 int a[455000] = {1};//the express code of hometown26 digit = 1;27 for(i = 2; i <= n; i++) {28 for(carry = 0, j = 1; j <= digit; ++j) {29 temp = a[j - 1] * i + carry;30 a[j - 1] = temp % 10;31 carry = temp / 10;32 }33 while(carry) {34 a[++digit - 1] = carry % 10;35 carry /= 10;36 }37 }38 39 for(int k = digit; k >= 1; --k)40 printf("%d", a[k - 1]);41 printf("\n");42 43 }44 /*45 TestData(IN)46 147 248 349 TestData(OUT)50 151 252 653 */
这里是附带的题目信息：
题目链接：（HDU 1042）N!
题目属性：大数，模拟（竟然有说这道题要枚举的，醉，怎么可能。好吧你要枚举我一点也不介意~）
相关题目：1002、1042、1133、1250、1297、1715、1753、1865、2100
题目原文：
【Desc】Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
【In】One N in one line, process to the end of file.
【Out】For each N, output N! in one line.
【SampIn/Out】参见代码下方的注释。
HDU1042（N!）题解