【題目鏈接】
ybt 1170：計算2的N次方
OpenJudge NOI 1.6 12:計算2的N次方
【題目考點】
1. 高精度
考察：高精乘低精
高精度計算講解
2. 快速冪
【解題思路】
先估算結果的位數。指數最大為100，求21002^{100}2100的位數。
已知：若正整數x的的位數為n，那么有：n=?lgx?+1n = \lfloor lgx \rfloor + 1n=?lgx?+1
21002^{100}2100的位數為?lg2100?+1=?100?lg2?+1≤?100?lg10?+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
)
{int r
= 1;while(b
> 0){if(b
% 2 == 1)r
*= a
;a
*= a
;b
/= 2;}return r
;
}
本題要求2n2^n2n，n≤100n\le 100n≤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)i
--;a
[0] = i
;
}
void Multiply(int a
[], int 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
;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
){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");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)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
[])
{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
[])
{int c
[N
] = {};numcpy(c
, a
);r
[0] = r
[1] = 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
;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
){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
){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;
}
總結
以上是生活随笔為你收集整理的信息学奥赛一本通 1170：计算2的N次方 | OpenJudge NOI 1.6 12:计算2的N次方的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
