Trang 3 trên tổng số 4 Đầu tiênĐầu tiên 1234 Cuối cùngCuối cùng
Từ 21 tới 30 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. #21
    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 CanHocCSharp Xem bài viết
    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
    Tìm hiểu cách tính căn bậc 3 bằng tay, rồi code theo các tính tay thôi. Sử dụng các phép +, -, *, / số lớn ở trên.
    Nhận code thuê :
    kiet.heros@gmail.com

  2. #22
    Ngày gia nhập
    04 2010
    Nơi ở
    Recycle Bin
    Bài viết
    358

    Nói chung thì cũng được. Nhưng với những bài toán phức tạp mà dùng cách tính này thì không thể được.
    Thứ nhất: Quá lãng phí bộ nhớ vì một biến kiểu char hoặc int mà chỉ dùng để lưu 1 bit.
    Thứ hai : Mỗi phép tính có hàng tá phép toán trên string được sử dụng vì vậy mà thời gian xử lý và tốc độ là không thể đáp ứng được.
    Tại sao không xây dựng một kiểu là lũy thừa số 2 số bit. Hoặc giả như 1 phần tử mảng chứa 1 000 hay 10 000 đơn vị. Và thao tác trực tiếp trên số nguyên thì kết quả sẽ khả thi hơn rất nhiều!
    YH : lobuocphuudu_218
    Phone : 0126 463 5095

    http://forums.congdongcviet.com/signaturepics/sigpic55872_2.gif

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

    hay quá, đúng là bài mình cần, nhưng làm với số thập phân thì sao nhỉ?

    - - - Nội dung đã được cập nhật ngày 25-11-2014 lúc 11:04 PM - - -

    Cảm ơn các ban rất nhiều, bài viết hữu ích quá!
    Nhưng mà có cách nào thêm dấu phẩy vào không?
    Xin các bạn làm thêm với số thập phân ah!

  4. #24
    Ngày gia nhập
    03 2011
    Bài viết
    5

    Trích dẫn Nguyên bản được gửi bởi donvuon Xem bài viết
    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
    Bạn cho mình hỏi trong hàm void nhapsn(songuyen &a, char ten) có đoạn
    Code:
     if (ch == '\b' && n>=0)
                            {
                                printf("%c%c%c",ch,32,ch);
                                if (n) n--;
                                if (n==0) sign = 0;
                            }
    tại sao mình ko dùng printf("%c",ch) mà phải dùng printf("%c%c%c",ch,32,ch)?

  5. #25
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    \b là backspace escape, kí tự này lui cursor về 1 bước.
    VD ( | là cursor)
    abcd -> abcd|
    abcd\b -> abc|d
    abcd\b{space} -> abc{space}|
    abcd\b{space}\b -> abc|{space}

    Thực ra thì dạng hiển thị cho user và dạng biểu diễn ko cần phải giống nhau (tức là bạn có thể biểu diễn theo nhị phân cho nhanh, nhưng chuyển đổi khá fer)
    Đã được chỉnh sửa lần cuối bởi prog10 : 29-06-2015 lúc 11:52 PM.

  6. #26
    Ngày gia nhập
    03 2011
    Bài viết
    5

    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

    Mình ko nghĩ \b chỉ lui cursor mà nó vừaa lui và vừa xóa ký tự đứng sau kế tiếp
    tức là theo ví dụ của bạn thì
    VD ( | là cursor)
    1. abcd -> abcd|
    2. abcd\b -> abc|
    3. abcd\b{space} -> abc{space}|
    4. abcd\b{space}\b -> abc|
    Bạn chú ý số 2 và số 4 của mình ko giống như cách biểu diễn của bạn. Nhưng số 2 và số 4 đều cho kết quả giống nhau.

    Thêm 1 câu hỏi khác:
    Cũng trong hàm nhapsn
    if ('0' <= ch && ch <= '9')
    {
    a[n++] = ch - '0';
    printf("%c",ch);
    }
    Tại sao mình ko dùng a[n++] = ch mà lại là a[n++] = ch - '0' ?

  7. #27
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    ^ Đây là phần biến đổi dạng dùng để I/O sang dạng internal.
    '0' -> '9' === 0x30 -> 0x39
    nên trừ 0x30 ('0') để thành 0 -> 9.

    Còn ý nghĩa của kí tự '\b' thì đúng là tuỳ terminal (console) thật, C ko quản lí mấy cái này.

  8. #28
    Ngày gia nhập
    06 2015
    Nơi ở
    Lagi - Bình Thuận
    Bài viết
    1,558

    Có những thư viện số lớn : bigInt, bigNumber sao không tìm hiểu để dùng ?
    //
    Phát minh, phát kiến đã có chủ rồi. Đường quang không đi cứ đâm quàng vào bụi, làm chuyện ruồi bu
    ĐT : 0906.83.71.25
    email : vn8hien62@yahoo.com
    http://diendan.congdongcviet.com/threads/t334310::chu-quoc-ngu-da-lac-hau-chua.cpp?p=815219#post815219

  9. #29
    Ngày gia nhập
    05 2011
    Nơi ở
    TP HCM
    Bài viết
    27

    Trích dẫn Nguyên bản được gửi bởi Van8Hien62 Xem bài viết
    Có những thư viện số lớn : bigInt, bigNumber sao không tìm hiểu để dùng ?
    //
    Phát minh, phát kiến đã có chủ rồi. Đường quang không đi cứ đâm quàng vào bụi, làm chuyện ruồi bu
    Bạn này nói mắc cười ha. Học thuật toán là để rèn luyện tư duy. Mấy trường lớn như BK vẫn yêu cầu sinh viên làm mấy thuật toán như thế này, chứ không phải dạng mấy khóa lập trình dăm ba tháng rồi đi code dạo thì nói làm chi. Bạn đã thi nhữung cuộc thi lập trình tầm cỡ chưa ? Cũng những dạng bài số nguyên lớn thế này mà thi thôi, nói như bạn dùng thư viên thì học sinh cũng làm được .
    http://khuyenmaianuong.com/ Khuyến mãi hấp dẫn

  10. #30
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi mini_bestboy Xem bài viết
    Bạn này nói mắc cười ha. Học thuật toán là để rèn luyện tư duy. Mấy trường lớn như BK vẫn yêu cầu sinh viên làm mấy thuật toán như thế này, chứ không phải dạng mấy khóa lập trình dăm ba tháng rồi đi code dạo thì nói làm chi. Bạn đã thi nhữung cuộc thi lập trình tầm cỡ chưa ? Cũng những dạng bài số nguyên lớn thế này mà thi thôi, nói như bạn dùng thư viên thì học sinh cũng làm được .
    Thi lập trình người ta cũng gọi thư viện boost chứ cài lại cái này chi

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