OJ ：1089 ： 阶乘的最高位

题目描述

输入一个正整数n。输出n!的最高位上的数字。

输入

输入一个正整数n（n不超过1000）。

输出

输出n!的最高位上的数字。

样例输入 

1000

样例输出 

4

思路： 

        这个问题的难点就在于如何处理据，需要注意数据溢出，比如1000的阶乘就很大很大，就算long long int 都存储不下，那么我们就用一个数组来存储阶乘的结果，然后从结果的高位开始找到第一个非零数字，即阶乘的最高位数字。不懂的可以结合代码的注释进行理解。

代码：

#include<stdio.h>

int main() 
{
    int n;
    scanf("%d", &n); // 从标准输入读取n

    // 定义一个数组来存储阶乘结果，最多需要1001位来表示n的阶乘
    int result[1001] = { 0 };
    result[0] = 1; // 初始值为1，因为1的阶乘等于1

    // 计算阶乘
    for (int i = 2; i <= n; i++) 
    {
        int carry = 0; // 进位
        // 逐位相乘
        for (int j = 0; j < 1001; j++) 
        {
            int product = result[j] * i + carry; // 当前位的乘积加上进位
            result[j] = product % 10; // 当前位的结果
            carry = product / 10; // 计算下一位的进位
        }
    }

    // 找到最高位上的数字
    int highestDigit;//需要在循环外进行声明，输出时要用到（涉及到局部变量）没理解可以私信问我
    for (highestDigit = 1000; highestDigit >= 0; highestDigit--) 
    {
        if (result[highestDigit] != 0) 
        {
            break; // 找到第一个非零数字，即最高位数字
        }
    }

    printf("%d", result[highestDigit]); // 输出最高位数字

    return 0;
}