Tóm Tắt
Giai thừa của số lớn -C/C++
Posted at 6:35 AM |  in
Như chúng ta đã biết, để viết 1 hàm tính giai thừa rất đơn giản, có thể dùng vòng lặp for hay đệ quy…
Nhưng vấn đề đặt ra ở đây là trong những cách trên ta đều phải dùng 1 biến để lưu kết quả, mà 1 biến như vậy chắc chắn sẽ bị hạn chế.Vì sao ???
Kiểu dữ liệu rất lớn như long long cũng chỉ biểu diễn được -9 223 372 036 854 775 808 tới 9 223 372 036 854 775 807
Nếu ta dùng unsigned long long thì được từ 0 đến 18 446 744 073 709 551 615
Như vậy lớn nhất thì cũng chỉ biểu diễn được các số có khoảng 19 chữ số, vậy lớn hơn thì sao ??? , ta phải lưu kết quả vào biến nào.
20!=2432902008176640000, OK, 19 chữ số vẫn được
Vậy 21!=20! . 21 > 20! . 10 —> kết quả ít nhất cũng có 20 chữ số, mà chính xác là 21!=51090942171709440000
Vậy từ 21 trở đi, làm sao để tính giai thừa ,100!=???, 1000!=???, tính đươc không? Được.
Nếu dùng 1 biến lưu kết quả không được, vậy tại sao ta không dùng mảng, một mảng thì có thể khai báo chứa mấy chục nghìn phần tử hoặc hơn nữa, mỗi phần tử ta biểu diễn 1 chữ số của kết quả, như vậy ta có thể biểu diễn được số có tới mấy chục nghìn chữ số, như vậy là OK hơn rất nhiều so với 19 chữ số như cách thông thường.
Vậy làm sao để lưu các chữ số vào 1 phần tử của mảng đây ???
Chúng ta có thể nghiên cứu thuật toán sau:
n!=1.2.3…(n-1).n
Ý tưởng ta sẽ làm như sau:
Ban đầu ta nhân 1.2 trước, được bao nhiêu thì lưu vào mảng.
1.2=2, vì 2 chỉ có 1 chữ số nên ta chỉ cần dùng 1 phần tử, lưu 2 vào A[0].
KQ 2: A[0]
2
Tiếp tục nhân tiếp với 3, A[0].3=6 cũng chỉ có 1 chữ số, ta lưu 6 vào A[0], như vậy A[0] bây giờ bằng 6 chứ ko phải bằng 2 nữa.
KQ 6: A[0]
6
Tiếp tục nhân tiếp với 4, A[0].4=24, nên nhớ một phần tử ta chỉ lưu 1 chữ số của kết qủa, vậy ta lưu A[0] bằng 4, còn 2 ??? , ta sẽ lưu 2 vào A[1] ( khi này mảng có 2 phần tử )
KQ 24: A[1] A[0]
2 4
Tiếp tục, nhân tiếp cho 5
24
x 5
120
lấy 4 nhân 5 được 20, viết 0, nhớ 2,
2 nhân 5 được 10, nhớ 2 ở hàng đơn vị nữa là 12, vậy kết quả là 120.
Hoàn toàn tương tự, bây giờ A[0]=4 đóng vai trò là hàng đơn vị, A[1]=2 đóng vai trò là hàng chục
A[0].5=20, vì mỗi phần tử của mảng chỉ lưu một chữ số nên A[0]=0, nhớ 2 vào hàng chục, vậy ta sẽ dùng 1 biến r để lưu giá trị nhớ này, r=2; lấy A[1].5=2.5=10, cộng với r=2 nữa( dư ở hàng đơn vị ) là được 12, mà 12 thì có 2 chữ số, một mình A[1] không thể lưu , vậy ta lưu A[1]=2, còn chữ số 1 lưu vào A[2].
kết qủa 120 tương ứng A[2] A[1] A[0]
1 2 0
Tiếp tục, nhân tiếp cho 6
120 A[2] A[1] A[0]
x 6 x 6
720 7 2 0
0 nhân 6 được 0; viết 0
2 nhân 6 được 12, viết 2 nhớ 1
1 nhân 6 được 6, nhớ 1 nữa là 7, vậy kết quả là 720
Hoàn toàn tương tự
A[0].6=0.6=0, suy ra A[0]=0, số dư để cộng vào khi nhân A[1] là r=0;
A[1].6=2.6=12, cộng với r=0, vẫn là 12, suy ra A[1]=2, nhớ 1 vào biến r, gán r=1
A[2].6=6, cộng r=1 nữa là 7, vậy A[2]=7
kết qủa 720 tương ứng A[2] A[1] A[0]
7 2 0
Tiếp tục nhân cho 7
720 A[2] A[1] A[0]
x 7 x 7
5040 50 4 0
A[0].7=0.7=0, suy ra A[0]=0; r=0;
A[1].7=2.4=14, cộng r=0 vẫn là 14, suy ra A[1]=4, r=1;
A[2].7=7.7=49, cộng r=1 nữa là 50, suy ra A[2]=0, lâý thêm A[3]=5
Kết quả 5040 tương ứng A[3] A[2] A[1] A[0]
5 0 4 0
( bây giờ mảng có 4 phần tử chứa 4 chữ số của kết quả )
Hoàn toàn tương tự, tiếp tục nhân cho 8, rồi nhân cho 9, …. , nhân cho n thì sẽ được kết quả
Vậy quy luật của nó là gì ???
Bước đầu ta sẽ khởi tạo 1 mảng có 1 phần tử, A[0]=1
Ta sẽ lấy mảng này nhân cho 2, kết quả như thế nào thì lưu lại vào mảng
Tiếp tục lấy mảng kết quả trên nhân cho 3, kết quả như thế nào thì lưu lại vào mảng
Tiếp tục như vậy khi nhân tới n thì mảng cuối cùng sẽ cho ta kết quả của n!
Việc còn lại chỉ là in mảng đó ra là xong
Để chạy vòng lặp này, rất đơn giản, ta chỉ cần for(i=2;i<=n;i++){
thực hiện nhân và lưu kết quả lại vào mảng }
Bây giờ xét: “
thực hiện nhân và lưu kết quả lại vào mảng
“
Xét trong 1 quá trình mảng nhân với i ( 2<=i <=n ), khi này mảng có m phần tử
Ta sẽ lấy từng phần tử của mảng nhân với i, từ A[0] đến A[m]
Xét 1 phần tử bất kì A[j], có r là số dư khi nhân i với phần tử A[j-1];
Gán s=A[j]*i+r; ( A[j] của mảng trước khi nhân )
Vì A[j] chỉ lưu được 1 chữ số nên ta lưu A[j]=s%10 ( A[j] của mảng sau khi nhân )
còn số dư r=s/10;
Cứ tiếp tục như vậy đến A[m-1]- phần tử cuối cùng của mảng, nếu khi đó r=0 thì coi như xong, ta được một mảng mới.
Vậy r>0 thì sao???
Ta sẽ lấy thêm 1 phần tử để lưu vào mảng, A[m]=r; khi này mảng có m+1 phần tử
Nhưng nếu r>=10 thì sao ???, ta không thể lưu A[m]=r ( vì mỗi phần tử chỉ lưu 1 chữ số )
Vậy ta lưu A[m]=r%10; tăng số phần tử của mảng lên 1 đơn vị và r=r/10;
Nếu r>0 thì tiếp tục lưu A[m+1]=r%10, tăng số phần tử của mảng lên 1 đơn vị nữa;
Cứ tiếp tục như vậy cho đến khi số dư r bằng 0 thì sẽ không cần phải tìm một phần tử nữa của mảng để lưu kết quả và mảng mới coi như đã hoàn thành
Vậy code của việc ” thực hiện nhân và lưu kết quả lại vào mảng” là:
for(j=0;j<m;j++){
s=A[j]*i+r;
A[j]=s%10;
r=s/10; }
while(r>0){
A[m]=r%10;
m++;
r/=10; }
Khi ban đầu khởi tạo, m( số phần tử của mảng) =1; còn r=0 ( vì mới lúc đầu nhân thì ta chưa có số dư nào cả ), nên khởi tạo mảng có số phần tử tối đa lơn môtj tí cho chắc
Ta cũng có thể không dùng biến s
ta sẽ lưu r=q; r=(A[j]*i+r)/10; A[j]=(A[j]*i+r)%10;
Cách này chắc chắn không tối ưu, nhưng không sao, số ta tính được giai thừa cũng khá lớn rồi, lớn hơn rất nhiều so với số 20 của cách thông thường
Vậy chương trinh có thể viết như sau:
#include<stdio.h>
void giaithua(int n );
int main(){
int n;
printf(“Nhap so can tinh giai thua: “);
scanf(“%d”,&n);
printf(“Ket qua la: “);
giaithua(n);
}
void giaithua(int n){
int A[500000],i,j,m=1;
long long r=0,q;
A[0]=1;
for(i=2;i<=n;i++){
for(j=0;j<m;j++){
q=r;
r=(A[j]*i+r)/10;
A[j]=(A[j]*i+q)%10;
}
while(r>0){
A[m]=r%10;
m++;
r=r/10;
}
}
for(i=m-1;i>=0;i–) printf(“%d”,A[i]);
}
Demo:
Mở rộng:
Ta dùng một phần tử của mảng để lưu 1 chữ số của kết quả, vậy tại sao ta không dùng một phần tử của mảng để lưu 2, 3 hay 4 chữ số của kết quả. Như vậy được không ???
Cái khó ở cách này là nếu mỗi phần tử mảng lưu i chữ số của kết quả mà khi tính được chỉ có j<i chữ số thì ta phải tự động thêm vào i-j chữ số 0 phía trước khi in kết quả( ví dụ mỗi mảng lưu 4 chữ số, A[3]=23 thì phải chuyển A[3]=0023), cái này chắc phải dùng thêm 1 hàm xuất vậy, mà nếu vậy thì lại tốn thêm thời gian gọi hàm xuất, chưa chắc chương trình chay nhanh hơn.
Việc thực hiện lưu như vậy cũng dễ gây hiện tượng tràn biến q, r hơn so với lưu 1 chữ số ( tại sao ??? – bởi A[j] càng lớn thì A[j]*i+r sẽ càng lớn )
Có thể thuật toán này chưa tối ưu nhất, nhưng nó cũng tính được giai thừa của số khoảng 40000, lớn hơn rất nhiều so với số 20 của cách thông thường
720 A[2] A[1] A[0]5040 50 4 0A[0].7=0.7=0, suy ra A[0]=0; r=0;A[1].7=2.4=14, cộng r=0 vẫn là 14, suy ra A[1]=4, r=1;A[2].7=7.7=49, cộng r=1 nữa là 50, suy ra A[2]=0, lâý thêm A[3]=5Kết quả 5040 tương ứng A[3] A[2] A[1] A[0]5 0 4 0( bây giờ mảng có 4 phần tử chứa 4 chữ số của kết quả )Bước đầu ta sẽ khởi tạo 1 mảng có 1 phần tử, A[0]=1Ta sẽ lấy mảng này nhân cho 2, kết quả như thế nào thì lưu lại vào mảngTiếp tục lấy mảng kết quả trên nhân cho 3, kết quả như thế nào thì lưu lại vào mảngTiếp tục như vậy khi nhân tới n thì mảng cuối cùng sẽ cho ta kết quả của n!Việc còn lại chỉ là in mảng đó ra là xongĐể chạy vòng lặp này, rất đơn giản, ta chỉ cần for(i=2;i<=n;i++){Bây giờ xét: “Xét trong 1 quá trình mảng nhân với i ( 2<=i <=n ), khi này mảng có m phần tửTa sẽ lấy từng phần tử của mảng nhân với i, từ A[0] đến A[m]Xét 1 phần tử bất kì A[j], có r là số dư khi nhân i với phần tử A[j-1];Gán s=A[j]*i+r; ( A[j] của mảng trước khi nhân )Vì A[j] chỉ lưu được 1 chữ số nên ta lưu A[j]=s%10 ( A[j] của mảng sau khi nhân )còn số dư r=s/10;Cứ tiếp tục như vậy đến A[m-1]- phần tử cuối cùng của mảng, nếu khi đó r=0 thì coi như xong, ta được một mảng mới.Vậy r>0 thì sao???Ta sẽ lấy thêm 1 phần tử để lưu vào mảng, A[m]=r; khi này mảng có m+1 phần tửNhưng nếu r>=10 thì sao ???, ta không thể lưu A[m]=r ( vì mỗi phần tử chỉ lưu 1 chữ số )Vậy ta lưu A[m]=r%10; tăng số phần tử của mảng lên 1 đơn vị và r=r/10;Nếu r>0 thì tiếp tục lưu A[m+1]=r%10, tăng số phần tử của mảng lên 1 đơn vị nữa;Cứ tiếp tục như vậy cho đến khi số dư r bằng 0 thì sẽ không cần phải tìm một phần tử nữa của mảng để lưu kết quả và mảng mới coi như đã hoàn thànhfor(j=0;j0){A[m]=r%10;m++;r/=10; }Khi ban đầu khởi tạo, m( số phần tử của mảng) =1; còn r=0 ( vì mới lúc đầu nhân thì ta chưa có số dư nào cả ), nên khởi tạo mảng có số phần tử tối đa lơn môtj tí cho chắcTa cũng có thể không dùng biến sta sẽ lưu r=q; r=(A[j]*i+r)/10; A[j]=(A[j]*i+r)%10;Cách này chắc chắn không tối ưu, nhưng không sao, số ta tính được giai thừa cũng khá lớn rồi, lớn hơn rất nhiều so với số 20 của cách thông thường#includevoid giaithua(int n );int main(){int n;printf(“Nhap so can tinh giai thua: “);scanf(“%d”,&n);printf(“Ket qua la: “);giaithua(n);void giaithua(int n){int A[500000],i,j,m=1;long long r=0,q;A[0]=1;for(i=2;i<=n;i++){for(j=0;j0){A[m]=r%10;m++;r=r/10;for(i=m-1;i>=0;i–) printf(“%d”,A[i]);Demo:Ta dùng một phần tử của mảng để lưu 1 chữ số của kết quả, vậy tại sao ta không dùng một phần tử của mảng để lưu 2, 3 hay 4 chữ số của kết quả. Như vậy được không ???Cái khó ở cách này là nếu mỗi phần tử mảng lưu i chữ số của kết quả mà khi tính được chỉ có j
Nice to meet you
Welcome to Programming
Programming
POPULAR POSTS
-
Giai thừa của số lớn -C/C++ -
Đạo lập trình / The Tao of Programming
