Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的老超时 麻烦那位高手帮忙解决一下 小弟感激不尽!#include<iostream> #include<string> using namespace std; int M,number; // 计录小数点的位数 int DotLocation(string str) // 计算小数点位数 { int lgth = str.length()-1; int location = str.find("."); // 判断是否有小数点 if(location!=-1) { if(str.at(lgth) == '0') // 有小数点且尾部数字为零 { int i = lgth; while(i>=0) { if(str.at(i)!='0') // 从后往前第一个不为零的字符停止 break; i--; } return i - location; // 返回小数点位数 } else // 有小数点但尾部不为零 { return lgth - location; } } else // 字符串中没有小数点 return -1; } void DealArray(int *a,int len) // 对整形数组的处理 { int i; for(i = len-1;i>0;i--) { if(a[i]>=10) { a[i-1] = a[i-1] + a[i]/10; a[i] = a[i]%10; } } } void OutPut(string str,int n) // 添加小数点输出函数 { int i; number = n*number; // 小数点有多少位 int k = str.length(); if(number > 0) { if(number >= k) { str.insert(0,"."); if(number > k) for(i=1;i<=number - k;i++) str.insert(i,"0"); if(str.at(str.length()-1)=='0') { i = str.length() - 1; while(i>=0) { i--; if(str.at(i)!='0') break; } if(str.at(i) == '.') str.substr(0,i); else str.substr(0,i+1); cout<<str<<endl; } else { cout<<str<<endl; } } else { str.insert(k-number,"."); if(str.at(str.length()-1)=='0') { i = str.length()-1; while(i>=0) { i--; if(str.at(i)!='0') break; } if(str.at(i) == '.') str.substr(0,i); else str.substr(0,i+1); cout<<str<<endl; } else { cout<<str<<endl; } } } else { cout<<str<<endl; } } void StrConvertInt(string str,int *a) // 字符串转为整形数组功能 { string str1; int i; for(i = 0;i<=str.length()-1;i++) { str1 = str.substr(i,1); a[i] = atoi(str1.c_str()); } } void Mult(int *a,int *s,int N,int len1,int len2) { int i,j; string str = ""; char*str1 = new char[5]; int *f = new int[len2]; int *sum = new int[len2]; // 动态分配数组 int *b = new int[len2]; for(j = 0;j<len2;j++) // 初始化 sum[j] = 0; for(i = len1-1;i >= 0;i--) { for(j=0;j <= len2-1;j++) { b[j] = sum[j]; } for(j = len2-1;j >= 0;j--) { f[j] = a[i]*s[j]; } DealArray(f,len2); for(j = len2-1;j > 0;j--) { sum[j] = f[j] + b[j-1]; } sum[0] = f[0]; DealArray(sum,len2); sprintf(str1,"%d",sum[len2 - 1]); str = str1 + str; } for(j = len2 -2;j>=0;j--) { sprintf(str1,"%d",sum[j]); str = str1 + str; } delete []str1; delete []f; delete []sum; delete []b; int *g = new int[str.length()]; StrConvertInt(str,g); if(N!=2) Mult(a,g,N-1,len1,str.length()); else OutPut(str,M); delete []g; } string DotCut(string str) // 去掉小数点的函数 { int i; string str1,str2; for(i = 0;i<=str.length()-1;i++) { if(str.at(i)=='.') { str1 = str.substr(0,i); str2 = str.substr(i+1,str.length()-i-1); break; } } return str1+str2; } string DealStr(string str) { number = DotLocation(str); int i; string str1,str2,str3; if(number == -1) // 无小数点 { return str; } else // 有小数点 { if(str.at(0) == '0') // 首部是零的情况 { for(i = 0;i<str.length();i++) { if(str.at(i)!='0'&&str.at(i)!='.') // 从首部开始直到第一个不为零结束 { str1 = str.substr(i,str.length()-1); // 子字符串去掉原字符串的首部零还有小数点 break; } } if(str1.at(str1.length()-1) == '0') // 子字符串尾部也是零 { for(i = str1.length()-1;i>=0;i--) // 从尾部开始直到第一个不为零为止 { if(str1.at(i)!='0') { str2 = str1.substr(0,i+1); // 截取子字符串去掉尾部零 break; } } return str2; } else // 字符串尾部不为零 return str1; } else // 首部不是零的情况 { if(str.at(str.length()-1) == '0') // 结尾是零的情况 { for(i = str.length()-1;i>=0;i--) // 从尾部开始第一个不为零的字符为止 { if(str.at(i)!='0') { str1 = str.substr(0,i+1); break; } } str2 = DotCut(str1); // 去掉小数点 return str2; } else // 尾部不是零的情况 { str1 = DotCut(str); // 去掉小数点 return str1; } } } } int main(int args[],char *argc[]) { string str,str1; int len,N; int *a; while(cin>>str>>N) { M = N; // 记录N 为计算结果的小数点时用 str1 = DealStr(str); len = str1.length(); a = new int[len]; StrConvertInt(str1,a); // 字符串转化为整形数组 Mult(a,a,N,len,len); } delete []a; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator