华为机试题：可怕的阶乘

红太狼 2022-08-20 06:30 106阅读 0赞

题目标题：

· 计算阶乘n!是一件可怕的事情，因为当n并不是很大时，n!将是一个很大的值。例如13! = 6227020800，已经超过了我们常用的unsigned int类型的取值范围。请设计一个程序，使其可以计算100以内的数的阶乘，结果用字符串的形式输出

详细描述：

· 接口说明

原型：

void CalcNN(int n, char \*pOut)

输入参数：

int n 需要计算的阶乘数

输出参数：

char \*pOut 结算结果，内存由调用者负责管理

返回值：

无

限制：

无

举例：

#include <stdlib.h>
    #include <stdio.h>
    #include <vector>
    #include <string.h>
    #include <algorithm>
    #include <iostream>
    #include "oj.h"
    
    using namespace std;
    
    /*****************************************************************************
    Prototype    : multiply
    Description  : 两个任意长度的长整数相乘, 输出结果
    Input Param  :
    const std::string strMultiplierA  乘数A
    const std::string strMultiplierB  乘数B
    Output       :
    std::string strRst            乘法结果
    Return Value :
    int                       0  正确
    -1  异常
    *****************************************************************************/
    int multiply(const std::string strMultiplierA, const std::string strMultiplierB, std::string &strRst)
    {
    
    	if (strMultiplierA.length() == 0 || strMultiplierB.length() == 0)
    	{
    		return -1;
    	}
    
    
    	/* 在这里实现功能 */
    	vector<int> vecA, vecB, vecC;
    	string strA = strMultiplierA;
    	int i = 0, j = 0;
    
    	/*将字符串转换为数字并翻转*/
    
    	/*将字符串转换为数字并翻转*/
    	for (i = strA.size() - 1; i >= 0; i--)
    	{
    		vecA.push_back(strA[i] - '0');
    	}
    
    	for (i = strMultiplierB.size() - 1; i >= 0; i--)
    	{
    		vecB.push_back(strMultiplierB[i] - '0');
    	}
    
    
    	vecC.resize(vecA.size() + vecB.size());
    
    	/**逐位相乘*/
    
    	for (i = 0; i < vecA.size(); i++)
    	{
    		for (j = 0; j < vecB.size(); j++)
    		{
    			vecC[i + j] += vecA[i] * vecB[j];
    		}
    	}
    
    
    	/*消除进位*/
    	for (i = vecC.size() - 1; i >= 0; i--)
    	{
    		if (vecC[i] != 0)
    		{
    			break;
    		}
    		else
    		{
    			vecC.pop_back();
    		}
    	}
    	int c = 0;
    	for (i = 0; i < vecC.size(); i++)
    	{
    		vecC[i] += c;
    		c = vecC[i] / 10;
    		vecC[i] = vecC[i] % 10;
    	}
    	if (c != 0)
    	{
    		vecC.push_back(c);
    	}
    
    	/*将计算结果转换为字符串并翻转*/
    	for (i = 0; i < vecC.size(); i++)
    	{
    		strRst.push_back(char(vecC[i] + '0'));
    	}
    
    	reverse(strRst.begin(), strRst.end());
    
    	return 0;
    }
    
    void CalcNN(int n, char *pOut)
    {
    	if (pOut == NULL)
    	{
    		return;
    	}
    	if (n == 0)
    	{
    		pOut[0] = '1';
    		pOut[1] = '\0';
    		return;
    	}
    	char retchar[10000] = { "1" };
    	int i = 0;
    
    	for (i = 1; i <= n; i++)
    	{
    		string strA(retchar);
    		string strB,strC;
    
    		strB.push_back(char(i / 10 + '0'));
    		strB.push_back(char(i % 10 + '0'));
    
    		multiply(strA, strB, strC);
    
    		const char* p = strC.c_str();
    		memset(retchar, 0, 10000);
    		
    		strcpy_s(retchar, p);
    	}
    
    	for (i = 0; i < strlen(retchar); i++)
    	{
    		pOut[i] = retchar[i];
    	}
    	pOut[i] = '\0';
    	return;
    }