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

[integer]

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.

#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";

}

--------------------------------------------------
Xem các chủ đề cùng chuyên mục:

• Quản lý nhân sự 19/07/2009
• C++ tích 2 ma trận đây 25/05/2009
• Danh sách liên kết đơn - CTDL 28/03/2011
• ".:'Đề Kiểm Tra Học Kì':." 10/06/2009
• Xóa các khoảng trống trong chuỗi 21/07/2009
• Lập trình Shell !! 07/12/2009
• Tích của 2 ma trận 14/05/2009
• Bài Toán Xóa Dấu Cách 28/05/2009
• Giải tiếp các bài trong giáo trình !! 11/05/2009
• Thuật toán nhân số nguyên lớn 04/03/2011

+2 EXP

[integer]

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ó.

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;
}

+1 EXP

[jun_alone]

thế giải thik rõ hơn không?Hay copy mạng ve

[integer]

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ế.

+1 EXP