UVA oj 练习水题 算法入门经典（大数系列）
发布时间：2020-12-14 04:06:13 所属栏目：大数据 来源：网络整理
导读：最近做了很多白皮书（算法入门经典）上面的很多水题，但是考验编程的细心还是很考验的，把一些题记录在这儿 424 - Integer Inquiry? 大数加法，代码改的很烂，很不容易的过了： #include iostream#include string#include cstring#include algorithmusing na
|
最近做了很多白皮书（算法入门经典）上面的很多水题，但是考验编程的细心还是很考验的，把一些题记录在这儿 424 - Integer Inquiry? 大数加法，代码改的很烂，很不容易的过了： #include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string a,b,c;
int la,lb,lc;
int ta[120],tb[120],tc[120];
cin>>a;
if(a[0]=='0')
{ return 0;}
reverse(a.begin(),a.end());
la=a.size();
for(int i=0;i<la;i++)
ta[i]=a[i]-'0';
while(cin>>b)
{
memset(tc,sizeof(tc));
memset(tb,sizeof(tb));
bool ok=false;
if(b[0]=='0'){
for(int i=la-1;i>=0;i--)
cout<<ta[i];
cout<<endl;
break;
}
reverse(b.begin(),b.end());
lb=b.size();
for(int i=0;i<lb;i++)
tb[i]=b[i]-'0';
int l=la>lb?la:lb;
if(la<l)
{
for(int i=la;i<l;i++)
ta[i]=0;
}
if(lb<l)
{
for(int i=lb;i<l;i++)
tb[i]=0;
}
for(int i=0;i<l;i++){
if(ta[i]+tb[i]>9){
if(i==l-1){
tc[i]=(ta[i]+tb[i])%10;
tc[i+1]=1;ok=true;
}
else{
tc[i]=(ta[i]+tb[i])%10;
tb[i+1]++;
}
}
else{
tc[i]=tb[i]+ta[i];
}
}
if(ok) l++;
ok=false;
la=l;
for(int i=0;i<la;i++)
ta[i]=tc[i];
}
return 0;
}
10106 - Product?简单大数乘法，刚开始没有考虑到05*05这样输出为0025的。wa了、、、后面输出加了判断之后0*0却不输出了，特殊处理过了。#include <iostream>
#include <vector>
using namespace std;
void multiply(const vector<int>& t,const vector<int>& d,vector<int>& result)
{
int i,j,k,tmp;
for(int i=0;i<t.size();i++){
k=i;
for (j = 0; j < d.size(); ++j)
{
result[k++] += t[i] * d[j];
}
}
for(k=result.size()-1;k>=0;--k){
if(result[k]>9){
if(k!=0){
result[k-1]+=result[k]/10;
result[k]%=10;
}
else{
tmp=result[k]/10;
result[k]%=10;
result.insert(result.begin(),tmp);
}
}
}
}
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
if(s1=="0"||s2=="0")
{cout<<"0"<<endl;continue;}
vector<int> vs1,vs2;
vs1.reserve(s1.size());
vs2.reserve(s2.size());
for(int i=0;i<s1.size();i++)
vs1.push_back(s1[i]-'0');
for(int i=0;i<s2.size();i++)
vs2.push_back(s2[i]-'0');
vector<int> vs3(s1.size()+s2.size()-1,0);
multiply(vs1,vs2,vs3);
bool ok=true;
for(int i=0;i<vs3.size();i++)
{
if(vs3[i]==0)
{
if(!ok)
cout<<vs3[i];
}
else{
cout<<vs3[i];
ok=false;
}
}
cout<<endl;
}
return 0;
}
10494 - If We Were a Child Again?大数除以高精度数，很简单的模拟，但是大牛看看23行到35行注释掉的代码，为什么那样写会出错，没搞懂。代码：#include <stdio.h>
#include <string.h>
int main()
{ char s[1000],lable;
long num,i,l,temp,a[1000],sum,pos;
while (scanf("%s %c %ld",&s,&lable,&num)!=EOF)
{
l=strlen(s); sum=0;
temp=0;
for (i=0;i<l;i++)
{
temp=temp*10+s[i]-'0';
if (temp>=num)
{
a[++sum]=temp/num;
temp=temp%num;
}
else
{ a[++sum]=0;}
}
if(lable=='/')
{
/*bool ok=true;
for(int i=1;i<=sum;i++)
{
if(a[i]==0)
{
if(!ok)
printf("0");
}
else{
printf("%d",a[i]);
ok=false;
}
}*/
pos=1;
while ((a[pos]==0)&&(pos<sum)){
++pos;
}
for (i=pos;i<=sum;i++)
printf("%ld",a[i]);
printf("n");
}
else
printf("%dn",temp);
}
return 0;
}
Uva113 - Power of Cryptography?求大数开n次方的结果。但是用double水过了、、但是long long 过不了。#include <stdio.h>
#include <string.h>
#include <math.h>
int main()
{
long mid,left,right;
double p;
int n;
while(~scanf("%d%lf",&n,&p)){
left=0,right=1000000000;
while(left<right)
{
mid=(left+right)/2;
if(pow(mid,n)==p) break;
if(pow(mid,n)<p)left=mid;
if(pow(mid,n)>p)
right=mid;
}
//printf("%lfn",p);
printf("%ldn",mid);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |