Đánh giá, nhận xét, review các công ty tuyển dụng
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 19 kết quả

Đề tài: Tính giai thừa số lớn | Tính 100! trong lập trình C

  1. #1
    No Avatar
    javi Khách

    Mặc định Tính giai thừa số lớn | Tính 100! trong lập trình C

    Nhớ ở đâu đó có người hỏi cách tính 100! mà không tìm ra chỗ nữa nên tạo 1 chủ đề mới.

    Nhận xét: Số 100! quá to nên không thể chứa trong 1 biến duy nhất. Nhưng muốn tính và in ra 100! bằng bao nhiêu thì có thể được.

    PP:
    + áp dụng phép nhân đã học hồi lớp 3
    + kết quả được lưu trong 1 mảng a[N], với a[i] có giá trị từ 0 đến 9
    (ví dụ kết quả của 4!= 24 sẽ được lưu vào a với a[0]=4, a[1]=2)
    + Tính 5! ta sẽ lấy a[0]*5, số hàng đơn vị cho lại vào a[0], số hàng chục nhớ lại (carry0). Tiếp theo tính a[1]*5 + carry0, ....
    + In ngược mảng sẽ cho kết quả cần tính

  2. #2
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Chẳng hạn có một số 199999999999999999999999999 thì làm sao để lưu trữ số này được, mình không biết cách tách từng con số của số này để lưu vào mảng. Chỉ cho mình nhé

  3. #3
    Ngày gia nhập
    07 2006
    Bài viết
    121

    Trích dẫn Nguyên bản được gửi bởi neverland87 Xem bài viết
    Chẳng hạn có một số 199999999999999999999999999 thì làm sao để lưu trữ số này được, mình không biết cách tách từng con số của số này để lưu vào mảng. Chỉ cho mình nhé
    Đầu tiên nếu cậu sử dụng các kiểu dữ liệu cơ bản thì không thể lấy được con số này đâu đừng sợ tách không được.
    Còn cậu sử dụng cấu trúc mảng thì khi người ta nhập số thì cậu cho nhập vào một mảng các chữ số. (Vậy còn tách gì nữa).

    Ở đây mình thêm một chút hương vị ha. giờ tớ có một số số này có giá trị trong khoản 80! đến 100! bây giờ làm sau lưu con số này lại chỉ bằng 16byte.
    Chú ý 16 byte thì có thể lưu một con số nguyên dương là 2 mũ (16*8) Một con số rất lớn. Gợi ý kiểu 16 byte = mảng 16 byte kiểu char .
    Nếu làm được cái này thì rất tốt cho việc lưu trữ thay vì lưu 200byte thì giờ chỉ còn 16 byte.-

    OoShinHaoO

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    822

    Không hiểu ý của shi nữa nhưng mà nếu chúng ta lưu từng số vào mảng kiểu char thì làm sao mất 16 byte được
    Phải mất 20byte chứ .

    Không rõ vấn đề của mọi người muốn nói nữa . Nhưng nếu lưu trong một mảng kiểu char rồi sao đó ép kiểu sang int để nhân rồi sao đó ép kiểu lại kiểu char để lưu giữ thì cũng được chứ nhỉ ?

  5. #5
    Ngày gia nhập
    07 2006
    Bài viết
    121

    Trích dẫn Nguyên bản được gửi bởi javi Xem bài viết
    100 ! = có khoảng 157 chữ số nên đặt N = 200 là ok rồi
    Cậu thấy đó thay vì phải mất 1 mảng 157 - 200 để lưu trử nên tớ gợi ý để chỉ mất 16-32 byte gì đó để lưu trữ.
    Ví dụ cậu dùng mảng 2 pt thì chỉ lưu được con số từ 0-99 nhưng với 2 pt này tớ có thể lưu một con số trong khoản 0 đến 2^16
    Đã được chỉnh sửa lần cuối bởi shinichi_haha : 17-03-2007 lúc 05:46 PM.

    OoShinHaoO

  6. #6
    No Avatar
    javi Khách

    Mặc định Tính giai thừa số lớn | Tính 100! trong lập trình C

    Hừm, mình chỉ đưa ra gợi ý chứ chưa tính toán kỹ.
    Ngoài việc biểu diễn được, còn phải có thể dùng để tính toán được. Ví dụ như tính 101!
    Hana nói rõ cách làm của bạn xem nào.

    Viết ct thật thì thấy kiểu double cũng đủ biểu diễn. Kết quả không chính xác hoàn toàn nhưng nói chung chấp nhận được. Chuyển sang tính gần đúng, loại các số sau dấu phẩy quá nhiều, biểu diễn kiểu 9.xxx * 10^157

  7. #7
    Ngày gia nhập
    08 2006
    Bài viết
    19

    Trích dẫn Nguyên bản được gửi bởi shinichi_haha Xem bài viết
    Ở đây mình thêm một chút hương vị ha. giờ tớ có một số số này có giá trị trong khoản 80! đến 100! bây giờ làm sau lưu con số này lại chỉ bằng 16byte.
    Chú ý 16 byte thì có thể lưu một con số nguyên dương là 2 mũ (16*8) Một con số rất lớn. Gợi ý kiểu 16 byte = mảng 16 byte kiểu char .
    Nếu làm được cái này thì rất tốt cho việc lưu trữ thay vì lưu 200byte thì giờ chỉ còn 16 byte.-
    dùng xử lí bit đúng không
    nếu xử lí bit thì coi mỗi byte là 1 mảng 8 phần tử. 16 byte là 16*8 phần tử.
    vì 1 số từ 0->2^16 sẽ chỉ thể hiện bằng 1 bit duy nhất. để lưu nó lại chỉ cần bật bit tương ứng lên là được.
    cái này có hạn chế là không thể nhân chia các số được. chỉ có thể dùng để đánh dấu thôi(đúng không nhỉ )

  8. #8
    No Avatar
    Leon88 Khách

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. main()
    4. {
    5.     unsigned a[200];
    6.     int i,j,
    7.     n,nho,tam;
    8.     printf("\nnhap vao so n = ");scanf("%d",&n);
    9.     a[1]=1;tam=n;
    10.     for (j=2;j<=200;a[j]=0,j++);
    11.     n=tam;nho=0;
    12.     for (i=1;i<=n;i++)
    13.     for (j=1;j<=190;j++)
    14.     {
    15.          tam=a[j];
    16.          if (a[j]*i+nho>=10)
    17.          {
    18.              a[j]=(a[j]*i+nho)%10;
    19.              nho=(tam*i+nho)/10;
    20.          }
    21.          else
    22.          {
    23.              a[j]=a[j]*i+nho;
    24.              nho=0;
    25.          }
    26.     }
    27.     clrscr();
    28.     printf("\nGiai thua cua %d : \n\n",n);
    29.     for (i=190;i>=1;i--)
    30.     if (a[i]!=0) {tam=i;break;}
    31.    
    32.     for (i=tam;i>=1;i--) printf("%d",a[i]);
    33.     getch();
    34. }

    Mình mới tham gia diễn đàn mong các bạn xem thử code đã áp dụng theo cách trên

    Cải tiến 100! giờ mình làm dc code chạy đến 270! mong các bạn cho ý kiến

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. main()
    4. {
    5.     unsigned a[400];
    6.     int i,j,
    7.     n,nho,tam;
    8.     printf("\nnhap vao so n = ");scanf("%d",&n);
    9.     a[1]=1;tam=n;
    10.     for (j=2;j<=n;a[j]=0,j++);
    11.     n=tam;nho=0;
    12.     for (i=1;i<=n;i++)
    13.     for (j=1;j<=n;j++)
    14.     {
    15.          tam=a[j];
    16.          if (a[j]*i+nho>=100)
    17.          {
    18.              a[j]=(a[j]*i+nho)%100;
    19.              nho=(tam*i+nho)/100;
    20.          }
    21.          else
    22.          {
    23.              a[j]=a[j]*i+nho;
    24.              nho=0;
    25.          }
    26.     }
    27.     clrscr();
    28.     printf("\nGiai thua cua %d : \n\n",n);
    29.     for (i=n;i>=1;i--)
    30.     if (a[i]!=0) {tam=i;break;}
    31.    
    32.     for (i=tam;i>=1;i--)
    33.     {
    34.         if (a[i]>=10) printf("%d",a[i]);
    35.         else printf("0%d",a[i]);
    36.     }
    37.     getch();
    38. }


    Theo cách 100! trên thì 1 mảng 200 số mỗi 1 phần tử là 1 số, giờ tôi làm mỗi phần tử là 2 số như vậy việc tính 200! sẽ rất nhanh, nếu 1 phần tử a[i] là 3 số thì việc tính đến giai thừa 900! cũng ko vấn đề. Do khai báo mảng 200 phần tử thuộc kiểu Unsigned nên mỗi phần tử có thể là số có 3 chữ số => mình có thể tính đến số 200*3 = 600 chữ số. Nếu khai báo mảng 200 phần tử thuộc kiểu integer thì có thể tính đến số có 10.000 chữ số ...

  9. #9
    Ngày gia nhập
    08 2006
    Bài viết
    19

    @ leonn88: 100! và 200! khác nhau là mấy đâu nhỉ? mình thấy cách làm của bạn có điểm khá đặc biệt, bình thường mọi người thường dùng mảng byte hoặc char, mỗi ô chỉ lưu 1 chữ số. Bạn lưu liền 1 lúc 3 ch/s, tuy nhiên cách này mình thấy khá là rắc rối- chưa kiểm tra thời gian chạy chương trình nhanh hay chậm hơn bình thường
    Tại sao mọi người không mở rộng hơn 1 chút nhỉ? cứ gì phải tính n! tổng quát nhất cứ nhân 2 số lớn bất kì với nhau xem nào VD:
    1111111111111111111111111111111111
    x 9999999999999999999999999999999999
    giải quyết được bài toán này thì có thể áp dụng cho tính giai thừa vô tư

  10. #10
    No Avatar
    Leon88 Khách

    $melaptrinh : byte tức là unsigned có giá trị từ 0..255 và nó đến 8bit mà dùng lưu trữ 1 số thì có uổng ko ? Nên mình mới cho nó lưu trữ đến 2 số (99 là max) ko thể lưu trữ dc 3 số vì nó chỉ có đến 255 mà ko đến 999, theo cách lưu trữ 1 số thì ko thể tính giai thừa 120!+ dc việc lưu 2 số cho ta tính đến giai thừa của 200! và mình text rồi ko đến 1s là ra kết quả. Còn bài nhân 2 số cực lớn sẽ ra 1 số rất là cực lớn việc nhập và xuất cũng phải dùng đến 3 mảng char rồi. Nhưng nó cũng khá hay để tôi cố gắng làm thử :P

    C++ Code:
    1. #include <iostream.h>
    2.  
    3. long giaithua (long a)
    4. {
    5.   if (a > 1)
    6.    return (a * giaithua (a-1));
    7.   else
    8.    return (1);
    9. }
    10.  
    11. int main ()
    12. {
    13.   long x;
    14.   cout << "Nhập vào x : ";
    15.   cin >> x;
    16.   cout << x << "!" << " = " << giaithua (x);
    17.   return 0;
    18. }
    Đó là chương trình tính giai thừa bằng cách đệ qui. Từ đây có thể xây dựng lại cách tính giai thừa = đệ qui đối với số lớn

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

  1. Chung cư Đại Thanh giá rẻ ở ngay giá gốc sốc 10 triệu
    Gửi bởi haonhien68 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 05-12-2013, 06:42 PM
  2. Atlazbooks giảm giá 25% nhiều đầu sách nhân ngày 8-3
    Gửi bởi pipilazy trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 25-02-2012, 11:35 PM
  3. Giai thừa, Tính toán giai thừa trong lập trình C
    Gửi bởi congthao 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: 14-07-2009, 01:12 PM

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