2012-02-18

大数运算经典:棋盘上的米粒。

有一个8*8共64格的棋盘，要求第一个格放1粒米，第二个格放2粒米，第三个放4粒，依次加倍，问放满棋盘共有多少粒米。

很显然，这是个很大的数，用long型也无法存放。所以只能通过模拟加法和乘法来达到计算的目的。

include

using namespace std;

//模拟乘2运算
void multi2(short a[])
{
short carry = 0; //进位
for(short i=999;i>=0;i–)
{
short tmp =a[i]*2;
a[i]=tmp%10+carry; //当前位结果
carry=tmp/10; //进位

}

return;
}

//模拟加运算

void plus(short sum[],short add[])
{
short carry = 0;
for(short i=999;i>=0;i–)
{
short tmp = sum[i]+add[i];
sum[i]=tmp%10 + carry;
carry=tmp/10;

}

return;

}

int main()
{
short sum[1000]={0};
short add[1000]={0};

add[999]=1;

for(short i=0;i<64;i++)
{

plus(sum,add);

multi2(add);
}

short k = 0; /结果中的0不打/
for(short j=0;j<1000;j++)
{
if(sum[j]!=0)
{
k=j;
break;
}
}

cout<<”result:”<<endl;
for(short i=k;i<1000;i++)
cout<<sum[i];

cout<<endl;
getchar();
return 0;

}