算法合集之《參考系與坐標(biāo)系》

1、ioi2006中國國家集訓(xùn)隊(duì)論文信息學(xué)中的參考系與坐標(biāo)系reference and coordinate system in olympiad in informatics 摘 要信息學(xué)是一門新興的學(xué)科，與數(shù)學(xué)、物理等經(jīng)典學(xué)科相比顯然年輕得多。因而信息學(xué)中的許多思想都來源于數(shù)學(xué)、物理。本文將通過三個(gè)方面介紹參考系與坐標(biāo)系在信息學(xué)中的應(yīng)用。希望能通過本文，開拓解決信息學(xué)問題的思路，使參考系與坐標(biāo)系的思想成為解決信息學(xué)問題的有力武器。關(guān)鍵字信息學(xué) 參考系 坐標(biāo)系 單位長度 離散化 數(shù)軸目 錄前言3參考系與坐標(biāo)系的介紹4單位長度的改變7參考系的選擇11坐標(biāo)系的建立15總結(jié)20參考文獻(xiàn)與資料來源21附

2、錄22致謝53前言我在做題中有時(shí)會(huì)靈光一現(xiàn)，想出一些很特殊或是未接觸過的解法，這些題目和想法都會(huì)給我留下很深刻的印象。本篇論文的第三題就是其中之一，可以說這題是整篇論文的導(dǎo)火索。但靈光總不會(huì)經(jīng)常光顧，大多數(shù)情況下解決新到手的問題都得按部就班地分析，做過類似的題型，當(dāng)然易于解決；但如果沒有呢？我常常想那些“靈光一現(xiàn)”的題目，是否也可以按套路分析出來呢？這里的套路也就是常說的解題的思維和方法了，然而個(gè)個(gè)人都不盡相同，但其中往往有很多相同和相通的思想。如果說解決題目是在黑暗中摸索，那么這些思想便是一個(gè)個(gè)的燈塔，正在這些燈塔的指引下，我們摸索出了道路也就是解題方法了。那么燈塔越多，解決問題的路徑便越清

3、晰。然而很多路，我們都只憑著直覺，也就是經(jīng)驗(yàn)走出來的，對(duì)途中未亮的燈塔視而不見。我寫本篇論文，就是想為大家點(diǎn)亮一個(gè)燈塔，這個(gè)燈塔就名為參考系與坐標(biāo)系的思想。希望大家今后在黑暗中摸索道路時(shí)能多一片光明；更希望大家在走出一條道路后，可以將道路中的燈塔都點(diǎn)亮。本篇論文主要分為兩大部分，第一部分是介紹參考系與坐標(biāo)系的基本概念，為后文作鋪墊；第二部分是介紹參考系與坐標(biāo)系思想在信息學(xué)中的應(yīng)用。第二部分分為三大塊：單位長度的改變，參考系的選擇，坐標(biāo)系的建立。每一塊都由問題引入，問題描述，問題分析以及小結(jié)構(gòu)成。每個(gè)問題的分析都不是單一方法，而是從簡單到復(fù)雜，從常規(guī)到特殊，這也是我們面臨一個(gè)未知問題時(shí)常用的思維

4、方法。雖然這些題目的道路已經(jīng)明朗了，但我仍希望本篇論文的分析能體現(xiàn)黑暗中的摸索，所以在分析中，會(huì)有“？”的出現(xiàn)，正由于這些“？”，使問題不斷深入。每個(gè)問題分析后的小結(jié)正是起點(diǎn)亮燈塔的作用。參考系與坐標(biāo)系的介紹 參考系的概念平時(shí)我們說樹木、房屋是靜止的，行駛的汽車是運(yùn)動(dòng)的，這是以地面作為標(biāo)準(zhǔn)來說的。坐在行駛的火車?yán)锏某丝?，認(rèn)為自己是靜止的，路旁的樹木在向后倒退，這是以車廂作為標(biāo)準(zhǔn)來說的。在描述一個(gè)物體運(yùn)動(dòng)時(shí)，選來作為標(biāo)準(zhǔn)的另外物體，叫做參考系。 坐標(biāo)系的概念我們都有去影院看電影的經(jīng)歷，觀眾席的所有座位都按“幾排幾號(hào)”編號(hào)，以便確定每個(gè)座位在影院中的位置。這樣，觀眾就能根據(jù)入場券上的“排數(shù)”和“號(hào)

