分治習(xí)題課-文庫吧
2025-04-07 15:46 本頁面
【正文】 100 1101 1111 1110 1010 1011 1001 1000 四川師范大學(xué)計算機科學(xué)學(xué)院 劉芳 5 ? 遞歸定義 ? 令： G(n)為 n為 Gray碼序列， G1(n)為 G(n)以相反序列排列的序列 ? 則： ? G(n+1)=0 G(n) ， 1 G1(n) 四川師范大學(xué)計算機科學(xué)學(xué)院 劉芳 6 算法實現(xiàn)題 2－ 1 ? 輸油管道問題 ? 分析 ? 設(shè)油井位置 Pi=(xi,yi)，（ 1≤i≤n) ? 主管道東西向，則用其主軸線的 y坐標(biāo)唯一標(biāo)定位置 ? 主管道的最優(yōu)位置 y，應(yīng)使： min{d(y,yi)| 1≤i≤n}， ? 顯然： y為 y1,y2,..,yn的中位數(shù)最佳 ? 可以應(yīng)用任意線性時間選擇算法找中位數(shù)，可在 O(n)時間完成位置選擇。 四川師范大學(xué)計算機科學(xué)學(xué)院 劉芳 7 算法實現(xiàn)題 23 ?郵局選址問題 ?分析 :(x,y) ? x為 x1,x2,..,xn的中位數(shù) ? y為 y1,y2,..,yn的中位數(shù) 四川師范大學(xué)計算機科學(xué)學(xué)院 劉芳 8 算法實現(xiàn)題 2－ 5 ? 半數(shù)集問題 ? 分析： ? 設(shè) set(n)中的元素個數(shù)為 f(n)，則： 21( ) 1 (
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1