具体我不知道怎么用。摸索着写了一下,但是效果还不如二分法快。
华罗庚先生已经证明黄金分割法优越于二分法,而二分法又显然优于逐个查找法
所以想了解一下查找到底是怎么做。。。
- 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有什么区别呢,我自已写了一下,发现变成了一个死循环,吃饭了再来调,闪了。