5、數(shù)”準(zhǔn)確地“對(duì)號(hào)入座”。這正運(yùn)用了坐標(biāo)系的有關(guān)知識(shí)。在參考物上任意選定一個(gè)參考點(diǎn)o，并安置一個(gè)以o為原點(diǎn)的坐標(biāo)系，就可以把物體相對(duì)于參考系的位置定量地用坐標(biāo)表示出來。 坐標(biāo)系的三要素為：原點(diǎn)，正方向，單位長度。 幾種坐標(biāo)系一維坐標(biāo)系-4 -3 -2 -1 0 1 2 3 4 5 6 7下圖是一條數(shù)軸，數(shù)軸上的點(diǎn)可以用一個(gè)數(shù)來表示，這個(gè)數(shù)就叫做這個(gè)點(diǎn)的坐標(biāo)。知道一個(gè)點(diǎn)的坐標(biāo)，這個(gè)點(diǎn)在數(shù)軸上的位置也就確定了。二維坐標(biāo)系平面上幾個(gè)非平行數(shù)軸原點(diǎn)重合組成的坐標(biāo)系就是二維坐標(biāo)系。o我們接觸最多的是兩條互相垂直、原點(diǎn)重合的數(shù)軸組成的平面直角坐標(biāo)系，也就是笛卡兒坐標(biāo)系。水平的數(shù)軸稱為x軸或橫軸，習(xí)慣上取向右

6、為正方向；豎直的數(shù)軸稱為y軸或縱軸，取向上為正方向；兩坐標(biāo)軸的交點(diǎn)為平面直角坐標(biāo)系的原點(diǎn)。iviiiiiioxy有了平面直角坐標(biāo)系，平面內(nèi)的點(diǎn)就可以用一個(gè)有序數(shù)對(duì)來表示了。一個(gè)點(diǎn)分別向x軸和y軸做垂線，垂足在x軸上的坐標(biāo)就是橫坐標(biāo)，垂足在y軸上的坐標(biāo)就是縱坐標(biāo)。建立了平面直角坐標(biāo)系以后，坐標(biāo)平面就被兩條坐標(biāo)軸分成i,ii,iii,iv四個(gè)部分，分別叫做第一象限，第二象限，第三象限和第四象限，坐標(biāo)軸上的點(diǎn)不屬于任何象限。三維坐標(biāo)系我么常見的是三維坐標(biāo)系是空間直角坐標(biāo)系。如圖，oabc-dabc是單位正方體，以o為原點(diǎn)，分別以射線oa，oc，od的方向?yàn)檎较?，以線段oa,oc,od的長為單位長，

7、建立三條數(shù)軸：x軸，y軸，z軸。這時(shí)我們說建立了一個(gè)空間直角坐標(biāo)系o-xyz。其中點(diǎn)o為坐標(biāo)原點(diǎn)；x軸，y軸，z軸叫做坐標(biāo)軸，通過每兩個(gè)坐標(biāo)軸的平面叫做坐標(biāo)平面，分別稱為xoy平面，yoz平面，zox平面。yxzobaabcdc在空間直角坐標(biāo)系中，讓右手拇指直向x軸的正方向，食指指向y軸的正方向，如果中指指向z軸的正方向，則稱這個(gè)坐標(biāo)系為右手直角坐標(biāo)系。無特別說明，三維坐標(biāo)系一般都是右手直角坐標(biāo)系。yzxyxzo設(shè)m為空間中一定點(diǎn)，過點(diǎn)m分別做垂直于x軸，y軸和z軸的平面，依次交x軸，y軸和z軸于點(diǎn)p，q和r，設(shè)點(diǎn)p，q和r在x軸，y軸和z軸上的坐標(biāo)分別是x,y,z，那么點(diǎn)m就對(duì)應(yīng)唯一確定的有

8、序?qū)崝?shù)組(x,y,z)。反過來，給定實(shí)數(shù)組(x,y,z)，我們可以在x軸，y軸和z軸上一次取坐標(biāo)為x，y和z的點(diǎn)p，q和r。yxzommpqr這樣，空間中一點(diǎn)m的坐標(biāo)可以由序?qū)崝?shù)組(x,y,z)來表示，有序?qū)崝?shù)組(x,y,z)叫做點(diǎn)m在此空間直角坐標(biāo)系中的坐標(biāo)，記作m(x,y,z)，其中x叫做點(diǎn)m的橫坐標(biāo)，y叫做點(diǎn)m的縱坐標(biāo)，z叫做點(diǎn)m的豎坐標(biāo)。 參考系與坐標(biāo)系的應(yīng)用參考系的應(yīng)用參考系的思想來源于物理。解決運(yùn)動(dòng)學(xué)問題的第一步就是選擇合適的參考系。研究太陽系中物體的運(yùn)動(dòng)選擇太陽為參考系比選擇地球?yàn)閰⒖枷岛唵蔚枚?。而研究地面上物體的運(yùn)動(dòng)，我們不會(huì)選擇太陽作為參考系。坐標(biāo)系的應(yīng)用坐標(biāo)系的概念最初來源

