摘要:試題四(共15分)閱讀以下說明和圖,填補(bǔ)流程圖中的空缺,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。[說明]在一條農(nóng)村公路的一邊稀疏地分布著房子,其分布如圖4-1所示。某電信公司需要在某些位置放置蜂窩電話基站,由于基站的覆蓋范圍是6公里,因此必須使得每棟房子到某個(gè)基站的直線距離不超過6公里。為簡化問題,假設(shè)所有房子在同一直
試題四(共15分)
閱讀以下說明和圖,填補(bǔ)流程圖中的空缺,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
[說明]
在一條農(nóng)村公路的一邊稀疏地分布著房子,其分布如圖 4-1 所示。某電信公司需要在某些位置放置蜂窩電話基站,由于基站的覆蓋范圍是6公里,因此必須使得每棟房子到某個(gè)基站的直線距離不超過6公里。為簡化問題,假設(shè)所有房子在同一直線上,并且基站沿該直線放置?,F(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。
實(shí)現(xiàn)貪心算法的流程如圖4-2所示,請(qǐng)?zhí)畛淦渲锌瞻撞⒂?jì)算該算法的時(shí)間復(fù)雜度,其中:
1.d[i](1≤ i ≤ N)表示第i個(gè)房子到公路A端的距離,N 表示房子的總數(shù),房子的編號(hào)按照房子到公路A 端的距離從小到大進(jìn)行編號(hào)。
2.s[k]表示第k(k ≥1)個(gè)基站到公路A 端的距離,算法結(jié)束后k的值為基站的總數(shù)。
該算法的時(shí)間復(fù)雜度為 (5) 。
軟考備考資料免費(fèi)領(lǐng)取
去領(lǐng)取
共收錄117.93萬道題
已有25.02萬小伙伴參與做題