Cách tính 3^10.000 trong C như thế nào?

[Shanks]

Đâ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!

[mini_bestboy]

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

[Shanks]

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 có thể nói rõ cho mình được không? Thanks bạn nhiều!

[mini_bestboy]

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

[maitan_10000]

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 :(

#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];        printf("Nhap co so (mot chu so): ");    scanf("%d", &coso);    printf("Nhap so mu: ");    scanf("%d", &somu);    LuyThua(a, coso, somu);    printf("KQ cua %d mu %d la: \n", 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)        {            printf("%d", a[i]);        }    }    printf("\n");}

[mini_bestboy]

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

[Shanks]

Hì, thanks mọi người rất nhiều!

[clamvn]

#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;   while (i<=atoi(argv[1])) {    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++;  }     printf("ket qua cua 2^%d :    ",atoi(argv[1]));  for(l=j;l<SIZE;l++)    printf("%d",array[l]);  return 0; }

dựa vào bài này viết bài của bạn nhé

[azurelonely]

Thuật toán chưa tối ưu...chờ đến 45s ~~

#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--;      }   }    for (short unsigned int i=end(luu);i<max;i++) printf("%u",luu[i]);   scanf("%*c");   return 0;}

Nguồn VN-EASY.COM

[Shanks]

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!