9、于數(shù)學(xué)，但在物理等學(xué)科中運(yùn)用極其廣泛。研究函數(shù)離不開坐標(biāo)系，解析幾何就是由于坐標(biāo)系的發(fā)明而誕生的。實(shí)際生活中，用經(jīng)緯度表示地球上一個(gè)地點(diǎn)的地理位置，用極坐標(biāo)表示區(qū)域內(nèi)地點(diǎn)的位置，用平面直角坐標(biāo)表示區(qū)域內(nèi)地點(diǎn)的位置等等，實(shí)際上都是利用了有序數(shù)對(duì)與點(diǎn)的對(duì)應(yīng)關(guān)系，是坐標(biāo)與點(diǎn)一一對(duì)應(yīng)思想的表現(xiàn)。單位長度的改變 問題引入：對(duì)于同一些數(shù)據(jù)，選用不同的單位長度的意義，建立的坐標(biāo)系就不同，解決問題的繁簡也會(huì)不同。比如，我們用數(shù)軸表示分?jǐn)?shù)，把一次考試中所考生的分?jǐn)?shù)填入數(shù)軸中，這時(shí)單位長度都是1分。我們?nèi)绻脭?shù)軸表示名次，單位就是1名。這種從分?jǐn)?shù)到名次的轉(zhuǎn)換，也就是我們常說的離散化。離散化常用于處理數(shù)據(jù)規(guī)模很大，

10、數(shù)據(jù)個(gè)數(shù)較小的問題。就剛才的例子而言，如果考試得滿分為1000分，一共有50名考生，那么以名次建立的數(shù)軸范圍就遠(yuǎn)小于以分?jǐn)?shù)建立的數(shù)軸范圍了。 問題描述：ahoi 2005 day1 穿越磁場（cross）探險(xiǎn)機(jī)器人在samuel星球上尋找一塊奇特的礦石，然而此時(shí)它陷入了一片神秘的磁場區(qū)域，動(dòng)彈不得。探險(xiǎn)空間站立刻掃描了這片區(qū)域，繪制出該區(qū)域的磁場分布平面圖。這片區(qū)域中分布了n個(gè)磁場，每個(gè)磁場呈正方形，且邊與坐標(biāo)軸平行。xyo例如下圖中，存在3個(gè)磁場，白點(diǎn)表示機(jī)器人的位置，黑點(diǎn)表示礦石的位置：科學(xué)家們分析平面圖，進(jìn)一步發(fā)現(xiàn)：這些磁場為大小不一的正方形，可能相交，甚至覆蓋，但是它們的邊緣不會(huì)重合，

11、頂點(diǎn)也不會(huì)重合。例如下面的兩種情形是不會(huì)出現(xiàn)的：科學(xué)家們給探險(xiǎn)機(jī)器人啟動(dòng)了磁力罩，這樣它就可以在磁場中自由穿越了。初始時(shí)，探險(xiǎn)機(jī)器人和所有礦石都不在任何磁場的邊緣。由于技術(shù)限制，在穿越過程中機(jī)器人只能夠水平或垂直移動(dòng)，且不能夠沿著磁場的邊緣行動(dòng)。由于磁力罩的能量有限，科學(xué)家們希望探險(xiǎn)機(jī)器人穿越盡量少的磁場邊緣采集到這塊礦石。例如上圖中，探險(xiǎn)機(jī)器人最少需要穿越兩次磁場邊緣?，F(xiàn)在小聯(lián)請你編寫程序，幫助科學(xué)家們設(shè)計(jì)探險(xiǎn)機(jī)器人的路線，統(tǒng)計(jì)探險(xiǎn)機(jī)器人最少需要穿越多少次磁場邊緣。輸入：第一行有一個(gè)整數(shù)n，表示有n個(gè)磁場（1 n 100）。隨后有n行，每行有三個(gè)整數(shù)x、y、c（0 x ,y ,c 10000

12、），表示一個(gè)磁場左下角坐標(biāo)為（x,y），邊長為c。接下來有一行，共有四個(gè)整數(shù)sx, sy, tx, ty，表示機(jī)器人初始坐標(biāo)為（sx, sy），礦石坐標(biāo)為（tx，ty）（其中，0 sx, sy, tx, ty 10000）。輸出：單行輸出一個(gè)整數(shù)，表示機(jī)器人最少需要穿越多少次磁場邊緣。樣例：輸入： 2 1 3 3 2 1 40 0 3 4輸出： 2 問題分析：方法1：將坐標(biāo)中的所有整點(diǎn)坐標(biāo)當(dāng)作頂點(diǎn)，在每個(gè)點(diǎn)與坐標(biāo)系中相鄰的點(diǎn)間加一條無向邊，如果穿過磁場，邊的權(quán)值為1，否則權(quán)值為0。000101000101000101101000oxy000000111011111000000000000000

