POJ做的很好,本题就是要求一个无限位大的指数乘法结果。
要求基础:无限大数位相乘
额外要求:处理特殊情况的能力 -- 关键是考这个能力了。
所以本题的用例特别重要,再聪明的人也会疏忽某些用例的。
本题对程序健壮性的考查到达了变态级别了。
某人贴出的测试用例数据地址:http://poj.org/showmessage?message_id=76017
有了这些用例,几下调试就过了。
我关键漏了的用例:
000.10 1
000000 1
000.00 1
.00000 0
000010 1
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool standardizeNumNoDot(string &s)
{
while (!s.empty() && '0' == s[0]) s.erase(s.begin());
if (s.empty()) s = "0";//防止n==1的时候,要输出0
bool notDot = true;
for (unsigned i = 0; i < s.size() && notDot; i++)
{
if ('.' == s[i]) notDot = false;
}
if (notDot) return true;
while (!s.empty() && '0' == s[s.size()-1]) s.erase(s.end()-1);
if (!s.empty() && '.' == s[s.size()-1]) s.erase(s.end()-1);
if ( s.empty() ) s = "0";
return false;
}
int handleDecimalPoint(string &s)
{
if (standardizeNumNoDot(s)) return 0;
int fraction = 0;
int j = 0;
for (unsigned i = 0; i < s.size() ; i++)
{
if (fraction > 0) fraction++;
if (s[i] != '.') s[j++] = s[i];
else fraction++;
}
s.erase(s.end()-1);
return fraction - 1;
}
string mulStr(string a, string b)
{
if ("0" == a || "0" == b) return "0";
int ap = handleDecimalPoint(a);
int bp = handleDecimalPoint(b);
string ans(a.size()+b.size(), '0');
for (int i = a.size() - 1; i >= 0 ; i--)
{
int carry = 0;
int an = a[i] - '0';
for (int j = b.size() - 1; j >= 0 ; j--)
{
int bn = b[j] - '0';
int sum = an * bn + carry + ans[i+j+1] - '0';
carry = sum / 10;
ans[i+j+1] = sum % 10 + '0';
}
if (carry) ans[i] += carry;
}
if (ap > 0 || bp > 0) ans.insert(ans.end() - ap - bp, '.');
standardizeNumNoDot(ans);
return ans;
}
string sPow(string s, int n)
{
if (s.empty() || "0" == s) return "0";//为了程序的健壮性,一定要加上
if (0 == n) return "1";
if (1 == n) return s;
string divideStr = sPow(s, n/2);
divideStr = mulStr(divideStr, divideStr);
if (n % 2) divideStr = mulStr(divideStr, s);
return divideStr;
}
void Exponentiation()
{
string s;
int n;
while(cin>>s>>n)
{
standardizeNumNoDot(s);//当n==1的时候
cout<<sPow(s, n)<<endl;
}
}
int main()
{
Exponentiation();
return 0;
}
本算法用时0MS,哈哈.
分享到:
相关推荐
poj 1001 Exponentiation用字符串操作的
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
如题所示,亲测可用。求高精度幂,不会的同学可以参考下,会做的同学可以给挑挑毛病!大家以代码会友!
poj 1001答案
用java的biginteger实现的poj1001,比较简单的方法
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
简单地poj1001代码,是典型的利用数组输出结果的方法,关键的是测试数据。
acm poj题目分类介绍 包含一个题解文档 acm poj题目分类介绍 包含一个题解文档
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems....
poj1001源码,c语言版,通过ac,包含注释,容易懂
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
北大POJ1001-Precision power 解题报告+AC代码
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
北京大学ACM详解poj1001, 内容很充实。
POJ题解及题目分类,共150道左右。C/C++
POJ部分题解
acm 1001 到1009代码,已通过验证
Description 对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如,对国债进行计算就是属于这类问题。 现在要你解决的问题是:对一个实数R( 0.0 ),要求写程序精确计算 R 的 n 次方(Rn),其中n 是...
Poj1155 题解 , 文档 , 资料