OJ-NOI-1.6-12 计算2的N次方 题解

题目

12:计算2的N次方

总时间限制: 1000ms 内存限制: 65536kB

描述

任意给定一个正整数N(N<=100)，计算2的N次方的值。

输入

输入一个正整数N。

输出

输出2的N次方的值。

样例输入

5

样例输出

32

提示

高精度计算

分析

题目结果限制为$2^{100} ≈ 1.26765 × 10^{30}$，很明显即使使用unsigned long long数据类型也无法表示这么大的数。
我们可以将结果进行拆分，存储至数组，最后遍历数组即可。
因此我们可以将每位上的数存储到数组中，每乘以一次2，就对数组上每一个元素进行进位处理。
则函数原型(C++版)为：

void multiply(int num[],int &len){    //len为当前所表达的数的位数
    int bit = 0;    //bit表示要进位时所加的数
    for(int i=0;i<len;i++){
        int tmp = num[i] * 2 + bit;
        num[i] = tmp % 10;    //当前位数取个位存储
        bit = tmp/10;    //将要进位的数存储至bit中
    }
    if(bit>0){
        num[len] += bit;    //如果最后一次循环bit大于0，则最高位前加上bit
        len++;    //位数加1
    }
}

在这个函数中，len表示这个数现在的位数，然后对数组每个数乘以2，取个位，将进位时所加的数存储到bit中，在下一位数乘以2后加上bit，以此类推。
在最后一个循环后，如果进位数bit大于0，就在最高位前加上要进的位，并len自增。
在main函数中只需根据输入确定循环次数调用此函数，最后从后往前遍历数组。

完整代码

C++版本：

#include <iostream>
using namespace std;

int arr[100];

void multiply(int num[],int &len){
    int bit = 0;
    for(int i=0;i<len;i++){
        int tmp = num[i] * 2 + bit;
        num[i] = tmp % 10;
        bit = tmp/10;
    }
    if(bit>0){
        num[len] += bit;
        len++;
    }
}

int main()
{
    int n;
    cin>>n;
    arr[0] = 1;
    int len = 1;
    for(int i=0;i<n;i++){
        multiply(arr,len);
    }
    for(int i=len-1;i>=0;i--) cout<<arr[i];
    return 0;
}

C版本：

#include <stdio.h>

int arr[100];

void multiply(int num[],int *len){
    int bit = 0;
    for(int i=0;i<*len;i++){
        int tmp = num[i] * 2 + bit;
        num[i] = tmp % 10;
        bit = tmp/10;
    }
    if(bit>0){
        num[*len] += bit;
        (*len)++;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    arr[0] = 1;
    int len = 1;
    for(int i=0;i<n;i++){
        multiply(arr,&len);
    }
    for(int i=len-1;i>=0;i--) printf("%d",arr[i]);
    return 0;
}

思考与拓展

理论上使用这种方法可以计算2的N次方（N为数组容量所能接受的最大整数），但时间复杂度为$O(n^2)$。
也可以进行拓展计算其他数的N次方，但需要注意进位的逻辑。