Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Xử lý số lớn | Chia 2 số nguyên có 30 chữ số

  1. #1
    Ngày gia nhập
    09 2006
    Bài viết
    20

    Mặc định Xử lý số lớn | Chia 2 số nguyên có 30 chữ số

    CHo mình hỏi về cáhc chia 2 số nguyên có 30 chữ số, cộng trừ nhân thì ok hết rồi còn các toán chia này không biét lam sao hết.??bạn nào chỉ giúp mình

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mỗi một số là một đa thức của x với x=10, chữ số thứ i là hệ số của phần tử bậc i (tính từ bậc 0) Ví dụ: 1234 có biểu diễn đa thức là 1*10^3+2*10^2+3*10+4
    Như vậy mỗi số là một đa thức, chia hai số chính là chia hai đa thức, cái này thì học từ lớp 7, bạn có thể dùng mảng để biểu diễn nó.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Trích dẫn Nguyên bản được gửi bởi hailoc12
    Mỗi một số là một đa thức của x với x=10, chữ số thứ i là hệ số của phần tử bậc i (tính từ bậc 0) Ví dụ: 1234 có biểu diễn đa thức là 1*10^3+2*10^2+3*10+4
    Như vậy mỗi số là một đa thức, chia hai số chính là chia hai đa thức, cái này thì học từ lớp 7, bạn có thể dùng mảng để biểu diễn nó.
    Cách làm này không hợp lý lắm. Vì như vậy đôi khi các hệ số sẽ là âm, và ta sẽ mất công tính lại.

    Có lẽ làm theo cách mà chúng ta vẫn làm = tay thì tốt hơn.

  4. #4
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Mỗi một số là một đa thức của x với x=10, chữ số thứ i là hệ số của phần tử bậc i (tính từ bậc 0) Ví dụ: 1234 có biểu diễn đa thức là 1*10^3+2*10^2+3*10+4
    Như vậy mỗi số là một đa thức, chia hai số chính là chia hai đa thức, cái này thì học từ lớp 7, bạn có thể dùng mảng để biểu diễn nó.
    => tui xin có chút thắc mắc:

    100=1*10^3
    2=2*10^0
    50=5*10^2

    Mình biết 100/2 = 50

    Không biết tui có hiểu lầm ý của bạn hailoc12 hay không: coi 100 như x^3, coi 2 như 2 (2*x^0), và coi 50 như 5*x^2
    => x^3/2 = 5*x^2
    =>x^3 = 2*(5*x^2) = 10*x^2 (***)

    Dĩ nhiên là mình thấy ngay (***) là không đúng: nó chỉ đúng với x bằng 10 mà thôi trong khi phép chia đa thức đòi hỏi là phải đúng với mọi x

    Theo như Tarzan: cứ làm như mình vẫn làm bằng tay => tui thấy có lý

    (có gì sai sót mong được góp ý, xin cám ơn)

    -thân

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    các ông nói ngốc thế cũng không thấy ngượng sao?
    Tui thấy giải thuật trên các số lớn nếu làm như hailoc12 là đúng rồi.
    Còn thuật toán trên đa thức thì có ngay:

    Code:
    float f1=0,f2=0;
    float a[20],b[20],c[20];
    int n,m,x,y,i,j;
    void tao_da_thuc()
     {
        textmode(C80);
        textcolor(YELLOW);
        textbackground(BLUE);
        window(1,1,80,25);
        clrscr();
        printf("Nhap bac cua da thuc A(x) n = ");
        scanf("%d",&n);
        printf("Nhap cac he so cua da thuc A(x)\n");
        for(i=n;i>=0;i--)
    	 {
    		printf("a[%d] = ",i);
    		scanf("%f",&a[i]);
    	 }
         printf("Nhap bac cua da thuc B(x) m = ");
         scanf("%d",&m);
         for(i=0;i<=m+n;i++) b[i]=0;
         for(i=n+1;i<=n+m;i++) a[i]=0;
         printf("Nhap cac he so cua da thuc B(x)\n");
        for(i=m;i>=0;i--)
    	 {
    		printf("b[%d] = ",i);
    		scanf("%f",&b[i]);
    	 }
    
       }
    
    float f(float x)
       {
          int i;
          for(i=0;i<=n;i++)
    	  {
    	      f1+= a[i]*pow(x,i);
    	  }
    
           /*for(i=0;i<=n;i++)
    	  {
    	      f2+= b[i]*pow(x,i);
    	  } */
           return(f1);
    
        }
    
    
    
    void cong_dt()
       {
         tao_da_thuc();
         if(m>n) { i=m;m=n;n=i;}
         printf(" \n da thuc C(x) =  A(x) + B(x) la ");
         printf("\n C(x) = ");
         c[n]=a[n]+b[n];
         if(c[n]!=0)printf("%g*x%d",c[n],n);
         for(i=n-1;i>=1;i--)
    	{
    	    c[i]=a[i]+b[i];
    	    if(c[i]>0)printf(" + %g*x%d",c[i],i);
    	    else if(c[i]<0)printf(" - %g*x%d",-c[i],i);
    
    	}
          c[0]=a[0]+b[0];
          if(c[0]<0) printf(" - %g",-c[0]);
          else printf(" + %g",c[0]);
          getch();
        }
    
    void tru_dt()
       {
         tao_da_thuc();
         if(m>n) { i=m;m=n;n=i; }
         printf(" \n da thuc C(x) =  A(x) - B(x) la ");
         printf("\n C(x) = ");
         c[n]=a[n]-b[n];
         if(c[n]!=0)printf("%g*x%d",c[n],n);
         for(i=n-1;i>=1;i--)
    	{
    	   c[i]=a[i]-b[i];
    
    	    if(c[i]>0)printf(" + %g*x%d",c[i],i);
    	    else if(c[i]<0)printf(" - %g*x%d",-c[i],i);
    
    	}
          c[0]=a[0]-b[0];
          if(c[0]<0) printf(" - %g",-c[0]);
          else printf(" + %g",c[0]);
         getch();
        }
    
    
    void nhan_dt()
       {
         tao_da_thuc();
         printf(" \nda thuc C(x) =  A(x) * B(x) la ");
         printf("\n C(x) = ");
         c[n+m]=a[n]*b[m];
         if(c[m+n]!=0) printf(" %g*x%d",c[m+n],m+n);
         for(i=m+n-1;i>=1;i--)
    	{
    	   for(j=i;j>=0;j--) c[i]+=a[j]*b[i-j];
    	    if(c[i]>0)printf(" + %g*x%d",c[i],i);
    	    else if(c[i]<0)printf(" - %g*x%d",-c[i],i);
    
    	}
          c[0]=a[0]*b[0];
          if(c[0]<0) printf(" - %g",-c[0]);
          else if(c[0]>0)printf(" + %g",c[0]);
         getch();
        }
    
     void chia_dt()
       {
         tao_da_thuc();
         i=n;
         printf("\n");
         while(i>=m)
    	{
    	     c[i-m]=a[i]/b[m];
    	     for(j=i-1;j>=i-m;j--)
    	     a[j]= a[j]-a[i]*b[i-j]/b[m];
    	     if(i==n)printf(" %g*x%d",c[i-m],i-m);
    	     else if(i!=n&&i!=m)
    		  {
    		   if(c[i-m]>0)printf(" + %g*x%d",c[i-m],i-m);
    		   else if(c[i-m]<0)printf(" - %g*x%d",-c[i-m],i-m);
    		  }
    	     else if(i==m)
    		  {
    		    if(c[i-m]>0)printf(" + %g",c[i-m]);
    		    else if(c[i-m]<0)printf(" - %g",-c[i-m]);
    		  }
    	     i--;
    	}
    	printf("\n");
          printf(" %g*x%d",a[m-1],m-1);
          for(j=m-2;j>=1;j--)
    	 {
    	   if(a[j]>0)  printf(" + %g*x%d",a[j],j);
    	   else if(a[j]<0) printf(" - %g*x%d",a[j],j);
    	 }
          if(a[0]>0)printf(" + %g",a[0]);
          if(a[0]<0)printf(" - %g",-a[0]);
         getch();
       }
    
    /*void nghiem_dt()
      {
         float p,q,z,epsilon=0.0000001;
         textmode(C80);
         textcolor(YELLOW);
         textbackground(BLUE);
         window(1,1,80,25);
         clrscr();
         printf("Nhap bac cua da thuc A(x) n = ");
         scanf("%d",&n);
         printf("Nhap cac he so cua da thuc A(x)\n");
         for(i=n;i>=0;i--)
    	 {
    		printf("a[%d] = ",i);
    		scanf("%f",&a[i]);
    	 }
         printf("\nNhap khoang nghiem cua da thuc (a,b) = \n");
       lai:  printf("\na = ");
         scanf("%f",&p);
         printf("b = ");
         scanf("%f",&q);
         if(f(p)*f(q)>0)printf("nhap lai khoang nghiem"); goto lai;
         i=1;
         while(pow(2,-i)<epsilon||f((p+q)/2)<epsiloni<1000)
          {
    	z=(p+q)/2;
    	if(f(p)==0) {printf("\n nghiem cua da thuc la x = %g",p);}
    	if(f(q)==0) {printf("\n nghiem cua da thuc la x = %g",q);}
    	if(f(z)==0) {printf("\n nghiem cua da thuc la x = %g",(q+p)/2);}
    	if(f(p)*f(z)<0) q=z;
    	else if(f(q)*f(z)<0) p=z;
           i++;
           printf("\n%g",z);
         }
        printf("nghiem cua da thuc la x = %g",z);
      }     */
    
     void dao_ham()
        {
           int l,i,j;
           textmode(C80);
           textcolor(YELLOW);
           textbackground(BLUE);
           window(1,1,80,25);
           clrscr();
           printf("Nhap bac cua da thuc A(x) n = ");
           scanf("%d",&n);
           printf("Nhap cac he so cua da thuc A(x)\n");
           for(i=n;i>=0;i--)
    	 {
    		printf("a[%d] = ",i);
    		scanf("%f",&a[i]);
    	 }
           printf("nhap cap cua dao ham l = ");
           scanf("%d",&l);
           for(i=n-l;i>=0;i--) c[i]=1;
    	 c[n-l]*=a[n];
           for(i=n;i>n-l;i--)
    	  c[n-l]*=i;
           printf("%g*x%d",c[n-l],n-l);
         for(i=n-1-l;i>=1;i--)
    	{
    	   c[i]=a[i+l];
    	   for(j=i+l;j>i;j--)
    	    c[i]*=j;
    	    if(c[i]>0)printf(" + %g*x%d",c[i],i);
    	    else if(c[i]<0)printf(" - %g*x%d",-c[i],i);
    
    	}
          c[0]=a[l];
         for(j=l;j>0;j--)
          c[0]*=j;
          if(c[0]<0) printf(" - %g",-c[0]);
          else printf(" + %g",c[0]);
          getch();
      }

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Xử lý số lớn | Chia 2 số nguyên có 30 chữ số

    Tui lười tách ra các phần, và trích chỉ dẫn, do đó mong mọi người vừa đọc vừa suy nghĩ và hiểu nha!

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Lần sau nếu có code bạn để trong tab code được không. Để vậy chả ai muốn đọc.

    Bạn bảo vệ ý kiến dùng đa thức, vậy chúng ta cùng làm 1 ví dụ:

    bạn chia cho tôi 3 2 số: 123456789 : 953

    Theo cách chia của tôi:
    1234 = 1*953 + 281
    2815 = 2*953 + 909
    9096 = ....
    cứ tiếp tục như vậy thì ta có kết quả: 129545 dư 404

    Đây chỉ là 1 ví dụ nhỏ nhỏ thôi, sau khi bạn trả lời. Chúng ta sẽ cùng xây dựng 1 cấu trúc dữ liệu để có thể thực sự làm việc với các số lớn 1 cách hiệu quả nhất. Khi đó, sẽ cùng chứng minh xem cách nào tối ưu hơn.

  8. #8
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Xin lỗi bạn hailoc12, tui đã nói sai. Tui nghĩ là tui đã hiểu sai ý của ban.
    Tui xin nói lại thử ý của bạn 1 lần nữa coi sao (nếu vẫn sai thì mong bạn sửa cho, cám ơn):

    100 => 1*x^3 (x=10)
    2 => 2*x^0 (x=10)
    100/2 => 1*x^3/2^x^0 => (1/2)(x^3)
    => thay x=10 vô mình sẽ có 50

    => cách làm của bạn (chia đa thức) là không có sai

    Tuy nhiên tui thấy có vài chỗ khúc mắc:

    1) mình có a và b là 2 số nguyên lớn => biểu diễn bằng mảng các chữ số. Nếu coi như là 2 đa thức thì các hệ số của các đa thức này là các số nguyên không âm. Tuy nhiên khi mình tính a/b bằng cách chia đa thức thì các hệ số của kết quả có thể không còn là các số nguyên không âm nữa (mà có thể là phân số hoặc số âm). Như vậy mình phải xài số thực (như trong ví dụ chia đa thức của PoPoPoPo) hoặc xài 1 cặp số nguyên để lưu các hệ số của kết quả

    2) Nếu mình xài số thực thì có thể phải lưu ý tới sai số. Mình có thể nghĩ là số thực (float hay double) là đủ để đảm bảo độ chính xác rồi, không cần lo. Tuy nhiên, tui nghĩ 10^3 = 1000 là xấp xỉ 2^10 (1024); như vậy 10^30 là xấp xỉ 2^100 . Tức là nếu số thực của mình có độ chính xác kém hơn 2^100 (100 bit) thì có lẽ phải coi chừng sai số

    3) Giả sử mình không phải lo về sai số thì trong trường hợp 100/2=50 mình không thể in ra 1/2*10^3 được mà phải tính toán và biểu diễn kết quả bằng 2 chữ số 5 và 0. Và để làm như vậy tui thấy mình phải có 1 hàm/thủ tục để nhân 2 đa thức (với các hệ số là số thực). Nếu mình đã có 1 hàm/thủ tục nhân 2 đa thức (nhưng với các hệ số là số nguyên -- đúng ra là hàm/thủ tục này là để nhân 2 số nguyên rất lớn) thì mình không thể xài hàm này để làm công việc trên được. Khi đó hoặc là mình phải viết 1 hàm/thủ tục mới tương tự (nhưng làm việc trên các số thực) để nhân 2 đa thức hoặc mình sửa lại cách biểu diễn số lớn của mình: biểu diễn các chữ số bằng số thực

    Nếu mình mô phỏng cách chia bằng tay thì mình cũng cần 1 hàm/thủ tục để nhân 2 đa thức. Tuy nhiên mình vì mình chỉ làm việc trên các hệ số nguyên cho nên mình có thể xài lại hàm /thủ tục nhân 2 số lớn sẵn có. Có điều là tại mỗi bước tui nghĩ mình phải làm mò 1 chút; ví dụ như của Tarzan đưa ra:
    2815 = 2*953 + 909
    => mình phải thử mới biết 1 là quá nhỏ, 3 là quá lớn => chọn ra 2 là vừa

    -thân
    Đã được chỉnh sửa lần cuối bởi bete : 09-10-2006 lúc 11:13 AM.

  9. #9
    Ngày gia nhập
    09 2009
    Bài viết
    24

    Mặc định chia hai đa thức

    minhf cũng chưa biết cách chia 2 đa thức. bạn nào co giải thuật chia 2 đa thức(bằng C càng tốt) thì cho mình với, cảm ơn

  10. #10
    Ngày gia nhập
    09 2009
    Bài viết
    24

    Wink cách chia đa thức

    bobobobo dưa gt sai rôi, nó không chạy được
    tham khảo gt sau xem sao.
    Code:
    #include<stdio.h>
    #include<math.h>
    #include<conio.h>
    #include<ctype.h>
    int max(int a,int b)
    {
    	if(a>=b)
    		return a;
    	else
    		return b;
    }
    void main()
    {       clrscr();
    	int i,n,m,j,p,k;
    	float a[100],b[100],c[100];
    	printf("\n\t\t\tCHUONG TRINH CHIA 2 DA THUC");
    	printf("\n\t\t\t--------***********--------");
    	printf("\n Ban hay nhap bac cua da thuc bi chia B : ");
    	scanf("%d",&n);
    	printf("\n Ban hay nhap vao he so cua B[i] : ");
    	for (i=0;i<=n;i++)
    		{
    			printf("\n\t b[%d] = ",i);
    			scanf("%f",&b[i]);
    		}
    	printf("\n Ban hay nhap bac cua da thuc chia C : ");
    	scanf("%d",&m);
    	printf("\n Ban hay nhap vao he so C[i] : ");
    	for (i=0;i<=m;i++)
    		{
    			printf("\n\t c[%d] = ",i);
    			scanf("%f",&c[i]);
    		}
    	p=n-m;
    	for(i=0;i<=p;i++)
    				for(j=max(0,i-n);j<=i-1;j++)
    		  {  	 	a[0]=b[0]/c[0];
    				a[i]=(b[i]/c[0])-(a[j]*c[i-j])/c[0];
    
    		  }
    
    	printf("\n\t DA THUC THUONG:");
    	for(i=0;i<=p;i++)
    
    	 {
    	   if(a[i]>0)  printf(" + %3.2f*x^%d",a[i],p-i);
    	   else if(a[i]<0) printf(" %3.2f*x^%d",a[i],p-i);
    	 }
    
    	for(i=p+1;i<=n;i++)
    		for(j=max(0,i-m);j<=p;j++)
    			a[i]=b[i]-a[j]*c[i-j];
    
    
    	printf("\n\t DA THUC DU: ");
    	for(i=p+1;i<=n;i++)
    	 {
    	   if(a[i]>0)  printf(" + %3.2f*x^%d",a[i],n-i);
    	   else if(a[i]<0) printf(" %3.2f*x^%d",a[i],n-i);
    	 }
    
    	getch();
    }

Các đề tài tương tự

  1. Trả lời: 4
    Bài viết cuối: 09-02-2012, 10:42 PM
  2. Kỹ thuật C++ Lời giải về Chuỗi Ký tự,mảng số nguyên 1 chiều,mảng 2 chiều,tạo Menu
    Gửi bởi xuanngoc trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 15-10-2011, 01:54 AM
  3. Lời giải bài tập: Chuỗi Ký tự, mảng số nguyên 1 chiều, mảng 2 chiều, tạo Menu
    Gửi bởi xuanngoc trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 15-10-2011, 01:17 AM
  4. tìm số nguyên tố có trong mảng 2 chiều, tính tổng các số nguyên tố đó??
    Gửi bởi lesliuton01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 08-06-2010, 10:21 AM
  5. mảng 1 chiều | Kiểm tra mảng có chứa số nguyên tố???
    Gửi bởi namekct trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 11-01-2010, 09:46 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn