//得到商和余数版本:
1,大整数除法运算,不同于其它的大整数运算,它不需要对字符串进行逆转,这主要是因为大整数除法是模拟手算过程,从最高位开始试商。
2,试商的过程是调用大整数减法和比较函数的过程,这里的减法运算只实现大数减小数的情形。
3,被除数为m位,除数为n位,则商最多为m位,余数最多为n位。
4,strcmp("2","123") 结果为1,所以这里必须重新写一个比较函数
//商和余数版本一
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10
bool NotZero(char ch)
{
return ch != '0';
}
int Cmp(char res[MAX][MAX],char right[MAX])
{
int i,len1,len2;
len1 = strlen(res[1]);
len2 = strlen(right);
if(len1 < len2)
return -1;
else if(len1 > len2)
return 1;
else
{
for(i = 0;i < len1 && res[1][i] == right[i];++i);
if(i == len1)
return 0;
else if(res[1][i] > right[i])
return 1;
else
return -1;
}
}
void Sub(char res[MAX][MAX],char right[MAX])
{
int i,len1,len2;
len1 = strlen(res[1]);
len2 = strlen(right);
reverse(res[1],res[1] + len1);
reverse(right,right + len2);
for(i = 0;i < len1;++i)
res[1][i] -= '0';
for(i = 0;i < len1;++i)
{
if(i < len2)
{
res[1][i] = res[1][i] - right[i] + '0';
if(res[1][i] < 0)
{
res[1][i] = res[1][i] + 10;
--res[1][i+1];
}
}
else
{
if(res[1][i] < 0)
{
res[1][i] = res[1][i] + 10;
--res[1][i+1];
}
}
}
while(len1 > 1 && res[1][len1-1] == 0)
--len1;
for(i = 0;i < len1;++i)
res[1][i] += '0';
res[1][len1] = '/0';
reverse(res[1],res[1] + len1);
reverse(right,right + len2);
}
void Div(char left[MAX],char right[MAX],char res[2][MAX])
{
int i,j,r,len1,len2;
len1 = strlen(left);
len2 = strlen(right);
for(i = 0;i <= len1;++i)//将商的各位归零,同时将结束符加进去
res[0][i] = 0;
for(i = 0;i <= len1;++i)//将余数的各位归零,同时将结束符加进去,这里之所以用len1,不用len2是因为余数的中间结果可能等于被除数的位数
res[1][i] = 0;
for(i = 0,j = 0;i < len1;++i)
{
r = 0;
res[1][j] = left[i];
while(Cmp(res,right) >= 0)
{
++r;
Sub(res,right);//这里的减法运算不会引入前导0
}
if(Cmp(res,"0") != 0)
j = strlen(res[1]);
else//当减的结果为0时,必须将j设置为0,否则随着前导0的增多影响Cmp的正确判断
j = 0;
res[0][i] = r + '0';
}
len1 = strlen(res[0]);
char* pos = find_if(res[0],res[0] + len1 - 1,NotZero);//在保留一位的范围内找第一个不为0的元素
copy(pos,res[0] + len1 + 1,res[0]);//+1将字符串结束符也移动的指定位置
}
int main()
{
char left[MAX],right[MAX],res[2][MAX];
while(cin >> left >> right)
{
Div(left,right,res);
cout << res[0] << endl;
cout << res[1] << endl;
}
return 0;
}
//商和余数版本二
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10
bool NotZero(char ch)
{
return ch != '0';
}
int Cmp(char* rm,char* rt)
{
int i,len1,len2;
len1 = strlen(rm);
len2 = strlen(rt);
if(len1 < len2)
return -1;
else if(len1 > len2)
return 1;
else
{
for(i = 0;i < len1 && rm[i] == rt[i];++i);
if(i == len1)
return 0;
else if(rm[i] > rt[i])
return 1;
else
return -1;
}
}
void Sub(char* rm,char* rt)
{
int i,len1,len2;
len1 = strlen(rm);
len2 = strlen(rt);
reverse(rm,rm + len1);
reverse(rt,rt + len2);
for(i = 0;i < len1;++i)
rm[i] -= '0';
for(i = 0;i < len1;++i)
{
if(i < len2)
{
rm[i] = rm[i] - rt[i] + '0';
if(rm[i] < 0)
{
rm[i] += 10;
--rm[i+1];
}
}
else
{
if(rm[i] < 0)
{
rm[i] += 10;
--rm[i+1];
}
}
}
while(len1 > 1 && rm[len1 - 1] == 0)
--len1;
for(i = 0;i < len1;++i)
rm[i] += '0';
rm[len1] = '/0';
reverse(rm,rm + len1);
reverse(rt,rt + len2);
}
void Div(char* left,char* right,char res[2][MAX])
{
int i,j,r,len1,len2;
len1 = strlen(left);
len2 = strlen(right);
for(i = 0;i <= len1;++i)
res[0][i] = res[1][i] = 0;
for(i = 0,j = 0;i < len1;++i)
{
r = 0;
res[1][j] = left[i];
while(Cmp(res[1],right) >= 0)
{
Sub(res[1],right);
++r;
}
if(Cmp(res[1],"0") == 0)
j = 0;
else
j = strlen(res[1]);
res[0][i] = r + '0';
}
len1 = strlen(res[0]);
char* pos = find_if(res[0],res[0] + len1 - 1,NotZero);
copy(pos,res[0] + len1 + 1,res[0]);
}
int main()
{
char left[MAX],right[MAX],res[2][MAX];
while(cin >> left >> right)
{
Div(left,right,res);
cout << res[0] << endl;
cout << res[1] << endl;
}
return 0;
}