PDA

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



javi
14-03-2007, 12:00 PM
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 :D
+ 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
17-03-2007, 04:27 PM
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
17-03-2007, 05:05 PM
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
17-03-2007, 05:28 PM
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
17-03-2007, 05:40 PM
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
18-03-2007, 10:23 AM
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
18-03-2007, 09:05 PM
Ở đâ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(=D)>
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
19-03-2007, 10:18 PM
#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ố ... :D

melaptrinh
20-03-2007, 05:13 PM
@ 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
20-03-2007, 06:42 PM
$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

javi
22-03-2007, 08:02 AM
Cải tiến 100! giờ mình làm dc code chạy đến 270! mong các bạn cho ý kiến

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

Bài này để vòng for thứ 2 duyệt từ 1 đến n thì hơi uổng.
Mình viết như sau. Chỉ khi có carry mới tăng số vòng lặp lên.
num = 10, 100, 1000 ... tùy theo cách chọn kiểu biến. carry = nhớ; tmp = tạm


for (i=2; i<=N; i++){
carry = 0;
for(j=0; j<=count; j++){
tmp = a[j] * i;
a[j] = tmp%num + carry;
if ((tmp/num) > 0) {
carry = tmp/num;
if(j==count)count++;//tăng số vòng lặp
}
}
}

hoangvnt
01-04-2007, 12:20 AM
Để tính toán với số lớn, thông thường phải tự tạo kiểu dữ liệu riêng. Các bạn có thể tham khảo thư viện tính toán số lớn GMP http://gmplib.org/. Thư viện này có thể tính toán chính xác những số cực lớn. Đây là thư viện mã nguồn mở nên các bạn có thể tham khảo source code (nếu cần thiết:)). Thư viện có thể tính được 500000! trong vòng 1412 ms đấy!!!

HKuspc
09-04-2007, 02:58 PM
mình dùng 1 hàm cộng 2 chuỗi số và 1 hàm nhân 2 chuỗi số(2 hàm này đương nhiên là ko có sẵn)và đã chạy được đến 7000! nhìn con số kết quả tuôn ra đầy màn hình dzui lắm

Paraside
09-04-2007, 05:33 PM
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
không biết bạn đã test chưa. Nhưng tui test bài của bạn thì thấy nó không work gì hết trơn. Lý do: khi bạn gán biến n=tam ....... sau đó lại gán tam=n (dư thừa tại đây. (:-)? Tại sao không bỏ đi? ===> Kết quả là : work.

nanh
07-06-2007, 11:00 AM
100 ! = có khoảng 157 chữ số nên đặt N = 200 là ok rồi
100! chính xác có 158 chữ số, tôi đã viết chương trình và chạy, tính rất nhanh, mảng 200 phần tử, có thể tính được đến 211!
Có cách nào để tính được >211! ???

tientu
09-06-2007, 01:28 AM
mình có một vấn đề: thây giáo dạy mình cho btvn có một dung rất ngắn gọn:
"viết một chương trinh c để lập một ma phương bất kỳ"(đã biết ma phương là một ma trận vuông cấp n x n có các hàng =các cột=đường chéo chính=đường chéo phụ).mình nghĩ mãi không ra .ai có thể giúp mình giải quyết bài mày không,có thể đưa ý tương xử lý hoặc viết được code càng tốt.
xin cảm ơn!

rox_rook
05-03-2008, 03:55 PM
Hix, hôm nay có dịp đụng nó mới thấy mệt mỏi T_T, ai thích thì mình cho code luôn đây. 1000! giai thừa luôn :D.


#include <iostream>
#include <cmath>
#include <vector>

typedef unsigned int USI;
typedef std::vector<USI> factorial;

/*Function prototype*/
void displayFactorial(std::ostream& , factorial& );
double calculateDigits(USI );
void readInNumber(std::istream& , std::ostream& );
void findFactorial(factorial& , USI , USI );

int main()
{
readInNumber(std::cin, std::cout);
return 0;
}

void displayFactorial(std::ostream &oss, factorial& aFact)
{
for(int x = aFact.size() - 1; x >= 0; --x){
oss << aFact[x];
}
}

double calculateDigits(USI _mNumber)
{
double approxi = 0.0;
for(USI digit = 2; digit <= _mNumber; ++digit)
approxi += std::log10(digit);
return approxi;
}

void readInNumber(std::istream &iss, std::ostream &oss)
{
USI _mNumber;
oss << "\nPlease enter a number : ";
iss >> _mNumber;

USI numberOfDigits = static_cast<int>(calculateDigits(_mNumber)) + 1;
factorial _mDigit(numberOfDigits, 0);
_mDigit[0] = 1;
findFactorial(_mDigit, numberOfDigits, _mNumber);
}


void findFactorial(factorial &aFact, USI numberOfDigits, USI _mNumber)
{
USI remainder, _zZemp, value;
double temp = 0.0;
for(USI dig = 2; dig <= _mNumber; ++dig)
{
remainder = 0;
temp += std::log10(dig);
_zZemp = static_cast<int>(temp) + 1;

for(int index = 0; index <= _zZemp; ++index)
{
value = (aFact[index] * dig) + remainder;
remainder = (value / 10);
aFact[index] = (value % 10);
}
}
std::cout << _mNumber << "! : \n";
displayFactorial(std::cout, aFact);
}

dragon143
05-07-2009, 12:09 AM
Tựa đề 100! (:-)? (:-)? . He he, kiểu này 80% học chung thầy với tui rồi. Hôm nay mới nộp bài xong. Cho file exe tham khao nè (:P)

mp121209
18-11-2010, 06:21 AM
1000! thì có gì ghê nhờ, mình cũng nghịch tí tính 50 000! luôn :P


#include <stdio.h>
#include <conio.h>
unsigned short array[1000] = {1};
unsigned int len= 1;

#define FACTOR 1000

int main()
{
// TODO: Place code here.
clrscr();
unsigned int i;
unsigned long l;
unsigned long cn;

cn= 0;
for(l= 1; l<=FACTOR; l++)
{
for(i= 0; i<len || cn; i++)
{
cn+= array[i]*l;
array[i]= (unsigned short)(cn%10000);
cn/= 10000;
}
len= i;
}

printf("%d", array[len-1]);
for(i= len-1; i--;)
{
printf("%04d", array[i]);
}

printf("\n");

return 0;
}