13、101122求機(jī)器人從起點(diǎn)到終點(diǎn)的最小耗費(fèi)，也就是求構(gòu)造的圖中兩點(diǎn)之間的最短路徑，我們可以用dijkstra解決。每次循環(huán)中尋找最大值的復(fù)雜度為o(v)，改進(jìn)相鄰點(diǎn)時(shí)由于要判斷是否穿過磁場邊，所以復(fù)雜度為o(n)。整個(gè)算法復(fù)雜度為就是o(vn+v2)，這里v=整個(gè)坐標(biāo)中的點(diǎn)的個(gè)數(shù)=10000*10000，顯然超時(shí)。當(dāng)然，在實(shí)現(xiàn)過程中我們可以有所優(yōu)化，比如確定查找點(diǎn)的范圍。方法2：dijkstra分為兩大部分，第一部分是取所有未標(biāo)記點(diǎn)中的最小值，第二部分是用當(dāng)前最小值改進(jìn)整個(gè)圖。那么建立一個(gè)上小下大的堆，堆中保存所有起始點(diǎn)到圖中未標(biāo)記的點(diǎn)的最短路徑值，這樣每次取出一個(gè)最小值的復(fù)雜度為o(1)；由

14、于此圖中，每個(gè)點(diǎn)的度最多為4，查找邊的權(quán)值的復(fù)雜度為o(n)，更新堆的復(fù)雜度為o(vlog2v)。因而算法復(fù)雜度降為o(v+nv+vlog2v)。但由于v=10000*10000仍不能在時(shí)限中出解。方法3：oxy00000000000000000000000000000000000000此題的數(shù)據(jù)規(guī)模有一些特性雖然坐標(biāo)系的范圍巨大，但有效坐標(biāo)（機(jī)器人的坐標(biāo)，寶藏的坐標(biāo)和磁場頂點(diǎn)坐標(biāo)）的個(gè)數(shù)卻很小。上兩個(gè)方法的主要復(fù)雜度都取決于v，也就是坐標(biāo)系中的點(diǎn)數(shù)。如果我們可以把坐標(biāo)系的范圍縮小，也就相當(dāng)于把v縮小，就可以大大降低問題的時(shí)間復(fù)雜度。在上種方法的構(gòu)圖中，我們會(huì)發(fā)現(xiàn)很多邊的權(quán)值為0，也就是說，可

15、能有很多連續(xù)點(diǎn)的最短路徑值都相等。如圖：那么我們將整個(gè)圖中有效坐標(biāo)抽出，建立一個(gè)新的坐標(biāo)系，這個(gè)坐標(biāo)系中相鄰兩個(gè)個(gè)坐標(biāo)的間距為單位“1”，但此時(shí)單位長度的意義為有效坐標(biāo)的序號(hào)。如圖：這樣我們依然用最短路徑的方法在這個(gè)圖中進(jìn)行操作，算法復(fù)雜度為o(v+vn+vlog2v)，但此時(shí)，v=204*204，問題得以解決。方法4：離散化后對(duì)整個(gè)圖中的連續(xù)無磁場部分進(jìn)行染色，如下圖：問題就是求機(jī)器人所在點(diǎn)的顏色區(qū)域到寶藏所在點(diǎn)的顏色區(qū)域的最短路徑。由于每相鄰兩個(gè)區(qū)域間的邊的權(quán)值均為1，所以算法復(fù)雜度為o(v)。因而整個(gè)算法的復(fù)雜度為o(nv)。這里的n=100,v=204*204。如果先構(gòu)圖，復(fù)雜度為o(

16、n)，再染色用寬搜求最短路復(fù)雜度為o(v)，所以總復(fù)雜度為o(n+v)。 小結(jié)：對(duì)于同一問題，選用的單位長度的意義不同，就會(huì)有不同效果。比如cross這題，開始是以題目已經(jīng)建立了的坐標(biāo)系的長度1為單位長度，到后來將有效坐標(biāo)排序后，以其序號(hào)為單位長度，坐標(biāo)系的范圍大大縮小。這是我們常說的離散化，但也可以理解為單位長度的意義改變。我們不能局限在原有的或常用的單位長度意義，而應(yīng)適宜題目做出改造或創(chuàng)造。參考系的選擇 問題引入：選擇不同的參考系來觀察同一運(yùn)動(dòng)，觀察的結(jié)果會(huì)不同。比如，馬路上停著n輛汽車，現(xiàn)在有n-1輛汽車以相同速度向前運(yùn)動(dòng)，以地面為參考系，n-1輛汽車運(yùn)動(dòng)，一輛汽車靜止；以n-1輛運(yùn)動(dòng)的

