Yahoo奇摩知識+ 將於 2021 年 5 月 4 日 (美國東部時間) 終止服務。自 2021 年 4 月 20 日 (美國東部時間) 起,Yahoo奇摩知識+ 網站將會轉為唯讀模式。其他 Yahoo奇摩產品與服務或您的 Yahoo奇摩帳號都不會受影響。如需關於 Yahoo奇摩知識+ 停止服務以及下載您個人資料的資訊,請參閱說明網頁。

匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 1 0 年前

用二元搜尋法求多項式的根

有一方程式為 f(x)=x^21-100x+10 請利用二元搜尋法撰寫出 f(x)=0 的解 範圍 Range_Min, Range_Max

我的寫法

#include <stdio.h>

func(double a);

void main()

{

//double i,a[100]; p.s本來是想用矩陣來寫 可是若條件將

//其視為min=0 max=99就不用了

//for(i=0;i<100;i++)

// a[i]=i;

double low=0,high=99,middle;

while(low<=high)

{

middle=(low+high)/2;

if(func(middle)==0)

printf("%g",middle);

else

if(func(middle)*func(low)<0)

high=middle-1;

else

if (func(middle)*func(high)<0)

low=middle+1;}

}

func(double x)

{

double a;a=pow(x,2)-5*x+6; //這裡是刻意湊出有兩個明顯的根2,3與原題目不一樣

return a;

}

但是這樣似乎跑不出來東西 請大大門幫我修改一下程式 謝謝

已更新項目:

給Pacy大大

勘根定理 : 若 f(a)f(b) < 0 , 則 f(x) = 0 在 a 與 b 二數之間, 至少有(必定有)一個實數解 你寫的那種我真的沒聽過,,,,,,

給空氣大大

可以簡述一下你用什麼方法嗎 你那是c++的寫法....我看得好辛苦優 = =

2 個已更新項目:

面對這深奧的問題 兩位大大猜拳決定誰要當最佳解答好了 哈哈

3 個解答

