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ố 12 kết quả

Đề tài: tính giá trị đa thức horner trong lập trình C?

  1. #1
    Ngày gia nhập
    12 2011
    Nơi ở
    không có nhà vì quá dốt :(
    Bài viết
    6

    Mặc định tính giá trị đa thức horner trong lập trình C?

    Em xin post nguyên cái đề bài
    Cho P(x)= c(n nhỏ) *x^n + c(n nhỏ -1) *x ^(n-1)+....+c0
    c0, c1 ....là số nguyên Tìm tất cả nghiệm nguyên của đa thức đã cho

    thuật toán (bắt buộc) dựa trên mệnh đề sau
    nếu số nguyên x0 khác 0 la nghiệm của P(x) thì x0 phải là ước số của c0

    để tính P(x) ta dùng thuật toán horner sau
    function p(x)
    begin
    q:= c[nư;
    for i:= n-1 downto 0 do q:= q*x+c[i];
    return q;
    end;

    Phát biểu bài toán và thuật giải
    Thiết kế chương trình

    Em đang thắc mắc ở 1 vài đoạn
    +Đó là làm sao đưa mảng c[i] vào trong hàm Vì là đa thức bậc n bất kì Nên em đoán phải dùng khai báo mảng kiểu con trỏ để có thể cấp phát cho mảng có n phần tử
    + a là ước số của C thế nào ạ
    Mong các cao nhân chỉ giáo Em ngu muội nghĩ tới nửa đêm không ra Mong được sự giúp đỡ ạ !!

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mảng c là mảng lưu các hệ số c của cái đa thức đó theo từng bậc
    Số phần tử của c = số mũ lớn nhất + 1
    Số mũ thể hiện từ n -> bậc 0
    Các chỗ nào không xuất hiện x thì hệ số của nó = 0 .
    ví dụ p(x)= 2x^3 + x = 2x^3 + 0x^2 + x + 0x^0
    => c={0,1,0,2} . Hiểu chỗ này rồi chứ ?
    __
    Thuật toán đã nói rõ. x0 !=0 là nghiệm khi x0 là ước của c0 .
    Tư tưởng : Kiểm tra các ước của c0, với mỗi ước. Ta thế vào phương trình xem có thỏa ko ? . Nếu thỏa thì nó là nghiệm.
    Bạn thực hiện viết cái hàm sau để thực hiện lấy ra tất cả nghiệm của nó .
    Quy ước lại cách đặt P(x) thành thế này cho dễ làm việc

    P(x)=c0.x^n + c1.x^(n-1) + ... + cn . <--- Làm với cn.
    Cái hàm tính P(int c[],int n, int x) cũng phải viết lại theo định dạng này cho phù hợp.
    C++ Code:
    1. int *TimNghiemDaThuc(int c[],int n, int &songhiem) // Tập nghiệm sẽ dc lưu vào mảng trả về của hàm, số nghiệm dc trả về qua tham biến songhiem
    2. {
    3.     int tapnghiem[n];
    4.     songhiem=0;
    5.     if (c[n] ==0) // Hệ số tự do = 0 thì  0 là 1 nghiệm của ptrinh`
    6.     {
    7.          thêm số 0 vào tập nghiệm;
    8.          tăng số nghiệm;
    9.          n--; //  Bỏ hệ số cuối cùng, ko quan tâm nữa
    10.     }
    11.     while(c[n] ==0) // Hệ số tự do cuối cùng = 0
    12.     {
    13.          n--; // Thì cứ bỏ hệ số cuối cùng, ko quan tâm
    14.     }
    15.     // Ra ngoài viết 1 cái hàm int KiemTraUoc(int n,int socankiemtra) xem socankiemtra có phải ước của n ko
    16.     // Công việc tìm các nghiệm trong trường hợp hệ số cuối cùng !=0.
    17.     for(int i=1 -> c[n])
    18.         if ( KiemTraUoc(c[n],i) && (P(c,n,i)==0)) // Không được thay đổi thứ tự 2 biểu thức bên trái và phải dấu &&.
    19.         {
    20.              thêm i vào tập nghiệm;
    21.              tăng số nghiệm;
    22.         }
    23.     return tapnghiem;
    24. }
    Thực ra ko cần thao tác Kiểm tra ước cũng được, không sao. Nhưng làm thế sẽ chậm hơn là kiểm tra ước.
    Công việc kiểm tra ước của 1 số nhanh hơn nhiều lần so với việc thế cái số đó vào đa thức để tính giá trị của đa thức .
    Trong khi đó khả năng xảy tra trường hợp Đa thức bậc n có đủ n nghiệm là điều ko hay xảy ra. BỞi vì ước của 1 số thường ko phải nhiều

    Do đó ta đưa thêm trước 1 cái cửa. Bước qua cái cửa KiemTraUoc rồi mới tới cái cửa kiểm tra nghiệm. Là vì nguyên nhân đó
    Để cái đại đa số đứa nào ko phải là ước của cn(c0 trước khi định dạng lại) thì loại ngay vòng giữ xe. Đứa nào thỏa là ước thì mới vào kiểm tra tiếp
    Đã được chỉnh sửa lần cuối bởi clchicken : 21-02-2012 lúc 01:16 AM.
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    12 2011
    Nơi ở
    không có nhà vì quá dốt :(
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Mảng c là mảng lưu các hệ số c của cái đa thức đó theo từng bậc
    Số phần tử của c = số mũ lớn nhất + 1
    Số mũ thể hiện từ n -> bậc 0
    Các chỗ nào không xuất hiện x thì hệ số của nó = 0 .
    ví dụ p(x)= 2x^3 + x = 2x^3 + 0x^2 + x + 0x^0
    => c={0,1,0,2} . Hiểu chỗ này rồi chứ ?
    __
    Thuật toán đã nói rõ. x0 !=0 là nghiệm khi x0 là ước của c0 .
    Tư tưởng : Kiểm tra các ước của c0, với mỗi ước. Ta thế vào phương trình xem có thỏa ko ? . Nếu thỏa thì nó là nghiệm.
    Bạn thực hiện viết cái hàm sau để thực hiện lấy ra tất cả nghiệm của nó .
    Quy ước lại cách đặt P(x) thành thế này cho dễ làm việc

    P(x)=c0.x^n + c1.x^(n-1) + ... + cn . <--- Làm với cn.
    Cái hàm tính P(int c[],int n, int x) cũng phải viết lại theo định dạng này cho phù hợp.
    C++ Code:
    1. int *TimNghiemDaThuc(int c[],int n, int &songhiem) // Tập nghiệm sẽ dc lưu vào mảng trả về của hàm, số nghiệm dc trả về qua tham biến songhiem
    2. {
    3.     int tapnghiem[n];
    4.     songhiem=0;
    5.     if (c[n] ==0) // Hệ số tự do = 0 thì  0 là 1 nghiệm của ptrinh`
    6.     {
    7.          thêm số 0 vào tập nghiệm;
    8.          tăng số nghiệm;
    9.          n--; //  Bỏ hệ số cuối cùng, ko quan tâm nữa
    10.     }
    11.     while(c[n] ==0) // Hệ số tự do cuối cùng = 0
    12.     {
    13.          n--; // Thì cứ bỏ hệ số cuối cùng, ko quan tâm
    14.     }
    15.     // Ra ngoài viết 1 cái hàm int KiemTraUoc(int n,int socankiemtra) xem socankiemtra có phải ước của n ko
    16.     // Công việc tìm các nghiệm trong trường hợp hệ số cuối cùng !=0.
    17.     for(int i=1 -> c[n])
    18.         if ( KiemTraUoc(c[n],i) && (P(c,n,i)==0)) // Không được thay đổi thứ tự 2 biểu thức bên trái và phải dấu &&.
    19.         {
    20.              thêm i vào tập nghiệm;
    21.              tăng số nghiệm;
    22.         }
    23.     return tapnghiem;
    24. }
    Thực ra ko cần thao tác Kiểm tra ước cũng được, không sao. Nhưng làm thế sẽ chậm hơn là kiểm tra ước.
    Công việc kiểm tra ước của 1 số nhanh hơn nhiều lần so với việc thế cái số đó vào đa thức để tính giá trị của đa thức .
    Trong khi đó khả năng xảy tra trường hợp Đa thức bậc n có đủ n nghiệm là điều ko hay xảy ra. BỞi vì ước của 1 số thường ko phải nhiều

    Do đó ta đưa thêm trước 1 cái cửa. Bước qua cái cửa KiemTraUoc rồi mới tới cái cửa kiểm tra nghiệm. Là vì nguyên nhân đó
    Để cái đại đa số đứa nào ko phải là ước của cn(c0 trước khi định dạng lại) thì loại ngay vòng giữ xe. Đứa nào thỏa là ước thì mới vào kiểm tra tiếp
    Cho em hỏi nếu em tìm tất cả ước của cn trước Ví dụ là a Rồi thay ngược trở lại xem P(a) =o thì kết luận là nghiệm thì có được không Hàm tìm ước của em viết ở dưới đây ..Cám ơn anh trước )
    Attached Files Attached Files

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Được chứ.
    Thì cũng như code mình gợi ý đấy.
    Lọc cái nào là ước của cn trước (cho đỡ mất công) . Rồi sau đó mới kiểm tra nghiệm hay không

    Thứ tự biểu thức đem ra kiểm tra là ( Là ước && Thỏa nghiệm) thì nó sẽ đi kiểm tra cái Là ước trước, nếu thỏa thì nó kiểm tra tiếp. Còn ko là nó bye luôn đấy
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    12 2011
    Nơi ở
    không có nhà vì quá dốt :(
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Được chứ.
    Thì cũng như code mình gợi ý đấy.
    Lọc cái nào là ước của cn trước (cho đỡ mất công) . Rồi sau đó mới kiểm tra nghiệm hay không

    Thứ tự biểu thức đem ra kiểm tra là ( Là ước && Thỏa nghiệm) thì nó sẽ đi kiểm tra cái Là ước trước, nếu thỏa thì nó kiểm tra tiếp. Còn ko là nó bye luôn đấy
    Nhưng đề bài yêu cầu phải sử dụng thuật toán horner để tính giá trị của P(a) bằng cách thay ước vào tính Như cái đề bài em viết ấy ạ Thế thì phải làm thế nào ạ????

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mặc định tính giá trị đa thức horner trong lập trình C?

    Trời đất.
    x là ước của cn . Đem thế vào P(x) = 0 hay không ? Nếu =0 thì là nghiệm
    Hiểu chỗ này rồi chứ nhỉ ?
    Thì với mỗi số x đem ra thử . Nếu x là ước của cn, thì kiểm tra tiếp P(x) = không hay không ?
    Thì cái code nó thể hiện ra hết đó rồi còn hỏi lui hỏi tới mấy cái vớ vẩn gì thế.
    Vì sao 1 = 1 hả ?
    Không hiểu được nữa thì
    C++ Code:
    1. if( x là ước )
    2.     if(P(x)==0)
    3.          Nó là nghiệm;
    Nhưng đề bài yêu cầu phải sử dụng thuật toán horner để tính giá trị của P(a)
    Thuật toán Óc-ne đó là để tính giá trị Đa thức. Chả có liên quan cái quái gì với giải phương trình cả.
    Bài bảo là Óc ne là để cho bạn biết cách tính Giá trị đa thức theo kiểu của óc-ne . (Vì ngoài óc ne ra còn có cách khác để tính nữa)
    Vận dụng cái hàm P( ... ) đó để kiểm tra nghiệm. P(x) ==0 thì x là nghiệm.

    Cái hàm P(a) đó nó độc lập với cái hàm tìm nghiệm này. Hàm tìm nghiệm chỉ sử dụng P(a) để kiểm tra thôi.
    Cái búa nó độc lập với việc của thợ rèn. Cái búa có thể dc sử dụng trong nhiều công việc ngoài thợ rèn . Nhưng thợ rèn cần cái búa để hoàn thành công việc rèn dũa.
    Hàm P(a) có thể sử dụng độc lập, thích dùng gì dùng : Ví dụ : Giờ tính thử P(10) = bao nhiêu, in ra xem cho vui . Cũng là 1 cách dùng
    Nhưng cái hàm TÌM NGHIỆM cần sử dụng P(a) này mới hoàn thành đc việc tìm nghiệm.
    Bạn hiểu chỗ này rồi chứ ?


    Còn cái lý thuyết bảo là : Là nghiệm khi x là ước của cn/c0 gì đấy là để giới hạn không gian tồn tại nghiệm.
    Để ta còn biết đường thử cái số x nào thuộc 1 tập hữu hạn số nào đấy. x nào thỏa là nghiệm thì kết luận.
    Nếu không có lý thuyết này thì không biết cái không gian nghiệm rộng thế nào, để thử cho hết . Thì không giải được = phép thử, vì ko có điểm dừng.

    Nói thế này chắc hiểu ngọn ngành vì sao người ta bắt làm cái này bắt làm cái kia rồi chứ ?
    Đã được chỉnh sửa lần cuối bởi clchicken : 24-02-2012 lúc 06:02 PM.
    Um Mani Padme Hum...!!

  7. #7
    Ngày gia nhập
    12 2011
    Nơi ở
    không có nhà vì quá dốt :(
    Bài viết
    6

    for(int i=1 -> c[n])
    if ( KiemTraUoc(c[n],i) && (P(c,n,i)==0))

    Cho em hỏi cái dấu -> này có nghĩa là gì ạ !!

  8. #8
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Cái kia ko phải code để chạy đâu bạn ơi. Là giả mã đấy.

    Cái đó nghĩa là
    Cho i chạy từ 1 tới c[n]. Mỗi bước tăng i lên 1
    Um Mani Padme Hum...!!

  9. #9
    Ngày gia nhập
    12 2011
    Nơi ở
    không có nhà vì quá dốt :(
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Cái kia ko phải code để chạy đâu bạn ơi. Là giả mã đấy.

    Cái đó nghĩa là
    Cho i chạy từ 1 tới c[n]. Mỗi bước tăng i lên 1
    Em cũng đoán thế

    Em làm theo rồi Nhưng mà code em viết ra không hiểu sao không ra được kết quả
    A xem có lỗi nào không chỉ em với Hic Tìm hoài không ra

    #include<iostream.h>


    Code:
    int KiemTraUoc(int n, int a)
    {
    	if (n%a==0) return 1;
    	else return 0;
    }
    
    int P( int c[], int n , int a)
    {
    	int q,i;
    	q=c[n];
    	for(i=0;i<=n;i++)
    		q=q*a+c[i];
    	return q;
    }
    
    int *TimNghiemDaThuc(int c[],int n) 
    {
        int j,i,songhiem;
        songhiem=0;
    	j=0;
    	int *tapnghiem =new int [n];
        if (c[n] ==0) 
        {
          tapnghiem[j]=0;
          songhiem+=1;
          n--;
    	  j++;
     
        }
        while(c[n] ==0) 
        {
             n--; 
        }
        
        for(i=1;i<=c[n];i++) 
            if ( KiemTraUoc(c[n],i) && (P(c,n,i)==0)) 
            {
               tapnghiem[j]=i;
    		   j++;
            }
        for(i=0;i<=j;i++)
    		cout <<tapnghiem[i]<<"\n";
    
    		
        return tapnghiem;
    }
    int main ()
    {
    	int n,i;
    	cout <<" nhap vao so phan tu \n";
    	cin >> n;
    	int *p = new int [n];
    	for (i=0;i<=n;i++)
    	{
    		cout << "nhap gia tri thu "<< i<<"\n";
    		cin >> p[i];
    	}
    	TimNghiemDaThuc(p,n);
    }

  10. #10
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Cái này bạn hỏi từ tháng 2.
    Tôi cũng đã và đang giúp bạn ở thời điểm đó
    bạn không chịu làm cho xong
    1 tháng sau bạn vào lại hỏi. Tôi không giúp nữa
    Um Mani Padme Hum...!!

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

  1. Bài tập C Tính đa thức theo công thức Horner
    Gửi bởi Pop trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 23-08-2011, 07:56 PM
  2. Tính đa thức theo giải thuật horner
    Gửi bởi luannguyenit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 12-07-2010, 10:21 AM

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