分治習(xí)題課-wenkub
2023-05-09 15:46:55 本頁面
【正文】 ? 設(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í)間選擇算法找中位數(shù)，可在 O(n)時(shí)間完成位置選擇。 ? 設(shè)有 n個(gè)不同的整數(shù)排好序后存于 T[1..i]中，如存在一個(gè)下標(biāo) I，使得 T[i]=i，設(shè)計(jì)一個(gè)有效算法找到這個(gè)下標(biāo)。要求算法在最壞情況下的計(jì)算時(shí)間為O(logn)。 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 7 算法實(shí)現(xiàn)題 23 ?郵局選址問題 ?分析 :(x,y) ? x為 x1,x2,..,xn的中位數(shù) ? y為 y1,y2,..,yn的中位數(shù) 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 8 算法實(shí)現(xiàn)題 2－ 5 ? 半數(shù)集問題 ? 分析： ? 設(shè) set(n)中的元素個(gè)數(shù)為 f(n)，則： 21( ) 1 ( )nif n f i??? ?四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 9 算法實(shí)現(xiàn)題 2－ 8 ? 有重復(fù)元素的排列問題 ? 例如： ? aacc ? 分析： 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 10
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1