Mình nghĩ bạn có thể dùng số nguyên lớn để giải bài toán này: dùng mảng để chưa từng kí số !
Đây là 1 bài tập trên lớp thầy mình ra...các bạn có thể giúp mình cách tính 3^10.000 không?
Thanks các bạn nhiều!
Mình nghĩ bạn có thể dùng số nguyên lớn để giải bài toán này: dùng mảng để chưa từng kí số !
Bạn tạo 1 mảng. Mỗi phần tử của mảng sẽ chứa 1 chữ số của con số kết quả bài toán !
Ví như số 123456 sẽ được lưu vào mảng 6 phần tử,các ptử lần lượt là 1 2 3 4 5 6
Tạo 1 hàm thực hiện phép nhân trên từng phần tử như bạn nhân có nhớ hồi cấp 1 ý ! Nhân từng số, có nhớ, cộng vào số tiếp theo ...
Sau đó cho 1 vòng lặp chạy 10000 lần, mỗi lần bạn sẽ dùng hàm đó, nhân mảng của bạn với số 3 !
Không biết cách này tốt chưa vì số tạo ra khá lớn, sẽ chạy lâu (dự đoán chắc <5000 chữ số)
bạn xem thử code này, mình mới tập code nên cứ có bài là code thử cho biết:
có một vấn đề hơi chán là code này chạy kết quả 3 mũ 10000 mất đến 8.8 s :(
C Code:
#include <stdio.h> #define MAX 5000 //Prototype void LuyThua(int a[MAX], int coso, int somu); void InKQ(int a[MAX]); main() { int coso, somu; int a[MAX]; LuyThua(a, coso, somu); InKQ(a); } void LuyThua(int a[MAX], int coso, int somu) { int i, nho = 0, tam; //khoi tao a[0] = 1; for(i = 1;i < MAX;i++) { a[i] = 0; } //tinh for(;somu > 0; somu--) { for(i = 0; i < MAX; i++) { tam = (a[i]*coso + nho); a[i] = tam%10; nho = tam/10; } } } void InKQ(int a[MAX]) { int i, flag = 0; for(i = MAX - 1; i >= 0;i-- ) { if (a[i + 1] == 0 && a[i] != 0) { flag = 1; } if(flag == 1) { } } }
@maitan_10000: Đoạn code bạn chạy lâu có lẽ do dư phần lúc tính, bạn cho i chạy 0->MAX mặc dù ban đầu thì mảng chỉ có thật sự 1,2 chữ số thôi, do đó chạy khá là lâu ! Nên cải tiến lại bằng cách kết hợp lưu số chữ số của kết quả (tức số phần tử mảng A), như thế ta cho i chạy -> numOfArray thôi, sẽ nhanh hơn đó
Một cách cải tiến hơn nữa, bạn có thể dùng 1 mảng kiểu long để chứa số, vì 1 biến long lưu được 1 số đến 9 chữ số. Và mỗi lần duyệt bạn vẫn nhân từng số cho số mũ, nếu lớn hơn 9 chữ số thì chuyển phần nguyên kết quả qua phần tử tiếp theo ! Do đó mảng chỉ cần khoảng [5000/9] phần tử, và khi lũy thừa cũng giảm được đến 9 lần tính toán so với cách trên nhỉ ^^
Dù sao vẫn nghĩ thầy bạn chỉ yêu cầu thuật toán thôi, chứ kết quả đến cả ngàn chữ số thì kiểm tra mệt đấy !
Hì, thanks mọi người rất nhiều!
C Code:
#include<stdio.h> #include<stdlib.h> #define SIZE 1000000 int main(int argc,char *argv[]){ int array[SIZE]; int i=1; int j=SIZE-1; array[SIZE-1]=1; int l; for(l=0;l<SIZE-1;l++) array[l]=0; int k=SIZE-1; int sup=0; while(k>=(j-1)){ int temp=(sup+array[k]*2) %10; sup=(sup+array[k]*2)/10; array[k]=temp; k--; } if(array[j-1]!=0) j=j-1; i++; } for(l=j;l<SIZE;l++) return 0; }
dựa vào bài này viết bài của bạn nhé
Come as guest...... stay as family......... because we're smiling together.
Thuật toán chưa tối ưu...chờ đến 45s ~~
C Code:
#include <stdio.h> #define max 10000 #define val 2000 short unsigned int end(const unsigned int a[]) { short unsigned int i=0; while (a[i++]==0); return i-1; } int main(void) { unsigned int luu[max]; short unsigned int m; for (short unsigned int i=0;i<max;i++) (luu[i]=0); luu[max-1]=1; for (short unsigned int i=1;i<=val;i++) { m=max-1; short unsigned int nho=0; while (m>=end(luu) || nho>0) { luu[m]*=729; luu[m]+=nho; nho=luu[m]/10; luu[m]%=10; m--; } } return 0; }
Nguồn VN-EASY.COM
Ai bất tài, tôi nhìn hoài chẳng thấy,
Đi khắp phòng tôi lấy 1 tấm gương,
Khẽ đặt lên một góc phía bức tường,
Nhìn vào đó, tôi tận tường kẻ đó.
Thanks mọi người nhiều...nhưng bạn nào chạy ra rùi có thể cho mình kết quả được không? Mình ngàn lần cảm ơn nhiều!
Đã được chỉnh sửa lần cuối bởi Shanks : 10-08-2011 lúc 11:33 AM.