Trang 2 trên tổng số 4 Đầu tiênĐầu tiên 1234 Cuối cùngCuối cùng
Từ 11 tới 20 trên tổng số 33 kết quả

Đề tài: Thao tác số nguyên lớn - Trình bày thuật toán và cách thực hiện

  1. #11
    Ngày gia nhập
    09 2010
    Nơi ở
    Hà Nôi
    Bài viết
    464

    Mặc định Thao tác số nguyên lớn - Trình bày thuật toán và cách thực hiện

    Trích dẫn Nguyên bản được gửi bởi icttrack Xem bài viết
    thuật toán chia của anh peterdrew sẽ ko ổn trong trường hợp cả số bị chia lẫn số chia đều rất lớn. Khi ấy chúng ta sẽ không thể dùng phép chia thông thường (áp dụng cho các số thành phần của số bị chia) để chỉa cho số chia được vì bản thân phép chia đó đã không thể thực hiện với khả năng của tính toán chia của CPU.
    Với thuât toán tính toán mô phỏng nhân tay thế kia, thì chỉ cần mảng lưu trữ đủ lớn thì tính toán số lớn bao nhiêu cũng đc cả.
    Việc tính toán bản chất chung là chỉ tính toán trên từng chữ số thôi và máy tính quá dễ để tính toán.
    Phép +, -, *, / đếu thế cả.
    Phép +, - chỉ có cộng, trừ các chữ số lại với nhau.
    Phép nhân thì có nhân các chữ số thôi, và thêm phép cộng số lớn đã xây dựng ở trên nữa => rút cục chỉ là tính toán trên các chữ số
    Phép chia kiểu chi tay rút cuc ra cũng chỉ là tính toán trên các chữ số thôi.
    Em ko hiểu anh nói " phép chia thông thương là gì ở đây" trong khi thuật toán chia ko có 1 phép chia nào cả, chỉ là cộng trừ, nhân thôi.
    Em nghĩ ko có vấn đề về giới hạn khả năng tính toán của CPU đây cả.
    Chỉ cần để để lưu trữ mảng 2 số nguyên lớn ban đầu là tính đc.

  2. #12
    Ngày gia nhập
    06 2010
    Bài viết
    22

    Bài này chắc cũng lâu rồi nhưng mình cũng đóng góp ý kiến về phép chia như sau (hiện giờ mình mới nghỉ ra cách chia 1 dãy số dài với dãy số ngắn thôi)

    ĐK: Độ dài chuỗi a > 18 và độ dài chuỗi b < 18
    Tại sao mình lấy độ dài chuỗi > 18 và < 18
    Vì kiểu long cho phép chứa tối đa 19 chữ số nên mình lấy 18 chữ số hoàn toàn phù hợp để thực hiện phép chia ^^

    VD:
    Input a = 758426914638721943691284321
    Input b = 65536

    Step1: Lấy 18 chữ số đầu chia cho b
    758426914638721943 / 65536 = 11572676309794
    758426914638721943 % 65536 = 62359
    Chuỗi a còn 691284321

    Step2: Vì độ dài 62359 là 5 nên ta lấy thêm 13 số nữa. Nhưng do chuỗi ban đầu ta đã lấy 18 chữ số rồi nên bây giờ nó còn 9 (9 < 13). Ta lấy nốt phần còn lại của chuỗi số
    62359691284321 / 65536 = 951533375 dư 20321

    KQ: Phép chia trên calculator: 11572676309794951533375.310073853
    Phép chia tay bình thường: 11572676309794951533375 dư 20321

    Với phần dư còn lại là 20321 chúng ta có thể làm cách thông thường là thêm số 0 vào và chia chuỗi b. Nếu là chuỗi vô hạn thì giới hạn lại, còn không thì có KQ ^^

    Còn một số trường hợp khác thì tự suy nghĩ nha ^^!

    Rất vui nhận được ý kiến của các bạn!

    Còn đây là code demo làm vội trên C# ^^

    Visual C# Code:
    1.         public String Chia(String x, String y)
    2.         {
    3.             String result = "";
    4.             String remainder = "";    // Phần dư
    5.             Int64 denominator = Convert.ToInt64(y); // Mẫu số được Convert từ String sang Long
    6.  
    7.             while (x.Length > 0)
    8.             {
    9.                 Int32 pos = 18 - remainder.Length < x.Length ? 18 - remainder.Length : x.Length;
    10.                 Int64 numerator = Convert.ToInt64(remainder.ToString()
    11.                     + x.Substring(0, pos));
    12.                 /*
    13.                  * Tử số Convert từ String qua Long như sau:
    14.                  * * * Phần đầu là phần dư ghép vào phần sau
    15.                  * * * Phần sau là chuỗi được lấy từ vị trí 0 tới
    16.                  * * * * * Nếu độ dài chuỗi > 18 thì lấy đến vị trí 18
    17.                  * * * * * Ngược lại lấy tại vị trí đúng bằng độ dài chuỗi
    18.                  */
    19.  
    20.                 result += (numerator / denominator).ToString(); // Cộng dồn Tử số / Mẫu số và ép kiểu ra String
    21.                 remainder = (numerator % denominator).ToString(); // Phần dư là của Tử số % Mẫu số
    22.  
    23.                 if (x.Length > 9 && remainder.ToString().Length < denominator.ToString().Length)
    24.                     result = result.PadRight(result.Length + (denominator.ToString().Length - remainder.ToString().Length), '0');
    25.                 /*
    26.                  * Kiểm tra độ dài số dư có nhỏ hơn độ dài chuỗi y hay không.
    27.                  * Nếu nhỏ hơn thì thêm số 0 vào bên phải đúng bằng độ dài chuỗi y - độ dài số dư
    28.                  * Kiểm tra độ dài chuỗi x có lớn hơn 18 hay không
    29.                  * Để chắc chắn không thêm số 0 khi đang chia ở những dãy số cuối cùng
    30.                  */
    31.  
    32.                 x = x.Substring(pos); // Sau khi thực hiện phép toán / và % thì lấy chuỗi từ vị trí pos
    33.             }
    34.             return result +"." + ChiaLayDu(remainder.ToString(), y, 18 - remainder.Length); // Kết quả trả về là phần nguyên + "." + phần dư
    35.         }
    36.         private String ChiaLayDu(String x, String y, int Length)
    37.         {
    38.             return (Convert.ToInt64(x.PadRight(x.Length + Length, '0')) / Convert.ToInt64(y)).ToString();
    39.         }
    Đã được chỉnh sửa lần cuối bởi hotanvu : 13-06-2011 lúc 10:59 PM.

  3. #13
    Ngày gia nhập
    08 2011
    Nơi ở
    TPHCM quận Thủ Đức
    Bài viết
    48

    Đây là cách làm bài tổng của em, em còn newbie nên các bro thông cảm nếu bài của e rườm rà nhé ^^ Các bro góp ý hộ em nhé. Thank các bro
    C++ Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3. #include "iostream.h"
    4. #include "string.h"
    5. void xuatChuoi(unsigned char a[200]);
    6. void congChuoi(unsigned char a[200],unsigned char b[200]);
    7. void main()
    8. {
    9.    unsigned char a[200];
    10.    unsigned char b[200];
    11.    cout<<"Nhap vao so thu 1 : ";
    12.    gets(a);
    13.    cout<<"Nhap vao so thu 2: ";
    14.    gets(b);
    15.    congChuoi(a,b);
    16.    getch();
    17. }
    18. void congChuoi(unsigned char a[200],unsigned char b[200])
    19. {
    20.    int i,doDaiChuoi,soSanhChuoi;
    21.    unsigned char c[200];
    22.    unsigned char temp1[200];
    23.    unsigned char temp2[200];
    24.    int dem; //nho, vi du 9+9=18 viet 8 nho 1
    25.    soSanhChuoi= strlen(b)-strlen(a);
    26.    strrev(a);
    27.    strrev(b);
    28.    if(soSanhChuoi<0)
    29.    {
    30.       strcpy(temp1,a);
    31.       strcpy(temp2,b);
    32.       strcpy(a,temp2);
    33.       strcpy(b,temp1);
    34.       doDaiChuoi= strlen(b);
    35.       for(i=(doDaiChuoi-(strlen(b)-strlen(a)));i<doDaiChuoi;i++)
    36.       {
    37.       a[i]=48;
    38.       }
    39.    }
    40.    else if(soSanhChuoi>0)
    41.    {
    42.       doDaiChuoi= strlen(b);
    43.       for(i=(doDaiChuoi-(strlen(b)-strlen(a)));i<doDaiChuoi;i++)
    44.       {
    45.       a[i]=48;
    46.       }
    47.    }
    48.    else if(soSanhChuoi==0)
    49.    {
    50.       doDaiChuoi= strlen(b);
    51.    }
    52.    dem=0;
    53.    for(i=0;i<doDaiChuoi;i++)
    54.    {
    55.       if((a[i]+b[i])>105)
    56.       {
    57.          if(dem==1)
    58.          {
    59.             c[i]=(a[i]+b[i])-48-10+1;
    60.             if(((a[i]+b[i])-48+1)>57)
    61.             {
    62.                 dem=1;
    63.             }
    64.             else if(((a[i]+b[i])-48+1)<58)
    65.             {
    66.                 dem=0;
    67.             }
    68.          }
    69.          else if(dem==0)
    70.          {
    71.             c[i]=(a[i]+b[i])-48-10;
    72.             dem=1;
    73.          }
    74.       }
    75.       else if((a[i]+b[i])<106)
    76.       {
    77.          if(dem==1)
    78.          {
    79.             c[i]=(a[i]+b[i])-48+1;
    80.             if(((a[i]+b[i])-48+1)>57)
    81.             {
    82.                 dem=1;
    83.                 c[i] -=10;
    84.             }
    85.             else if(((a[i]+b[i])-48+1)<58)
    86.             {
    87.                 dem=0;
    88.             }
    89.          }
    90.          else if(dem==0)
    91.          {
    92.             c[i]=(a[i]+b[i])-48;
    93.             dem=0;
    94.          }
    95.       }
    96.    }
    97.    if( c[doDaiChuoi-1]==48)
    98.    {
    99.       c[doDaiChuoi]=49;
    100.       c[doDaiChuoi+1]=0;
    101.    }
    102.    else if( c[doDaiChuoi-1]!=48)
    103.    {
    104.       if(soSanhChuoi==0)
    105.       {
    106.         c[doDaiChuoi]=49;
    107.         c[doDaiChuoi+1]=0;
    108.       }
    109.       if(soSanhChuoi!=0)
    110.       {
    111.          c[doDaiChuoi]=0;
    112.       }
    113.    }
    114.    strrev(c);
    115.    cout<<"Vay tong la: ";
    116.    puts(c);
    117. }
    Đã được chỉnh sửa lần cuối bởi laksjd8979343 : 10-08-2011 lúc 10:24 AM.
    Kẻ nào bắt buộc nghe ai.
    Luôn luôn vẫn giữ ý sai của mình.

  4. #14
    Ngày gia nhập
    08 2011
    Nơi ở
    TPHCM quận Thủ Đức
    Bài viết
    48

    Đây là bài trừ, các bro vào chỉ giáo nhé ^^
    C++ Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3. #include "iostream.h"
    4. #include "string.h"
    5. void xuatChuoi(unsigned char a[200]);
    6. void truChuoi(unsigned char a[200],unsigned char b[200]);
    7. void xoaKiTu(unsigned char s[],unsigned char kt);
    8. void main()
    9. {
    10.    unsigned char a[200];
    11.    unsigned char b[200];
    12.    cout<<"Nhap vao so thu 1 : ";
    13.    gets(a);
    14.    cout<<"Nhap vao so thu 2 : ";
    15.    gets(b);
    16.    truChuoi(a,b);
    17.    getch();
    18. }
    19. void truChuoi(unsigned char a[200], unsigned char b[200])
    20. {
    21.    int i,doDaiChuoi,soSanhChuoi;
    22.    unsigned char c[200];
    23.    unsigned char temp1[200];
    24.    unsigned char temp2[200];
    25.    int dem,nhoHon; //nho 1
    26.    nhoHon=0;
    27.    soSanhChuoi= strlen(a)-strlen(b);
    28.    strrev(a);
    29.    strrev(b);
    30.    if(soSanhChuoi==0)
    31.    {
    32.       doDaiChuoi= strlen(a);
    33.       for(i=0;i<doDaiChuoi;i++)
    34.       {
    35.         if(a[i]==b[i])
    36.         {
    37.         }
    38.         else if(a[i]<b[i])
    39.         {
    40.             nhoHon=1;
    41.             goto nhan;
    42.         }
    43.         else if(a[i]>b[i])
    44.         {
    45.             nhoHon=0;
    46.             goto nhan2;
    47.         }
    48.       }
    49.    }
    50.    else if(soSanhChuoi<0)     // chuoi a nho hon chuoi b
    51.    {
    52.     nhan:
    53.         strcpy(temp1,a);
    54.         strcpy(temp2,b);
    55.         strcpy(a,temp2);
    56.         strcpy(b,temp1);
    57.         doDaiChuoi= strlen(a);
    58.     for(i=(doDaiChuoi-(strlen(a)-strlen(b)));i<doDaiChuoi;i++)
    59.     {
    60.         b[i]=48;
    61.         }
    62.         goto nhan2;
    63.    }
    64.    else if(soSanhChuoi>0)     //chuoi a lon hon chuoi b
    65.    {
    66.       doDaiChuoi= strlen(a);
    67.       for(i=(doDaiChuoi-(strlen(a)-strlen(b)));i<doDaiChuoi;i++)
    68.       {
    69.       b[i]=48;
    70.       }
    71.       goto nhan2;
    72.    }
    73.    nhan2:
    74.    dem=0;
    75.    for (i=0;i<doDaiChuoi;i++)
    76.    {
    77.     if(dem==0)
    78.         {
    79.              if(a[i]<b[i])
    80.              {
    81.               c[i]=(a[i]+49+57)-48-b[i];
    82.                   dem=1;
    83.              }
    84.              else if(a[i]>=b[i])
    85.              {
    86.               c[i]=a[i]-b[i]+48;
    87.                   dem=0;
    88.              }
    89.         }
    90.     else if(dem==1)
    91.         {
    92.              if(a[i]<=b[i])
    93.              {
    94.               c[i]=(a[i]+49+57)-48-b[i]-1;
    95.               dem=1;
    96.              }
    97.              else if(a[i]>b[i])
    98.              {
    99.               c[i]=a[i]-b[i]-1+48;
    100.                   dem=0;
    101.              }
    102.         }
    103.    }
    104.    if(dem==0)
    105.    {
    106.       if(soSanhChuoi<0)
    107.       {
    108.           c[doDaiChuoi]=45;
    109.       }
    110.       else if(soSanhChuoi>0)
    111.       {
    112.       }
    113.       else if(soSanhChuoi==0)
    114.       {
    115.           if(nhoHon==1)
    116.          {
    117.               c[doDaiChuoi]=45;
    118.          }
    119.          else if(nhoHon==0)
    120.          {
    121.          }
    122.       }
    123.    }
    124.    c[doDaiChuoi+1]=0;
    125.    strrev(c);
    126.    xoaKiTu(c,'0');
    127.    cout<<"Vay hieu la: ";
    128.    puts(c);
    129. }
    130. void xoaKiTu(unsigned char c[],unsigned char kt)
    131. {
    132.    int i,j;
    133.    int dem = 0;
    134.    for(i=1;i<strlen(c);)
    135.    {
    136.     if(c[i]=='0')
    137.         {
    138.             for(j=i;j<strlen(c)-1;j++)
    139.             {
    140.             c[j]=c[j+1];
    141.             }
    142.             c[strlen(c)-1]=0;
    143.         }
    144.         else if(c[i]!='0')
    145.         {
    146.             break;
    147.         }
    148.    }
    149. }
    Đã được chỉnh sửa lần cuối bởi laksjd8979343 : 10-08-2011 lúc 11:01 AM.
    Kẻ nào bắt buộc nghe ai.
    Luôn luôn vẫn giữ ý sai của mình.

  5. #15
    Ngày gia nhập
    04 2009
    Bài viết
    3

    Giải thuật chia: Thông thường, khi chia a với b, chúng ta thực hiện từ trái qua phải. Lần đầu tiên lấy nhóm có số chữ số bằng số chữ số của b, các lần sau đó chỉ lần lượt hạ một số xuống phần dư. Thay vì nhẩm xem được mấy lần, ở đây chỉ việc thử lần lượt từ 0 đến có thể. Vì chúng ta lưu ngược nên ta thực hiện từ phải qua trái. Hàm sau thực hiện chia a cho b, đặt kết quả vào c và phần dư vào r.
    C Code:
    1. pchar strdiv(const pchar a, const pchar b, const pchar c, const pchar r)
    2. {
    3.     int len = strlen(a), k = 0;
    4.     pchar temp = new char[len+1];     // Vùng nhớ lưu các kết quả trung gian
    5.     strcpy(temp,a);              // Ban đầu là bản sao của a
    6.     pchar p = temp + len - strlen(b);    // Cho p trỏ tới nhóm trong a có số chữ số bằng b
    7.     do                    // Lặp cho tới khi hạ hết các chữ số của a
    8.     {
    9.         c[k] = zero;            // Ban đầu đặt bằng '0' (tức = 0 lần)
    10.         while (strrcmp(p,b)>= 0)    // Nếu còn được lần nữa
    11.         {
    12.             c[k]++;        // Thì cộng thêm 1
    13.             strsub(p,b,r);        // Trừ bớt p đi 1 lần b
    14.             strcpy(p,r);        // Cập nhật lại hiệu
    15.         }
    16.         p--;                 // Chuẩn bị hạ 1 chữ số của a
    17.         k++;                 // Đã chia xong một nhóm
    18.         c[k]=0;                // Đặt null vào cuối
    19.     } while (p >= temp );            // Khi chưa hết các chữ số của a
    20.  
    21.     strrev(c,c);                // Vì thương được ghi thuận nên phải dảo lại
    22.     k = strlen(c)-1;            
    23.     while (c[k]== zero) k--;        // Loại bỏ '0' sinh ra vì nhóm đầu tiên có thể < b
    24.     c[++k]=0;                // Đặt null vào cuối xâu kết quả
    25.     delete temp;                // Xoá vùng nhớ
    26.     return c;                // Cho hàm trỏ tới thương
    27. }

    Theo tớ hiểu thì cách chia này của bạn là sử dụng lại phép trừ
    đầu tiên bạn lấy đủ độ dài của số bị chia với số chia để trừ xem được bao nhiêu lần, đó là chữ số đầu tiên của thương, sau đó lấy thêm số kết hợp với phần dư để lặp lại phép trừ như vậy có đúng không ?
    Thực ra cách chia này của bạn rất là hay vì nó có độ chính xác cao vì sử dụng lại phép trừ nhưng chắc chắn sẽ lâu hơn rất nhiều so với 1 cách chia như ta chia nháp ngoài giấy ở 1 số trường hợp như :

    9999999999999999999......9 / 1

    vậy thi ngay từ bước lặp đầu tiên của bạn bạn đã phải thực hiện 9 lần phép trừ và sau đó sẽ còn phải thực hiên bao nhiêu phép lặp 9 lần phép trừ

    Mình cũng đã cài đặt phép chia giống với phép chia mà ta thường làm trên giấy, nhưng không biết có còn lỗi j ảnh hưởng đến kết quả của phép tính không
    Nhưng mình rất thích cách này của bạn

  6. #16
    Ngày gia nhập
    02 2011
    Bài viết
    15

    Mặc định Số lớn, Bignum

    Mình vừa làm một bài về số lớn đã tham khảo một số nguồn, tiện đây chia sẻ cho ace đồng thời là mong mọi người có góp ý cho mình hoàn thiện hơn. Cơ bản đã xử lý được cộng trừ div mod nhân còn phép giai thừa sẽ được bổ sung trong thời gian ngắn nữa Mong được góp ý nhiều nhé.
    C Code:
    1. #include <conio.h>
    2. #include <stdio.h>
    3. #define n 254
    4. #include <string.h>
    5. #include <stdlib.h>
    6. ///////////////////////////Khai báo biến/////////////////////////////
    7. typedef struct
    8. {
    9.     int sign;// luu tru dau cua so lon, 0: duong,1:am
    10.     char val[n];//luu tru dau vao nhap dang chuoi ki tu
    11.     int _val[n];// luu tru so lon duoi dang mang so nguyen chuyen tu mang val
    12.     int len;// luu do dai cua so lon
    13. }bigNum;
    14. int i,j,maxa,mina;
    15. bigNum sb,mb,mub,db,rb,re;
    16. int convi(char c );
    17. ///////////////////////////Khai báo hàm///////////////////////////////////
    18. int convi(char c);
    19. bigNum sumBig(bigNum no1 ,bigNum no2);
    20. bigNum minusBig(bigNum no1,bigNum no2);
    21. bigNum multiBig(bigNum no1, bigNum no2);
    22. bigNum devideBig(bigNum no1, bigNum no2);
    23. void multiply10x(int x,int l,int resultBig[]);
    24. int length(int la, int re[]);
    25. int compare(bigNum no1,bigNum no2);
    26. void display(bigNum rb);
    27. ////////////////////////////định nghĩa hàm/////////////////////////////////////
    28. int convi(char c)       //Doi ki tu sang chu so
    29. {
    30.     switch (c)
    31.     {
    32.     case '0': return 0;  
    33.     case '1': return 1;  
    34.     case '2': return 2;  
    35.     case '3': return 3;  
    36.     case '4': return 4;  
    37.     case '5': return 5;  
    38.     case '6': return 6;  
    39.     case '7': return 7;  
    40.     case '8': return 8;  
    41.     case '9': return 9;  
    42.     default : return 0;  
    43.     }
    44. }
    45. //Hàm tính tổng số lớn
    46. bigNum sumBig(bigNum no1,bigNum no2)
    47. {  
    48.     if (no2.sign==1)
    49.     {
    50.         no2.sign=0;
    51.         return minusBig(no1,no2);
    52.     }
    53.     else
    54.     {
    55.     //Bước 1: Thực hiện phép cộng tương ứng các phần tử từ hàng đơn vị i=0,..,maxa
    56.         for(i=0;i<maxa;i++)
    57.         {
    58.             sb._val[i]=no1._val[i]+no2._val[i];
    59.         }
    60.         //Bước 2: Duyệt từ hàng đơn vị i=0,..,maxa tìm phần tử > 10
    61.         for (i=0;i<maxa;i++)
    62.         {
    63.             if(sb._val[i]>=10)
    64.             {
    65.                 sb._val[i+1]+=sb._val[i]/10;sb._val[i]=sb._val[i]%10;
    66.             }
    67.         }
    68.         // Tính độ dài của sb
    69.         if (sb._val[maxa]>0)
    70.         {
    71.             sb.len=maxa+1;
    72.         }
    73.         else sb.len=maxa;
    74.     }
    75.     sb.sign=rb.sign;// Gán biến dấu của rb cho sb trước sau đó mới gán rb=sb
    76.     rb=sb;
    77.     return rb;
    78. }
    79. //Hàm tính hiệu số lớn
    80. bigNum minusBig(bigNum no1,bigNum no2)
    81. {
    82.     //tinh hieu
    83.     mb.len=maxa;
    84.     if (no2.sign==1)
    85.     {
    86.         no2.sign=0;
    87.         return sumBig(no1,no2);
    88.     }
    89.     else
    90.     {   //Bước 1: Thực hiện phép trừ tương ứng các phần tử từ hàng đơn vị i=0,..,maxa
    91.         for(i=0;i<maxa;i++)
    92.         {
    93.             mb._val[i]=no1._val[i]-no2._val[i];
    94.         }
    95.         if (compare(no1,no2)==0) // Nếu 2 số bằng nhau thì kết quả là 0
    96.         {          
    97.             rb=mb;
    98.             rb.sign=0;
    99.             return rb;
    100.         }
    101.         if (compare(no1,no2)>0)
    102.         {
    103.         //Bước 2: Duyệt từ hàng đơn vị i=0,..,maxa tìm phần tử < 0
    104.             for (i=0;i<maxa;i++)
    105.             {
    106.                 if(mb._val[i]<0)
    107.                 {
    108.                     mb._val[i+1]-=1;mb._val[i]=mb._val[i]+10;
    109.                 }
    110.             }
    111.         }
    112.         else // Nếu no1<no2 thì dấu kết quả sẽ +1
    113.         {
    114.             rb.sign+=1;
    115.             return minusBig(no2,no1); //return bang -minusBig(no1,no2)         
    116.         }
    117.     }
    118.     mb.sign=rb.sign;
    119.     rb=mb;
    120.     return rb;
    121. }
    122. //Hàm tính tích số lớn
    123. bigNum multiBig(bigNum no1, bigNum no2)
    124. {
    125.     if (no1.sign!=no2.sign)
    126.     {
    127.         mub.sign=1;
    128.     } else mub.sign=0;
    129.     //Bước 1: Tính
    130.     for (i=0;i<maxa;i++)
    131.     {
    132.         for (j=0;j<maxa;j++)
    133.         mub._val[i+j]=mub._val[i+j]+ no1._val[i]*no2._val[j];
    134.     }
    135.     //Bước 2: Duyệt
    136.     for(i=0;i<mina+maxa;i++)
    137.     {
    138.         mub._val[i+1]+=mub._val[i]/10; mub._val[i]%=10;
    139.     }
    140.     // DO dai ket qua
    141.     if (mub._val[mina+maxa-1] !=0) mub.len=mina+maxa; else mub.len=mina+maxa-1;
    142.         return mub;
    143. }
    144. //Hàm tính thương số lớn
    145. bigNum devideBig(bigNum no1, bigNum no2)
    146. {
    147.     db.sign=0;
    148.     int k=0,h,dem=no1.len-no2.len;
    149.     bigNum dbTemp,reTemp;
    150.     //Khoi tao gia tri cho cac bien
    151.     for(j=0;j<n;j++)
    152.     {
    153.         dbTemp._val[j]=no2._val[j];
    154.         reTemp._val[j]=0;
    155.         re._val[j]=no1._val[j];
    156.     }
    157.     for(h=no1.len-no2.len;h>=0;h--)
    158.     {
    159.         for(j=0;j<no1.len;j++) dbTemp._val[j]=no2._val[j];
    160.         // Qua hàm multiply10x thì giá trị của dbTemp._val tăng gấp 10^h lần
    161.         multiply10x(h,length(no1.len,dbTemp._val),dbTemp._val);
    162.         re.len=length(no1.len,re._val);// độ dài tạm thời của biến re
    163.         dbTemp.len=length(no1.len,dbTemp._val);//độ dài tạm thời của biến dbTemp
    164.         while(compare(dbTemp,re)<=0)
    165.         {
    166.             reTemp=minusBig(re,dbTemp);
    167.             for (j=0;j<no1.len;j++)
    168.             {
    169.                 re._val[j]=reTemp._val[j];
    170.                 reTemp._val[j]=0;
    171.             }
    172.             re.len=length(no1.len,re._val);
    173.             db._val[dem]=db._val[dem]+1;
    174.         }
    175.         for(j=0;j<no1.len;j++) dbTemp._val[j]=0;
    176.         dem=dem-1;
    177.     }
    178.     db.len=no1.len-no2.len+1;
    179.     return db;
    180.  
    181. }
    182. // Hàm gán giá trị gấp 10^x lần cho giá trị ban đầu
    183. void multiply10x(int x,int l,int resultBig[])
    184. {
    185.     int j;
    186.     for (j=l;j>=0;j--)
    187.         resultBig[j+x]=resultBig[j];
    188.     for(j=0;j<x;j++)
    189.         resultBig[j]=0;
    190. }
    191. int length(int la, int re[])
    192. {
    193.     int j;
    194.     for(j=la;j>=0;j--)
    195.     {
    196.         if (re[j]!=0) return j+1;
    197.     }
    198.     return 0;
    199. }
    200. int compare(bigNum no1,bigNum no2)
    201. {
    202.     if (no1.len>no2.len) return 1;
    203.     if (no1.len<no2.len) return -1;
    204.     if (no1.len==no2.len)
    205.     {
    206.         for(j=no1.len;j>=0;j--)
    207.         {
    208.             if (no1._val[j]>no2._val[j]) return 1;
    209.             if (no1._val[j]<no2._val[j]) return -1;
    210.         }
    211.     }
    212.     return 0;
    213. }
    214. //Hàm hiển thị
    215. void display(bigNum rb)
    216. {
    217.     if (rb.len==0) printf("0");
    218.     while (rb._val[rb.len-1]==0&& rb.len>1)
    219.     {
    220.         rb.len=rb.len-1;
    221.     }
    222.     if (rb.sign%2==1)
    223.     {
    224.         printf("-");
    225.     }
    226.     for (i=rb.len-1;i>=0;i--)
    227.     {
    228.         printf("%d",rb._val[i]);       
    229.     }  
    230.     printf("\n");
    231.     }
    232. ////////////////////////////Hàm main//////////////////////////////////////
    233. void main()
    234. {
    235.     bigNum no1,no2;
    236.     int bnext;//bien logic vong lap while
    237.     do
    238.     {
    239.         no1.sign=0;no2.sign=0;
    240.         printf("a=");
    241.         scanf("%s",&no1.val);
    242.         printf("b=");
    243.         scanf("%s",&no2.val);
    244.         for (i=0;i<n;i++)
    245.         {
    246.             sb._val[i]=0;
    247.             mb._val[i]=0;
    248.             mub._val[i]=0;
    249.             re._val[i]=0;
    250.             db._val[i]=0;
    251.         }
    252.         no1.len=strlen(no1.val);
    253.         no2.len=strlen(no2.val);
    254.         //Chuyển từ mảng xâu kí tự sang mảng số nguyên
    255.         for (i=0;i<no1.len;i++)
    256.         {
    257.             no1._val[i]=convi(no1.val[no1.len-1-i]);
    258.         }
    259.         for (i=0;i<no2.len;i++)
    260.         {
    261.             no2._val[i]=convi(no2.val[no2.len-1-i]);
    262.         }
    263.         //Kiem tra dau
    264.         if(no1.val[0]=='-')
    265.         {
    266.             no1.sign=1;
    267.             no1.len-=1;
    268.         }
    269.         if(no2.val[0]=='-')
    270.         {
    271.             no2.sign=1;
    272.             no2.len-=1;
    273.         }
    274.         // Tính độ dài no1, no2
    275.         while(no1._val[no1.len-1]==0&&no1.len>1)
    276.         {
    277.             no1.len-=1;
    278.         }
    279.         while(no2._val[no2.len-1]==0&&no2.len>1)
    280.         {
    281.             no2.len-=1;
    282.         }
    283.         maxa= strlen(no1.val)>strlen(no2.val)?strlen(no1.val):strlen(no2.val);
    284.         mina=strlen(no1.val)+strlen(no2.val)-maxa;
    285.         //Khởi tạo giá trị ban đầu cho mảng giá trị no1,no2
    286.         for (i=no1.len;i<=maxa;i++)
    287.             no1._val[i]=0;
    288.         for (i=no2.len;i<=maxa;i++)
    289.             no2._val[i]=0;
    290.         multiBig(no1,no2);
    291.         if (no1.sign==0)
    292.         {
    293.             rb.sign=0;
    294.             sumBig(no1,no2);
    295.             printf("No1 add No2 is: ");
    296.             display(rb);rb.sign=0;
    297.             minusBig(no1,no2);
    298.             printf("No1 minus No2 is : ");
    299.             display(rb);
    300.         }
    301.         else
    302.         {
    303.             rb.sign=1; 
    304.             no1.sign=0;
    305.             minusBig(no1,no2);
    306.             printf("No1 add No2 is: ");
    307.             display(rb);rb.sign=1; 
    308.             sumBig(no1,no2);
    309.             printf("No1 minus No2 is : ");
    310.             display(rb);
    311.         }
    312.         printf("No1 multiply with No2 is : ");
    313.         display(mub);
    314.         if (no2.len== 1 &&no2._val[0]==0)
    315.         {
    316.             printf("Cant devide by zero\n");
    317.         }
    318.         else
    319.         {
    320.             if (compare(no1,no2)==0)
    321.             {
    322.                 printf("No1's abs devide by No2's abs is: 1");
    323.                 printf("\n");
    324.                 printf("Remainder: 0");
    325.                 printf("\n");
    326.             }
    327.             if (compare(no1,no2)==1)
    328.             {
    329.                 devideBig(no1,no2);
    330.                 printf("No1's abs devide by No2's abs is: ");
    331.                 display(db);
    332.                 printf("Remainder: ");
    333.                 display(re);
    334.             }
    335.             else
    336.             {
    337.                 printf("Cant calculate |a| : |b|\n");
    338.             }
    339.         }
    340.         printf("-----------------------------\n");
    341.         printf("Do you want to continue (1/0)");
    342.         fflush(stdin);
    343.         scanf("%d",&bnext);
    344.         if (bnext!=1)
    345.         {
    346.             return;
    347.         }
    348.     } while (bnext==1);
    349.  
    350. }
    351. ///////////////The End. Daniel wu KSTNTT K54 11/2011 /////////////////

  7. #17
    Ngày gia nhập
    06 2012
    Bài viết
    4

    xin chào mọi người,em vừa thử ứng dụng thuật toán như trên vào tính 1 số fibonaxi f(100),tuy nhiên bài của em chỉ chạy được đúng đến n=7,còn từ n=8 trở đi thì lỗi.Mong mọi người chỉ giúp em sai ở đâu,cảm ơn nhiều

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. //#include <string.h>
    4. #define zero '0'
    5. typedef char* pchar;
    6. int val(char chr) {return chr-zero;}
    7. char chr(int num) {return num + zero;}
    8. int strlen(const pchar a)      
    9. { pchar p = a;     while (*p) p++; return p-a;}
    10.  
    11. pchar strcpy (const pchar dest, const pchar src);
    12. pchar strrev( const pchar src, const pchar dest);
    13. char chradd(char a, char b, int &carry)  ;
    14. pchar stradd (const pchar a, const pchar b, const pchar c) ;
    15.  
    16. int main(){
    17. char a[]="1",b[]="1";
    18. char c[100],da[100],db[100];
    19. int n;
    20. scanf("%d",&n);
    21. for(int i=0;i<n-2;i++){
    22.         stradd(a,b,c);
    23.         strcpy(a,b);
    24.         strcpy(b,c);
    25.         }
    26.  
    27.         printf("%s",c);
    28.  
    29. getch();
    30. }
    31.  
    32. char chradd(char a, char b, int &carry)  
    33. {
    34.     int temp = val(a) + val(b) + carry;
    35.     carry = temp/10;
    36.     return chr(temp %10);
    37. }
    38. pchar stradd (const pchar a, const pchar b, const pchar c)
    39. {
    40.     int i = 0, carry = 0;  
    41.     while(a[i] && b[i]) c[i++] = chradd(a[i],b[i],carry);
    42.     if(a[i])                            
    43.         while (a[i]) c[i++] = chradd(a[i],zero,carry);
    44.     else                        
    45.         while (b[i]) c[i++] = chradd(b[i],zero,carry);
    46.     if (carry) c[i++] = chr(carry);            
    47.     c[i] = 0;                
    48.     return c;
    49. }
    50.  
    51. pchar strcpy (const pchar dest, const pchar src)
    52. {
    53.     int k = 0;
    54.     while (src[k]) dest[k] = src[k++];
    55.     dest[k] = 0;
    56.     return dest;
    57. }
    58. pchar strrev( const pchar src, const pchar dest)
    59. {
    60.     strcpy(dest,src);  
    61.     int len = strlen(src);
    62.     for (int k = 0; k < len/2; k++)
    63.         {
    64.             char temp = dest[k];
    65.             dest[k] = dest[len-k-1];
    66.             dest[len-k-1] = temp;
    67.         }
    68.     return dest;
    69. }

  8. #18
    Ngày gia nhập
    04 2013
    Bài viết
    2

    mình tìm code bài này đã lâu nhưng k thấy một ai làm với số âm cả
    đại loại là -4+5=1
    -4-5=-9
    4-10=-6
    4*(-3)=-12
    4/(-2)=-2
    mong các bạn giúp tks all

  9. #19
    Ngày gia nhập
    12 2012
    Nơi ở
    TIN5A - UNETI
    Bài viết
    167

    cũng giông như số dương mà bạn chỉ đổi dấu của số nguyen lớn là được

  10. #20
    Ngày gia nhập
    11 2014
    Bài viết
    6

    Các bạn giúp mình nhé!

    Giải quyết bài toán căn bậc 3 và lấy sau dấu phẩy chính xác n số nhập từ bàn phím:
    Ví dụ ta có 1 số : Căn bậc 3 của A= B.122321434546576787686786574563452343243546576587 6867863452353465467576576567…..n
    Làm thế nào để giải quyết bài toán này:
    Và biểu diễn nó trên màn hình

Các đề tài tương tự

  1. Thuật Toán Eratosthenes về số nguyên tố như thế nào?
    Gửi bởi alibaba314 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 10-06-2016, 02:30 PM
  2. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  3. Bài tập C++ chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được
    Gửi bởi nghiapro512 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-01-2011, 02:14 PM
  4. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM
  5. Hàng đợi | Thuật toán in đảo số nguyên n
    Gửi bởi hoangchauhamy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 18-05-2009, 08:37 PM

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn