算法合集之信息學競賽中搜索問題的常見優(yōu)化技巧(參考版)
2024-10-19 20:30本頁面
【正文】 而這需要我們在做題的過程中多思考、多分析、多總結。兩個程序效率對比： 0121 2 3 4 5 6算法一算法二小結 ? 原始的搜索方法搜索量巨大，我們通過分析，選擇適當?shù)乃阉鲗ο螅谒阉髁繙p少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，使題目得到較好的解決。 推而廣之 當我們已經(jīng)搜索出原數(shù)列的 a1， a2……a i和 an,an1……aj ，此時搜索排序后第 k小的數(shù) W[k],只可能有兩種存在的可能： Try(I,j) W[k] Try(I+1,j) Try(I,j1) else Exit A[I+1]=W[k] A[j1]=W[k] ? 這個算法在最壞情況下擴展的節(jié)點為21000(實際中遠遠小于這個數(shù) )， 在搜索的同時可以利用 Si+TnI=Sn=Tn這個約束條件進行剪枝。 改變搜索對象 ? 題目的約束條件集中在 Si和 Ti中，我們改變搜索的對象，不再搜索原數(shù)列中每個數(shù)的值，而是搜索給出的數(shù)
教學課件相關推薦
鄂ICP備17016276號-1