天下网吧 >> 网吧天地 >> 网吧技术 >> 网吧软件 >> 正文

大整数阶乘的算法思路

2010-2-5不详佚名
听说中科院软件所09年复试的笔试题就是这个,打算自己写写。

  这里的大整数指大于500以上的整数,当然更大也可以。由于整数阶乘递增的很快,远大于指数式递增,对于小整数,比如20,30左右,可以直接使用比如递归的方式进行,这很基本。

  但是当整数较大时,阶乘的结果很大,远非一个int或者long就能存的下的,比如1000的阶乘结果有上千位。

  所以大整数阶乘设计的关键点就是存储大整数,当选择了存储大整数,那么整数的乘法运算也不能再依靠*了,所以还要重新设计大整数的惩罚运算。

  上面是我的设计思路。网上找过相关的文章,有高手以4行代码完成了该算法,确实佩服!当然这涉及了算法的优化,不管那么多了,这里要的就是以尽量清晰地思路快速设计该算法,这是使用了STL标准库的容器。

  下面是我的算法代码,直接贴这里了,注意看相关的注释:

  #include <iostream>

  #include <vector>

  using namespace std;

  // 传入整数:int,和整数-1的阶乘结果,进行相乘的结果

  // 结构依然存储到容器中

  void Calc(int num,vector<int> &calcresult)

  {

  vector<int> tempnum;

  vector<int> rest;

  // 将传入的int拆分之后保存到容器中

  do

  {

  tempnum.push_back(num % 10);

  num = num / 10;

  } while (num);

  // 将分拆之后的num进行乘法计算

  unsigned int i = 0,j = 0;

  for(i = 0;i < tempnum.size();++i)

  {

  int carry = 0;// 存储每位计算时来自低位的进位

  for(j = 0;j < calcresult.size();++j)

  {

  int bit1 = 0,bit2 = 0,res = 0;

  bit1 = calcresult[j];

  bit2 = tempnum[i];

  res = bit1 * bit2;

  // 保存当前位

  if((i+j)<rest.size())

  {

  // 临时结果中有对应位存在,则直接更新

  rest[i+j] += (res + carry) % 10;

  }

  else

  {

  // 没有对应位则需要添加

  rest.push_back((res+carry)%10);

  }

  // 有进位,则更新进位

  carry = (res + carry) / 10;

  }

  // 如果计算之后还有最高位的进位,那么则直接添加进去

  if(carry)

  {

  // 保存当前位

  if((i+j)<rest.size())

  {

  // 临时结果中有对应位存在,则直接更新

  rest[i+j] += carry;

  }

  else

  {

  // 没有对应位则需要添加

  rest.push_back(carry);

  }

  }

  }       // 上述计算之后,会出现有些位的数字超过了10,那是因为在处理每一位运算结果之后

  // 相加时地位向高位可能存在进位,上面没有考虑,所以需要进行调整

  for(i = 0;i < rest.size();++i)

  {

  if(rest[i] > 9)

  {

  if((i+1) != rest.size())

  {

  // 高位存在,则直接更新高位

  rest[i+1] += rest[i] / 10;

  rest[i] = rest[i] % 10;

  }

  else

  {

  // 高位不存在,则需要插入

  rest.push_back(rest[i] / 10);

  rest[i] = rest[i] % 10;

  }

  }

  }

  // 将计算结果存储到原来的容器中

  calcresult.clear();

  for(i = 0;i < rest.size();++i)

  {

  calcresult.push_back(rest[i]);

  }

  }

  int main()

  {

  int num = 0;

  vector<int> calcresult;

  // 将初值1赋进去

  calcresult.push_back(1);

  // 获取欲求阶乘的整数

  cout<<"输入欲求阶乘的整数:"<<endl;

  cin>>num;

  for(int i = 0;i < num;++i)

  {

  Calc(i+1,calcresult);

  }

  // 输出计算结果

  cout<<num<<"的阶乘:"<<endl;

  for(unsigned int i = calcresult.size();i > 0 ;--i)

  {

  cout<<calcresult[i-1];

  }

  cout<<endl;

  return 0;

  }

本文来源:不详 作者:佚名

声明
声明:本站所发表的文章、评论及图片仅代表作者本人观点,与本站立场无关。文章是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益,请作者持权属证明与本网联系,我们将及时更正、删除,谢谢。 Email:support@txwb.com,系统开号,技术支持,服务联系微信:_WX_1_本站所有有注明来源为天下网吧或天下网吧论坛的原创作品,各位转载时请注明来源链接!
天下网吧·网吧天下
  • 本周热门
  • 本月热门
  • 阅读排行