17、汽車為參考系，一輛汽車運(yùn)動(dòng)，n-1輛汽車靜止。在不同參考系中描述物體運(yùn)動(dòng)，繁簡是不一樣的。 問題描述：usaico 2005 day6 布丁(puddin)fj建立了一個(gè)布丁工廠。在接下來的n(1=n=40,000)個(gè)星期里，原料牛奶和勞動(dòng)力的價(jià)格會(huì)有很大波動(dòng)。fj希望能夠在滿足消費(fèi)者需求的前提下盡量減小花費(fèi)。fj預(yù)計(jì)接下來每個(gè)星期會(huì)需要ci(1=ci=5,000)元錢來生產(chǎn)一單位布丁，且消費(fèi)者會(huì)需要pi(0=pi=10,000)單位布丁。fj每星期即可以生產(chǎn)布丁，也可以儲(chǔ)存布丁供以后使用。它的倉庫存儲(chǔ)一星期一單位布丁需要s(1=s=100)元錢。但是由于布丁有保質(zhì)期，所以最多只能保存t(0=

18、t=40,000)星期。也就是說x星期生產(chǎn)的布丁可以在(x+t)星期銷售，但是不能在(x+t+1)星期銷售。請幫助fj安排生產(chǎn)與存儲(chǔ)的方案使得在滿足消費(fèi)者需求的前提下盡量減小花費(fèi)。輸入文件：第一行為n,s與t.第二行到第(n+1)行：每一行兩個(gè)數(shù)，即ci與pi。輸出文件：僅一個(gè)數(shù)，即滿足顧客需求前提下的最小花費(fèi)。樣例：輸入：5 10 312 121 227 445 552 3輸出：488 問題分析：方法1：問題是求滿足每星期需求量的最小的費(fèi)用wmin，我們很容易wmin=，每個(gè)星期的最小費(fèi)用是相互獨(dú)立的。又因?yàn)閣i=最小單價(jià)vi*pi，pi已給定，那么問題就是求個(gè)個(gè)星期的最小單價(jià)vi。根據(jù)vi

19、=min(cj+s*(i-j) (0j=i-t)，我們可以求出每星期的vi，繼而求出wi和wmin。時(shí)間復(fù)雜度為o(nt)，由于n,t最大為40000，所以不能在時(shí)限中出解。方法2：每個(gè)星期的vi都得求出，也就是o(n)的復(fù)雜度不可少，我們試圖將求解vi的復(fù)雜度降低。我們想到用線段樹、堆、平衡樹等數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，就vi的求解公式，我們選用堆。建立一個(gè)上小下大的最多有t個(gè)節(jié)點(diǎn)的堆，堆中保存保質(zhì)期內(nèi)每個(gè)星期布丁到此星期的價(jià)值。那么從第i星期，到i+1星期對(duì)堆的操作有：1) 刪除堆中超過保質(zhì)期的布丁價(jià)值2) 將堆中所有布丁的價(jià)值加上s3) 插入ci4) 取出堆頂作為vi上面這四步操作，第3，4都是

20、堆的基本操作，復(fù)雜度分別為o(log2t)，o(1)；第1步我們可以通過數(shù)組記錄位置在o(log2t)的復(fù)雜度內(nèi)解決；但第2步就不容易解決了。那么是否就不可以用堆進(jìn)行優(yōu)化呢？方法3：我們建立堆的目的就是求出所有保質(zhì)期內(nèi)的布丁在此星期時(shí)的最小單價(jià)，那么只要知道是第幾星期成產(chǎn)的布丁此星期中價(jià)值最小便可。上種方法是完全按照題目意思進(jìn)行的，那么我們不妨改變一下。我們將2) 將堆中所有布丁的價(jià)值加上s3) 插入ci這兩步用圖表示，如下：3576579856987s=2ci=6我們回想一下上面問題引入中汽車的例子，n-1個(gè)物體運(yùn)動(dòng)；n-1個(gè)物體為參照物，也就是1個(gè)靜止的物體做相反運(yùn)動(dòng)了。這題也是一樣，堆中

21、所有的價(jià)值增加s；以這些增加的值為參照物，也就相當(dāng)于新插入的ci減少s。這樣一來，每個(gè)星期對(duì)布丁的操作就是：1) 刪除堆中超過保質(zhì)期的布丁價(jià)值2) 插入ci-s*(i-1)3) 取出堆頂s=2347653576i=6問題復(fù)雜度降為o(nlog2t)。方法4：現(xiàn)在問題劃歸為每次插入ci-s(i-1)，求保值期t內(nèi)的最小費(fèi)用。這樣，我們不妨用隊(duì)列來解決。維持一個(gè)遞增的長度最長為t的隊(duì)列，步驟為：1) 刪除隊(duì)列中超過保質(zhì)期的布丁單價(jià)2) 插入新的布丁單價(jià)ci-s(i-1)3) 從隊(duì)頭刪除所有大于ci-s(i-1)的布丁單價(jià)由于，第1，2步復(fù)雜度為o(1)，第三步平坦復(fù)雜度為o(1)，所以整個(gè)算法的復(fù)

