SDUT 2059 简单n!(大数阶乘)解题报告

2016-01-26 221 次浏览 解题报告

题面

简单n!
Time Limit: 1000MS Memory limit: 65536K

题目描述
给定一个数n(0 <= n <=150), 求0到n中所有数的阶乘。

输入
题目有多组数据,处理到文件结尾。输入一个数n。

输出
输出阶乘,形式如:4! = 24.每组数据输出后跟一个空行。

示例输入
1 4

示例输出
0! = 1 1! = 1

0! = 1 1! = 1 2! = 2 3! = 6 4! = 24

解题思路

注意到题目中给出的 n 最大值是 150,显然其阶乘用 int 和 long long 都是存不下的,需要模拟能存放大数的数据类型,容易想到的方法是定义一个 int 型数组 a, 每个元素存储大数的每一位数字。但是每一个元素仅存储一位数字显然有些浪费,并且在运算中做乘法运算时,每一位数字都参与运算一次,当大数的位数较大时循环次数会比较多。因此,我们不妨让每个元素记录 4 位数字。例如:对于一个大数 12345678987,我们从后向前每 4 位数记录到数组 a 的一个元素中,即 a[0] = 8987, a[1] = 4567, a[2] = 123。在输出时按下标从后向前输出即可表示大数。

解决了如何存储大数的问题,剩下的就是如何做乘法了。容易想到的思路是模拟手算竖式乘法,但是稍有不同的是我们将每 4 位数存储到一个数组元素中当作一位,所以我们的进位设定为逢万进一。例如:

_36230
x____8
289840

对于 36230 x 8 ,我们的被乘数是 36230,即 a[0] = 6230, a[1] = 3,乘数是8。和传统竖式乘法不同的是,我们每 4 位数做一次运算,即首先运算 6230 x 8 = 49840,逢万进一,进位为 4,进位后 a[0] 为 9840。之后计算下一个位,3 x 8 = 24,加上进位为 a[1] = 24 + 4 = 28,进位为 0。至此 a 中元素全部运算完毕,按数组下标逆序输出即为结果 289840。

这样我们就可以写出本题的代码了:

#include <stdio.h>

int main(int argc, char const *argv[])
{
    //数组a的大小能存下150!(200多位的数)即可
    //len表示当前大数的长度
    //carry表示进位数
    //product表示当前位做乘法运算后的乘积
    int a[66], n, len, carry, product, i, j;
    while(~ scanf("%d", &n))
    {
        printf("0! = 1\n");
        len = 1;
        a[0] = 1;
        for(i=1; i<=n; ++i)
        {
            carry = 0;
            for(j=0; j<len; ++j)
            {
                //计算当前位的乘积
                product = a[j]*i + carry;
                //进位后的值通过乘积取余10000得到
                a[j] = product % 10000;
                //进位数通过乘积/10000得到
                carry = product / 10000;
            }
            a[j] = carry;
            //计算完毕后如果存在进位,则长度+1
            if(carry) len++;
            printf("%d! = %d", i, a[len-1]);
            for(j=len-2; j>=0; --j)
            {
                //不足四位数的前补0来输出
                printf("%04d", a[j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}

其他解题方法

其实运用 Java 的 BigInteger 可以方便的处理大数运算,具体关于 BigInteger 的用法可以自行去搜索。在这里只提供代码:

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger a;
        int n;
        while(in.hasNext()) {
            n = in.nextInt();
            a = BigInteger.ONE;
            System.out.println(0 + "! = " + 1);
            for(int i=1; i<=n; ++i) {
                a = a.multiply(BigInteger.valueOf(i));
                System.out.println(i + "! = " + a);
            }
            System.out.println();
        }
    }
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/01/26/sdut-2059.dream

还不快抢沙发

添加新评论