博客

思考题1:

国际象棋是很久以前由一个印度人Shashi发明的，当他吧该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏，Shashi要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢？



思路：题目主要围绕的数大数展开的，应该单个2的63次方已经很大了

int的范围：  2147483648～2147483647 
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615

这里，你可能要说unsigned long long类型也挺大的嘛！不过笔者通过程序实现了下2^64还比unsigned long long的最大值大一个（虽然我们求的最大值是2^63次方但要求总和，势必不够放的）！这里笔者打算用int类型的数组去解决。

上全部的代码：

/*大数计算int类型的数组，次方*/
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
int Array1[500];//全局变量的数组初始化的时候第一个单元的值为1
//int Array2[500];
int Sum[500];
int Num=0;
void Add() {//将两个大数相加
    for (int i = 0; i < 500;i++) {
        Sum[i] += Array1[i];
    }
    for (int j = 0; j < 500; j++) {
        if (Sum[j] > 9) {//大于9就进位
            Sum[j + 1] += Sum[j] / 10;
            Sum[j] %= 10;//如果是10的话进上去后直接为0
        }
    }
    /*输出Array的值*/
    cout << "第"<<Num<<"个棋盘上的数目为："<< endl;
     int t = 0;
    for (int i = 499; i >= 0; i--) {
        if (Array1[i] != 0) {
            t = i;
            break;
        }
    }
    //cout << "t:" << t << endl;
    for (int i = t; i >= 0; i--) {
        cout << Array1[i];
    }
    cout << endl;
    /*输出最终总和Sum的结果*/
    cout <<"从第1棋盘到第"<<Num<<"棋盘的总数为：" << endl;
     t = 0;
    for (int i = 499; i >= 0; i--) {
        if (Sum[i] != 0) {
            t = i;
            break;
        }
    }
    //cout << "t:" << t << endl;
    for (int i = t; i >= 0; i--) {
        cout << Sum[i];
    }
    cout << endl;
    memset(Array1, 0, sizeof(Array1));
    Array1[0] = 1;
}
void SumFun(int n){//求第n个格子中的数目 
    for (int i = 0; i < n-1; i++) {//第一个for循环时次方的次数
        for (int j = 0; j < 500; j++) {
            Array1[j] *= 2;
        }
        for (int j = 0; j < 500; j++) {
            if (Array1[j]>9) {//大于9就进位
                Array1[j + 1] += Array1[j] / 10;
                Array1[j] %= 10;//如果是10的话进上去后直接为0
            }
        }
    }
}
int main(){
    memset(Sum, 0, sizeof(Sum));
    memset(Array1, 0, sizeof(Array1));
    Array1[0] = 1;
    for (int i = 1; i <=64;i++) {
        Num = i;
        SumFun(i);
        Add();
    }
    /*输出最终总和Sum的结果*/
    cout << "最后的结果为：" << endl;
    int t = 0;
    for (int i = 499; i >= 0; i--) {
        if (Sum[i] != 0) {
            t = i;
            break;//
        }
    }
    //cout << "t:" << t << endl;
    for (int i = t; i >= 0; i--) {
        cout << Sum[i];
    }
    cout << endl;


    return 0;
}

代码思路：就是先求出第i个格子的数目Array1数组去记录，通过Sum函数记录从第1个到第i个的总的数目。最后将Sum数组输出。

功能代码：求第i个格子的数目
void SumFun(int n){//求第n个格子中的数目 
memset(Array1, 0, sizeof(Array1));
    Array1[0] = 1;
    for (int i = 0; i < n-1; i++) {//第一个for循环时次方的次数
        for (int j = 0; j < 500; j++) {
            Array1[j] *= 2;
        }
        for (int j = 0; j < 500; j++) {
            if (Array1[j]>9) {//大于9就进位
                Array1[j + 1] += Array1[j] / 10;
                Array1[j] %= 10;//如果是10的话进上去后直接为0
            }
        }
    }
}

功能代码其实没那么复杂，主要是为了将它输出！！嘿嘿！