当前位置:首页 > 题解目录 > 正文内容

【题解】高精度除法

亿万年的星光2年前 (2023-02-15)题解目录16064

【题目描述】

高精除以高精,求它们的商和余数。

【输入描述】

输入两个低于300位的正整数。

【输出描述】

输出商和余数。

【样例输入】

1231312318457577687897987642324567864324567876543245671425346756786867867867
1231312318767141738178325678412414124141425346756786867867867

【样例输出】

999999999748590
179780909068307566598992807564736854549985603543237528310337

【参考代码】

#include<iostream>  
#include<cstring>  
using namespace std;  
int a[100],b[100],c[100];  
int compare(int a[],int b[])//比较a、b,若a>b为1;若a<b为-1;若a=b为0  
{  
    int i;  
    if(a[0]>b[0])  
        return 1;  
    if(a[0]<b[0])  
        return -1;  
    for(i=a[0];i>0;i--)//从高位到低位比较  
    {  
        if(a[i]>b[i])  
            return 1;  
        if(a[i]<b[i])  
            return -1;  
    }  
    return 0;  
}  
  
void subduction(int a[],int b[])//计算a=a-b  
{  
    int flag;  
    int i;  
  
    flag=compare(a,b);  
    if(flag==0)//相等  
    {  
        a[0]=0;  
        return;  
    }  
    if(flag==1)//大于  
    {  
        for(i=1;i<=a[0];i++)  
        {  
            if(a[i]<b[i])//若不够向上借位  
            {  
                a[i+1]--;  
                a[i]+=10;  
            }  
            a[i]-=b[i];  
        }  
        while(a[0]>0&&a[a[0]]==0)//删除前导0  
            a[0]--;  
        return;  
    }  
}  
int main()  
{  
    char str1[100],str2[100];  
    int i,j;  
  
    memset(a,0,sizeof(a));  
    memset(b,0,sizeof(b));  
    memset(c,0,sizeof(c));  
  
    cin>>str1>>str2;  
    a[0]=strlen(str1);//a[0]存储串1的位数  
    b[0]=strlen(str2);//b[0]存储串2的位数  
    for(i=1;i<=a[0];i++)  
        a[i]=str1[a[0]-i]-'0';  
    for(i=1;i<=b[0];i++)  
        b[i]=str2[b[0]-i]-'0';  
  
  
    int temp[100];  
    c[0]=a[0]-b[0]+1;  
    for(i=c[0];i>0;i--)  
    {  
        memset(temp,0,sizeof(temp));  
  
        for(j=1;j<=b[0];j++)//从i开始的地方,复制数组b到数组temp  
            temp[j+i-1]=b[j];  
        temp[0]=b[0]+i-1;  
  
        while(compare(a,temp)>=0)//用减法模拟  
        {  
            c[i]++;  
            subduction(a,temp);  
        }  
    }  
  
    while(c[0]>0&&c[c[0]]==0)//删除前导0  
        c[0]--;  
  
//    cout<<"商为:";  
    if(c[0]==0)//输出结果  
        cout<<0<<endl;  
    else  
    {  
        for(i=c[0];i>0;i--)  
            cout<<c[i];  
        cout<<endl;  
    }  
  
//    cout<<"余数为:";  
    if(a[0]==0)//输出余数  
        cout<<0<<endl;  
    else  
    {  
        for(i=a[0];i>0;i--)  
            cout<<a[i];  
        cout<<endl;  
    }  
  
    return 0;  
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: 高精度
分享给朋友:

相关文章

【题解】均分蛋糕

【题解】均分蛋糕

【题目描述】小明的生日要到了!根据习俗,他需要将一些派分给大家。他有 N 个不同口味、不同大小的派。有 F 个朋友会来参加我的派对,每个人会拿到一块派(必须一个...

【题解】分糖果

【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

【题解】阶乘的末尾

【题目描述】n的阶乘定义为n!=1*2*3*……*n  如3!=6   n!通常最后会有很多0,如5!=120  最后有一个0,现在统计n!去除末尾的0后,最后k位是多少...

字符串反连接

【题目描述】写一函数,使输入的一个字符串按反序存放,在主函数中输入并输出反序后的字符串(不包含空格)。【输入描述】一行字符【输出描述】逆序后的字符串【样例输入】123456abcdef【样例输出】fe...

【题解】日期排序

【题目描述】有一些日期,日期格式为“MM/DD/YYYY”。编程将其按日期大小排列。【输入描述】无【输出描述】无【样例输入】15/12/1999 10/21/2003 10/22/2003 02...

【题解】合并有序表

【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数,表示第i个序列。总数小于100000。【输出描述】输...