一道阶乘的笔试题答案:阶乘n*(n-1)*(n-2)*...*2*1

前几天面试遇到的一个笔试题,如下：

给一个int型参数n，求其阶乘结果。result=n*(n-1)*(n-2)*...*2*1;

//以下给出了unsigned int型正数n的阶乘代码。

//负数n只需在函数外做个判断<0，将结果置为负值就OK。

//c++ code
//输入参数n
//输出参数result，由Uint数组拼成,从地位到高位依次从[0][1][2]...[ret-1]

//返回值ret表示result由多少个unsigned int型数据拼成

#include <vector>
int func_xx(unsigned int n, std::vector<unsignedint> &result)
{
const int length_of_int =sizeof(n)*8;//测试本机的int型数据有多少bit，char为8个bit
//int ret_result_length_in_int = 0;//返回值由Uint型数据拼成
result.clear();
if(n==0)
{
return 0;
}

result.push_back(1);
if(n==1)
{
return 1;
}

const long long max_Uint = ((longlong)1<<length_of_int) - 1;
long long temp = 1;
for(int i=n; i>1; i--)
{
if((temp=result[0]*((longlong)i)) <= max_Uint&& result.size()==1)
{
result[0] =(unsigned int)temp;
continue;
}

int result_size =result.size();//避免与新进位的最高位int相乘

long long tt=0;//中间进位值
std::vector<unsignedint>::iterator iter_begin = result.begin();
std::vector<unsignedint>::iterator iter =iter_begin;

for(intj=0;j++<result_size&& iter!=result.end();iter++)
{
temp = (longlong) (*iter);
temp = (longlong)i*temp + tt;//进位值只做加法

if(temp<= max_Uint)
{
*iter= temp;
continue;
}
else//if(temp > max_Uint)
{
longlong high =temp>>length_of_int;
longlong low = temp&max_Uint;

*iter= low;
if(iter+1== result.end())
{
result.push_back(high);//扩展 结果的最高位数
//iter= & result[result.size() - 1];
break;
}
else
{
tt= high;//记住进位值
}
}

}

}

return result.size();

}

int main(int argc, char* argv[])
{
std::vector<unsignedint> result;
int n=20;//求16的阶乘，可以任意给定参数n

int size_in_int = func_xx(n,result);

if(size_in_int==1 )
{
printf("(%d)*(%d-1)...*(2)*1 ==%d;n", n,n,result[0]);
}
else if(size_in_int==2)
{
printf("(%d)*(%d-1)...*(2)*1 ==%lld;n", n,n,((longlong)result[1]<<32)+(longlong)result[0]);
}
else
{
printf("n(%d)*(%d-1)...*(2)*1== ", n,n);
for(inti=size_in_int;i>0;--i)
{
if(i!=size_in_int)
{
printf("+(%d<<%d)",result[i-1],(i-1)*32);
}
else
{
printf("(%d<<%d)",result[i-1],(i-1)*32);
}
}
printf(";n");
}

return n;
}

//原题坑爹的表达式n!=n*（n-1)*(n-2)。。。*3*2

(谁一把岁数还记得初中数学：阶乘使用n!表示的。编程题，我只知道"!="表示不等于)

百度百科的阶乘

爱华网本文地址 » http://www.aihuau.com/a/25101014/232898.html