我很好奇我这种歪门邪道的方法比人家正常的还快,还是我计时器弄错了
code:
#include<iostream>
#include<string>
#include<cstdlib>
#include<windows.h>
#include<ctime>
using namespace std;
//高精度比大小
//a>b return 1;b>a return -1;a=b return 0;
int bidaxiao(string a, string b){
int lena=a.length(),lenb=b.length(),flag;
if (a[0]=='-'&&b[0]=='-')flag=-1;
else if(a[0]=='-'&&b[0]!='-')return -1;
else if(a[0]!= '-'&&b[0]=='-')return 1;
else flag=1;
if (lena<lenb)return -flag;
if (lena>lenb)return flag;
for(int i=0;i<max(lena,lenb);i++) {
if (a[i]!= '.'){
if (a[i]-'0'>b[i]-'0')return flag;
if (a[i]-'0'<b[i]-'0')return -flag;
}
}
return 0;
}
//高精度加法
//结果为string类型且去除整数部分前置0、小数部分后置0,小数点为英文句号"."
//a>=0,b>=0
string jiafa(string a, string b) {
string a1 = "", a2 = "", b1 = "", b2 = "";
{
int i;
for (i=a.length()-1;i>-1;i--){
if(a[i]=='.')break;
a2=a[i]+a2;
}
for(i--;i>-1;i--){
a1=a1+a[i];
}
for(i=b.length()-1;i>-1;i--) {
if(b[i] == '.')break;
b2=b[i]+b2;
}
for (i--;i>-1;i--)b1= b1 + b[i];
if (a1=="")a1=a2,a2 = "";
if (b1=="")b1=b2,b2="";
}
int lena1 = a1.length(), lenb1 = b1.length(), lena2 = a2.length(), lenb2 = b2.length();
{
if(lena1<lenb1)for(int i=0;i<lenb1-lena1;i++)a1="0"+a1;
else for(int i=0;i<lena1-lenb1;i++)b1="0"+b1;
if (lena2<lenb2)for(int i=0;i<lenb2-lena2;i++)a2+="0";
else for(int i=0;i<lena2-lenb2;i++)b2+="0";
}
string ans1= "",ans2 = "";int jinwei=0,yujia;
{
for(int i=max(lena2, lenb2)-1;i>-1;i--) {
yujia=(a2[i]-'0'+b2[i]-'0'+jinwei);
ans2=to_string(yujia % 10)+ans2;
if (yujia>9)jinwei = 1;
else jinwei = 0;
}
for(int i=max(lena1,lenb1)-1;i>-1;i--) {
yujia=(a1[i]-'0'+b1[i]-'0'+jinwei);
ans1=to_string(yujia%10)+ans1;
if(yujia>9)jinwei = 1;
else jinwei = 0;
}
if(jinwei!=0)ans1=to_string(jinwei)+ans1;
}
{
string str = "";int i = 0;
for(i;i<ans1.length()-1;i++)if(ans1[i]!='0')break;
for(i;i<ans1.length();i++)str=str+ans1[i];ans1=str;i=ans2.length()-1;
str="";
for(i;i>-1;i--)if(ans2[i]!='0')break;
for (i;i>-1;i--)str=ans2[i]+str;
ans2=str;
}
string finish_ans;
if (ans2=="")finish_ans = ans1;
else finish_ans=ans1+"."+ans2;
return finish_ans;
}
//0<=b<=a
//高精度减法
//结果为string类型且去除整数部分前置0、小数部分后置0,小数点为英文句号"." 负号为"-"
string jianfa(string a, string b){
string a1="",a2="",b1="",b2="";
{
int i;
for(i=a.length()-1;i>-1;i--) {
if(a[i] == '.'||a[i] == '-')break;
a2=a[i]+a2;
}
for(i--;i>-1;i--) {
if(a[i]=='.'||a[i]=='-')break;
a1+=a[i];
}
for(i=b.length()-1;i>-1;i--) {
if(b[i]=='.'||b[i]=='-')break;
b2=b[i]+b2;
}
for(i--;i>-1;i--) {
if(b[i]=='.'||b[i]=='-')break;
b1+=b[i];
}
if(a1=="")a1=a2,a2 = "";
if(b1=="")b1=b2,b2 = "";
}
int lena1=a1.length(),lenb1=b1.length(),lena2=a2.length(),lenb2 = b2.length();
{
if (lena1<lenb1)for(int i=0;i<lenb1-lena1;i++)a1="0"+a1;
else for(int i=0;i<lena1-lenb1;i++)b1="0"+b1;
if(lena2<lenb2)for(int i=0;i<lenb2-lena2;i++)a2=a2+"0";
else for(int i=0;i<lena2-lenb2;i++)b2+="0";
}
string ans1,ans2;
int tuiwei=0,yujian=0;
{
for (int i=max(lena2,lenb2)-1;i>-1;i--) {
yujian=(a2[i]-'0')-(b2[i]-'0')-tuiwei;
if(yujian<0)yujian=yujian+10,tuiwei=1;
else tuiwei=0;
ans2=to_string(yujian)+ans2;
}
for (int i=max(lena1,lenb1)-1;i>-1;i--) {
yujian=(a1[i]-'0')-(b1[i]-'0')-tuiwei;
if(yujian<0)yujian=yujian+10,tuiwei=1;
else tuiwei=0;
ans1=to_string(yujian)+ans1;
}
}
{
string str = "";int i=0;
for (i;i<ans1.length()-1;i++)if(ans1[i]!='0')break;
for (i;i<ans1.length();i++)str=str+ans1[i];
ans1=str,str = "";i=ans2.length()-1;
for (i;i>-1;i--)if(ans2[i]!='0')break;
for(i;i>-1;i--)str=ans2[i]+str;
ans2=str;
}
string finish_ans;
if(ans2 == "")finish_ans = ans1;
else finish_ans=ans1+"."+ans2;
return finish_ans;
}
//a>=0,b>=0
//需要高精度加法
string chengfa(string a,string b){
string a1="",b1="",ans="0",sum[10]{"0","","","","","","","","",""};int xsw=0,flag=0;
for(int i=0;i<a.length();i++){
if(flag)xsw++;
if(a[i]!='.')a1+=a[i];
else flag=1;
}
flag=0;
for(int i=0;i<b.length();i++){
if(flag)xsw++;
if(b[i]!='.')b1+=b[i];
else flag=1;
}
sum[1]=a1;
for(int i=2;i<10;i++)sum[i]=jiafa(sum[i-1],a1);
for(int i=0;i<b1.length();i++){
string c=sum[b1[i]-'0'];
for(int j=0;j<b1.length()-i-1;j++)c+="0";
ans=jiafa(ans,c);
}
if(xsw!=0){
int lenans=ans.length();
ans+=" ";
for(int i=lenans-1;i>=lenans-xsw;i--)ans[i+1]=ans[i];
ans[lenans-xsw]='.';
}
return ans;
}
int compare(string str1,string str2)
{
if(str1.length()>str2.length()) return 1;
else if(str1.length()<str2.length()) return -1;
else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
string add(string str1,string str2)//高精度加法
{
string str;
int len1=str1.length();
int len2=str2.length();
//前面补0,弄成长度相同
if(len1<len2)
{
for(int i=1;i<=len2-len1;i++)
str1="0"+str1;
}
else
{
for(int i=1;i<=len1-len2;i++)
str2="0"+str2;
}
len1=str1.length();
int cf=0;
int temp;
for(int i=len1-1;i>=0;i--)
{
temp=str1[i]-'0'+str2[i]-'0'+cf;
cf=temp/10;
temp%=10;
str=char(temp+'0')+str;
}
if(cf!=0) str=char(cf+'0')+str;
return str;
}
//高精度减法
//只能是两个正数相减,而且要大减小
string sub(string str1,string str2)//高精度减法
{
string str;
int tmp=str1.length()-str2.length();
int cf=0;
for(int i=str2.length()-1;i>=0;i--)
{
if(str1[tmp+i]<str2[i]+cf)
{
str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
cf=1;
}
else
{
str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
cf=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(str1[i]-cf>='0')
{
str=char(str1[i]-cf)+str;
cf=0;
}
else
{
str=char(str1[i]-cf+10)+str;
cf=1;
}
}
str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
return str;
}
//高精度乘法
//只能是两个正数相乘
string mul(string str1,string str2)
{
string str;
int len1=str1.length();
int len2=str2.length();
string tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr="";
int temp=str2[i]-'0';
int t=0;
int cf=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(str1[j]-'0')+cf)%10;
cf=(temp*(str1[j]-'0')+cf)/10;
tempstr=char(t+'0')+tempstr;
}
if(cf!=0) tempstr=char(cf+'0')+tempstr;
}
str=add(str,tempstr);
}
str.erase(0,str.find_first_not_of('0'));
return str;
}
int main() {
string a="",b="",ans1,ans2,c;
for(int i=1;i<=100;i++){
for(int i=0;i<100;i++)a+=to_string(rand());
for(int i=0;i<100;i++)b+=to_string(rand());
//弄了随机数作比较
double time1,time2;
time1=clock();ans1=chengfa(a,b);time1=clock()-time1;
time2=clock();ans2=mul(a,b);time2=clock()-time2;
if(bidaxiao(ans1,ans2)==0)c="AC";else c="WA";
cout<<"#"<<i<<":"<<c<<" true:"<<time1<<" my:"<<time2<<endl<<"true:"<<ans1<<endl<<"yours;"<<ans2<<endl<<endl;
a="",b="";
}
return 0;
}
我找了份高精度代码和我自己的作比较 找的样本函数是这儿
他的函数名是英文开头几个 我的是拼音
在自己电脑上测试time1和time有10倍之差 不知道评测机上情况怎样
正常写法应该是模拟竖式计算 但我是把0-10乘以因数1的情况都算出来存在sum[0-10]再ans+=sum[b[i]](高精度加法&&b[i]需要-'0')