評分
  • 1 0 年前
    最佳解答

    根據題目目的~

    #include <cstdlib>

    #include <iostream>

    #include <math.h>

    using namespace std;

    class FunctionA{

    private:

    double Range_Min;//搜尋下限

    double Range_Max;//搜尋上限

    double theX_LimitToZero;//在上下限中,最接近神的男人

    bool isLimitToZero(const double x);//何謂等於零

    void search();//二元搜尋

    public:

    FunctionA(const double from, const double to);//上下限建構式

    double eval(const double x);// y=eval(x), 即f(x)

    void display()

    {

    cout << "solution x:" << theX_LimitToZero << '\n';

    cout << "how much the y is:" << eval(theX_LimitToZero) << '\n';

    }

    };

    int main(int argc, char *argv[])

    {

    FunctionA test1(0.0,10.0);//搜尋0~10

    test1.display();

    FunctionA test2(-10.0,0.0);//搜尋-10~0

    test2.display();

    system("PAUSE");

    return EXIT_SUCCESS;

    }

    // f(x)

    double FunctionA::eval(const double x)

    {

    return pow(x,21)-100*x+10;

    }

    FunctionA::FunctionA(const double from, const double to)

    {

    if( from > to )

    {

    Range_Max = from;

    Range_Min = to;

    }

    else if( to > from)

    {

    Range_Max = to;

    Range_Min = from;

    }

    else

    {

    theX_LimitToZero = Range_Max = Range_Min = to;

    return;

    }

    search();

    }

    bool FunctionA::isLimitToZero(const double x)

    {

    return ( fabs( 0-eval(x) ) <= 1E-12 );//接近零的極限

    }

    void FunctionA::search()

    {

    const double middle = (Range_Max + Range_Min)/2;

    if( (Range_Max - Range_Min) <= 1E-12 )//搜尋極限

    {

    theX_LimitToZero = middle;

    return;

    }

    if( isLimitToZero(middle) )

    {

    theX_LimitToZero = middle;

    }

    else

    {

    const double middleY = eval(middle);

    if( 0-middleY > 0)

    {

    Range_Min = middle;

    search();

    }

    else

    {

    Range_Max = middle;

    search();

    }

    }

    2009-03-28 01:54:18 補充:

    結果為

    X= 1.2537 和

    X= -1.26373

    2009-03-28 01:55:44 補充:

    其實我完全不懂電腦數值分析~

    2009-03-29 05:18:36 補充:

    不好意思~

    你可以把class 看成是 C的 struct

    private是私有區,有三個成員,分別是

    double Range_Min;    //搜尋下限

    double Range_Max;    //搜尋上限

    double theX_LimitToZero;; //在上下限中,最接近神的男人

    2009-03-29 05:21:12 補充:

    FunctionA test1(0.0,10.0);

    會呼叫FunctionA(const double from, const double to);

    來初始化 test1 struct的成員

    double Range_Min;    

    double Range_Max;

    2009-03-29 05:23:23 補充:

    您可以看成是這樣

    FunctionA(&test1 ,const double from, const double to);

    傳入 test1位址,來初始化test1成員

    2009-03-29 05:27:59 補充:

    FunctionA函式中除了初始化上下限

    還呼叫search()函式企圖來找出theX_LimitToZero

    使的 f( theX_LimitToZero )趨近於零

    在這裡定義為

    零減去 f( theX_LimitToZero )的絕對值小於十的負12次方就可以接受了

    值越小要算越久  

    2009-03-29 05:31:50 補充:

    void FunctionA::search()函式可看為

    void search(FunctionA*);

    把struct FunctionA傳入search函式中進行蹂躪~

    它是一個遞迴函式,終止條件為

    2009-03-29 05:32:33 補充:

     f( theX_LimitToZero )趨近於零

    2009-03-29 05:37:38 補充:

    先把上下限相加除以二求中間點

    const double middle = (Range_Max + Range_Min)/2;

    再把中間點代入 f( middle ),這裡我把這個 f(x)取名為 eval(x)

    所以你在程式中會看到

    eval( middle )

    0 - eval( middle )並呼叫 abs()取絕對值若很接近零就是收斂~

    算是找到答案 

    2009-03-29 05:42:24 補充:

    如果沒有收斂呢?

    沒關係我們遞迴呼叫 search()

    1.若 0減f(middle) 大於零,代表答案在右邊

    以middle為新下限 Range_Min = middle;再呼叫search()

    2.若 0減f(middle) 小於零,代表答案在左邊

    以middle為新上限 Range_Max = middle;再呼叫search()

    以上假設其為線性函式

    2009-03-29 05:49:20 補充:

    test1.display()

    只是呼叫 display(&test1), 將初始化成功的結果輸出到控制台而已~

    寫得這麼雜是在下的錯~

    常常只為了求速度~忘了程式碼是要給人看的

    2009-03-29 05:53:05 補充:

    奇摩的排版其實也有很大的關係~

    在下都是剪貼程式碼到編輯器中排版~

    不然都看不懂...........

    2009-03-29 18:53:00 補充:

    有一方程式為 f(x)=x^21-100x+10

    ...................."請利用二元搜尋法"............................

    撰寫出 f(x)=0 的解 範圍 Range_Min, Range_Max

    在下只是根據版大要求而已........

    如果作文題目出了一個

    "如何利用三民主義來統一中國"

    總不能答說:

    老師~三民主義不能統一中國耶~故拒答

    老師:..............

  • 匿名使用者
    1 0 年前

    Pacy 大大 和 空氣 大大 的推論都很不錯壓 至少又獲得了一些不同的 想法 ^^ 有關類似的問題 小弟發現 數值分析似乎有談到這內容 可以用2分逼近法去 逼近到一個接近答案的值

    2009-03-29 23:44:23 補充:

    = = 抱歉= =

  • 1 0 年前

    1. function的宣告

    double func(double );

    2. function的內容

    你可以直接這樣寫

    double func(double x)

    {

    return pow(x,2)-5*x+6;

    }

    3. #include <math.h> //要加這行

    因為你用了pow()這個函數

    4. 我知道你用了堪根定理

    但是勘根定理的內容是:

    f(a)*f(b)<0表示a和b之間有奇數個根

    f(a)*f(b)>0表示a和b之間有偶數個根

    所以你這個方法是行不通的

    用這個方式判斷還是無法確定根到底是在哪個區間

    基本上二元搜尋法是用在線性函數

    二次以上的函數請另覓其他解法會較適當

    以上,希望有幫忙到你囉!

    2009-03-29 17:34:57 補充:

    http://web.cc.ntnu.edu.tw/~495401037/all/4-5.htm

    這個網頁的最後面有寫到

    f(a)×f(b)<0是確定有根

    但是f(a)×f(b)>0可能也會有根

    所以我說不能用堪根定理

    2009-03-29 17:44:22 補充:

    空氣先生的方法也頗有問題

    1.若 0減f(middle) 大於零,代表答案在右邊

    2.若 0減f(middle) 小於零,代表答案在左邊

    其實不一定要線性函數

    只要是遞增函數就可以

    但是遞減函數呢?

    答案會完全錯誤

    如果用這個去算呢(二次函數)

    f(x)=pow(x,2)-5*x+6

    會有一個對一個錯

    因為這個函數是一半遞增一半遞減的

    結論是:

    不能用二元搜尋法求多項式的根!

    2009-03-29 22:08:40 補充:

    f(x)=|x|

    這個根是重根

還有問題?馬上發問,尋求解答。