Thuật toán nhân số nguyên lớn

Thảo luận trong 'Thuật toán' bắt đầu bởi integer, 4 Tháng ba 2011.

  1. Offline

    integer

    • Tiếu Ngạo Giang Hồ

    • :-?
    Số bài viết:
    1.695
    Đã được thích:
    1.313
    Điểm thành tích:
    900
    Khi cài đặt thuật toán này phần lớn các bạn gặp vấn đề là làm sao để thêm số 0 vào trước chuỗi có độ dài n lẻ và làm thế nào để thêm số 0 trước số có độ dài ngắn hơn để 2 chuỗi số bằng nhau.

    Đoạn chương trình sau sẽ giải quyết 2 vấn đề cơ bản trên, sau khi thu được 2 chuỗi có độ dài bằng nhau và độ dài n chẵn, việc còn lại là của các bạn: Viết thuật toán nhân 2 số nguyên lớn.

    Mã:
    #include<iostream>
    #include<string.h>
    #include<ctype.h>
    #include<stdlib.h>
    using namespace std;
    char x[100],y[100];
    void xulychuoi(char x[],char y[],int &n)
    {
        if(n%2!=0)
        {
            char ss[2];
            ss[0]='0';
            ss[1]='\0';
            strcat(ss,x);//noi chuoi ss vao x
            strcpy(x,ss);//gan lai chuoi moi cho x
            ss[0]='0';
            ss[1]='\0';
            strcat(ss,y);
            strcpy(y,ss);
            n++;
        }
        ///them 1 so 0 dang truoc neu n le
        ///doan truong trinh duoi  lam do dai 2 chuoi bang nhau
        ///bang cach them cac so 0 vao truoc chuoi ngan hon
        int sx=strlen(x),sy=strlen(y);
        if(sx>sy)
        {
            int i,d=sx-sy;
            ///khoang cach giua do dai x va y
            char s[100];
            for(i=0; i<d; i++)
                s[i]='0';
            s[i]='\0';
            ///chuoi s la chuoi so 0 can them vao dang truoc
            strcat(s,y);///noi chuoi so 0 la s voi y
            strcpy(y,s);///gan s nguoc lai cho y
        }
        else if(sx<sy)
        {
            int i,d=sy-sx;
            char s[100];
            for(i=0; i<d; i++)
                s[i]='0';
            s[i]='\0';
            strcat(s,x);
            strcpy(x,s);
        }
    }
    
    main()
    {
        char tmp[100];
        int n,sx,sy;
        cout<<"\nNhap x: ";
        cin>>tmp;
        strcpy(x,tmp);
        cout<<"\nNhap y: ";
        cin>>tmp;
        strcpy(y,tmp);
        sx=strlen(x);
        sy=strlen(y);
        sx>sy ? n=sx : n=sy;
        xulychuoi(x,y,n);
        cout<<x<<"\n"<<y<<"\n"<<n<<"\n";
    
    }
    lyvinhr00m thích bài này.
  2. Offline

    integer

    • Tiếu Ngạo Giang Hồ

    • :-?
    Số bài viết:
    1.695
    Đã được thích:
    1.313
    Điểm thành tích:
    900
    Mới code cứng được cho nó chạy sơ bộ đã, phần tiếp theo là áp dụng chia để trị không đệ quy để giải quyết nó.
    Mã:
    long mu(int a,int n)
    {
        if(n==1)
            return a;
        else
            return a*mu(a,n-1);
    }
    long karaoke(int n)
    {
        char a[max],b[max],c[max],d[max];
        for(int i=0; i<n/2; i++)
        {
            a[i]=x[i];
            a[n/2]='\0';
        }
        int j=0;
        for(int i=n/2; i<=n; i++)
        {
            b[j]=x[i];
            j++;
            b[n+1]='\0';
        }
    
        for(int i=0; i<n/2; i++)
        {
            c[i]=y[i];
            c[n/2]='\0';
        }
        j=0;
        for(int i=n/2; i<=n; i++)
        {
            d[j]=y[i];
            j++;
            b[n+1]='\0';
        }
        //tach so thanh cong
        cout<<"\n"<<a<<"\n"<<b<<"\n"<<c<<"\n"<<d;
        unsigned long int soa=atoi(a),sob=atoi(b),soc=atoi(c),sod=atoi(d);
        unsigned long int U=soa*soc,V=sob*sod,W=(soa+sob)*(soc+sod);
        cout<<"\n"<<(U*mu(10,n))+((W-U-V)*mu(10,n/2))+V;
    }
    
    lyvinhr00m thích bài này.
  3. Offline

    jun_alone

    • Windows 3.0

    Số bài viết:
    203
    Đã được thích:
    47
    Điểm thành tích:
    40
    thế giải thik rõ hơn không?Hay copy mạng ve
  4. Offline

    integer

    • Tiếu Ngạo Giang Hồ

    • :-?
    Số bài viết:
    1.695
    Đã được thích:
    1.313
    Điểm thành tích:
    900
    Là mình tự code nhưng chưa xong, trên mới chỉ là phần chia đôi chuỗi và thêm các số 0 vào trước cho bằng nhau thôi. Sau đó áp dụng Karasuba vào để tính. Nhưng mình thấy cách này có vẻ không hiệu quả lắm.

    Đang thử code lại bằng cách nhân tay. Tức là nhân tay như thế nào, viết code nhân như thế.

Chia sẻ trang này

Advertising: Linux system admin | nukeviet | nukeviet 4 | Upload ảnh miễn phí