輸油管道問題

1、 2-1 輸油管道問題輸油管道問題 某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x坐標(biāo)（東西向）和y坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置,即使各油井到主管道之間的輸油管道長度總和最小的位置?證明可在線性時(shí)間內(nèi)確定主管道的最優(yōu)位置。問題描述：算法設(shè)計(jì)：算法設(shè)計(jì)：給定n 口油井的位置,編程計(jì)算各油井到主管道之間的輸油管道最小長度總和。數(shù)據(jù)輸入：數(shù)據(jù)輸入：由文件 input.txt 提供輸入數(shù)據(jù)。文件第一行是油井?dāng)?shù) n ，接下來的n行是油井的位置，每行2個(gè)整數(shù)x和y

2、。數(shù)據(jù)輸出：數(shù)據(jù)輸出：將計(jì)算結(jié)果輸出到文件output.txt 。文件的第一行中的數(shù)是各油井到主管道之間的輸油管道最小長度總和 如果只有一口井，顯然是越近越好如果有兩口井，那么有以下三種情況： 1.兩口井都在主管道北邊，那么這個(gè)時(shí)候的兩個(gè)連接管道的長度和肯定大于兩口井的Y坐標(biāo)之差 2.兩口井都在主管道南邊，和情況1是一樣的 3.兩口井，一個(gè)在主管道南邊，一個(gè)在主管道北邊，那么兩個(gè)連接管道的長度和就等于兩口井的Y坐標(biāo)之差 顯然情況三是所要的最短管道的設(shè)計(jì)情況 就是當(dāng)主管道在兩口井之間的任意位置時(shí)，連接管道長度之和等于兩口井的Y坐標(biāo)之差，是最短的長度 將這個(gè)結(jié)論推廣，當(dāng)有n口井的時(shí)候 n是偶數(shù) 只

3、要這n口井分布在主管道的兩邊，一邊n/2個(gè)，那么就是距離之和最小的 1.n是奇數(shù) 只要將這n個(gè)井中，Y坐標(biāo)最中間的（也就是Y是中值的那個(gè)）井不算，其余的偶數(shù)個(gè)井分布在主管道的兩側(cè)，這個(gè)時(shí)候移動(dòng)主管道，那么這n個(gè)連接管道長度之和就決定于那個(gè)沒有算的井了，因?yàn)槠溆嗟木木嚯x之和是固定了的，這個(gè)時(shí)候只要主管道最接近那個(gè)點(diǎn)就好了算法實(shí)現(xiàn): 1.通過劃分算法對(duì)所有油井y坐標(biāo)進(jìn)行排序2.通過隨機(jī)選擇方法RandomizedSelect得到中位數(shù)3.連接管道長度之和等于各油井的Y坐標(biāo)到中位數(shù)的絕對(duì)差之和程序分析：Patition（劃分）函數(shù)的作用：將一串?dāng)?shù)據(jù)由小到大進(jìn)行排序，最后返回劃分時(shí)所用基數(shù)的位置in

4、t Partition(int yLEN, int p, int r) /將x的元素交換到右邊區(qū)域 int i = p, j = r+1; int x = yp; while(true) while(y+ix&ix); if(i=j) break; Swap(yi,yj); yp = yj; yj = x; return j; /返回劃分后基數(shù)的位置RandomizedPartition（隨機(jī)劃分）函數(shù)的：在所有坐標(biāo)中隨機(jī)選擇一個(gè)，并以此作為基數(shù)進(jìn)行劃分，最后返回該基數(shù)的位置int RandomizedPartition(int yLEN, int p, int r) int i =

5、Random(p,r);/產(chǎn)生隨機(jī)數(shù) Swap(yi,yp);/交換基數(shù)和第一個(gè)數(shù) return Partition(y,p,r);/返回劃分后基數(shù)的位置RandomizedSelect（隨機(jī)選擇）函數(shù)：找到排序后數(shù)據(jù)的中位數(shù)int RandomizedSelect(int yLEN, int p, int r, int k) if(p=r) return yp; /如果基數(shù)在中間則返回基數(shù)的值 int i = RandomizedPartition(y,p,r);/將數(shù)組yp:r劃分成兩個(gè)子數(shù)組yp:i、yi+1:r,使yp:i中每個(gè)元素不大于yi+1:r中每個(gè)元素 int j = i-p+

6、1;/計(jì)算子數(shù)組yp:i中元素個(gè)數(shù)j if(k=k,則第k小元素落 在子數(shù)組yp:i中,否則落在yi+1:r中 else return RandomizedSelect(y,i+1,r,k-j);此函數(shù)就是當(dāng)基數(shù)處在油井的中間時(shí)返回該值void main() /計(jì)算輸油管道最小長度總和 int n; /油井?dāng)?shù) int sum = 0;/管道長度總和 int yLEN;/油井y坐標(biāo) int dy; /油井y坐標(biāo)中位數(shù)printf(請(qǐng)輸入油井?dāng)?shù)n= n);scanf(%d,&n); /讀取油井?dāng)?shù)printf(請(qǐng)輸入油井?dāng)?shù)坐標(biāo)n);for(int i=0;in;i+) scanf(“%d”,&yi); /x坐標(biāo)在此題中無用，而y坐標(biāo)在x坐標(biāo)之后寫 scanf(%d,&yi); dy = RandomizedSelect(y, 0, n-1, (n+1)/2); /中位數(shù)求取