一道华为的机试题

同学最近找工作，遇到了一个机试题，咋一看感觉很简单，后来做了一下，才发现里面考察了很多东西，如字符串的操作，大数的计算等等....

废话不说，直接上题目

 

1、程序实现目标：输入1~20的数字n，求n以内数据的阶乘之和。
1! + 2! + 3! +......+n! = ?

void GetCount(int Num ,float pOutput[])
{

}
void main()
{
    float pNumber[2] = {0};
    Number = 20;
    GetCount(Number ,pNumber);
}

下面是lz写的程序

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN50

// float占4个字节，有符号 表示数的范围2^31 = 正负2147483648
// 2147483648反方向存储到maxStr中，低位存储低位数，方便计算
// maxStr 序号 9  8  7  6  5  4  3  2  1  0
//         值  2  1  4  7  4  8  3  6  4  8
static const char SIGN_NUM[10] = {'8', '4', '6', '3', '8', '4', '7', '4', '1', '2'};

// 缓存上一次阶乘的结果
static char lastResult[LEN] = {0};

// 获得有效位
int GetValidBits(char result[], int len)
{
int pos = len - 1;
while(result[pos] == 0) {
--pos;
}
return pos;
}

void Add(char num1[], char num2[], char result[]) 
{
int iadd = 0;
int carryAdd = 0;
for (iadd=0; iadd < LEN; ++iadd) {
int sum = num1[iadd] + num2[iadd];
result[iadd] = sum % 10 + carryAdd;
carryAdd = sum / 10;
}
if (carryAdd != 0) {
result[iadd] += carryAdd;
}

// 处理所有的进位
for (iadd = 0; iadd < LEN; ++iadd) {
if (result[iadd] >= 10) {
int sum = result[iadd];
result[iadd] = sum % 10;
result[iadd+1] += sum/10;
}
}

}

void Factorial(int num, char result[])
{
if (num == 1) {
result[0] = 1;
lastResult[0] = 1;
return;
}

int addPos = 0;
while (num != 0) {
int tmpNum = num % 10;
int carry = 0;

char middleNum[LEN] = {0};

// high其中的一位和lastResult 相乘
int ipos = 0;
for (ipos=0; ipos<LEN; ++ipos) {
int multi = lastResult[ipos] * tmpNum;
middleNum[ipos] = multi % 10 + carry;
carry = multi / 10;
}
if (carry != 0) {
middleNum[ipos] += carry;
}
// 处理所有的进位
for (ipos = 0; ipos < LEN; ++ipos) {
if (middleNum[ipos] >= 10) {
int sum = middleNum[ipos];
middleNum[ipos] = sum % 10;
middleNum[ipos+1] += sum/10;
}
}


// middleNum 和 result 错位相加
int iadd = 0;
int carryAdd = 0;
for (iadd=0; iadd < LEN; ++iadd) {
int sum = result[iadd+addPos] + middleNum[iadd];
result[iadd+addPos] = sum % 10 + carryAdd;
carryAdd = sum / 10;
}
// 加法进位，直到处理完
if (carryAdd != 0) {
result[iadd+addPos] += carryAdd;
}
// 处理所有的进位
for (iadd = 0; iadd < LEN; ++iadd) {
if (result[iadd] >= 10) {
int sum = result[iadd];
result[iadd] = sum % 10;
result[iadd+1] += sum/10;
}
}

num /= 10;
++addPos;
}

memcpy(lastResult, result, LEN);
}

void Multi(int num, char result[])
{
int ipos = 0;
int carry = 0;
for (ipos; ipos < sizeof(SIGN_NUM); ++ipos) {
int muti = (SIGN_NUM[ipos] - '0') * num;
result[ipos] = muti % 10 + carry;
carry = muti / 10;
}
if (carry != 0) {
result[ipos] += carry;
}

// 处理所有的进位
for (ipos = 0; ipos < sizeof(SIGN_NUM); ++ipos) {
if (result[ipos] >= 10) {
int sum = result[ipos];
result[ipos] = sum % 10;
result[ipos+1] += sum/10;
}
}
}