22、雜度為o(n)。 小結(jié)：對(duì)于只要比較，不需求具體值或具體值很方便求出的問題，我們所建立的模型，可以換用非常規(guī)參考系。就像本題，原先模型中都是對(duì)真實(shí)值進(jìn)行處理，不易解決；但換用已有的需改變的值為參考系后，所有的價(jià)值不是真實(shí)值，但價(jià)值的相對(duì)大小依舊，問題也就迎刃而解。所以對(duì)于這類問題，我們要開拓思維，利用參考系思想，將數(shù)值進(jìn)行改造，保持其相對(duì)大小，方便解決問題。坐標(biāo)系的建立 問題引入：一般來說幾維坐標(biāo)系就有幾個(gè)非平行的原點(diǎn)重合的坐標(biāo)軸。平面中，任意一個(gè)向量都可以用兩個(gè)非平行的向量合成，所以二維坐標(biāo)系只需要兩個(gè)數(shù)軸，就足以表示此平面中的所有點(diǎn)了，如果多加一個(gè)坐標(biāo)軸則是冗雜。 問題描述：delta-w

23、ave一個(gè)三角形的田野用遞增的正整數(shù)按照圖中方式進(jìn)行編號(hào)。一位旅行者，要從編號(hào)為m的格子到編號(hào)為n的格子(1=n,m=1000000000)。旅行者只能通過穿過邊進(jìn)入一個(gè)新格子，而不能通過點(diǎn)在格子中旅行。旅行者穿過的邊數(shù)為旅行者的路程長度。求從n到m的最小路程長度。輸入文件：一行包含n,m輸出文件：僅一個(gè)數(shù)，即最小路程長度。樣例：輸入：6 12輸出：3 問題分析：方法1：把每個(gè)小三角形視為頂點(diǎn)，在一個(gè)小三角形與相鄰小三角形間加一條無向邊，邊的權(quán)值為1。那么從起始點(diǎn)到目標(biāo)點(diǎn)所要穿越的最少邊數(shù)就等于構(gòu)造的圖中兩點(diǎn)間的最短路徑。221123233444450由于此圖中所有邊的權(quán)值均為1，所以我們可用

24、“灌水法”，即從起始點(diǎn)開始寬搜，最短路徑就是目標(biāo)點(diǎn)的層數(shù)。算法復(fù)雜度為o(n)，由于n最大時(shí)=1000000000，所以不能在規(guī)定時(shí)限中出解。方法2：用題目中的編號(hào)來描述這個(gè)圖形，顯然不太方便，我們用常用的行列來表示一個(gè)小三角形的位置。這也就相當(dāng)于把圖形給拉直了，放入坐標(biāo)系中，如下圖：(3,4)(1,1)2321(1,1)，22起始點(diǎn)的移動(dòng)過程，就是不斷逼近（兩點(diǎn)之間所要穿過的邊數(shù)越來越少）的過程。那么行、列坐標(biāo)都要不斷地逼近。但行坐標(biāo)的改變不會(huì)影響列坐標(biāo)；相反，列坐標(biāo)的改變也不會(huì)影響行坐標(biāo)。所以，我們可以先使行坐標(biāo)逼近，再使列坐標(biāo)逼近。不妨令目標(biāo)坐標(biāo)的編號(hào)小于起始坐標(biāo)。1 同行中：兩個(gè)三角形

25、所要經(jīng)過的最少邊數(shù)就等于列坐標(biāo)的差值。2 非同行時(shí)：1) 行坐標(biāo)偶數(shù)：直接移到臨近目標(biāo)三角形的一行。穿過邊數(shù)為1。2) 行坐標(biāo)奇數(shù)：必須移到相鄰的偶數(shù)坐標(biāo)，再移到臨近目標(biāo)三角形的一行。列坐標(biāo)也有所改變，我們向更加逼近目標(biāo)三角形列坐標(biāo)的方向移動(dòng)，如果列坐標(biāo)相同，我們隨意移到相鄰的偶數(shù)坐標(biāo)。穿過邊數(shù)為2。這樣模擬點(diǎn)的運(yùn)行軌跡，要經(jīng)過|m-n|行，算法復(fù)雜度為o()，最大為=10000*，已可以在時(shí)限中出解。那么是否有更好的方法呢？方法3：a(x1,y1)b(x2,y2)我們先看一個(gè)與此題類似的簡單題目：一個(gè)m*n的矩陣中，求a格到b格所要穿過的最少邊數(shù)。這個(gè)問題的答案似乎十分顯然，我們給把矩陣放在

