ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 关于大数阶乘

关于大数阶乘

原创 Linux操作系统 作者:xuhuai1 时间:2009-05-19 21:07:45 0 删除 编辑

// bigNumMultiplication.cpp : 定义控制台应用程序的入口点。
//
#pragma once;
#include "stdafx.h"
#include
#include
using namespace std;

class CBigNum
{
public:
 CBigNum(){}
 CBigNum(vector b):m_vData(b){}
 CBigNum(size_t nValu)
 {
  /*
   * 得到个位
   */
  size_t nGeWei = nValu % 10;
  m_vData.push_back(nGeWei);
  size_t nShanwei = (nValu-nGeWei)/10;
  while (nShanwei >= 10)
  {
   nGeWei = nShanwei%10;
   m_vData.push_back(nGeWei);
   nShanwei = (nShanwei-nGeWei)/10;
  }
  m_vData.push_back(nShanwei);
 }
private:
 vector m_vData;
public:
 /*
  * 重载减号
  */
 friend CBigNum operator-(CBigNum &obj1,CBigNum &obj2)
 {
  
  if(obj2.m_vData.size() > obj1.m_vData.size())
  {
   return obj2 - obj1;
  }
  CBigNum bj = obj1;
  vector::iterator it1 = obj.m_vData.begin();
  vector::iterator it2 = obj2.m_vData.begin();
  while (it1!=obj.m_vData.end() && it2 != obj2.m_vData.end())
  {
   calculateDecrease(it1,it2,obj.m_vData.end(),obj2.m_vData.end());
   it1++;
   it2++;
  }
  return obj;
 }
 friend ostream &operator<<(ostream &os,const CBigNum &obj)
 {
  vector::const_reverse_iterator it = obj.m_vData.rbegin();
  /*
   * 去掉末尾多的零
   */
  while (*it == 0)
  {
   it++;
  }
  while (it !=obj.m_vData.rend())
  {
   os<<*it;
   it++;
  }
  return os;
 }
 /*
  * 定义为friend 则需要两个参数
  */
 friend CBigNum operator *(CBigNum &obj1,CBigNum &obj2)
 {
  
  vector vTmp1 = obj1.m_vData;
  vector vTmp2  = obj2.m_vData;
  vector vTmp(vTmp1.size()+vTmp2.size(),0);
  for (size_t st1=0;st1  {
   for (size_t st2=0; st2 < vTmp2.size();++st2)
   {
    vTmp[st1+st2] += vTmp1[st1]*vTmp2[st2];
   }
  }
  calculateMultiplication(vTmp.begin(),vTmp.end());
  return CBigNum(vTmp);
 }
private:
 /*
  * multiplication operator
  */
 static void calculateMultiplication(vector::iterator itBeg,vector::iterator itEnd)
 {
  if (itBeg == itEnd)
  {
   return;
  }
  size_t nTmp=*itBeg;
  if (nTmp >= 10)
  {
   size_t nTmp1=nTmp % 10;
   *(itBeg++) =nTmp1;
   *itBeg += (nTmp-nTmp1)/10;
  }
  else
  {
   itBeg++;
  }
  calculateMultiplication(itBeg,itEnd);
 }
 /*
  * decrease operator
  */
 static void calculateDecrease(vector::iterator &item1,vector::iterator &item2,
          vector::iterator &item1end,vector::iterator &item2end)
 {
   if (*item1<*item2)
   {
    borrowOne(item1,item1end);
   }
   *item1=*item1 - *item2;
 }
 /*
  * 借一作十
  */
 static void borrowOne(vector::iterator itemBeg,vector::iterator itemEnd)
 {
  /*
   * 不能借下
   */
  while (itemBeg == itemEnd)
  {
   return;
  }
  if (*(itemBeg+1)==0)
  {
   borrowOne(itemBeg+1,itemEnd);
  }
  *itemBeg += 10;
  *(itemBeg+1) -= 1;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 //cout<<"hello";
 vector v1;
 //v1.push_back(7);
 v1.push_back(1);
 v1.push_back(1);
 v1.push_back(1);
 v1.push_back(1);
 v1.push_back(1);
 vector v2;
 v2.push_back(1);
 v2.push_back(1);
 v2.push_back(1);
 v2.push_back(1);
  v2.push_back(1);
 //v2.push_back(5);
 //CBigNum b1(v1);
 //CBigNum b2=b1;
 //cout<

 CBigNum big(104);
 cout< CBigNum one(5);
 cout< 
 /*for (CBigNum maxV(4294967295);maxV != 0;maxV-CBigNum(1))
 {

 }*/
 return 0;
}

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/12560256/viewspace-600495/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 封装ado
下一篇: 双缓冲
请登录后发表评论 登录
全部评论

注册时间:2008-09-03

  • 博文量
    13
  • 访问量
    26610