int BigNumCompare(char numStr1[], char numStr2[])
{
// ipos指向高位
int ipos1 = GetValidBits(numStr1, 11);
int ipos2 = GetValidBits(numStr2, 11);

// 如 numStr1 ： 00123有效位下标2
//   numStr2 :  01234有效位下标1
if (ipos1 > ipos2) {
return 1;
}
if (ipos1 < ipos2) {
return -1;
}

while (true) {
if ((ipos1 < 0) || (ipos2 < 0)) {
break;
}

if (numStr1[ipos1] > numStr2[ipos2]) {
return 1;
}
if (numStr1[ipos1] < numStr2[ipos2]) {
return -1;
}
--ipos1;
--ipos2;
}
return 0;
}

void StrSubtract(char ret[], char num[], int len)
{
int carry = 0;
int ipos = 0;
for (ipos=0; ipos<len; ++ipos) {
ret[ipos] -= num[ipos];
carry = ipos;
while (ret[carry] < 0) {
// 后位向前位借10
ret[carry+1] -= 1;
ret[carry] += 10;
++carry;
}
}
}

void CharToFloat(char numStr[], float result[])
{
// result[0]存储numStr与2147483648相除的余数
// result[1]存储numStr与2147483648相除的倍数

// 存储2147483648 与 1-9相乘的结果,  n位数和个位数相乘，结果最大为n+1位数，故numStrList的列大小为11个字节
char multiBuf[9][11] = {0};
Multi(1, multiBuf[0]);
Multi(2, multiBuf[1]);
Multi(3, multiBuf[2]);
Multi(4, multiBuf[3]);
Multi(5, multiBuf[4]);
Multi(6, multiBuf[5]);
Multi(7, multiBuf[6]);
Multi(8, multiBuf[7]);
Multi(9, multiBuf[8]);

int integerPos = 10;
// 整数部分
char *integerStr = new char[11];
memset(integerStr, 0, 11);
// 余数部分
char *remainderStr = new char[11];
int remainderLen = 11;
memset(remainderStr, 0, remainderLen);

char *bigNumStr = new char[LEN];

memset(bigNumStr, 0, LEN);
memcpy(bigNumStr, numStr, LEN);

int validPos = GetValidBits(bigNumStr, LEN);


if (validPos < 9) {
// bigNumStr小于2147483648，故不用相除， bigNumStr就为余数
int low = 0;
int remainderValidPos = GetValidBits(bigNumStr, LEN);
for (int i=remainderValidPos; i>=0; --i) {
low *= 10;
low += bigNumStr[i];
}
memcpy(&result[0], &low, sizeof(int));

int high = 0;
memcpy(&result[1], &high, sizeof(int));
return;
}

// 从bigNumStr取出前10位数
int curPos = validPos;
for (int i=remainderLen-2; i>=0; --i, --curPos) {
remainderStr[i] = bigNumStr[curPos];
}

while (true) {
if (curPos < 0 && BigNumCompare(remainderStr, multiBuf[0]) < 0) {
break;
}
// 取出的数小于2147483648，则商补0，再取一位
while (BigNumCompare(remainderStr, multiBuf[0]) < 0) {
integerStr[integerPos--] = 0;
// 左移，然后补一位

for (int i=remainderLen-1; i>0; --i) {
remainderStr[i] = remainderStr[i-1];
}
remainderStr[0] = bigNumStr[curPos];
curPos--;
}

// 获得最接近的一个multiBuf值
int ipos = 0;
for (ipos=0; ipos<9; ipos++) {
if (BigNumCompare(remainderStr, multiBuf[ipos]) < 0) {
break;
}
}

// i放入integer
integerStr[integerPos--] = ipos;
// 相减
StrSubtract(remainderStr, multiBuf[ipos-1], 11);

if (curPos >= 0) {
// 左移，然后补一位
for (int i=remainderLen-1; i>0; --i) {
remainderStr[i] = remainderStr[i-1];
}
remainderStr[0] = bigNumStr[curPos];
--curPos;
}
}

int low = 0;
int remainderValidPos = GetValidBits(remainderStr, 11);
for (int i=remainderValidPos; i>=0; --i) {
low *= 10;
low += remainderStr[i];
}
        // 不能用 赋值语句，否则精度会有丢失
memcpy(&result[0], &low, sizeof(int));

int high = 0;
for (int i=10; i>=integerPos+1; --i) {
high *= 10;
high += integerStr[i];
}
memcpy(&result[1], &high, sizeof(int));
}

