当前位置: 代码迷 >> VC >> 问一下黄金分割搜索具体如何做
  详细解决方案

问一下黄金分割搜索具体如何做

热度:8106   发布时间:2013-02-25 00:00:00.0
问一下黄金分割搜索具体怎么做?
具体我不知道怎么用。摸索着写了一下,但是效果还不如二分法快。
华罗庚先生已经证明黄金分割法优越于二分法,而二分法又显然优于逐个查找法

所以想了解一下查找到底是怎么做。。。

C/C++ code
int GetCountHalf(int min,int max,int inNum);int GetCountGold(int min,int max,int inNum);const double gold = 0.6180339887;int _tmain(int argc, _TCHAR* argv[]){    int count[512];    for(int i=0;i<512;i++)        count[i]=0;    int min,max;    cout << "Press in the min Num:";    cin >> min;    cout << "Press in the max Num:";    cin >> max;    for(int i=min;i<=max;i++)        count[GetCountGold(min,max,i)]++;    for(int i=min;i<=max;i++)        count[GetCountHalf(min,max,i)+256]++;            printf_s("Views\tGold\tHalf\n");    for(int i=1;i<256 &&( count[i]>0 || count[i+256]>0);i++){        if(count[i]>0 && count[i+256]>0)            printf_s("%d\t%d\t%d\n",i,count[i],count[i+256]);        else if(count[i]>0)            printf_s("%d\t%d\n",i,count[i]);        else            printf_s("%d\t\t%d\n",i,count[i+256]);    }    getchar();    getchar();}int GetCountGold(int min,int max,int inNum){    int count = 1;    int now  =(int)((max - min) * gold + min);    double thisNow = 0;    while (now!=inNum) {        count++;        if (now > inNum) {            thisNow = now - (now - min) * gold;            max = now;        } else{            thisNow = now + (max - now) * gold;            min = now;        }        if (thisNow - (int) thisNow >= 0.5)            now = (int) thisNow + 1;        else            now = (int) thisNow;    }    return count;}int GetCountHalf(int min,int max,int inNum){    int count = 1; min--;    int now  =(int)((max - min) * 0.5 + min);    double thisNow = 0;    while (now!=inNum) {        count++;        if (now > inNum) {            max = now;        } else{            min = now;        }        thisNow = (max - min) * 0.5 + min;        if (thisNow - (int) thisNow >= 0.5)            now = (int) thisNow + 1;        else            now = (int) thisNow;    }    return count;}


------解决方案--------------------------------------------------------
看 Numerical recipe in C
有原理, 有代码.

------解决方案--------------------------------------------------------
理论上说是要快些,但用在计算机上就不一样的

本来折半查找就很快了,找百万级的数据最多20来次比较就完成了

就算用黄金分割,能已然到15次到20次的话,也差不了多少,而且乘以0.618速度肯定没有除2快
------解决方案--------------------------------------------------------
那我*0.628,0.638有什么区别呢,我自已写了一下,发现变成了一个死循环,吃饭了再来调,闪了。