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

[javi]

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

[neverland87]

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é

[shinichi_haha]

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

[kidkid]

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ỉ ?

[shinichi_haha]

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

[javi]

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

[melaptrinh]

Ở đâ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ỉ )

[Leon88]

#include<stdio.h>#include<conio.h>main(){    unsigned a[200];    int i,j,    n,nho,tam;    printf("\nnhap vao so n = ");scanf("%d",&n);    a[1]=1;tam=n;    for (j=2;j<=200;a[j]=0,j++);    n=tam;nho=0;    for (i=1;i<=n;i++)    for (j=1;j<=190;j++)    {         tam=a[j];         if (a[j]*i+nho>=10)         {             a[j]=(a[j]*i+nho)%10;             nho=(tam*i+nho)/10;         }         else         {             a[j]=a[j]*i+nho;             nho=0;         }    }    clrscr();    printf("\nGiai thua cua %d : \n\n",n);    for (i=190;i>=1;i--)    if (a[i]!=0) {tam=i;break;}        for (i=tam;i>=1;i--) printf("%d",a[i]);    getch();}

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

#include<stdio.h>#include<conio.h>main(){    unsigned a[400];    int i,j,    n,nho,tam;    printf("\nnhap vao so n = ");scanf("%d",&n);    a[1]=1;tam=n;    for (j=2;j<=n;a[j]=0,j++);    n=tam;nho=0;    for (i=1;i<=n;i++)    for (j=1;j<=n;j++)    {         tam=a[j];         if (a[j]*i+nho>=100)         {             a[j]=(a[j]*i+nho)%100;             nho=(tam*i+nho)/100;         }         else         {             a[j]=a[j]*i+nho;             nho=0;         }    }    clrscr();    printf("\nGiai thua cua %d : \n\n",n);    for (i=n;i>=1;i--)    if (a[i]!=0) {tam=i;break;}        for (i=tam;i>=1;i--)    {        if (a[i]>=10) printf("%d",a[i]);        else printf("0%d",a[i]);    }    getch();}

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

[melaptrinh]

@ 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ư

[Leon88]

$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

#include <iostream.h> long giaithua (long a){  if (a > 1)   return (a * giaithua (a-1));  else   return (1);} int main (){  long x;  cout << "Nhập vào x : ";  cin >> x;  cout << x << "!" << " = " << giaithua (x);  return 0;}

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