前幾天面試遇到的一個筆試題,如下：

給一個int型參數(shù)n，求其階乘結(jié)果。result=n*(n-1)*(n-2)*...*2*1;

//以下給出了unsigned int型正數(shù)n的階乘代碼。

//負數(shù)n只需在函數(shù)外做個判斷<0，將結(jié)果置為負值就OK。

//c++ code
//輸入?yún)?shù)n
//輸出參數(shù)result，由Uint數(shù)組拼成,從地位到高位依次從[0][1][2]...[ret-1]

//返回值ret表示result由多少個unsigned int型數(shù)據(jù)拼成

#include <vector>
int func_xx(unsigned int n, std::vector<unsignedint> &result)
{
const int length_of_int =sizeof(n)*8;//測試本機的int型數(shù)據(jù)有多少bit，char為8個bit
//int ret_result_length_in_int = 0;//返回值由Uint型數(shù)據(jù)拼成
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);//擴展 結(jié)果的最高位數(shù)
//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的階乘，可以任意給定參數(shù)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

(誰一把歲數(shù)還記得初中數(shù)學(xué)：階乘使用n!表示的。編程題，我只知道"!="表示不等于)

百度百科的階乘

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101014/232898.html