資訊學奧賽一本通 1170：計算2的N次方 | OpenJudge NOI 1.6 12:計算2的N次方

【題目連結】

ybt 1170：計算2的N次方

OpenJudge NOI 1.6 12:計算2的N次方

【題目考點】

1. 高精度

考察：高精乘低精

高精度計算講解

2. 快速幂

【解題思路】

先估算結果的位數。指數最大為100，求 2 100 2^{100} 2100的位數。

已知：若正整數x的的位數為n，那麼有： n = ⌊ l g x ⌋ + 1 n = \lfloor lgx \rfloor + 1 n=⌊lgx⌋+1

2 100 2^{100} 2100的位數為 ⌊ l g 2 100 ⌋ + 1 = ⌊ 100 ⋅ l g 2 ⌋ + 1 ≤ ⌊ 100 ⋅ l g 10 ⌋ + 1 = 101 \lfloor lg2^{100} \rfloor + 1 = \lfloor 100\cdot lg2 \rfloor + 1 \le \lfloor 100\cdot lg10 \rfloor + 1 = 101 ⌊lg2100⌋+1=⌊100⋅lg2⌋+1≤⌊100⋅lg10⌋+1=101

可知結果不會超過101位，數字數組長度可以設為105

解法1：累乘

由于每次乘的數字是2，那麼可以使用高精對低精乘法，盡量減少算法複雜度，高精乘低精累乘n次即可。

解法2：快速幂

低精度快速幂如下：

int Pow(int a, int b)//求a^b
{
	int r = 1;
	while(b > 0)
	{
		if(b % 2 == 1)
			r *= a;
		a *= a;
		b /= 2;
	}
	return r;
}
           

本題要求 2 n 2^n 2n， n ≤ 100 n\le 100 n≤100，n是個低精度數字。

即上述函數中的a、r替換為高精，b為低精。是以隻需要實作高精度計算中的高精乘高精。

【題解代碼】

解法1：累乘

• 使用數組與函數

#include <bits/stdc++.h>
using namespace std;
#define N 105
void setLen(int a[], int i)
{
    while(a[i] == 0 && i > 1)//去除多餘的0
        i--;
    a[0] = i;
}
void Multiply(int a[], int b)//a *= b 高精乘低精
{
    int c = 0, i;
    for(i = 1; i <= a[0]; ++i)
    {
        a[i] = a[i]*b + c;
        c = a[i] / 10;
        a[i] %= 10; 
    }
    while(c > 0)
    {
        a[i] = c % 10;
        c /= 10;
        i++;
    }
    setLen(a, i);
}
void toNum(char s[], int a[])
{
    a[0] = strlen(s);
    for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0] - i] - '0';
}
void showNum(int a[])
{
	for(int i = a[0];i >= 1;--i)
		cout << a[i];
	cout << endl;
}
int main()
{
    int a[N] = {1,1}, n;//高精度數字a初始化為1 
    cin >> n;
    for(int i = 1; i <= n; ++i)
        Multiply(a, 2);
    showNum(a);
    return 0;
}
           

• 使用高精度數字類

#include<bits/stdc++.h>
using namespace std;
#define N 105
struct HPN
{
   int a[N];
   HPN()
   {
       memset(a, 0, sizeof(a));
   }
   HPN(char s[])
   {
       memset(a, 0, sizeof(a));
       a[0] = strlen(s);
       for(int i = 1; i <= a[0]; ++i)
           a[i] = s[a[0] - i] - '0';
   }
   int& operator [] (int i)
   {
       return a[i];
   }
   void setLen(int i)//确定數字位數
   {
       while(a[i] == 0 && i > 1)
           i--;
       a[0] = i;
   }
   void operator *= (int b)//a *= b
   {
       int c = 0, i;
       for(i = 1; i <= a[0]; ++i)
       {
           a[i] = a[i]*b + c;
           c = a[i] / 10;
           a[i] %= 10; 
       }
       while(c > 0)
       {
           a[i] = c % 10;
           c /= 10;
           i++;
       }
       setLen(i); 
   }
   void show()
   {
       for(int i = a[0]; i >= 1; --i)
           cout << a[i];
   }
};
int main()
{
   int n;
   cin >> n;
   HPN a("1");//a初值為1 
   for(int i = 1; i <= n; ++i)
       a *= 2;
   a.show();
   return 0;
}
           