void FloatToChar(float data[], char resultStr[])
{
// high为2147483648的倍数
int low = 0;
int high = 0;

        // 不能用 赋值语句，否则精度会有丢失
memcpy(&low, &data[0], sizeof(int));
memcpy(&high, &data[1], sizeof(int));

int addPos = 0;
while (high != 0) {
int num = high % 10;
int carry = 0;

// n位数和个位数相乘，结果最大为n+1位数，故middleNum大小为11个字节
char middleNum[11] = {0};

// high其中的一位和SIGN_NUM 相乘
int ipos = 0;
for (ipos=0; ipos<10; ++ipos) {
// 把字符的数字 转换成 相应的int型
int num1 = SIGN_NUM[ipos] - '0';
int multi = num * num1;

middleNum[ipos] = multi % 10 + carry;
carry = multi / 10;
}
if (carry != 0) {
middleNum[ipos] += carry;
}
// 处理所有的进位
for (ipos = 0; ipos < 10; ++ipos) {
if (middleNum[ipos] >= 10) {
int sum = middleNum[ipos];
middleNum[ipos] = sum % 10;
middleNum[ipos+1] += sum/10;
}
}

// middleNum 和 resultStr 错位相加
int iadd = 0;
int carryAdd = 0;
for (iadd=0; iadd < sizeof(middleNum); ++iadd) {
int sum = resultStr[iadd+addPos] + middleNum[iadd];
resultStr[iadd+addPos] = sum % 10 + carryAdd;
carryAdd = sum / 10;
}
if (carryAdd != 0) {
resultStr[iadd+addPos] += carryAdd;
}
// 处理所有的进位
for (iadd = 0; iadd < LEN; ++iadd) {
if (resultStr[iadd] >= 10) {
int sum = resultStr[iadd];
resultStr[iadd] = sum % 10;
resultStr[iadd+1] += sum/10;
}
}

high /= 10;
++addPos;
}

// 把low转化成字符串
int ipos = 0;
char middleNum[11] = {0};
while(low != 0) {
middleNum[ipos] = low % 10;
low /= 10;
ipos ++;
}

// resultStr 和 low相加
int iadd = 0;
int carryAdd = 0;
for (iadd=0; iadd < sizeof(middleNum); ++iadd) {
int sum = resultStr[iadd] + middleNum[iadd];
resultStr[iadd] = sum % 10 + carryAdd;
carryAdd = sum / 10;
}
if (carryAdd != 0) {
resultStr[iadd] += carryAdd;
}
// 处理所有的进位
for (iadd = 0; iadd < LEN; ++iadd) {
if (resultStr[iadd] >= 10) {
int sum = resultStr[iadd];
resultStr[iadd] = sum % 10;
resultStr[iadd+1] += sum/10;
}
}
}

void GetCount(int Num ,float pOutput[])
{
// float占4个字节，有符号 表示数的范围2^31 = 正负2147483648
// pOutput[0]存储大数与2147483648相除的余数
// pOutput[1]存储大数与2147483648相除的倍数

char *multi = new char[LEN];
char *sum   = new char[LEN];
char *total = new char[LEN];
memset(total, 0, LEN);

if (Num > 20) {
printf("输入数字不能大于20......");
getchar();
return;
}

for (int i=1; i <= Num; ++i) {
memset(multi, 0, LEN);
memset(sum, 0, LEN);

Factorial(i, multi);
Add(total, multi, sum);
memcpy(total, sum, LEN);
}

// 上面已经完成了计算, 接下来把total存储到pOutput中
CharToFloat(total, pOutput);

delete [] total;
delete [] sum;
delete [] multi;
}

void Printf(char bigData[], int len)
{
int ipos = GetValidBits(bigData, LEN);
for (ipos; ipos >= 0; --ipos) {
printf("%c", bigData[ipos] + '0');
}
}

int main(void)
{
float  pNumber[2] = {0};
int Number = 20;
GetCount(Number ,pNumber);

char bigData[LEN] = {0};
FloatToChar(pNumber, bigData);
Printf(bigData, LEN);

getchar();
return 0;
}