迅雷招聘题：2009的2009次方，所得数各位数字求和，结果继续求和，直到剩下一位数字，需要几次求和运算？？

2009的2009次方，所得数各位数字求和，结果继续求和，直到剩下一位数字，需要几次求和运算？？ 收藏
迅雷2010招聘海报上的题目.

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


const int N = 7000;

void smooth(vector<int>& vr){
int i = vr.size();
for (int m = i-1;m>0;m--)
{
  if(vr[m]>=10){
   vr[m-1] += vr[m]/10;
   vr[m] = vr[m]%10;
  }
}
}

void doplus(vector<int>vr1,vector<int>&vr2,int i){
vector<int>::iterator it;
int n =vr1.size();
for (int m =n-1;m>=0;m--)
{
  vr2[n--]= vr1[m] * i;//从最后一位
}
smooth(vr2);
}

void add(vector<int>& vr1,vector<int>& vr2,vector<int>& vr3){
int i = vr1.size();

for (int m=i-1;m>=0;m--)
  vr3[m]=vr1[m]; //vr3后3位为0
int n= vr3.size()-1;
int p =vr2.size()-1;
for (;p>=0;p--)
{
  vr3[n--] +=vr2[p];
}

smooth(vr3);
}

void update(vector<int>&vr1,vector<int>& vr2){
int i = vr2.size();
int a=N-1;
for (int m=i-1;m>=0;m--)
{
  vr1[a--] = vr2[m];
}

}
void plus2009(vector<int>& vector1){

vector<int>::iterator it;
int i =0;
for(it = vector1.begin();*it == 0 && it !=vector1.end();++it)
  i++;

int bit = N - i;


  vector<int>vector2(bit+1);//赋值
  vector<int>vector3(bit+1);//赋值
  vector<int>vector4(bit);//vector1有效数字 的副本

  vector<int>::iterator it2;
  for (it2 =vector4.begin();it!=vector1.end();++it2,++it)
  {
  *it2 = *it;
  }

  doplus(vector4,vector2,2);// ×2 放入新数组
   doplus(vector4,vector3,9);//X9放入新数组

   int m= vector2.size();
   vector<int>vr3(m+3);

   add(vector2,vector3,vr3);

   update(vector1,vr3);//赋值到原数组

}

int main(){
vector<int>vector1(N);
vector1[N-1]=9;
vector1[N-2]=0;
vector1[N-3]=0;
vector1[N-4]=2;

cout<<"2009的"<<"2009次方: "<<endl;

for(int i = 1;i<=2008;i++) //2009次方
plus2009(vector1);


  vector<int>::iterator it;
bool z=0;
int number =0;


int sum = 0;//计算各个位数之和
int tamp=0;//统计数字玩，与题目无关

vector<int>vectornumber(10);//统计数字玩，与题目无关

for (it = vector1.begin();it!=vector1.end();++it){
  if(*it !=0)
    z =1;

  if(z){
   number++;
   cout<<*it;
      tamp = *it;
   vectornumber[tamp]++;
   sum += *it;
  }
}
cout<<endl;
cout<<"这个数的位数为 : "<<number;
cout<<"各个数字累加为: "<<sum<<endl;

int step = 1;//已经加了一步
while(sum > 10){
  int  sum2=0;
  while(sum != 0){
   sum2 += sum%10;
   sum = sum/10;
  }
  sum = sum2;
  step++;
}

cout<<"共需要加 "<<step<<"步"<<endl;
cout<<"最后数字为"<<sum<<endl;

vector<int>::iterator itnum;//统计数字玩，与题目无关
int fig=0;//统计数字玩，与题目无关
for (itnum = vectornumber.begin();itnum!=vectornumber.end();++itnum)
{
  cout<<fig++<<" :"<<*itnum<<endl;
}

getchar();
}

代码写的丑，本来想再整理下，又有其他事情就放下啦，将就吧 。其实把数字颠倒存储代码写的会更简单些，更好看些。以后慢慢修改吧 其实还可以提炼成更通用的代码 ，不仅仅是2009次方，还可以是任意次方，或者就是任意大的数相乘。既然有任意大数相乘算法了，我也就更懒得修改啦。

本来以为会有数学规律的，不需要暴力解答。但是我运行出来结果发现，竟然不符合我使用数学方法的归纳猜想。郁闷。数学解法我就没有继续探究啦。

2009的2009次方是个有着6636位数的数字，这些数字加起来和为30119，30119 再加为14，再加为5.

那么答案为3次



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/houxudongdongxu/archive/2009/10/15/4676646.aspx