解法2：快速幂

• 使用數組與函數

#include <bits/stdc++.h>
using namespace std;
#define N 105
void setLen(int a[], int i)
{
    while(a[i] == 0 && i > 1)//去除多餘的0
        i--;
    a[0] = i;
}
void numcpy(int a[], int b[])
{
    for(int i = 0; i <= b[0]; ++i)
        a[i] = b[i];
}
void Multiply(int a[], int b[])//a *= b 高精乘高精
{
    int r[N] = {};
    for(int i = 1; i <= a[0]; ++i)
    {
        int c = 0;
        for(int j = 1; j <= b[0]; ++j)
        {
            r[i+j-1] += a[i]*b[j] + c;
            c = r[i+j-1] / 10;
            r[i+j-1] %= 10;
        }
        r[i+b[0]] += c;
    }
    setLen(r, a[0] + b[0]);
	numcpy(a, r);
}
void toNum(char s[], int a[])
{
    a[0] = strlen(s);
    for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0] - i] - '0';
}
void showNum(int a[])
{
	for(int i = a[0];i >= 1;--i)
		cout << a[i];
	cout << endl;
}
void fastPower(int a[], int b, int r[])//快速幂 r = a^b 傳入前r初始化為0 
{
	int c[N] = {};//c:變化的底數 
	numcpy(c, a);
	r[0] = r[1] = 1;//将r設為1
	while(b > 0)
	{
		if(b % 2 == 1)
			Multiply(r, c);
		Multiply(c, c);
		b /= 2;
	}
}
int main()
{
    int a[N] = {1,2}, r[N] = {}, n;//a:初值為2， r初值為空 
    cin >> n;
    fastPower(a, n, r);
    showNum(r);
    return 0;
}
           

• 使用高精度計算類

#include<bits/stdc++.h>
using namespace std;
#define N 105
struct HPN
{
    int a[N];
    HPN()
    {
        memset(a, 0, sizeof(a));
    }
    HPN(char s[])
    {
        memset(a, 0, sizeof(a));
        a[0] = strlen(s);
        for(int i = 1; i <= a[0]; ++i)
            a[i] = s[a[0] - i] - '0';
    }
    int& operator [] (int i)
    {
        return a[i];
    }
    void setLen(int i)//确定數字位數
    {
        while(a[i] == 0 && i > 1)
            i--;
        a[0] = i;
    }
    HPN operator * (HPN b)//r = a * b
    {
        HPN r;
	    for(int i = 1; i <= a[0]; ++i)
	    {
	        int c = 0;
	        for(int j = 1; j <= b[0]; ++j)
	        {
	            r[i+j-1] += a[i]*b[j] + c;
	            c = r[i+j-1] / 10;
	            r[i+j-1] %= 10;
	        }
	        r[i+b[0]] += c;
	    }
	    r.setLen(a[0] + b[0]);
		return r;
    }
    HPN operator ^ (int b)//快速幂 求a^b 
    {
    	HPN c = *this, r("1"); 
		while(b > 0)
		{
			if(b % 2 == 1)
				r = r * c;
			c = c * c;
			b /= 2;
		}
		return r;
	}
    void show()
    {
        for(int i = a[0]; i >= 1; --i)
            cout << a[i];
    }
};

int main()
{
    int n;
    cin >> n;
    HPN a("2"), r;
    r = a ^ n;//快速幂求乘方 
    r.show();
    return 0;
}