求助高精
  • 板块灌水区
  • 楼主藕丝泥霸NZ
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/7/26 18:52
  • 上次更新2023/11/6 22:12:45
查看原帖
求助高精
275658
藕丝泥霸NZ楼主2020/7/26 18:52

我的高精除程序的问题在哪? 其他的程序有问题吗?

#include<bits/stdc++.h>
using namespace std;
const int MAX=100000;
typedef struct Bigint
{
    int data[MAX];
    int len;
}Big;
int to_0( Big &a)
{
    memset(a.data,0,MAX*sizeof(int));
    a.len = 0;
    return 0;
}
int length( Big &a)
{
    int i;
    for( i=a.len-1; i>=0; i-- )
    {
        if( a.data[i]>0||i<0 )
        {
            break;
        }
    }
    a.len = i + 1;
    return i+1;
}
int in( string a , Big &b )
{
    int i = 0, j;
    j = a.size()-1;
    to_0(b);
    for( j=a.size()-1; j>=0; j-- )
    {
        if( a[j]<='9'&&a[j]>='0' )
        {
            if( i==MAX ) return -1;
            b.data[i] = a[j]-'0';
            b.len++;
            i++;
        }
    }
    length(b);
    return i;
}
string out( Big &b, string &a )
{
    int k, j;
    k = b.len-1;
    a = "";
    for( j=0; j<b.len; j++ )
    {
        a.push_back( b.data[k]+'0' );
        k--;
    }
    if( a.size()==0 )
    {
        a = "0";
    }
    return a;
}
int copy( Big &org, Big &desk )
{
    to_0(desk);
    memcpy( desk.data, org.data, MAX*sizeof(int));
    desk.len = org.len;
    return 0;
}
int add( Big &a, Big &b, Big &c )
{
    int i = 0, jw = 0, len;
    to_0(c);
    len = max(a.len+1,b.len+1);
    for( i=0; i<min(len,MAX); i++ )
    {
        c.data[i] = jw+a.data[i]+b.data[i];
        jw = c.data[i]/10;
        c.data[i] %= 10;
    }
    if(c.data[i-1]==0)
    {
        c.len = i-1;
    }
    else
    {
        c.len = i;
    }
    return jw;
}
int sub( Big &a, Big &b, Big &c )
{
    int i = 0, tw = 0, len;
    to_0(c);
    len = max(a.len, b.len);
    c.len=len;
    for( i=0; i<len; i++ )
    {
        c.data[i] = a.data[i]-b.data[i]+tw;
        if( c.data[i]<0 )
        {
            tw = -1;
            c.data[i] += 10;
        }
        else
        {
            tw = 0;
        }
    }
    length(c);
    return tw;
}
int mul_2( Big &a , Big &b )
{
    to_0(b); 
    Big c;
    int jw;
    copy(a,c);
    jw = add(a,c,b);
    return jw;
}
int div_2( Big &a , Big &b )
{
    to_0(b);
    int ys = 0, i;
    for( i=a.len-1; i>=0; i-- )
    {
        b.data[i] = (10*ys+a.data[i])/2;
        ys = a.data[i]%2;
    }
    b.len = a.len;
    if (b.len>0 &&b.data[b.len-1]==0) b.len--;
    return ys;
}
int mul( Big &a, Big &b, Big &c )
{
    Big d;
    int j;
    to_0(c);
    to_0(d);
    do
    {
        if( a.data[0]%2==1 ) 
        {
            j = add(b,c,d);
            if(j==1)
            {
                return 1;
            }
            copy(d,c);
            to_0(d);
        }
        div_2(a,d);
        copy(d,a);
        to_0(d);
        j = mul_2(b,d);
        if(j==1)
        {
            return 1;
        }
        copy(d,b);
        to_0(d);
    }while(a.len!=0);
    return 0;
}
int in_from_int( int i, Big &a)
{
    to_0(a);
    while(i!=0)
    {
        a.data[a.len++] = i%10;
        i=i/10;
    }
    return a.len;
}
int bigger( Big &a , Big &b )
{
    if(a.len>b.len)
    {
        return 1;
    }
    else if(b.len>a.len)
    {
        return 0;
    }
    else
    {
        if(a.data[a.len-1]>b.data[b.len-1])
        {
            return 1;
        }
        else if(a.data[a.len-1]<b.data[b.len-1])
        {
            return 0;
        }
        else
        {
            return 2;
        }
    }
    return 0;
} 
int div( Big &a , Big &b , Big &c )
{
    Big d;
    to_0(c);
    to_0(d);
    int ys = 0, i;
    in_from_int( 1, d );
    while((!bigger(b,a)))
    {
        mul_2(b,c);
        copy(c,b);
    }
    div_2(b,c);
    copy(c,b);
    return ys;
}
int main()
{
    string s, ss;
    Big a,b,c;
    int n, i, j, k = 0, ys;
    cin >> s >> ss;
    in(s,a);
    in(ss,b);
    ys = div(a,b,c);
    out(c,s);
    cout << s;
    cout << ys;
    return 0;
}


2020/7/26 18:52
加载中...