X02-day04高精度、快排、归并排序
2023-08-15 20:32:47
发布于：浙江
22阅读
0回复
0点赞
//归并排序
#include<iostream>
using namespace std;
int n,a[100005],c[100005];
void f(int l,int r){//把区间[l,r]划分成左右两边
if(l==r) return; //区间只有一个数就返回
int mid=(l+r)/2;
f(l,mid);
f(mid+1,r);
//l~mid mid+1~r
int i=l,j=mid+1,k=l-1;
while(i<=mid && j<=r){
if(a[i]<=a[j]) c[++k]=a[i++];
else c[++k]=a[j++];
}
while(i<=mid) c[++k]=a[i++];
//a数组里面的元素没有存放完
while(j<=r) c[++k]=a[j++];
//把c数组里面l,r的元素，完全给a数组
for(int i=l;i<=r;i++) a[i]=c[i];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f(1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
//高精度加法
#include<bits/stdc++.h>
using namespace std;
int a[105],b[105],c[105];
int main(){
//1.用字符串存储
string s1,s2; //1234 567
cin>>s1>>s2;
//2.反转
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
//3.把s1，s2里面的数字字符转换成数字
for(int i=0;i<s1.length();i++){
a[i]=s1[i]-'0';
}
for(int i=0;i<s2.length();i++){
b[i]=s2[i]-'0';
}
//a数组和b数组对应位相加 两个字符串较长的字符串的下标
int len=max(s1.length(),s2.length());
for(int i=0;i<=len-1;i++){
c[i]+=a[i]+b[i];//c[i]里面有可能存放了进位
//进位
if(c[i]>9){
c[i+1]++;
c[i]-=10;
}
}
//最高位进位
if(c[len]>0) cout<<c[len];
for(int i=len-1;i>=0;i--) cout<<c[i];
return 0;
}
//高精度减法
#include<bits/stdc++.h>
using namespace std;
int a[255],b[255],c[255];
int main(){
//1.用字符串存储
string s1,s2; //1234 567
cin>>s1>>s2;
//2.判断s1和s2的大小关系 s1<s2 字典序
if(s1.size()<s2.size() || (s1.size()==s2.size() && s1<s2)){
cout<<"-";
swap(s1,s2); //s1 s2
}
//2.反转
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
//3.把s1，s2里面的数字字符转换成数字
for(int i=0;i<s1.length();i++){
a[i]=s1[i]-'0';
}
for(int i=0;i<s2.length();i++){
b[i]=s2[i]-'0';
}
//a数组和b数组对应位相减
int len=max(s1.length(),s2.length());
for(int i=0;i<=len-1;i++){
c[i]=a[i]-b[i];//c[i]里面有可能存放了进位
//借位
if(c[i]<0){
a[i+1]--; //借位
c[i]+=10; //
}
}
//去除前导0 &&len>1 考虑结果为0的情况，至少保留一个0
while(c[len-1]==0 && len>1) len--;
for(int i=len-1;i>=0;i--) cout<<c[i];
return 0;
}
//高精度乘法
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[2100],b[2100],c[4100],cnt1,cnt2;
int main(){
cin>>s1>>s2;
for(int i=s1.size()-1;i>=0;i--)
a[cnt1++]=s1[i]-'0';
for(int i=s2.size()-1;i>=0;i--)
b[cnt2++]=s2[i]-'0';
int len1=s1.size(),len2=s2.size();
//用第2个数的每一个数去乘以第一个数的每一位
for(int i=0;i<len2;i++){
for(int j=0;j<len1;j++){
c[i+j]=b[i]*a[j]+c[i+j];
//进位
if(c[i+j]>9){
c[i+j+1]+=c[i+j]/10; // 8*9
c[i+j]%=10;
}
}
}
//输出
int l=len1+len2;
while(c[l]==0 && l>0) l--;
for(int i=l;i>=0;i--)
cout<<c[i];
return 0;
}
//高精度除低精度
#include<bits/stdc++.h>
using namespace std;
string a;
int b,c[5005],d[5005],cnt;
//抽奖4
long long p;
int main(){
cin>>a>>b;
//除法 正序存放到c数组
for(int i=0;i<a.size();i++)
c[i]=a[i]-'0';
for(int i=0;i<a.size();i++){
p=p*10+c[i];
d[cnt++]=p/b; //d[4] 5
p%=b;
}
//去除前导0
//d[cnt-1]
int idx=0; //1
while(d[idx]==0 && idx<cnt-1) idx++;
for(int i=idx;i<cnt;i++)
cout<<d[i];
cout<<endl;
cout<<p;
return 0;
}
//高精度除高精度
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[300005],b[300005],c[300005],d[300005];
//初始化清空辅助数组
void init(){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
}
//高精度减法
string sub(string p,string q){
init();
string ans="";
for(int i=0;i<p.size();i++) a[p.size()-i-1]=p[i]-'0';
for(int i=0;i<q.size();i++) b[q.size()-i-1]=q[i]-'0';
int len=max(p.size(),q.size());
for(int i=0;i<len;i++){
c[i]=a[i]-b[i];
if(c[i]<0){
a[i+1]--;
c[i]+=10;
}
}
//去除前导0
len--;
while(c[len]==0 && len>0) len--;
for(int i=len;i>=0;i--) ans+=c[i]+'0';
return ans;
}
bool check(string p,string q){
return p.size()>q.size() || p.size()==q.size()&&p>=q;
}
//模拟除法
void div(string p,string q){
string now="";
int cnt;
for(int i=0;i<p.size();i++){
cnt=0;
now+=p[i];
while(check(now,q)){
cnt++;
now=sub(now,q);
}
d[i]=cnt;
if(now=="0") now="";
}
int len=0;
while(d[len]==0 && len<p.size()-1) len++;
for(int i=len;i<p.size();i++) cout<<d[i];
printf("\n");
if(now=="") now="0";
cout<<now;
}
int main(){
cin>>s1>>s2;
div(s1,s2);
return 0;
}
这里空空如也
有帮助，赞一个