26、直角坐標(biāo)系中，這樣每個(gè)格子都有一個(gè)坐標(biāo)值(x,y)，如果a(x1,y1)，b(x2,y2)，那么從a格到b格的最少穿過邊的個(gè)數(shù)為|x1-x2|+|y1-y2|。道理和方法2的相類，行列都需不斷逼近，且一個(gè)坐標(biāo)的逼近不會(huì)影響另一個(gè)坐標(biāo)，那么不妨先使一個(gè)坐標(biāo)相等，再改變另一個(gè)坐標(biāo)。但方法2卻不能直接出解，原因在于對(duì)列的奇偶坐標(biāo)操作不同。這是否說明我們的坐標(biāo)系建立的不完備呢？xyz我們觀察原始三角形，會(huì)發(fā)現(xiàn)有三個(gè)方向，如圖：建立一個(gè)有三個(gè)軸的平面坐標(biāo)系，用(x,y,z)來表示一個(gè)點(diǎn)的坐標(biāo)，那么從a(x1,y1,z1)到b(x2,y2,z2)穿過的最少邊數(shù)是否就等于|x1-x2|+|y1-y2|+|z

27、1-z2|呢？下面給出證明：命題1： 從a到b穿過最少邊數(shù)的下限為|x1-x2|+|y1-y2|+|z1-z2|。證明：x,y,z坐標(biāo)都是相互獨(dú)立的，一個(gè)坐標(biāo)的改變不會(huì)影響另一個(gè)坐標(biāo)，所以命題1成立。命題2：存在從a到b穿過邊數(shù)為|x1-x2|+|y1-y2|+|z1-z2|的方案。證明：如果任意點(diǎn)a(ab)都能向某個(gè)方向走縮小與b的坐標(biāo)差值，就可以找到一種方案。下面用反證法證明：假設(shè)：存在a點(diǎn)(ab)無論向哪個(gè)方向走，與b點(diǎn)的坐標(biāo)差值都不會(huì)減少。為起始點(diǎn)如果沿x軸，與b的x坐標(biāo)差值增大，則b在中。如果沿y軸，與b的y坐標(biāo)差值增大，則b在中。如果沿z軸，與b的z坐標(biāo)差值增大，則b在中。為目標(biāo)點(diǎn)

28、所在范圍與假設(shè)ab矛盾！結(jié)論：從a(x1,y1,z1)到b(x2,y2,z2)穿過的最少邊數(shù)=|x1-x2|+|y1-y2|+|z1-z2|。由于題目中給的是a,b的編號(hào)n,m，我們只要將n,m轉(zhuǎn)化為坐標(biāo)值(x,y,z)即可。頂上的三角形坐標(biāo)為(1,1,1)，編號(hào)為n的點(diǎn)的坐標(biāo)值為x= y=z=所以算法復(fù)雜度為o(1)。 小結(jié)：本題從不用坐標(biāo)系，到使用常規(guī)坐標(biāo)系，再到根據(jù)題目建立特殊坐標(biāo)系，問題不斷明朗，復(fù)雜度不斷降低。問題引入中說一般情況幾維坐標(biāo)系就有一個(gè)數(shù)軸，但此題的方法3卻建立了有三個(gè)軸的二維坐標(biāo)系，這種形式上的“冗雜”，換來的是思維上的簡潔。所以我們要打破思維枷鎖，不能只限于“常規(guī)”，

29、而應(yīng)根據(jù)“常規(guī)”繼續(xù)發(fā)散。我們分析問題時(shí)應(yīng)細(xì)致認(rèn)真，抓住問題的矛盾所在，繼續(xù)分析。比如本題中就是由于發(fā)現(xiàn)方法2中奇偶列不能統(tǒng)一，才引發(fā)了方法3?？偨Y(jié)上面的三題看似毫無關(guān)聯(lián)，因?yàn)榻忸}思維不盡相同。但其實(shí)三題中都一個(gè)重要的燈塔，也是這三題的突破口，那就是“參考系與坐標(biāo)系思想”。雖然我們開始分析時(shí)，毫不知參考系與坐標(biāo)系思想，憑著經(jīng)驗(yàn)走出了道路。但走完這些道路后，我們再悉心回首，會(huì)發(fā)現(xiàn)這些道路中都有著相通點(diǎn)。所以在走出條道路后，就點(diǎn)亮道路中的燈塔，使以后的分析更加明朗。參考文獻(xiàn)與資料來源吳文虎 王建德，實(shí)用算法分析與程序設(shè)計(jì)，電子工業(yè)出版社，1998.1張維善，普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書 物理 必修1

30、，人民教育出版社，2004.5劉紹學(xué)，普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書 數(shù)學(xué) 必修2，人民教育出版社，2004.5林群，義務(wù)教育課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書 數(shù)學(xué) 七年級(jí)下冊，人民教育出版社，2004.6附錄/cross 1#include#include#includeconst char *inname=cross.in;const char *outname=cross.out;const int maxn=10010;const int max=110;const int infi=100000000;struct node int x,y,c;file *fin,*fout;int total,mi

