题目描述
给定两个正整数A,B,请你计算 A / B的商和余数。
输入格式
共两行,第一行包含整数A,第二行包含整数B。
输出格式
共两行,第一行输出所求的商,第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000
样例
输入样例:
7
2
输出样例:
3
1
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址,便于直接对余数r进行修改
vector<int> C;
for(int i=0;i<A.size();i++){//对A从最高位开始处理
r=r*10+A[i];//将上次的余数*10在加上当前位的数字,便是该位需要除的被除数
C.push_back(r/B);//所得即为商在这一位的数字
r=r%B;
}
//由于在除法运算中,高位到低位运算,因此C的前导零都在vector的前面而不是尾部,vector只有删除最后一个数字pop_back是常数复杂度,而对于删除第一位没有相应的库函数可以使用,而且删除第一位,其余位也要前移,
//因此我们将C翻转,这样0就位于数组尾部,可以使用pop函数删除前导0
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main(){
string a;
int B,r=0; //代表余数
cin>>a>>B;
vector<int> A;
for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位,由于在除法的手算过程中,发现从高位进行处理
//for(int i=0;i<A.size();i++) cout<<A[i];
//cout<<B;
auto C = div(A,B,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
cout<<endl<<r;//输出余数
cout<<endl;
return 0;
}
vector[HTML_REMOVED] div(vector[HTML_REMOVED] &A,int B,int &r){//r传入r的地址,便于直接对余数r进行修改
vector[HTML_REMOVED] C;
bool f = false;
for(int i=0;i<A.size();i++){//对A从最高位开始处理
r=r10+A[i];//将上次的余数10在加上当前位的数字,便是该位需要除的被除数
if(r/B!=0) {C.push_back(r/B); f = true;}
else if(f == true) C.push_back(r/B);
r=r%B;
}
if(C.size() == 0) C.push_back(0);
return C;
}
这样写就不用先反转再去掉前导零了
我想问一下为什么不学高精度除以高精度
因为一般来讲不会用到。而且复杂度应该会很高。
你好,可以帮我解答一个困惑吗?翻转如果是为了删除前导零的话,那删除以后return的时候不用再翻转回去吗?
是因为后面在输出的时候是反着输出的C是吗?
对滴,你也可以模拟一下
为什么不学高精除高精呀
我觉得把你这高精度减法和高精度乘法堆一块应该就是除法,小学的竖式
y总的错冷吗??
没有呀
为什么不能定义一个全局变量r
请问这个算法 n^2 是怎么推出来的?
应该是n,由A的长度决定,他应该是没有修改题解模板
algorithm头文件中的reverse()算法时间复杂度是O(n^2)的
逆置时间复杂度为O(n)把,从两头开始对调,到中间停止,执行n/2次,复杂度为O(n)
感觉这个复杂度一个是n
高精度拿java的BigDecimal写可不可以啊
java和python不用学高精度吧
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
//去除前导0
int delPreZero(int x[], int xLen){
int i=xLen;
}
//逆序输出数组值
void printArr(int x[], int xLen){
for(int i=xLen-1; i>=0; i–){
cout << x[i];
}
cout << endl;
}
//若x>=y返回true,否则返回false
bool compare(int x[], int y[], int xLen, int yLen){
if(xLen < yLen){
return false;
}
}
//若x>=y,则x的高位减去y(只减一次),返回值为x的新长度
int sub(int x[], int y[], int z[], int xLen, int yLen){
int zLoc = xLen - yLen ; //商的位置
}
int main(){
char as[301], bs[301];
}
解析特别详细,好评!
详细
可以可以正在记录模板
reverse(C.begin(),C.end()); 这个是什么意思呢
对数组C进行反转
写得太细致了👍👍
当时y总为什么说不学 那个 高精度除以高精度来着?
注释对新手太友好了
棒棒棒
写的不错!