c++任意长度高精度幂计算

偶然看到了POJ 1001问题,想起以前python的一个任意长度大数相乘的帖子(在这里),c++的解法也类似,都是用字符串来储存位数即可.此题的一个有意思的地方是对于输入字符串的处理,要考虑各种情况,例如: 0.00(0),10.0(100),0012.00(12),1.0100(1.01),001.0100100(1.01001)等等.第一次做题时候对于这个问题考虑欠周,弄了好几次wrong answer.代码如下:


其中__MYDEBUG__是中间计算步骤的显示开关(0或者1)

// 高精度幂计算,POJ1001, 地址: http://poj.org/problem?id=1001
// 任意长度字符串,结果输出: 小数点前后均无无意义0,如果整数部分为0,输出小数点+小数部分
// 也可以用来计算任意长度整数/小数乘法,直接调用 string stringMul(string a, string b) 即可

#include <iostream>
#include <string>
using namespace std;

// 开关,是否显示竖式乘法运算步骤
#define __MYDEBUG__ 1

// 整理字符串,如果有小数点,去除右边多余0,如果没有,去除左边多余0
// 返回小数位数*pos
string cleanUp(string s,int *pos)
{
 string result = s;

 size_t lpos,rpos,ppos;
 ppos = s.find(".");
 lpos = s.find_first_not_of("0");
 rpos = s.find_last_not_of("0");

 // 无小数点
 if (ppos==string::npos)
 {
  *pos = 0;
  if (lpos==string::npos) result = "0";
  else result = s.substr(lpos);
 }
 else
 {
  if (rpos==ppos) // 最右非0位是小数点,无小数位
  {
   *pos = 0;
   if (lpos==ppos) // 如果最左非0也是小数点,是0.0
   {
    result = "0";
   }
   else // 否则是01.000类
   {
    result = s.substr(lpos,ppos-lpos);
   }
  }
  else // 有小数位
  {
   *pos = rpos-ppos;
   if (lpos==ppos) // 最左非0是小数点,截取小数点后部分继续判断最左非0位,0.0100类
   {
    result = s.substr(ppos+1,rpos-ppos);
    lpos = result.find_first_not_of("0");
    result = result.substr(lpos,rpos-lpos+1);
   }
   else // 否则直接拼接小数点左右部分,01.0100类
   {
    result = s.substr(lpos,ppos-lpos)+s.substr(ppos+1,rpos-ppos);
   }
  }
 }

 return result;
}

// 字符串表示的大数相乘
string stringMul(string a, string b)
{
 int lena = a.size();    // a长度
 int lenb = b.size();    // b长度
 int pos = 0;            // 错位数

 int curmul = 0,         // 当前计算结果
  carry = 0,          // 进位
  curnum = 0;         // 当前位数字. 关系: 当前计算结果=进位*10+当前位数字

 // 最终计算结果结果肯定小于2个字符串长度之和
 // 证明:长度为lena和lenb的2个数,最大可表示为10^lena-1和10^lenb-1
 // (10^lena-1)*(10^lenb-1) = 10^(lena+lenb)-10^lena-10^lenb+1 < 10^(lena+lenb),证毕.
 string result = "";
 result.insert(result.begin(),lena+lenb,'0');
 string tempresult = "";
 string current = "";

#if (__MYDEBUG__)
 int wid = 40;
 char fm[20];
 sprintf(fm,"%%%ds\n",wid);
 printf(fm,a.c_str());
 sprintf(fm,"* %%%ds\n",wid-2);
 printf(fm,b.c_str());
 printf("-----------------------------------------\n");
#endif

 for (int i=lenb-1;i>=0;i--)
 {
  current = "";   // 当前字符串
  carry = 0;      // 进位
  curnum = 0;     // 要添加的字符

  if ((int)(b[i]-'0')==0)
  {
#if (__MYDEBUG__)
   sprintf(fm,"%%%ds\n",wid-pos);
   printf(fm,"0");
#endif
   pos++;
   continue;
  }

  for (int j=lena-1;j>=0;j--)
  {
   curmul = (int)(b[i]-'0')*(int)(a[j]-'0')+carry;
   carry = curmul/10;
   curnum = curmul%10;
   current.insert(current.begin(),1,(char)(curnum+'0'));
  }

  // 处理最后进位
  while (carry>0)
  {
   current.insert(current.begin(),1,(char)(carry%10+'0'));
   carry /= 10;
  }

#if (__MYDEBUG__)
  sprintf(fm,"%%%ds\n",wid-pos);
  printf(fm,current.c_str());
#endif
  // 添加给当前结果
  if(result.empty())
  {
   result = current;
  }
  else    // 错位相加
  {
   tempresult = "";
   curmul = 0;
   carry = 0;
   curnum = 0;
   for (int i=(int)current.size()-1,j=(int)result.size()-1-pos;i>=0&&j>=0;i--,j--)
   {
    curmul = (int)(result[j]-'0')+(int)(current[i]-'0')+carry;
    carry = curmul/10;
    curnum = curmul%10;
    tempresult.insert(tempresult.begin(),1,(char)(curnum+'0'));
   }

   // 处理剩余的字符
   while (carry>0)
   {
    tempresult.insert(tempresult.begin(),1,(char)(carry%10+'0'));
    carry /= 10;
   }

   // 添加给结果
   result.replace((int)result.size()-(int)tempresult.size()-pos,(int)tempresult.size(),tempresult);
  }

  // 错位+1
  pos++;
 }

 // 清理结果
 int dummy = 0;
 result = cleanUp(result,&dummy);

#if (__MYDEBUG__)
 printf("-----------------------------------------\n");
 sprintf(fm,"%%%ds\n",wid);
 printf(fm,result.c_str());
#endif

 return result;
}

// 处理结果字符串,加上小数点,n是小数位数
string processResult(string s,int n)
{
 // 无小数,直接返回结果
 if (n==0) return s;

 string result = "";

 // 长度不足小数位,左边加点补0
 if (s.size()<n)
 {
  result = ".";
  result.append(n-(int)s.size(),'0');
  result += s;
 }
 else if (s.size()==n) //刚够小数位,直接加.
 {
  result = "."+s;
 }
 else // 否则在合适位置加点
 {
  result = s.substr(0,s.size()-n)+"."+s.substr(s.size()-n);
 }
 return result;
}

int main()
{
 string s;
 int n;
 string result;
 int pos = 0;
 while (cin>>s>>n)
 {
  pos = 0;

  s = cleanUp(s,&pos);

  result = s;

  for (int i=1;i<n;i++) { result = stringMul(result,s); }

  result = processResult(result,pos*n);

  cout << result.c_str() << endl;
 }
}