算法合集之信息學競賽中搜索問題的常見優(yōu)化技巧-資料下載頁
2024-10-16 20:30本頁面
【正文】 推而廣之 當我們已經(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這個約束條件進行剪枝。程序效率得到顯著的提高。兩個程序效率對比： 0121 2 3 4 5 6算法一算法二小結(jié) ? 原始的搜索方法搜索量巨大，我們通過分析，選擇適當?shù)乃阉鲗ο?，在搜索量減少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，使題目得到較好的解決。 總結(jié) 我們在搜索得過程中，靈活得改變搜索的順序和搜索的對象可以使程序效率得到很大的提升。 而這需要我們在做題的過程中多思考、多分析、多總結(jié)。
教學課件相關(guān)推薦
鄂ICP備17016276號-1