31、nmaxnmaxn,maxx,maxy,sx,sy,tx,ty,minx,miny;bool markmaxnmaxn;node recmax;void init();void print();void work();void goy(int x,int y,int v);void gox(int x,int y,int v);void init() int i; fin=fopen(inname,r); fscanf(fin,%d,&total); for (i=0;itotal;i+) fscanf(fin,%d%d%d,&reci.x,&reci.y,&reci.c); if (reci

32、.x-1minx) minx=reci.x-1; if (reci.y-1maxx) maxx=reci.x+reci.c+1; if (reci.y+reci.c+1maxy) maxy=reci.y+reci.c+1; fscanf(fin,%d%d%d%d,&sx,&sy,&tx,&ty); if (sxmaxx) maxx=sx; if (txmaxx) maxx=tx; if (symaxy) maxy=sy; if (tymaxy) maxy=ty; if (sxminx) minx=sx; if (txminx) minx=tx; if (syminy) miny=sy; if

33、(tyminy) miny=ty; if (minx0) minx=0; if (miny0) miny=0; fclose(fin);void print() fout=fopen(outname,w); fprintf(fout,%dn,mintxty); fclose(fout);void work() int i,j,m,n,v; for (i=minx;i=maxx;i+) for (j=miny;j=maxy;j+) minij=infi; minsxsy=0; for (;) for (v=infi,i=minx;i=maxx;i+) for (j=miny;j=maxy;j+)

34、 if (!markij & minijmaxx | xmaxy | y=minxy | markxy) return ; for (i=0;i=reci.x & x=reci.x+reci.c) return ; for (i=0;i=reci.y & y=reci.y+reci.c) if (v+1minxy) minxy=v+1; return; if (vmaxx | xmaxy | y=minxy | markxy) return ; for (i=0;i=reci.y & y=reci.y+reci.c) return ; for (i=0;i=reci.x & x=reci.x+

35、reci.c) if (v+1minxy) minxy=v+1; return; if (vminxy) minxy=v;int main() init(); work(); print(); return 0;/cross 2#include#include#includeconst char *inname=cross.in;const char *outname=cross.out;const int maxn=10010;const int max=110;const int infi=100000000;struct node int x,y,c;struct node1 short

36、 int x,y; int v;file *fin,*fout;int total,maxx,maxy,sx,sy,tx,ty,minx,miny,pointmaxnmaxn,tt;bool markmaxnmaxn;node recmax;node1 heapmaxn*maxn;void init();void print();void work();void goy(int x,int y,int v);void gox(int x,int y,int v);void swap(node1 &a,node1 &b);void down(int v);void up(int v);void

37、init() int i; fin=fopen(inname,r); fscanf(fin,%d,&total); for (i=0;itotal;i+) fscanf(fin,%d%d%d,&reci.x,&reci.y,&reci.c); if (reci.x-1minx) minx=reci.x-1; if (reci.y-1maxx) maxx=reci.x+reci.c+1; if (reci.y+reci.c+1maxy) maxy=reci.y+reci.c+1; fscanf(fin,%d%d%d%d,&sx,&sy,&tx,&ty); if (sxmaxx) maxx=sx;

38、 if (txmaxx) maxx=tx; if (symaxy) maxy=sy; if (tymaxy) maxy=ty; if (sxminx) minx=sx; if (txminx) minx=tx; if (syminy) miny=sy; if (tyminy) miny=ty; if (minx0) minx=0; if (miny0) miny=0; fclose(fin);void print() fprintf(fout,%dn,heappointtxty.v); fclose(fout);void work() int i,j,m,n,v,cc; for (i=minx

39、;i=maxx;i+) for (j=miny;jmaxx | xmaxy | y=heaph.v) return ; for (i=0;i=reci.y & y=reci.y+reci.c) return ; for (i=0;i=reci.x & x=reci.x+reci.c) if (v+1maxx | xmaxy | y=heaph.v) return ; for (i=0;i=reci.x & x=reci.x+reci.c) return ; for (i=0;i=reci.y & y=reci.y+reci.c) if (v+1tt) return; if (v*2+1tt |

40、 heapv*2.vheapv*2+1.v) k=v*2; else k=v*2+1; if (heapv.v=heapv/2.v) return ; swap(heapv,heapv/2); up(v/2);void swap(node1 &a,node1 &b) node1 temp; int temp1; temp=a; a=b; b=temp; temp1=pointa.xa.y; pointa.xa.y=pointb.xb.y; pointb.xb.y=temp1;int main() init(); fout=fopen(outname,w); work(); print(); r

41、eturn 0;/cross 3#include#include#includeconst char *inname=cross.in;const char *outname=cross.out;const int max=210;const int infi=100000000;struct node int x,y,c,xm,ym;struct node1 short int x,y; int v;file *fin,*fout;int total,totx,toty,sx,sy,tx,ty,pointmaxmax,tt,xaxismax,yaxismax;bool markmaxmax;node recmax;node1 heapmax*max;void init();void print();void work()