<style type="text/css"> .slides { text-align: left !important; } </style> # 三分搜與黃金比例搜 #### Author: H1de_on_bruH --- ### 暖身活動:找最低點 給定一個二次函數$ax^2+bx+c=0$且$0<a$ 請找出他的最低點(四捨五入至小數第6位) ---- #### 想法1:暴力 一個一個點下去看啊 ---- #### TLE $O(值域\times 10^6)$ ---- #### 想法2:利用數學 化成$a(x-k)^2+h$ 則最低點即為k ---- #### AC $O(1)$解直接過，看來三分搜也沒什麼用嘛 直接下課吧 ---- ## 且慢 那如果題目的函數不是一個多次函數呢? ---- 如果說這個函數保證最低點前單調遞減，且最低點後單調遞增，但長得奇形怪狀的 像這樣  數學解\\|/ --- #### 想法3:切塊 跟剛剛講的二分搜類似 用不斷讓上下界逼近的概念 我們把這個區間切成三塊  ---- 比較$f(ML)$跟$f(MR)$的大小 如果ML的值比較大 就讓L=ML 反之則讓R=MR 一直持續逼近就可以找到足夠精確的值 ---- 實作上大概長這樣 ```cpp= int counter=1e5;//counter代表逼近的次數 理論上求越多次就會越精準 double l=0,r=1e9; while(counter--) { double three=(r-l)/3; double ml=l+three,mr=r-three; if(f(ml)>f(mr)) l=ml; else r=mr; } cout<<l<<endl; ``` --- ## 黃金比例搜 ---- 黃金比例搜的用途跟三分搜類似 刻意讓他切的比例等於黃金比例就可以減少呼叫函數的次數 ---- ### 如圖  ---- $A:B=C:A$ 如果ML比較大 縮左邊後新的ML就會是原本的MR 下一輪的時候就只需要算一次新MR的函數值就可以 反之亦然 ---- 這樣做的話就可以少叫一次函數 常數--; # {>w<|開心} ---- ### 實作 ```cpp= double l=0,r=1e9,ml,mr; double vl,vr; int counter=1e5; const double gold=(sqrt(5)-1)/2; ml=(r-l)*gold+l; mr=r-(r-l)*gold; vl=f(ml); vr=f(mr); while(counter--) { if(vl>vr) { l=ml; ml=mr; vl=vr; double the=(r-l)*gold; mr=r-the; vr=f(mr); } else { r=mr; mr=ml; vr=vl; double the=(r-l)*gold; ml=l+the; vl=f(ml); } } cout<<l<<endl; ``` --- ### 以上 ---- 其實打競賽真的很少遇到用三分搜的題目 不過自己覺得這個主題還蠻有趣而且也比較不需要太多的競賽知識 ---- \\\\\\\\\\感謝各位的聽講 >w</////