Trang 1 trên tổng số 4 123... Cuối cùngCuối cùng
Từ 1 tới 10 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. #1
    Ngày gia nhập
    05 2010
    Bài viết
    265

    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

    Dùng xâu ký tự để diễn số nguyên lớn với cấu trúc như sau:

    Các chữ số được viết theo chiều ngược lại. Nếu số nguyên có n chữ số thì xâu tương ứng có n+2 byte (phía cuối thêm 2 byte, byte thứ nhất chứa dấu '-' nếu đó là số âm, hoặc null nếu số dương, byte cuối cùng là null). Ví dụ, số a = 12345678901234567890 được biểu diễn bởi xâu xa = "09876543210987654321"nulnul, còn b = -12345678901234567890 được biểu diễn bởi xâu xb = "09876543210987654321-"nul. Để xác định số -a ta chỉ việc thay null đầu tiên bởi '-' , và –b nhận được bằng cách thay '-' bởi null.

    Việc biểu diễn ngược đó thuận tiện trong các thao tác về cộng, trù, nhân chia mà không phải chèn thêm '0' (leading zero). Sau đây là một số giải thuật về cộng, trù, nhân chia các số không âm (Các số âm sẽ được nói sau). Trước hết, ta cần định nghĩa:

    C Code:
    1.     #define zero '0'
    2.     typedef char* pchar;
    Một số hàm liên quan đến cộng, trừ, nhân hai ký tự biểu thị số:
    C Code:
    1. int val(char chr) {return chr-zero;} // Giá trị tương ứng với ký tự chr biểu thị số
    2. char chr(int num) {return num + zero;} // Ký tự tương ứng với giá trị num
    3. int strlen(const pchar a)        // Độ dài của xâu
    4. { pchar p = a;     while (*p) p++; return p-a;}
    Giải thuật cộng: Thông thường, khi cộng hai số có nhiều chữ số, chúng ta thực hiện từ phải qua trái. Với mỗi lần cộng, kết quả của nó còn được cộng với giá trị nhớ của lần trước đó và đồng thời cũng xác định giá trị nhớ mới. Ở đây, vì các số được lưu theo chiều ngược lại nên chúng ta thực hiện từ trái qua phải, tức là từ đầu đến cuối xâu. Do đó code có thể là:
    C Code:
    1. char chradd(char a, char b, int &carry)  // Cộng hai chữ số
    2. {
    3.     int temp = val(a) + val(b) + carry;
    4.     carry = temp/10;
    5.     return chr(temp %10);
    6. }
    7. pchar stradd (const pchar a, const pchar b, const pchar c) // Cộng hai số có nhiều chữ số
    8. {
    9.     int i = 0, carry = 0;    //Ban đầu, nhớ bằng 0
    10.     while(a[i] && b[i]) c[i++] = chradd(a[i],b[i],carry); // Cộng lần lượt từ đầu đến cuối
    11.     if(a[i])                             // Nếu xâu a dài hơn xâu b
    12.         while (a[i]) c[i++] = chradd(a[i],zero,carry); // Cộng tiếp a[i] với 0
    13.     else                            // Nếu xâu b dài hơn
    14.         while (b[i]) c[i++] = chradd(b[i],zero,carry); // Cộng tiếp b[i] với 0
    15.     if (carry) c[i++] = chr(carry);            //Nếu cuối cùng mà nhớ khác 0
    16.     c[i] = 0;                    // Đặt null vào cuối
    17.     return c;
    18. }
    Giải thuật trừ: Giống như cộng, chúng ta cũng thực hiện từ phải qua trái. Với mỗi lần trừ, đề phòng chữ số của số bị trừ nhỏ hơn nên ta cứ vay tạm một chục. Nếu lần trước đã vay rồi thì lần này phải trừ đi. Nhưng chỉ đáng vay nếu kết quả sau khi trừ là bé hơn 10, còn lớn hơn 10 là không phải vay. Dưới đây ta xem rằng a >= b:
    C Code:
    1. char chrsub(char a, char b, int &carry)
    2. {
    3.     int temp = 10 + val(a) - val(b) - carry; // Cứ vay 10 rồi trừ đi (kể cả cho nhớ cũ)
    4.     carry = 1 - temp/10;            // Nếu sau trừ mà >= 10 thì không phải vay
    5.     return chr(temp %10);
    6. }
    7. pchar strsub (const pchar a, const pchar b, const pchar c) // Trừ số có nhiều chữ số
    8. {
    9.     int i = 0, carry = 0;    
    10.     while (a[i] && b[i]) c[i++] = chrsub(a[i],b[i],carry);
    11.     while (a[i]) c[i++] = chrsub(a[i],zero,carry);
    12.     while (i > 0 && c[--i] == zero);    
    13.     c[++i]=0;
    14.     return c;
    15. }
    Như chúng ta vẫn làm, kết quả của a – b với a < b chính là –(b – a), vì vậy cần viết hàm so sánh. Số nào có nhiều chữ số thì số đó lớn hơn. Khi hai số có số các chữ số khác nhau thì sự so sánh này được thực hiện từ phải qua trái do chúng ta lưu ngược lại.
    C Code:
    1. int strrcmp(const pchar a, const pchar b)
    2. {
    3.     int aj = strlen(a), bj = strlen(b);
    4.     while (aj && a[--aj]== zero);     //Bỏ qua các '0' ở cuối của a
    5.     while (bj && b[--bj]== zero);     //Bỏ qua các '0' ở cuối của b
    6.     if (aj > bj) return 1;            //Nếu xâu a dài hơn thì a > b
    7.     if (aj < bj) return -1;            //Nếu xâu a ngắn hơn thì a < b
    8.     while (aj && a[aj]==b[aj])aj--;    // Nếu độ dài như nhau thì tìm đến chữ số khác nhau đầu tiên
    9.     return a[aj] - b[aj]; // So sánh hai chữ số đó, cùng lắm thì so các chữ số đầu tiên.
    10. }
    Một số hàm bổ trợ khác:
    C Code:
    1. pchar strcpy (const pchar dest, const pchar src) // Sao chép src vào dest
    2. {
    3.     int k = 0;
    4.     while (src[k]) dest[k] = src[k++];
    5.     dest[k] = 0;
    6.     return dest;
    7. }
    8. pchar strrev( const pchar src, const pchar dest) //Hàm trỏ tới xâu dest, là đảo ngược của xâu src
    9. {
    10.     strcpy(dest,src);    // Khi dest trùng với src vẫn dùng được
    11.     int len = strlen(src);
    12.     for (int k = 0; k < len/2; k++)
    13.         {
    14.             char temp = dest[k];
    15.             dest[k] = dest[len-k-1];
    16.             dest[len-k-1] = temp;
    17.         }
    18.     return dest;
    19. }
    Giải thuật nhân: Thông thường, khi nhân a với b, chúng ta thực hiện từ phải qua trái. Mỗi lần sẽ nhân một chữ số của b với số a và đặt kết quả dịch sang trái 1 chữ số. Nhưng trong mỗi lần đó chúng ta lại lần lượt nhân từng chữ số của a với chữ số nói trên của b. Cũng như phép cộng, kết quả cũng phụ thuộc việc nhớ của lần nhân trước và xác định giá trị nhớ mới. Việc nhận này được thực hiện từ trái qua phải đó.
    C Code:
    1. char chrmul(char a, char b, int &carry) // Nhân hai chữ số
    2. {
    3.     int temp = val(a) * val(b) + carry;
    4.     carry = temp/10;
    5.     return chr(temp %10);
    6. }
    7. pchar strmul(const pchar a, const pchar b, const pchar c)     // Nhân hai số có nhiều chữ số, c=a*b
    8. {
    9.     int jb = 0;
    10.     pchar temp = new char[strlen(a)+2];     // Vùng nhớ lưu kết quả trung gian khi nhân a với
    11.     do                    // từng chữ số của b.
    12.     {
    13.         int ja = 0, carry = 0;
    14.         do                    //Lần lượt với từng chữ số của a
    15.         {
    16.             temp[ja++] = chrmul(a[ja],b[jb],carry);  // Có tăng ja đấy nhé
    17.         }    while (a[ja]);
    18.  
    19.         if (carry) temp[ja++] = chr(carry); // Cuối mỗi lượt nhân a với 1 chữ số của b
    20.         temp[ja]=0;                // Đặt null vào temp
    21.  
    22.         if (jb==0) strcpy(c,temp);        // Với lượt nhân đầu tiên
    23.         else stradd(c+jb,temp,c+jb);        // Đây chính là đặt kết quả dịch 1 chữ số đó
    24.         jb++;                    // Chuyển sang chữ số kế tiếp của b
    25.  
    26.     } while (b[jb]);                // Khi xâu b vẫn còn
    27.     delete temp;                // Giải phóng vùng nhớ lưu kết quả trung gian
    28.     return c;                // Cho hàm trỏ tới c
    29. }
    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. }

    Sau đây là một số lời gọi kiểm chứng. Do các hàm của ta thao tác với xâu ghi ngược nên chúng ta phải đảo ngược chúng trước. Tất nhiên việc này chỉ sử dụng khi ta thử thôi, còn sau này khi đã viết thành class hoàn chỉnh (dùng cho các số âm) thì các hàm input(), output() sẽ làm việc đó.
    C Code:
    1. void main()
    2. {
    3.     char a[] = "7650035435430002526471232732", b[] = "19153500423021";
    4.     char c[100], r[100], da[100],db[100], dc[100];
    5.  
    6.     strrev(a,da); strrev(b,db);             // da và db là đảo ngược của a và b
    7.     stradd(da,db,c);                // c = da + db
    8.     printf("\n%s + %s = %s\n",a, b, strrev(c,c));    // Vì c là đảo ngược
    9.  
    10.     strsub(da,db,c);                // c = da – db, đừng lấy db – da nhé
    11.     printf("\n%s - %s = %s\n",a, b, strrev(c,c));
    12.  
    13.     strmul(da,db,c);                // c = da*db
    14.     printf("\n%s * %s = %s\n",a, b, strrev(c,c));
    15.  
    16.     strrev(c,dc);                    // Do c bị đảo ở lệnh printf(), nên đảo lại
    17.     stradd(dc,"123",dc);                // Cộng thêm "321 vào dc
    18.     strdiv(dc,db,da,r);                // da = dc/db <=> da = c/b đó
    19.     strrev(da,da);        
    20.     strrev(r,r);
    21.     strrev(dc,dc);
    22.     printf("\n%s / %s = %s du %s\n,dc, b, da, r); // Chắc chắn dư là 321
    23. }
    Kết quả:

    Output Code:
    1. 7650035435430002526471232732 + 19153500423021 = 7650035435430021679971655753
    2.  
    3. 7650035435430002526471232732 - 19153500423021 = 7650035435429983372970809711
    4.  
    5. 7650035435430002526471232732 * 19153500423021 = 146524956948634193321801854882749341523372
    6.  
    7. 14652531001826721947557587760652816748690988242741523693 / 19153546575700423021 = 765003543543000252657567909471232732 du 321

  2. #2
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Mặc định Thao tác số nguyên lớn được lưu dưới dạng mảng

    Với vấn đề lưu số nguyên lớn dưới dạng mảng các số, mình xin đóng góp như sau:
    Các chữ số được lưu theo chiều ngược lại và có -1 ở cuối để đánh dấu sự kết thúc. Ngoài ra còn thêm 0 hoặc -1 vào cuối để phân biệt không âm và âm. Hơn nữa, đề phòng rác trong bộ nhớ nên còn thêm 1 giá trị 0 nữa vào cuối mảng. Ví dụ, 12345 được lưu là 54321-100, còn -12345 được lưu là 54321-1-10. Số 0 được lưu là 0-100, số -1 là 1-1-10. Giải thuật cộng, trừ, nhân, chia (với các số dương) được mô phỏng theo các giải thuật xử lý xâu mà mình đã trình bày ở bài trước. So với lưu trữ dạng xâu ký tự, mình nhận thấy có hai nhược điểm. Thứ nhất là các thao tác phức tạp hơn, thứ hai là tốn bộ nhớ hơn. Khi code hàm nhập số nguyên lớn, mình xử lý theo kiểu char nên tránh được việc hỏi số chữ số cần nhập và không có khoảng cách giữa các chữ số, nhờ đó việc nhập được tự nhiên như hàm scanf(). Mặc dù có hai nhược điểm nói trên, nhưng mình cũng post lên đây nhằm tranh thủ sự góp ý của các bạn.

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #define max 200
    4.  
    5. typedef int songuyen[max];
    6.  
    7. void daonguoc(songuyen &a) // Đảo ngược
    8. {
    9.     int n = 0;
    10.     while (a[n]>=0) n++;
    11.     for (int k=0; k < n/2; k++)
    12.     {
    13.         int t = a[k];
    14.         a[k] = a[n-1-k];
    15.         a[n-1-k] = t;
    16.     }
    17. }
    18.  
    19. void xoakhongcuoi(songuyen &a) //Xoá các chữ số 0 ở cuối sau khi đã đảo ngược
    20. {
    21.     int n = 0;
    22.     while (a[n]>= 0) n++;
    23.     if (a[n-1]> 0 || n==1) return;
    24.     int p = n;
    25.     while (p && a[p-1]==0) p--;
    26.     if (p==0) p++;
    27.     a[p]= -1;
    28.     a[p+1]= a[n+1];
    29.     a[p+2]= a[n+2];
    30. }
    31.  
    32. void hienthi(songuyen a, char *s = "\n") //Hiển thị số
    33. {
    34.     int n = 0;
    35.     while (a[n]>=0) n++;
    36.     if (a[n+1] == -1) printf("%c",'-');
    37.     while (n) {printf("%c",a[n-1]+'0'); n--;}
    38.     printf("%s",s);
    39.    
    40. }
    41.  
    42. void nhapsn(songuyen &a, char ten) // Nhập số nguyên lớn
    43. {
    44.     printf("\nMoi ban nhap so nguyen %c: ", ten);
    45.     int n = 0, sign = 0; char ch;
    46.     do
    47.         {
    48.             ch = getch();
    49.             if (ch == '-' && n == 0 && !sign)
    50.                 {
    51.                     sign = 1;
    52.                     printf("%c",ch);
    53.                 }
    54.             else
    55.                 if ('0' <= ch && ch <= '9')
    56.                 {
    57.                     a[n++] = ch - '0';
    58.                     printf("%c",ch);
    59.                 }
    60.                 else
    61.                     if (ch == '\b' && n>=0)
    62.                         {
    63.                             printf("%c%c%c",ch,32,ch);
    64.                             if (n) n--;
    65.                             if (n==0) sign = 0;
    66.                         }
    67.         } while (ch != '\r' || n == 0);
    68.         printf("\n");
    69.  
    70.         a[n++] = -1;
    71.         if (sign) a[n++]=-1;
    72.         a[n++] = 0;
    73.         daonguoc(a);
    74.         xoakhongcuoi(a);
    75. }
    76.  
    77. int sosanh(const songuyen a, const songuyen b, int p = 0) //So sánh
    78. {
    79.     int aj = 0, bj = 0;
    80.     while (a[aj++] != -1);  
    81.     while (b[bj++] != -1);
    82.     if (aj - p > bj) return 1;
    83.     if (aj - p < bj) return -1;
    84.     while (bj && a[p+bj]==b[bj])bj--;
    85.     return a[p+bj] - b[bj];
    86. }
    87.  
    88. int congchuso(int a, int b, int &carry)  // Cộng hai chữ số
    89. {
    90.     int temp = a + b + carry;
    91.     carry = temp/10;
    92.     return temp %10;
    93. }
    94.  
    95. void cong (const songuyen a, const songuyen b, songuyen &c, int p = 0) // Cộng số lớn
    96. {
    97.     int i, carry = 0;  
    98.     for (i = 0; i < p; i++) c[i] = a[i];
    99.     i = 0;
    100.     while(a[i+p]!=-1 && b[i]!=-1) c[p+i++] = congchuso(a[p+i],b[i],carry);
    101.     if(a[i+p]!=-1)                            
    102.         while (a[i+p]!=-1) c[p+i++] = congchuso(a[p+i],0,carry);
    103.     else                            
    104.         while (b[i]!=-1) c[p+i++] = congchuso(b[i],0,carry);
    105.     if (carry) c[p+i++] = carry;
    106.     c[p+i] = -1;
    107.     c[p+i+1] = 0;                  
    108. }
    109.  
    110. int truchuso(int a, int b, int &carry)// Trừ hai chữ số
    111. {
    112.     int temp = 10 + a - b - carry;
    113.     carry = 1 - temp/10;          
    114.     return temp %10;
    115. }
    116.  
    117. void tru (const songuyen a, const songuyen b, songuyen &c, int p=0)//Trừ số lớn
    118. {
    119.     int i, carry = 0;  
    120.     for (i = 0; i < p; i++) c[i] = a[i];
    121.     i = 0;
    122.     while (a[p+i]!=-1 && b[i]!=-1) c[p+i++] = truchuso(a[p+i],b[i],carry);
    123.     while (a[p+i]!=-1) c[p+i++] = truchuso(a[p+i],0,carry);
    124.     c[p+i++]=-1;c[p+i++] = 0;
    125.     xoakhongcuoi(c);
    126. }
    127.  
    128. int nhanchuso(int a, int b, int &carry) //Nhân 2 chữ số
    129. {
    130.     int temp = a*b + carry;
    131.     carry = temp/10;
    132.     return temp %10;
    133. }
    134.  
    135. void saochep(songuyen &b, const songuyen a)//Sao chép
    136. {
    137.     int n=0;
    138.     while (a[n] != -1) b[n] = a[n++];
    139.     while (a[n] == -1) b[n] = a[n++];
    140.     b[n] = 0;
    141. }
    142.  
    143. void nhan(const songuyen a, const songuyen b, songuyen &c)  //Nhân hai số lớn
    144. {
    145.     int jb = 0;
    146.     songuyen temp;
    147.     do                  
    148.     {
    149.         int ja = 0, carry = 0;
    150.         do                  
    151.         {
    152.             temp[ja++] = nhanchuso(a[ja],b[jb],carry);  
    153.         }   while (a[ja]!=-1);
    154.  
    155.         if (carry) temp[ja++] = carry;
    156.         temp[ja]= -1; temp[ja+1]= 0;            
    157.         if (jb==0) saochep(c,temp);
    158.         else cong(c,temp,c,jb);
    159.         jb++;                  
    160.  
    161.     } while (b[jb]!=-1);                
    162. }
    163.  
    164. void chia(const songuyen a, const songuyen b, songuyen &c, songuyen &r)//Chia hai số lớn
    165. {
    166.     int ja=0, jb=0,k = 0;
    167.     while (a[ja] != -1) ja++;
    168.     while (b[jb] != -1) jb++;
    169.     songuyen temp;  
    170.     saochep(temp,a);
    171.     int jt = ja - jb;
    172.     do                
    173.     {
    174.         c[k] = 0;            
    175.         while (sosanh(temp,b,jt)>= 0)    
    176.         {
    177.             c[k]++;
    178.             tru(temp,b,r,jt);      
    179.             saochep(temp,r);
    180.         }
    181.         jt--;              
    182.         k++;                
    183.     } while (jt >= 0 );          
    184.     c[k]=-1; c[k+1]=0;
    185.     daonguoc(c);
    186.     xoakhongcuoi(c);
    187. }
    188.  
    189. void main()
    190. {
    191.     songuyen a, b, c,r;
    192.     nhapsn(a,'a'); nhapsn(b,'b');
    193.     cong(a,b,c); hienthi(a," + "); hienthi(b," = "); hienthi(c);
    194.     tru(a,b,c); hienthi(a," - "); hienthi(b," = "); hienthi(c);
    195.     nhan(a,b,c); hienthi(a," * "); hienthi(b," = "); hienthi(c);
    196.     chia(a,b,c,r); hienthi(a," / "); hienthi(b," = "); hienthi(c," du "); hienthi(r);
    197. }
    Dưới đây là kết quả minh họa:
    Output Code:
    1. Moi ban nhap so nguyen a: 001234567891234567890123
    2.  
    3. Moi ban nhap so nguyen b: 0012345678
    4. 1234567891234567890123 + 12345678 = 1234567891234580235801
    5. 1234567891234567890123 - 12345678 = 1234567891234555544445
    6. 1234567891234567890123 * 12345678 = 15241577654320997640597938394
    7. 1234567891234567890123 / 12345678 = 100000007390000 du 7470123

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    42

    theo mình làm số âm hay số dương thì dùng 1 biến bool để kiểm tra là được
    bài này mình làm trong OOP các bạn xem qua
    còn phép chia nó hơi bị sao ý mình mới xóa

    file huge.h

    C++ Code:
    1. #include <iostream>
    2. #include <conio.h>
    3. using namespace std;
    4. class solon
    5. {
    6. private:
    7.     int *so;
    8.     int sopt;
    9.     bool soam;
    10. public:
    11.     solon(){so=new int[100];soam=false;}
    12.     void ChuyenSo(int mang[],char so[])
    13.     {
    14.         for(int i=0;i<strlen(so);i++)
    15.             {
    16.                 char tam=so[strlen(so)-i-1];
    17.                 mang[i]=atoi(&tam);
    18.             }
    19.     }
    20.     friend ostream & operator <<(ostream &out,solon &p);
    21.     friend istream & operator >>(istream &cn,solon &p);
    22.     ///////////////////////////////////////////////////////////////////
    23.     //Phép cộng
    24.     ///////////////////////////////////////////////////////////////////
    25.     solon operator+(solon p)
    26.     {
    27.         solon kq;
    28.         if(p.sopt>sopt)
    29.         {
    30.             int m=p.sopt-sopt;
    31.             for(int i=1;i<=m;i++)
    32.             {
    33.                 so[sopt-1+i]=0;
    34.             }
    35.             sopt=p.sopt;
    36.         }
    37.         else
    38.         {
    39.             int m=sopt-p.sopt;
    40.             for(int i=1;i<=m;i++)
    41.             {
    42.                 p.so[p.sopt-1+i]=0;
    43.             }
    44.             p.sopt=sopt;
    45.         }
    46.         kq.sopt=sopt+1;
    47.         int nho=0;
    48.         for(int i=0;i<sopt;i++)
    49.         {
    50.             kq.so[i]=(so[i]+p.so[i]+nho)%10;
    51.             nho=(so[i]+p.so[i]+nho)/10;
    52.         }
    53.         if(nho>0)
    54.         {
    55.             kq.so[sopt]=nho;
    56.         }
    57.         else
    58.         {
    59.             kq.sopt=sopt;
    60.         }
    61.         return kq;
    62.     }
    63.     //////////////////////////////////////////////////////////
    64.     //phep trừ
    65.     //////////////////////////////////////////////////////////
    66.     solon operator-(solon p)
    67.     {
    68.         //cân bằng số phần tử
    69.         solon kq;
    70.         if(p.sopt>sopt)
    71.         {
    72.             int m=p.sopt-sopt;
    73.             for(int i=1;i<=m;i++)
    74.             {
    75.                 so[sopt-1+i]=0;
    76.             }
    77.             sopt=p.sopt;
    78.         }
    79.         else
    80.         {
    81.             int m=sopt-p.sopt;
    82.             for(int i=1;i<=m;i++)
    83.             {
    84.                 p.so[p.sopt-1+i]=0;
    85.             }
    86.             p.sopt=sopt;
    87.         }
    88.         kq.sopt=sopt;
    89.         for(int i=sopt-1;i>=0;i--)
    90.         {
    91.             if(so[i]>p.so[i])//kt so nao lon hon( ss 2 so)
    92.             {
    93.                 soam=false;
    94.                 p.soam = false;
    95.                 kq.soam = false;
    96.                 break;
    97.             }
    98.             else if(so[i]<p.so[i])
    99.             {
    100.                 soam=true;
    101.                 p.soam=true;
    102.                 kq.soam=true;
    103.                 break;
    104.             }
    105.         }
    106.         //phép trừ
    107.         int vay=0;
    108.         if(soam)
    109.         {
    110.             for(int i=0;i<sopt;i++)
    111.             {
    112.                 if(p.so[i]<so[i])
    113.                 {
    114.                     kq.so[i]=10+p.so[i]-so[i]-vay;
    115.                     if(i!=sopt-1)
    116.                     vay=1;
    117.                 }
    118.                 else
    119.                 {
    120.                     kq.so[i]=p.so[i]-so[i]-vay;
    121.                     vay=0;
    122.                 }
    123.             }
    124.         }
    125.         else
    126.         {
    127.             for(int i=0;i<sopt;i++)
    128.             {
    129.                 if(so[i]<p.so[i])
    130.                 {
    131.                     kq.so[i]=10+so[i]-p.so[i]-vay;
    132.                     if(i!=sopt-1)
    133.                     vay=1;
    134.                 }
    135.                 else
    136.                 {
    137.                     kq.so[i]=so[i]-p.so[i]-vay;
    138.                     vay=0;
    139.                 }
    140.             }
    141.         }
    142.        
    143.        
    144.         return kq;
    145.     }
    146.     /////////////////////////////////////////////////////////////////////
    147.     //Phép nhân
    148.     /////////////////////////////////////////////////////////////////////
    149.     solon operator *(solon p)
    150.     {
    151.         solon kq;
    152.         int bac=0;
    153.         //////////// buoc 1 //////////
    154.         if(sopt<p.sopt)//đổi lại 2 số để phép nhân được tối ưu hơn vì sẽ nhân số lớn với lần lượt sopt
    155.             //( sẽ chọn số pt nhỏ hơn để nhân)
    156.         {
    157.             solon x;
    158.             x.sopt = sopt;
    159.             for(int i=0;i<sopt;i++)
    160.                 x.so[i] = so[i];
    161.             sopt = p.sopt;
    162.             for(int i=0;i<sopt;i++)
    163.                 so[i] = p.so[i];
    164.             p.sopt = x.sopt;
    165.             for(int i=0;i<p.sopt;i++)
    166.                 p.so[i] = x.so[i];
    167.         }
    168.                 bac=p.sopt;
    169.                 int x = sopt;
    170.                 solon *mang = new solon[bac];
    171.                 //mảng các số lớn --> sẽ cộng đồn vào sau các phép nhân với từng chữ số
    172.                 for(int i=0;i<bac;i++)
    173.                 {
    174.                     mang[i].sopt = x+1;
    175.                     for(int j=0;j<x+1;j++)//gán cho tất cả các mảng =0
    176.                         mang[i].so[j]=0;
    177.                     x++;
    178.                 }
    179.                 int l=0;//xác định xem làm với mảng nào
    180.                 for(int j=0;j<p.sopt;j++)
    181.                 {
    182.                     int nho=0,g=0;
    183.                     for(int k=0;k<sopt;k++)
    184.                     {
    185.                         mang[l].so[g+l] = (so[k]*p.so[j]+nho)%10;
    186.                         nho = (so[k]*p.so[j]+nho)/10;
    187.                         g++;
    188.                     }
    189.                     //hết vòng for nếu vẫn còn nhớ thì phải thêm 1 pt nữa
    190.                     if(nho!=0)
    191.                     {
    192.                         mang[l].so[g+l]= nho;
    193.                     }
    194.                     else
    195.                     {
    196.                         mang[l].sopt = g+l;
    197.                     }
    198.                     l++;
    199.                 }
    200.                
    201.             //////// can = so pt ////////////
    202.                
    203.                 for(int i=0;i<bac;i++)
    204.                 {
    205.                     int z= mang[bac-1].sopt - mang[i].sopt;
    206.                     for(int j=1;j<=z;j++)
    207.                     {
    208.                         mang[i].so[mang[i].sopt-1+j]=0;
    209.                     }
    210.                     mang[i].sopt = mang[bac-1].sopt;
    211.                 }
    212.                 kq.sopt = mang[bac-1].sopt+1;
    213.                 int nhokq=0;
    214.                 //phép cộng tất cả các số trong mảng vào
    215.                 for(int i=0;i<mang[bac-1].sopt;i++)
    216.                 {
    217.                     int w=0;
    218.                     for(int j=0;j<bac;j++)
    219.                     {
    220.                         w += mang[j].so[i];
    221.                     }
    222.                     kq.so[i] = (w+nhokq)%10;
    223.                     nhokq = (w+nhokq)/10;
    224.                 }
    225.                 if(nhokq!=0)
    226.                 {
    227.                     kq.so[mang[bac-1].sopt] = nhokq;
    228.                 }
    229.                 else
    230.                     kq.sopt = mang[bac-1].sopt;
    231.         return kq;
    232.     }
    233.  
    234.     ////////////////////////////////////////////////////////////////////
    235.     //Phép chia
    236.     ////////////////////////////////////////////////////////////////////
    237.     solon operator /(solon p)
    238.     {
    239.         solon kq;
    240.  
    241.     }
    242. };
    243. ostream &operator <<(ostream &out,solon &p)
    244. {
    245.     out<<"Ket qua la: ";
    246.     if(p.soam)
    247.     {
    248.         int x=0;
    249.         out<<"-";
    250.         for(int i=p.sopt-1;i>=0;i--)
    251.         {
    252.             if(p.so[i]!=0)
    253.             {
    254.                 x=i;
    255.                 break;
    256.             }
    257.         }
    258.         for(int i=x;i>=0;i--)
    259.             out<<p.so[i];
    260.         out<<"\n";
    261.     }
    262.     else
    263.     {
    264.         for(int i=p.sopt-1;i>=0;i--)
    265.             out<<p.so[i];
    266.         out<<"\n";
    267.     }
    268.     return out;
    269. }
    270. istream &operator >>(istream &cn,solon &p)
    271. {
    272.     char a[100];
    273.     cout<<"nhap so lon: ";
    274.     gets(a);
    275.     p.sopt=strlen(a);
    276.     p.ChuyenSo(p.so,a);
    277.     return cn;
    278. }


    file App.cpp

    C++ Code:
    1. #include "Huge.h"
    2. #include "conio.h"
    3. #include "iostream"
    4. void main()
    5. {
    6.     solon p,p1,p2;
    7.     cin>>p1;
    8.     cin>>p2;
    9.     p=p1+p2;
    10.     cout<<"ket qua cong: "<<p;
    11.     p=p1-p2;
    12.     cout<<"ket qua tru: "<<p;
    13.     p=p1*p2;
    14.     cout<<"ket qua nhan: "<<p;
    15.     getch();
    16. }

  4. #4
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Trích dẫn Nguyên bản được gửi bởi sakervista Xem bài viết
    theo mình làm số âm hay số dương thì dùng 1 biến bool để kiểm tra là được
    bài này mình làm trong OOP các bạn xem qua
    còn phép chia nó hơi bị sao ý mình mới xóa
    Cậu chưa hiểu vấn đề người ta đang bàn luận. Góp ý cho cậu nè: với class có cấp phát động thì cậu phải định nghĩa BỐN cái cơ bản sau:
    1. constructor (cậu đã có)
    2. copy constructor
    3. deconstructor
    4. assignment operator
    Nếu chưa cài đặt được 4 cái đó thì đừng code vội. Trên 4rum đã có một số bài viết về điều đó rồi, cậu nên tìm và đọc.

  5. #5
    Ngày gia nhập
    03 2009
    Bài viết
    42

    okie cái đó e chỉ code theo ý tưởng cũng chưa chau chuốt mấy
    lần sau sẽ chỉnh chu hơn )

  6. #6
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Mặc định Hướng dẫn thao tác số nguyên lớn

    Theo hướng xử lý số nguyên lớn bằng xâu ký tự, mình cài đặt lớp digits và tải bội các toán tử cần thiết, chỉ sử dụng iostream thôi. Giờ trình diện ra đây mong được góp ý. Cám ơn nhiều nha.
    C Code:
    1. #include <iostream.h>
    2. #define zero '0'
    3. #define space (char)32
    4. #define minussign '-'
    5. // Các hàm chỉ liên quan đến kiểu (char *) pchar mà có lần mình đã post rồi
    6. typedef char* pchar;
    7.  
    8. int strlen(const pchar a)
    9. {
    10.     pchar p = a;
    11.     while (*p) p++;
    12.     return p-a;
    13. }
    14.  
    15. int val(char chr){return chr-zero;}
    16. char chr(int num){return num + zero;}
    17.  
    18. char chradd(char a, char b, int &carry)
    19. {
    20.     int temp = val(a) + val(b) + carry;
    21.     carry = temp/10;
    22.     return chr(temp %10);
    23. }
    24.  
    25. char chrsub(char a, char b, int &carry)
    26. {
    27.     int temp = 10 + val(a) - val(b) - carry;
    28.     carry = 1 - temp/10;
    29.     return chr(temp %10);
    30. }
    31. pchar strcpy (const pchar dest, const pchar src)
    32. {
    33.     int k = 0;
    34.     while (src[k]) dest[k] = src[k++];
    35.     dest[k] = 0;
    36.     return dest;
    37. }
    38.  
    39. pchar strrev( const pchar src, const pchar dest)
    40. {
    41.     strcpy(dest,src);
    42.     int len = strlen(src);
    43.     for (int k = 0; k < len/2; k++)
    44.         {
    45.             char temp = dest[k];
    46.             dest[k] = dest[len-k-1];
    47.             dest[len-k-1] = temp;
    48.         }
    49.     return dest;
    50. }
    51.  
    52. void remzers(const pchar a)
    53. {
    54.     int n = 0, sign = 0, p;
    55.     while (a[n]) n++;
    56.     if (a[n-1] == minussign)
    57.     {
    58.         sign = 1; p = n-2;
    59.     }
    60.     else p = n-1;
    61.  
    62.     while (p>0 && a[p]== zero) p--;
    63.     p++;
    64.     if (sign && p > 1) a[p++]= minussign;
    65.     a[p++]= 0; a[p]=0;
    66. }
    67.  
    68. pchar stradd (const pchar a, const pchar b, const pchar c)
    69. {
    70.     int i = 0, carry = 0;  
    71.     while(a[i] && b[i]) c[i++] = chradd(a[i],b[i],carry);
    72.     if(a[i])
    73.         while (a[i]) c[i++] = chradd(a[i],zero,carry);
    74.     else   
    75.         while (b[i]) c[i++] = chradd(b[i],zero,carry);
    76.     if (carry) c[i++] = chr(carry);
    77.     c[i] = 0;c[i+1]=0;
    78.     return c;
    79. }
    80.  
    81. pchar strsub (const pchar a, const pchar b, const pchar c)
    82. {
    83.     int i = 0, carry = 0;  
    84.     while (a[i] && b[i]) c[i++] = chrsub(a[i],b[i],carry);
    85.     while (a[i]) c[i++] = chrsub(a[i],zero,carry);
    86.     remzers(c);
    87.     return c;
    88. }
    89. char chrmul(char a, char b, int &carry)
    90. {
    91.     int temp = val(a) * val(b) + carry;
    92.     carry = temp/10;
    93.     return chr(temp %10);
    94. }
    95.  
    96. pchar strmul(const pchar a, const pchar b, const pchar c)
    97. {
    98.     int jb = 0;
    99.     pchar temp = new char[strlen(a)+2];
    100.     do
    101.     {
    102.         int ja = 0, carry = 0;
    103.         do
    104.         {
    105.             temp[ja++] = chrmul(a[ja],b[jb],carry);
    106.         }   while (a[ja]);
    107.  
    108.         if (carry) temp[ja++] = chr(carry);
    109.         temp[ja]=0;
    110.  
    111.         if (jb==0) strcpy(c,temp);
    112.         else stradd(c+jb,temp,c+jb);
    113.         jb++;
    114.  
    115.     } while (b[jb]);
    116.     delete temp;
    117.     remzers(c);
    118.     return c;
    119. }
    120.  
    121. int strrcmp(const pchar a,const pchar b)
    122. {
    123.     int aj = strlen(a), bj = strlen(b);
    124.     if (aj > bj) return 1;
    125.     if (aj < bj) return -1;
    126.     while (aj && a[aj]==b[aj])aj--;
    127.     return a[aj] - b[aj];
    128. }
    129.  
    130. pchar strdiv(const pchar a, const pchar b, const pchar c, const pchar r)
    131. {
    132.     int len = strlen(a), k = 0;
    133.     pchar temp = new char[len+1]; strcpy(temp,a);
    134.     pchar p = temp + len - strlen(b);
    135.     do
    136.     {
    137.         c[k] = zero;
    138.         while (strrcmp(p,b)>= 0)
    139.         {
    140.             c[k]++;    
    141.             strsub(p,b,r);
    142.             strcpy(p,r);
    143.         }
    144.         p--; k++; c[k]=0;
    145.     } while (p >= temp );
    146.     if (p < temp)p++;
    147.     strcpy(r,p);
    148.     remzers(r);
    149.     strrev(c,c);
    150.     remzers(c);
    151.     delete temp;
    152.     return c;
    153. }
    154.  
    155. int max (int x, int y){ return x > y ? x : y;}
    156.                             // Cài đặt lớp từ đây
    157. class digits
    158. {
    159.     pchar v;
    160.     public:
    161.         digits(int len = 2);
    162.         digits(const digits &);
    163.         digits(const pchar &);
    164.         digits& operator = (const digits &);
    165.         ~digits(){delete v;}
    166.         char& operator [](int k) const {return v[k];}
    167.        
    168.         friend int operator < (const digits &, const digits &);
    169.         friend int operator < (const digits &, int);
    170.         friend int operator >= (const digits &, int);
    171.         friend int operator > (const digits &, int);
    172.         friend int operator <= (const digits &, int);
    173.  
    174.         friend int operator > (const digits &, const digits &);
    175.         friend int operator >= (const digits &, const digits &);
    176.         friend int operator <= (const digits &, const digits &);
    177.         friend int operator == (const digits &, const digits &);
    178.         friend int operator != (const digits &, const digits &);
    179.         digits operator - ()const;
    180.         friend digits operator + (const digits &, const digits &);
    181.         friend digits operator - (const digits &a, const digits &b){return a + -b;}
    182.         friend digits operator * (const digits &, const digits &);
    183.         friend digits operator / (const digits &, const digits &);
    184.         friend digits operator % (digits &, digits &);
    185.  
    186.         friend digits abs(const digits &a){return a >= 0 ? a : -a;}
    187.         int len()const{return strlen(v);}
    188.         friend ostream & operator << (ostream &, const digits&);
    189.         friend istream & operator >> (istream &, const digits&);
    190. };
    191.  
    192. digits ::digits(int len)
    193. {
    194.     if (len < 2) len = 2;
    195.     v = new char[len+1];
    196.     for (int k=0; k < len-1; k++) v[k] = zero;
    197.     v[len-1] = v[len] = 0;
    198. }
    199.  
    200. digits ::digits(const digits &a)
    201. {
    202.     int _len = a.len();
    203.     v = new char[_len+2];
    204.     strcpy(v,a.v);
    205.     v[_len+1] = 0;
    206. }
    207.  
    208. digits ::digits(const pchar &a)
    209. {
    210.     int _len = strlen(a);
    211.     v = new char[_len+2];
    212.     strrev(a,v);v[_len+1] = 0;
    213.     remzers(v);
    214. }
    215.  
    216. digits& digits ::operator = (const digits &b)
    217. {
    218.     if (this != &b)
    219.     {
    220.         delete v;
    221.         int _len = b.len();
    222.         v = new char[_len+2];v[_len+1] = 0;
    223.         strcpy(v,b.v);
    224.     }
    225.     return *this;
    226. }
    227.  
    228. ostream & operator << (ostream &pout, const digits &a)
    229. {
    230.     pchar s = new char[a.len()+1];
    231.     strrev(a.v,s);
    232.     pout << s;
    233.     return pout;
    234. }
    235.  
    236. istream & operator >> (istream &pin, const digits &a)
    237. {
    238.     int n = 0, sign = 0; char ch;
    239.     do
    240.         {
    241.             cout.flush(); pin.get(ch);
    242.             if (ch == minussign && n == 0 && !sign) sign = 1;
    243.             else
    244.                 if (zero <= ch && ch <= '9') a[n++] = ch;
    245.                 else
    246.                     if (ch == '\b' && n>=0)
    247.                         {
    248.                             if (n) n--;
    249.                             if (n==0) sign = 0;
    250.                         }
    251.         } while (ch != 10 || n == 0);
    252.     cout << endl;
    253.  
    254.     a[n++] = 0;a[n] = 0;
    255.     strrev(a.v,a.v);
    256.     if (sign) {a[n-1]='-';}
    257.     remzers(a.v);
    258.     return pin;
    259. }
    260.  
    261. int operator <(const digits &a, const digits &b)
    262. {
    263.     if (a < 0 && b >= 0) return 1;
    264.     if (a >= 0 && b < 0) return 0;
    265.     if (strrcmp(abs(a).v, abs(b).v) < 0) return 1;
    266.     else return 0;
    267. }
    268.  
    269. int operator >  (const digits &a, const digits &b) {return b < a;}
    270. int operator >= (const digits &a, const digits &b) {return !(a < b);}
    271. int operator <= (const digits &a, const digits &b) {return !(b < a);}
    272. int operator == (const digits &a, const digits &b) {return a <= b && b <= a;}
    273. int operator != (const digits &a, const digits &b) {return !(a == b);}
    274. int operator <  (const digits &a, int x) {return a[a.len()-1] == minussign;}
    275. int operator >= (const digits &a, int x) {return a[a.len()-1] != minussign;}
    276. int operator >  (const digits &a, int x) {return a[a.len()-1] != minussign && a[0] != zero;}
    277. int operator <= (const digits &a, int x) {return a[a.len()-1] == minussign || a[0] == zero;}
    278.  
    279. digits digits::operator - ()const
    280. {
    281.     digits b(*this);
    282.     int _len = len();
    283.     if (b[_len-1] == minussign) b[_len-1] = 0;
    284.     else b[_len] = minussign;
    285.     return b;
    286. }
    287.  
    288. digits operator + (const digits &a, const digits &b)
    289. {
    290.     if (a >= 0)
    291.     {
    292.         int clen = max(a.len(), b.len());
    293.         digits c(clen + 2);
    294.         if (b >= 0)
    295.         {
    296.             stradd(a.v,b.v,c.v);
    297.             return c;
    298.         }
    299.         else
    300.             if (a >= -b) {strsub(a.v,(-b).v,c.v); return c;}
    301.             else {strsub((-b).v,a.v,c.v); return -c;}
    302.     }
    303.     else return -(-a + -b);
    304. }
    305.  
    306. digits operator * (const digits &a, const digits &b)
    307. {
    308.         int clen = a.len()+ b.len();
    309.         int sign = 1;
    310.         if (a < 0) sign = -1;
    311.         if (b < 0) sign = -sign;
    312.         digits c(clen + 1);
    313.         strmul(abs(a).v,abs(b).v,c.v);
    314.         if (sign ==1) return c;
    315.         return -c;
    316. }
    317.  
    318. digits operator / (const digits &a, const digits &b)
    319. {
    320.         if (abs(a) < abs(b)) return digits("0");
    321.         if (b == digits("0")) return digits("divide by zero");
    322.         int sign = 1;
    323.         if (a < 0) sign = -1;
    324.         if (b < 0) sign = -sign;
    325.         digits c(a.len()+2);
    326.         digits r(b.len()+2);
    327.         strdiv(abs(a).v,abs(b).v,c.v,r.v);
    328.         if (sign ==1) return c;
    329.         return -c;
    330. }
    331.  
    332. digits operator % (digits &a, digits &b)
    333. {
    334.         if (abs(a) < abs(b)) return a;
    335.         if (b == digits("0")) return digits("mod by zero");
    336.         int sign = 1;
    337.         if (a < 0) sign = -1;
    338.         if (b < 0) sign = -sign;
    339.         digits c(a.len()+2);
    340.         digits r(b.len()+2);
    341.         strdiv(abs(a).v,abs(b).v,c.v,r.v);
    342.         return r;
    343. }
    344.  
    345. void main()
    346. {
    347.     digits a("17062010170620101706201017062010"), b(100);
    348.     cout << "\na = " << a<< endl;
    349.     cout << "\nNhap so b: "; cin >> b;
    350.     cout << a <<" + " << b <<" = " << a + b << endl;
    351.     cout << a <<" - " << b <<" = " << a - b << endl;
    352.     cout << a <<" * " << b <<" = " << a * b << endl;
    353.     cout << a <<" / " << b <<" = " << a / b << endl;
    354.     cout << a <<" % " << b <<" = " << a % b << endl;   
    355. }
    Kết quả khi chạy lần 1:
    Output Code:
    1. a = 17062010170620101706201017062010
    2.  
    3. Nhap so b: -0
    4.  
    5. 17062010170620101706201017062010 + 0 = 17062010170620101706201017062010
    6. 17062010170620101706201017062010 - 0 = 17062010170620101706201017062010
    7. 17062010170620101706201017062010 * 0 = 0
    8. 17062010170620101706201017062010 / 0 = divide by zero
    9. 17062010170620101706201017062010 % 0 = mod by zero

    Kết quả khi chạy lần 2:
    Output Code:
    1. a = 17062010170620101706201017062010
    2.  
    3. Nhap so b: 100000000000000000000000
    4.  
    5. 17062010170620101706201017062010 + 100000000000000000000000 = 17062010270620101706201017062010
    6. 17062010170620101706201017062010 - 100000000000000000000000 = 17062010070620101706201017062010
    7. 17062010170620101706201017062010 * 100000000000000000000000 = 1706201017062010170620101706201000000000000000000000000
    8. 17062010170620101706201017062010 / 100000000000000000000000 = 170620101
    9. 17062010170620101706201017062010 % 100000000000000000000000 = 70620101706201017062010
    Đã được chỉnh sửa lần cuối bởi donvuon : 07-07-2010 lúc 02:12 AM.

  7. #7
    Ngày gia nhập
    07 2010
    Bài viết
    1

    Trích dẫn Nguyên bản được gửi bởi donvuon Xem bài viết
    Theo hướng của peterdrew (lưu số nguyên lớn dưới dạng mảng các số), mình xin đóng góp như sau: Các chữ số được lưu theo chiều ngược lại và có -1 ở cuối để đánh dấu sự kết thúc. Ngoài ra còn thêm 0 hoặc -1 vào cuối để phân biệt không âm và âm. Hơn nữa, đề phòng rác trong bộ nhớ nên còn thêm 1 giá trị 0 nữa vào cuối mảng. Ví dụ, 12345 được lưu là 54321-100, còn -12345 được lưu là 54321-1-10. Số 0 được lưu là 0-100, số -1 là 1-1-10. Giải thuật cộng, trừ, nhân, chia (với các số dương) được mô phỏng theo các giải thuật xử lý xâu mà mình đã trình bày ở bài trước. So với lưu trữ dạng xâu ký tự, mình nhận thấy có hai nhược điểm. Thứ nhất là các thao tác phức tạp hơn, thứ hai là tốn bộ nhớ hơn. Khi code hàm nhập số nguyên lớn, mình xử lý theo kiểu char nên tránh được việc hỏi số chữ số cần nhập và không có khoảng cách giữa các chữ số, nhờ đó việc nhập được tự nhiên như hàm scanf(). Mặc dù có hai nhược điểm nói trên, nhưng mình cũng post lên đây nhằm tranh thủ sự góp ý của các bạn.

    Dưới đây là kết quả minh họa:
    Output Code:
    1. Moi ban nhap so nguyen a: 001234567891234567890123
    2.  
    3. Moi ban nhap so nguyen b: 0012345678
    4. 1234567891234567890123 + 12345678 = 1234567891234580235801
    5. 1234567891234567890123 - 12345678 = 1234567891234555544445
    6. 1234567891234567890123 * 12345678 = 15241577654320997640597938394
    7. 1234567891234567890123 / 12345678 = 100000007390000 du 7470123
    Cái này bạn chỉ thử cho số dương thôi.
    Bạn thử số âm thử xem, hình như là bị sai đó

    Không biết mình thử có sai chỗ nào không

  8. #8
    Ngày gia nhập
    05 2010
    Bài viết
    265

    Cậu không đọc thấy đoạn này sao?
    Giải thuật cộng, trừ, nhân, chia (với các số dương) được mô phỏng theo các giải thuật xử lý xâu mà mình đã trình bày ở bài trước. So với lưu trữ dạng xâu ký tự, mình nhận thấy có hai nhược điểm. Thứ nhất là các thao tác phức tạp hơn, thứ hai là tốn bộ nhớ hơn. Khi code hàm nhập số nguyên lớn, mình xử lý theo kiểu char nên tránh được việc hỏi số chữ số cần nhập và không có khoảng cách giữa các chữ số, nhờ đó việc nhập được tự nhiên như hàm scanf(). Mặc dù có hai nhược điểm nói trên, nhưng mình cũng post lên đây nhằm tranh thủ sự góp ý của các bạn.
    Với các số nguyên, mình có bài sau đó cơ mà.

  9. #9
    Ngày gia nhập
    07 2010
    Bài viết
    288

    mình có ý tưởng phép chia thế này
    ví dụ
    321:12
    ta có 32 -12=20(1 lần)-12=8(2 lần) dư 8. vì ở sau còn nên lấy 2*10=20
    81-12=69(1 lần)-12=57(2 lần)-12=45(3 lần)-12=33(4 lần)-12=21(5 lần)-12=9(6 lần). công với số lần trước ta có 20+6=26

    mình không giỏi lắm về trình bày ý tưởng. nên dẫn nó vào ví dụ luôn cho mọi người dễ hình dung. không biết ý mọi người thế nào.

  10. #10
    Ngày gia nhập
    04 2010
    Bài viết
    1

    Mình đang phải làm bài này lục lên tham khảo, thử bài của mình nhé

    C++ Code:
    1.  //xay dung lop quan ly so lon
    2. # include<iostream.h>
    3. # include<conio.h>
    4. # include<string.h>
    5. # include<stdlib.h>
    6. # include<ctype.h>
    7. class big_int
    8.  {
    9.     private :
    10.      int a[100]; //chuoi so
    11.      int n;      //so ky tu co nghia
    12.      int dau;    //dau cua so
    13.     public :
    14.      int nhap();
    15.      void in();
    16.      big_int();
    17.      big_int (int b,int c);
    18.      big_int congcungdau(big_int b);
    19.      big_int congkhacdau(big_int b);
    20.      big_int operator +(big_int b);
    21.      big_int operator -(big_int b);
    22.      big_int operator *(big_int b);
    23.      void chia (big_int b,big_int c,big_int &d);
    24.      int sosanh (big_int b);
    25.      void dich (int b);
    26.      big_int nhan (int b);
    27.      void xoa0 ();
    28.      big_int giaithua();
    29.  };
    30. //ham tao----------------------------------------------------------------------
    31. big_int ::big_int (int b,int c)
    32.  {
    33.     n=b;
    34.     for (int i=0;i<100;i++)
    35.      {
    36.         if (i<n) a[i]=c;
    37.         else a[i]=0;
    38.      }
    39.  }
    40. //xoa cac ky tu 0 vo nghia 00001234->1234-------------------------------------
    41. void big_int :: xoa0()
    42.  {
    43.     int i=n-1,dem=0;
    44.     i=n-1;
    45.     while (i)
    46.      {
    47.         if (a[i]) break;
    48.         else
    49.         {dem++;a[i]=NULL;}
    50.         i--;
    51.  
    52.      }
    53.     n=n-dem;
    54.  }
    55. //nhan mot chuoi voi 1 so-----------------------------------------------------
    56. big_int big_int ::nhan (int b)
    57.  {
    58.     big_int c;
    59.     int i,nho=0;
    60.     c.n=n;
    61.     for (i=0;i<n;i++)
    62.      {
    63.         c.a[i]=(a[i]*b+nho)%10;
    64.         nho=(a[i]*b+nho)/10;
    65.      }
    66.     if (nho)
    67.      {
    68.         a[c.n]=nho;
    69.         c.n++;
    70.      }
    71.      c.dau=dau;
    72.      return c;
    73.  }
    74. //nhan hai so lon----------------------------------------------------------------
    75. big_int big_int :: operator *(big_int b)
    76.  {
    77.     big_int c,d;
    78.     int i;
    79.     for (i=0;i<b.n;i++)
    80.      {
    81.         d=nhan(b.a[i]);
    82.         d.dich(i);
    83.         c=c+d;
    84.      }
    85.     if (dau==b.dau) c.dau=0;
    86.     else c.dau=1;
    87.     return c;
    88.  }
    89. //nhan day so voi  10^b-------------------------------------------------------------
    90. void big_int :: dich (int b)
    91.  {
    92.     for (int i=n-1;i>=0;i--)  a[i+b]=a[i];
    93.     for (i=0;i<b;i++)  a[i]=0;
    94.     n=n+b;
    95.  }
    96. //so sanh tri tuyet doi 2 so------------------------------------------------------
    97. int big_int :: sosanh (big_int b)
    98.  {
    99.     if (n>b.n) return 1;
    100.     if (n<b.n) return -1;
    101.     else
    102.      {
    103.         int s=0;
    104.         for (int i=n;i>=0;i--)
    105.          {
    106.           if (a[i]>b.a[i])
    107.            {
    108.             s=1;break;
    109.            }
    110.           if (a[i]<b.a[i])
    111.            {
    112.             s=-1;break;
    113.            }
    114.          }
    115.         return s;
    116.      }
    117.  }
    118. //ham tao----------------------------------------------------------------------
    119. big_int ::big_int()
    120.  {
    121.     for (int i=0;i<100;i++)
    122.     a[i]=0;
    123.     n=0;dau=0;
    124.  }
    125. //nhap chuoi thanh cong tra ve 1 neu khong tra ve 0----------------------------
    126. int big_int::nhap()
    127.  {
    128.     int i;
    129.     char c[100];
    130.     cout<<"nhap so ";
    131.     cin.ignore(0);
    132.     cin.get(c,100);
    133.     if (c[0]!='-'&&(!isdigit(c[0])))  return 0;
    134.     for (i=1;i<strlen(c);i++)
    135.         if (!isdigit(c[i])) return 0;
    136.     if (c[0]=='-')
    137.      {
    138.         dau=1;
    139.         for (i=strlen(c)-1;i>0;i--)
    140.          {
    141.           char *b;
    142.           b[0]=c[i];
    143.           a[strlen(c)-i-1]=atoi(b);
    144.          }
    145.      }
    146.     else
    147.      {
    148.         dau=0;
    149.         for (i=0;i<strlen(c);i++)
    150.          {
    151.           char *b;
    152.           b[0]=c[i];
    153.           a[strlen(c)-i-1]=atoi(b);
    154.          }
    155.      }
    156.     n=strlen(c)-dau;
    157.     return 1;
    158.  }
    159. //in chuoi so------------------------------------------------------------------
    160. void big_int :: in()
    161.  {
    162.     if (dau) cout<<"-";
    163.     for (int i=n-1;i>=0;i--)
    164.         cout<<a[i];
    165.  }
    166. //ham cong 2 so cung dau-------------------------------------------------------
    167. big_int big_int::congcungdau(big_int b)
    168.  {
    169.     big_int c;
    170.     if (n>b.n) c.n=n;else c.n=b.n;
    171.     int nho=0;
    172.     for(int i=0;i<c.n;i++)
    173.      {
    174.         c.a[i]=(b.a[i]+a[i]+nho)%10;
    175.         nho=(a[i]+b.a[i]+nho)/10;
    176.      }
    177.     if (nho)
    178.     {
    179.     c.a[c.n]=nho;
    180.     c.n=c.n+1;
    181.     }
    182.     c.dau=dau;
    183.     return c;
    184.  }
    185. //ham cong 2 so khac dau-------------------------------------------------------
    186. big_int big_int :: congkhacdau(big_int b)
    187.  {
    188.     big_int c,d,e,g=(*this);
    189.     if (n>b.n) c.n=n;
    190.     else c.n=b.n;
    191.     if (g.sosanh(b)==1)
    192.      { d=b; e=g; }
    193.     if (g.sosanh(b)==-1)
    194.       { d=g; e=b; }
    195.     if (!g.sosanh(b))
    196.      {
    197.         c.a[0]=0; n=1;
    198.         dau=0;
    199.      }
    200.     int muon=0;
    201.     for (int i=0;i<e.n;i++)
    202.      {
    203.         if (d.a[i]+muon<=e.a[i])
    204.          {
    205.           c.a[i]=e.a[i]-d.a[i]-muon;
    206.           muon=0;
    207.          }
    208.         else
    209.          {
    210.           c.a[i]=(10+e.a[i]-d.a[i]-muon);
    211.           muon=1;
    212.          }
    213.      }
    214.     c.dau=e.dau;
    215.     return c;
    216.  }
    217. //nap chong toan tu + --------------------------------------------------------------
    218. big_int big_int :: operator + (big_int b)
    219.  {
    220.     big_int c;
    221.     if (dau==b.dau) c=congcungdau(b);
    222.     else c=congkhacdau(b);
    223.     return c;
    224.  }
    225. //nap chong toan tu (-) -------------------------------------------------------
    226. big_int big_int :: operator - (big_int b)
    227.  {
    228.     big_int c;
    229.     if (dau==b.dau) c=congkhacdau(b);
    230.     else c=congcungdau(b);
    231.     return c;
    232.  }
    233. //phep chia tra ve thuong va so du---------------------------------------------------
    234. void big_int :: chia (big_int b,big_int c,big_int &d)
    235.  {
    236.     int d1=b.dau,d2=c.dau;
    237.     b.dau=0;c.dau=0;
    238.     if (d1==d2) dau=0;else dau =1;
    239.     if (!b.sosanh(c))
    240.      {
    241.         a[0]=1;
    242.         n=1;
    243.      }
    244.     else
    245.     {
    246.      if (b.sosanh(c)==-1)
    247.            { d=b;n=1;dau=0;}
    248.      else
    249.       {
    250.         big_int e;
    251.         int i=b.n-1;
    252.         for (i=b.n-1;i>=0;i--)
    253.          {
    254.           a[i]=0;
    255.           e.dich(1);
    256.           e.a[0]=b.a[i];
    257.           e.xoa0();
    258.           if (e.sosanh(c)!=-1)
    259.           {
    260.           while (e.sosanh(c)!=-1)
    261.            {
    262.             e=e-c;
    263.             e.xoa0();
    264.             a[i]++;
    265.            }
    266.           }
    267.  
    268.          }
    269.         n=b.n;
    270.         (*this).xoa0();
    271.         b.dau=d1;c.dau=d2;
    272.         d=e;
    273.       }
    274.     }
    275.  }
    276. //tao menu va nhap chon muc-----------------------------------------------------
    277. int chonmenu()
    278.  {
    279.     int a;
    280.     cout<<endl<<"1.phep cong";
    281.     cout<<endl<<"2.phep tru";
    282.     cout<<endl<<"3.phep nhan ";
    283.     cout<<endl<<"4.phep chia";
    284.     cout<<endl<<"5.thoat";
    285.     cout<<endl<<"Moi ban chon ";
    286.     cin>>a;
    287.     return a;
    288.  }
    289. //ham nhap 2 so lon---------------------------------------------------------------
    290. void nhap(big_int &x, big_int &y)
    291.  {
    292.     clrscr();
    293.     cin.ignore(1);
    294.     int k;
    295.     k=x.nhap();
    296.     if (!k)
    297.      {
    298.         cout<<endl<<"loi nhap ";
    299.         getch();
    300.         exit(0);
    301.      }
    302.     cout<<endl;x.xoa0();
    303.     x.in();cout<<endl;
    304.     cin.ignore(1);
    305.     k=y.nhap();
    306.      if (!k)
    307.       {
    308.         cout<<endl<<"loi nhap ";
    309.         getch();
    310.         exit(0);
    311.       }
    312.     cout<<endl;
    313.     y.in();
    314.  }
    315. //thuc hien phep chia--------------------------------------------------------------
    316. void phepchia()
    317.  {
    318.     big_int x,y,z,d;
    319.     nhap(x,y);
    320.     cout<<"\nphep chia ";
    321.     z.chia(x,y,d);
    322.     cout<<endl<<"thuong ";z.in();
    323.     cout<<endl<<"du     ";d.in();
    324.  }
    325. //ham mo phong phep nhan--------------------------------------------------------
    326. void phepnhan()
    327.  {
    328.     big_int x,y,z;
    329.     nhap(x,y);
    330.     cout<<endl<<"phep nhan ";
    331.     z=x*y;
    332.     cout<<endl<<"tich ";z.in();
    333.  }
    334. //ham phep cong-------------------------------------------------------------------
    335. void phepcong()
    336.  {
    337.     big_int x,y,z;
    338.     nhap(x,y);
    339.     cout<<endl<<"phep cong ";
    340.     z=x+y;
    341.     cout<<endl<<"tong ";z.in();
    342.  }
    343. //ham phep tru-------------------------------------------------------------------------
    344. void pheptru()
    345.  {
    346.     big_int x,y,z;
    347.     nhap(x,y);
    348.     cout<<endl<<"phep tru ";
    349.     z=x-y;
    350.     cout<<endl<<"hieu ";z.in();
    351.  }
    352. //xay dung muc chon------------------------------------------------------------
    353. void giaodien(int b)
    354.  {
    355.     switch (b)
    356.      {
    357.         case 1 :
    358.          phepcong();
    359.          break;
    360.         case 2:
    361.          pheptru();
    362.          break;
    363.         case 3:
    364.          phepnhan();
    365.          break;
    366.         case 4:
    367.          phepchia();
    368.          break;
    369.         case 5:
    370.          exit(0);
    371.         default :
    372.          cout<<endl<<"muc chon khong ton tai";
    373.          break;
    374.      }
    375.  }
    376. //ham main---------------------------------------------------------------------------
    377. void main ()
    378.  {
    379.     int chon;
    380.     while (1)
    381.      {
    382.         clrscr();
    383.         chon=chonmenu();
    384.         giaodien(chon);
    385.         getch();
    386.      }
    387.  }

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