高精度除以低精度.cpp

/*
高精度除以低精度，通常高精度算法掌握四部分（加法和乘法，减法，高精度除以低精度，高精度除以高精度）
由于除数是低精度的值，也就是说除数没有超出整型的数据范围，虽然被除数是高精度，但是我们模拟竖式除法时，从被除数取出的数是可以和除数直接作算术运算的，
减下后的余数继续模拟竖式除法的后续过程，直到我们完成整个竖式除法，因此商是高精度的值，而余数肯定是低精度的值
注意高精度的实现我们用结构体，这样方便我们的实现
*/
#include <bits/stdc++.h>
using namespace std;
typedef struct bignum
{
        int num[5005],l;/*num长度视题目要求而定，各位数从0开始存放，l表示数字的长度*/
}BIGNUM,*PBIGNUM;
char tmp[5005];
BIGNUM Big_Div(const BIGNUM & a,int b,int & mod)/*a是高精度的被除数，b是低精度的除数，mod为余数同时也是输出参数，函数返回值为高精度商*/
{
        BIGNUM c;
        int i,j,s=0;
        c.l=0;
        for(i=a.l-1;i>=0;--i)
        {
                s=s*10+a.num[i];
                if(s<b)
                {
                        c.num[c.l++]=0;
                        continue;
                }
                else
                {
                        c.num[c.l++]=s/b;
                        s%=b;  
                }      
        }
        mod=s;
        for(i=0,j=c.l-1;i<j;++i,--j)
        {
                swap(c.num[i],c.num[j]);        
        }
        while(c.num[c.l-1]==0&&c.l>1)//高精度除以低精度中，无法确定高位在被减后的情况，所以从最高位开始扫描，删除前导0
        {
        c.l--;//高精度除以低精度中，乘积长度-1
        }
        return c;
}
void Big_Read(BIGNUM & a,char s[])
{
        int i,j;
        memset(a.num,0,sizeof(a.num));
        a.l=strlen(s);
        for(i=0,j=a.l-1;i<a.l;++i,--j)//高精度除以低精度中，通过循环把s数组的值逆置保存到a.num数组中
        {
                a.num[i]=s[j]-'0';
        }
}
void Big_Print(const BIGNUM & a)
{
        int i;
        for(i=a.l-1;i>=0;--i)
        {
                printf("%d",a.num[i]);
        }
        printf("\n");
}
int main()
{
        BIGNUM a,c;
        int b,mod;
        gets(tmp);
        Big_Read(a,tmp);
        scanf("%d",&b);
        c=Big_Div(a,b,mod);
        Big_Print(c);
        //printf("%d",mod);
        return 0;
}