算法 - 華東理工大學(xué)計算機科學(xué)與工程系

1、算法 李開復(fù)：算法的力量算法是計算機科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國內(nèi)一些程序員的冷落。許多學(xué) 生看到一些公司在招聘時要求的編程語言五花八門就產(chǎn)生了一種誤解，認為學(xué)計算機就是學(xué) 各種編程語言，或者認為，學(xué)習(xí)最新的語言、技術(shù)、標(biāo)準(zhǔn)就是最好的鋪路方法。其實大家都 被這些公司誤導(dǎo)了。編程語言雖然該學(xué)，但是學(xué)習(xí)計算機算法和理論更重要，因為計算機算 法和理論更重要，因為計算機語言和開發(fā)平臺日新月異，但萬變不離其宗的是那些算法和理 論，例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計算機體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫原理等等。在開復(fù)學(xué) 生網(wǎng)上，有位同學(xué)生動地把這些基礎(chǔ)課程比擬為內(nèi)功，把新的語言、技術(shù)、標(biāo)準(zhǔn)比擬為 外功氣整天

2、趕時髦的人最后只懂得招式，沒有功力，是不可能成為高手的。算法與我當(dāng)我在1980年轉(zhuǎn)入計算機科學(xué)系時，還沒有多少人的專業(yè)方向是計算機科學(xué)。有許多 其他系的人嘲笑我們說：知道為什么只有你們系要加一個科學(xué)，而沒有物理科學(xué)系或 化學(xué)科學(xué)系嗎？因為人家是真的科學(xué)，不需要畫蛇添足，而你們自己心虛，生怕不科學(xué)， 才這樣欲蓋彌彰。其實，這點他們徹底弄錯了。真正學(xué)懂計算機的人(不只是編程匠)都 對數(shù)學(xué)有相當(dāng)?shù)脑煸?，既能用科學(xué)家的嚴謹思維來求證，也能用工程師的務(wù)實手段來解決問 題一而這種思維和手段的最佳演繹就是算法。記得我讀博時寫的Othello對弈軟件獲得了世界冠軍。當(dāng)時，得第二名的人認為我是 靠僥幸才打贏他，

3、不服氣地問我的程序平均每秒能搜索多少步棋，當(dāng)他發(fā)現(xiàn)我的軟件在搜索 效率上比他快60多倍時，才徹底服輸。為什么在同樣的機器上，我可以多做60倍的工作呢？ 這是因為我用了一個最新的算法，能夠把一個指數(shù)函數(shù)轉(zhuǎn)換成四個近似的表，只要用常數(shù)時 間就可得到近似的答案。在這個例子中，是否用對算法才是能否贏得世界冠軍的關(guān)鍵。還記得1988年貝爾實驗室副總裁親自來訪問我的學(xué)校，目的就是為了想了解為什么他 們的語音識別系統(tǒng)比我開發(fā)的慢幾十倍，而且，在擴大至大詞匯系統(tǒng)后，速度差異更有幾百 倍之多。他們雖然買了幾臺超級計算機，勉強讓系統(tǒng)跑了起來，但這么貴的計算資源讓他們 的產(chǎn)品部門很反感，因為昂貴的技術(shù)是沒有應(yīng)用前景

4、的。在與他們探討的過程中，我驚訝 地發(fā)現(xiàn)一個O(n*m)的動態(tài)規(guī)劃(dynamic programming)居然被他們做成了 O(n*n*m)。更驚訝 的是，他們還為此發(fā)表了不少文章，甚至為自己的算法起了一個很特別的名字，并將算法提 名到一個科學(xué)會議里，希望能得到大獎。當(dāng)時，貝爾實驗室的研究員當(dāng)然絕頂聰明，但他們 全都是學(xué)數(shù)學(xué)、物理或電機出身，從未學(xué)過計算機科學(xué)或算法，才犯了這么基本的錯誤。我 想那些人以后再也不會嘲笑學(xué)計算機科學(xué)的人了吧！網(wǎng)絡(luò)時代的算法有人也許會說：今天計算機這么快，算法還重要嗎？ 其實永遠不會有太快的計算機， 因為我們總會想出新的應(yīng)用。雖然在摩爾定律的作用下，計算機的計算能

5、力每年都在飛快增 長，價格也在不斷下降?？晌覀儾灰?，需要處理的信息量更是呈指數(shù)級的增長?，F(xiàn)在每 人每天都會創(chuàng)造出大量數(shù)據(jù)(照片，視頻，語音，文本等等)日益先進的紀(jì)錄和存儲手段使 我們每個人的信息量都在爆炸式的增長?；ヂ?lián)網(wǎng)的信息流量和日志容量也在飛快增長。在科 學(xué)研究方面，隨著研究手段的進步，數(shù)據(jù)量更是達到了前所未有的程度。無論是三維圖形、 海量數(shù)據(jù)處理、機器學(xué)習(xí)、語音識別，都需要極大的計算量。在網(wǎng)絡(luò)時代，越來越多的挑戰(zhàn) 需要靠卓越的算法來解決。再舉另一個網(wǎng)絡(luò)時代的例子。在互聯(lián)網(wǎng)和手機搜索，如果要找附近的咖啡店，那么搜 索引擎該怎么處理這個請求呢？最簡單的辦法就是把整個城市的咖啡館都找出來，

6、然后計算 出它們的所在位置與你之間的距離，再進行排序，然后返回最近的結(jié)果。但該如何計算距離 呢？圖論里有不少算法可以解決這個問題。這么做也許是最直觀的，但絕對不是最迅速的。如果一個城市只有為數(shù)不多的咖啡館， 那么這么做應(yīng)該沒什么問題，反正計算量不大。但如果一個城市里有很多咖啡館，又有很多 用戶都需要類似的搜索，那么服務(wù)器所承受的壓力就大多了。在這種情況下，我們該怎樣優(yōu) 化算法呢？首先，我們可以把整個城市的咖啡館做一次預(yù)處理。比如，把一個城市分成若干個 格子(grid)，然后根據(jù)用戶所在的位置把他放到某一個格子里，只對格子里的咖啡館進行距 離排序。問題又來了，如果格子大小一樣，那么絕大多數(shù)結(jié)果都

7、可能出現(xiàn)在市中心的一個格子 里，而郊區(qū)的格子里只有極少的結(jié)果。在這種情況下，我們應(yīng)該把市中心多分出幾個格子。 更進一步，格子應(yīng)該是一個樹結(jié)構(gòu)，最頂層是一個大格一整個城市，然后逐層下降，格子 越來越小，這樣有利于用戶進行精確搜索一如果在最底層的格子里搜索結(jié)果不多，用戶可以 逐級上升，放大搜索范圍。上述算法對咖啡館的例子很實用，但是它具有通用性嗎？答案是否定的。把咖啡館抽 象一下，它是一個點，如果要搜索一個面該怎么辦呢？比如，用戶想去一個水庫玩，而 一個水庫有好幾個入口，那么哪一個離用戶最近呢？這個時候，上述 樹結(jié)構(gòu)就要改成 r-tree”，因為樹中間的每一個節(jié)點都是一個范圍，一個有邊界的范圍。通

8、過這個小例子，我們看到，應(yīng)用程序的要求千變?nèi)f化，很多時候需要把一個復(fù)雜的 問題分解成若干簡單的小問題，然后再選用合適的算法和數(shù)據(jù)結(jié)構(gòu)。并行算法：Google的核心優(yōu)勢上面的例子在Google里就要算是小case 了！每天Google的網(wǎng)站要處理十億個以上的 搜索，GMail要儲存幾千萬用戶的2G郵箱，Google Earth要讓數(shù)十萬用戶同時在整個地球上 遨游，并將合適的圖片經(jīng)過互聯(lián)網(wǎng)提交給每個用戶。如果沒有好的算法，這些應(yīng)用都無法成 為現(xiàn)實。在這些的應(yīng)用中，哪怕是最基本的問題都會給傳統(tǒng)的計算帶來很大的挑戰(zhàn)。例如，每 天都有十億以上的用戶訪問Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很

9、多很多的日志 (Log)。因為Log每份每秒都在飛速增加，我們必須有聰明的辦法來進行處理。我曾經(jīng)在面試 中問過關(guān)于如何對Log進行一些分析處理的問題，有很多面試者的回答雖然在邏輯上正確， 但是實際應(yīng)用中是幾乎不可行的。按照它們的算法，即便用上幾萬臺機器，我們的處理速度 都根不上數(shù)據(jù)產(chǎn)生的速度。那么Google是如何解決這些問題的？首先，在網(wǎng)絡(luò)時代，就算有最好的算法，也要能在并行計算的環(huán)境下執(zhí)行。google 的數(shù)據(jù)中心，我們使用的是超大的并行計算機。但傳統(tǒng)的并行算法運行時，效率會在增加機 器數(shù)量后迅速降低，也就是說，十臺機器如果有五倍的效果，增加到一千臺時也許就只有幾 十倍的效果。這種事半功倍

10、的代價是沒有哪家公司可以負擔(dān)得起的。而且，在許多并行算法 中，只要一個結(jié)點犯錯誤，所有計算都會前功盡棄。那么Google是如何開發(fā)出既有效率又能容錯的并行計算的呢？Google最資深的計算機科學(xué)家Jeff Dean認識到，Google所需的絕大部分數(shù)據(jù)處理都 可以歸結(jié)為一個簡單的并行算法：Map and Reduce ( HYPERLINK /papers/mapreduce.htmDo%e8%bf%99%e4%b8%aa%e7%ae%97%e6%b3%95%e8%83%bd%e5%a4%9f%e5%9c%a8%e5%be%88%e5%a4%9a%e7%a7%8d%e8%ae%a1%e7%ae

11、%97%e4%b8%ad%e8%be%be%e5%88%b0%e7%9b%b8 /papers/mapreduce.htmDo這個算法能夠在很多種計算中達到相 當(dāng)高的效率，而且是可擴展的（也就是說，一千臺機器就算不能達到一千倍的效果，至少也 可以達到幾百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉價的機器組 成功能強大的server farm。最后，它的容錯性能異常出色，就算一個server farm宕掉一 半，整個fram依然能夠運行。正是因為這個天才的認識，才有了 Map and Reduce算法。借 助該算法，Google幾乎能無限地增加計算量，與日新月異的互

12、聯(lián)網(wǎng)應(yīng)用一同成長。算法并不局限于計算機和網(wǎng)絡(luò)舉一個計算機領(lǐng)域外的例子：在高能物理研究方面，很多實驗每秒鐘都能幾個TB的數(shù) 據(jù)量。但因為處理能力和存儲能力的不足，科學(xué)家不得不把絕大部分未經(jīng)處理的數(shù)據(jù)丟棄掉。 可大家要知道，新元素的信息很有可能就藏在我們來不及處理的數(shù)據(jù)里面。同樣的，在其他 任何領(lǐng)域里，算法可以改變?nèi)祟惖纳?。例如人類基因的研究，就可能因為算法而發(fā)明新的 醫(yī)療方式。在國家安全領(lǐng)域，有效的算法可能避免下一個911的發(fā)生。在氣象方面，算法可 以更好地預(yù)測未來天災(zāi)的發(fā)生，以拯救生命。所以，如果你把計算機的發(fā)展放到應(yīng)用和數(shù)據(jù)飛速增長的大環(huán)境下，你一定會發(fā)現(xiàn)； 算法的重要性不是在日益減小，而

13、是在日益加強。轉(zhuǎn)自計算機科學(xué)論壇注：算法是計算機科學(xué)的核心，是程序的靈魂，它的基礎(chǔ)性地位遍布計算機科學(xué)的各個 分支領(lǐng)域.原文作者介紹：李開復(fù)博士現(xiàn)google中國總裁1998年7月加盟微軟，當(dāng)年11月出任微軟中國研究院（現(xiàn)微軟亞洲研究院）院長。 李開復(fù)在語音識別、人工智能、三維圖形及網(wǎng)絡(luò)多媒體等領(lǐng)域享有很高的聲譽。在他的帶領(lǐng) 下，微軟中國研究院以新一代多媒體、新一代用戶界面和新一代信息處理技術(shù)為主要方向開 展基礎(chǔ)研究。后升任微軟副總裁。加盟微軟公司前，李博士曾擔(dān)任SGI公司的多媒體軟件子公司一CosmoSoftware的總裁，負責(zé)多平臺、互聯(lián)網(wǎng)三維圖形和多媒體軟件方面的研發(fā)工作。此前 他還曾在

14、蘋果公司工作了六年，主管該公司的多媒體部門。李博士在蘋果公司任職六年中的最后一個職務(wù)是其交互式多媒體部門的副總裁，他們 后來開發(fā)出 QuickTime， QuickDraw3D，QuickTimeVR 等產(chǎn)品。在加入蘋果公司之前，李博士曾就讀于美國卡內(nèi)基梅隆大學(xué)，獲計算機科學(xué)博士學(xué)位。 后擔(dān)任副教授。在他的博士課題研究工作中,首次創(chuàng)造性的提出基于統(tǒng)計學(xué)的語音識別方法， 并在此基礎(chǔ)上開發(fā)出了世界上第一個非特定人連續(xù)語音識別系統(tǒng)，使識別率由原來的百分 之三十提高到百分之九十六，該方法今天已成為計算機語音識別的技術(shù)主流，也奠定了李博 士在該領(lǐng)域的權(quán)威地位。1988年，商業(yè)周刊授予該系統(tǒng)最重要科學(xué)創(chuàng)新

15、獎。在校期間，李 博士還開發(fā)了奧賽羅人機對弈系統(tǒng)，因為在1988年擊敗了國際象棋世界冠軍而名噪一時。 李開復(fù)同時還是美國電氣電子工程協(xié)會的院士。常用算法&數(shù)據(jù)結(jié)構(gòu)浙江大學(xué)微軟技術(shù)俱樂部彭鵬ACM競賽競賽中常見的16種題型3,競賽中基本的數(shù)據(jù)結(jié)構(gòu)與算法時空復(fù)雜度的分析0,如何建立一支強隊如何建立一支強隊個人的能力理論（幾何，數(shù)論，動態(tài)規(guī)劃，圖論等）技術(shù)（編程）隊員能力上的互補某論壇，一無聊男yy的中國夢之隊錢文杰（）反應(yīng)奇快，擅長隨機化，貪心,NOI貪心王劉汝佳or吳嘉之 見多識廣,做過的題必別人見過的題多趙爽上海交大的割題手一支強隊需要的角色Leader/Coordinato（協(xié)調(diào)比賽進程）R

16、eader（發(fā)現(xiàn)題目隱諱的涵義）Thinker（邏輯能力強，收集其他隊員意見）Programmer/Debugger（反應(yīng)快 / 穩(wěn)，細心）Helper（協(xié)助比賽，查錯，驗證數(shù)據(jù)等）參考書籍主要參考書籍C+ PrimerC+標(biāo)準(zhǔn)程序庫算法導(dǎo)論算法藝術(shù)與信息學(xué)競賽組合數(shù)學(xué)計算幾何歷屆國家集訓(xùn)隊論文時空復(fù)雜度的分析時間復(fù)雜度的分析空間復(fù)雜度的分析函數(shù)增長和運行時間引用劉汝佳序列和字符串常見題型Dynamic Programming（動態(tài)規(guī)劃）Greedy（貪心）Complete Search（窮舉）Flood Fill （種子填充）常見題型Shortest Path （最短路徑）Recursive

17、 Search Techniques （回溯）Minimum Spanning Tree （最小生成樹）Knapsack（背包）常見題型Computational Geometry（計算幾何）Network Flow（網(wǎng)絡(luò)流）Eulerian Path （歐拉回路）Two-Dimensional Convex Hull （二維凸包）常見題型BigNums （大數(shù)）Heuristic Search（啟發(fā)式搜索）Approximate Search （近似搜索）Ad Hoc Problems（雜題）枚舉法又叫窮舉法，它利用了計算機計算速度快且準(zhǔn)確的特點，是最為樸素和有效的一種算法.不是辦法的辦法但

18、有時卻是最好的辦法Pizza Anyone （ZOJ 1219）題目大意：你需要為你和你的朋友們訂一個皮薩.每個朋友都會告訴你他們想和不想放進皮薩里的東西.你是否能訂一個皮薩，讓他滿足每個人至少一個條件.假設(shè)一共有16種東西可以放進皮薩.是個對計算機很小的數(shù)貪心法（Greedy）矩陣胚理論（詳情請參考算法導(dǎo)論）枚舉法的時間效率很低，貪心法恰恰與其相反.并且貪心法的程序也很好實現(xiàn).無數(shù)論文都指責(zé)貪心法往往得不到問題的最優(yōu)解.絕世高手與普通高手的差距所在.棧和隊列棧:后進先出（LIFO）隊列:先進先出（FIFO）字符串的輸入與輸出或char s100;scanf（%s”,s）; string a（

19、s）;String a; cin a;C+常用頭文件字符串的讀入哪種讀入更快在輸入數(shù)據(jù)達到1M時,cin,cout將比scanf , printf在速度上有明顯的劣勢排序排序的種類：交換排序，選擇排序，插入排序,堆排序希爾排序，快速排序，歸并排序,桶排序用C+實現(xiàn)排序#include數(shù)組asort（ a , a + 5 ）;vector a sort( a. begin() , a. end();并查集并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并問題.并查集的主要操作有合并兩個不相交集合判斷兩個元素是否屬于同一個集合路徑壓縮Parity(ceoi99)有一個01序列，長度=1000

20、000000，現(xiàn)在有n條信息，每條信息的形式是-a b even/odd.表示 第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù).你的任務(wù)是對于這些給定的信息，輸出第一個不正確的信息所在位置-1.信息的數(shù)目不超過 5000.如果信息全部正確,即可以找到一個滿足要求的01序列，那么輸出n.Parity(ceoi99)從整個01序列肯定是無法入手的，因為它的長度高達109.從范圍比較小的n入手.也就是說我們需要對信息進行一些特殊的處理.a b even/odd，那么將元素b指向a-1,邊的權(quán)值是even/odd.下面我們由樣例來說明一下這個處理方法.Parity(ceoi99)(肖天)建立sum數(shù)組，

21、sumi表示從1到i之和是奇(true)還是偶(false),sum0=false.這樣題目 中給的任意問題(a,b)的答案都可以用sumb xor suma-1 表示.開始我們并不知道sum1.n的值，不妨設(shè)為false,這時任意suma,sumb都是獨立的.對 于每對問答(a,b,c),都可以知道sumb xor suma-1=c,由此把sumb和suma-1 聯(lián)系起 來.這步操作可以用并查集完成,對于問答(a,b,c)如果suma-1,sumb不屬于一個集合就 把它們并起來，否則如果suma-1 xor sumb不等于c則說明出現(xiàn)矛盾，輸出總句數(shù)，退出. 對于不出現(xiàn)矛盾的sum數(shù)組,對于

22、每個集合分為兩個部分，我們指定其中一個部分為true,另 一個部分為false,則可以確定sum數(shù)組，利用sumi xor sumi-1 可以求出第i位的數(shù)字， 由于不同集合之間沒有問答出現(xiàn)，所以此數(shù)列是一可行解，證明算法正確.堆(優(yōu)先隊列)優(yōu)點：實現(xiàn)簡單動態(tài)維護一組數(shù)據(jù)中最小(大)的一個數(shù)組維護例題：積水一個長方形網(wǎng)格包含了n*m塊地,每塊地上面有1個長方體.每一個長方形蓋住了一塊地，地的 面積是1平方英寸.相鄰的地上的長方體之間沒有空隙.一場大雨降臨了這個建筑物,在建筑 物的某些區(qū)域有積水產(chǎn)生.給各方格高度，求積水總量分析定義每塊地上的長方體的高度稱為原始高度積滿水時的水面高度稱為積水高度

23、(高于積水高度的水一定會流走，低于積水高度的水一定流不走)積水高度與原始高度之差為積水深度如果一個長方體上不可能有積水,那么它的積水高度就等于它的原始高度.最外圈不能積水，積水高度等于原始高度分析由外而內(nèi)計算.每次選取外圍的格子中積水高度最低的一個格子X,考慮它周圍所有在網(wǎng)格內(nèi) 部的格子y想象不斷的往x和y里注水，但是x的積水高度固定(想象該高度處有一個小孔)，因此 如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度 如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度 每次用堆取出x進行計算,O(mnlogmn).哈希表(Hash)理論上查找速度最快的數(shù)據(jù)結(jié)

24、構(gòu)之一缺點：需要大量的內(nèi)存需要構(gòu)造KeyHash表的實現(xiàn)數(shù)組沖突解決法開散列法閉散列法C+ sgi stl 實現(xiàn)Hash Key的選取數(shù)值：方法一:直接取余數(shù)(一般選取質(zhì)數(shù)M最為除數(shù))方法二:平方取中法，即計算關(guān)鍵值的平方，再取中間r位形成一個大小為的表是多少字符串：int ELFhash( char* key )unsigned int h = 0;while( *key )h = ( h 24;h &= -g;return h % M;方法二:ELFhash函數(shù)方法一:折疊法:即把所有字符的ASCII碼加起來二分搜索樹普通的二分搜索樹時間復(fù)雜度：缺點：容易出現(xiàn)不平衡的情況AVL Tree

25、, Splay tree ,紅黑樹樹堆(Treap)Treap = Tree + heap每次插入/刪除結(jié)點的時候,給結(jié)點隨機分配一個優(yōu)先級，讓Treap關(guān)于優(yōu)先級形成一個堆的 同時，關(guān)于關(guān)鍵碼形成BST跳躍表,B樹跳躍表(Skiplists)線段樹在一類問題中，我們需要經(jīng)常處理可以映射在一個坐標(biāo)軸上的一些固定線段，例如說映射在 OX軸上的線段.由于線段是可以互相覆蓋的,有時需要動態(tài)地取線段的并，例如取得并區(qū)間的 總長度，或者并區(qū)間的個數(shù)等等.一個線段是對應(yīng)于一個區(qū)間的，因此線段樹也可以叫做區(qū)間 樹.Atlantis (ZOJ 1128)一個平面被很多矩形覆蓋,矩形之間會相互疊加.輸出矩形覆蓋

26、的總面積.Atlantis (ZOJ 1128)線段樹矩形切割矩形切割字典樹(Trie )當(dāng)關(guān)鍵字是串的時候，理論上查找最快的數(shù)據(jù)結(jié)構(gòu)定義:保存字符串用的樹型數(shù)據(jù)結(jié)構(gòu)(多叉樹)，其中每個節(jié)點表示一個公共前綴，單詞信息保 存在相應(yīng)的頁節(jié)點里面.給如下幾個單詞，構(gòu)造的單詞樹：An,Ant,All,AllotAlloy,Aloe,Are,Atebe版權(quán)歸浙江大學(xué)ACM領(lǐng)隊徐串所有轉(zhuǎn)載需保留此字樣T9(ZOJ 1038)題目描述:手機有智能英文輸入法，他根據(jù)自己已有的詞匯表，即使你每個數(shù)字只按一次也可 以猜出你要按的是哪個單詞(方法就是從所有可能的串中選出出現(xiàn)概率最高的一個).詞匯表：hell 3he

27、llo 4idea 8next 8super 3按435561是的響應(yīng)顯示iid helhellhello動態(tài)規(guī)劃動態(tài)規(guī)劃的時間效率極高.動態(tài)規(guī)劃的算法簡潔，一般只用邊界和狀態(tài)轉(zhuǎn)移方程就可清晰地表示出進行規(guī)劃的步驟;而因 為有了這些用數(shù)學(xué)語言描述的天然材料，編程也較為方便.最重要的一點：動態(tài)規(guī)劃不單是一種思想，也不單是一類算法,它是思想方法和具體算法的混 合物.摘自徐靜動態(tài)規(guī)劃的算法與實現(xiàn)動態(tài)規(guī)劃無后效性遞推法和記憶化搜索深度優(yōu)先搜索(DFS)按照深度優(yōu)先的順序遍歷狀態(tài)空間，通常用遞歸或者棧來實現(xiàn).void dfs ( state , depth )if ( state =結(jié)束狀態(tài))退出；枚舉

28、所有可行狀態(tài)更新全局變量；dfs( newstate , depth + 1 );還原全局變量寬度優(yōu)先搜索(BFS)如果代價和搜索樹深度成正比，那么可以通過廣度優(yōu)先搜索得到解.由于空間占用大,BFS用 處不是很廣，一般只用在路徑尋找問題中,但是一旦使用，將比深度優(yōu)先搜括看得多 雙向?qū)挾葍?yōu)先搜索深度優(yōu)先和寬度優(yōu)先搜索比較Prime Ring Problem (ZOJ 1457)A ring is compose of n circles as shown in diagram. Put natural number 1, 2,., n into each circle separately, a

29、nd the sum of numbers in two adjacent circles should be a prime.Note: the number of first circle should always be 1. n (0 n 20)while ( !deque.empty() )state = deque0;deque.pop();枚舉所有可行狀態(tài)tempstate =狀態(tài)改變(state);deque.push_back(tempstate);寬度優(yōu)先搜索(BFS)寬度優(yōu)先搜索的框架Winlinez (ZOJ 1591)Now we have a board of 9

30、* 9 grids, on which there are several beads. These beads have only seven colors, we number them 1 - 7. We define the empty grid to be zero. Each turn you can move any bead on the board to the destination where there is a route between them. The route means that the bead can move up, down, left or ri

31、ght to the adjacent empty grid and may go on until it reaches the destination. After the moving, if there are five or more same-colored beads in a line (row, column, diagonal), they will all be eliminated.博弈問題給定一個有向無環(huán)圖(X, F),其中X是一個非空的點集(每個點表示一個位置)，F(xiàn)是一個在集 合X上的函數(shù)，對于集合X中的任意一個元素x,F(x)返回一個集合X的子集，即,F(x)表示

32、了 由一個位置x可以到達的位置.如果F(x)是空集，則稱x是一個結(jié)束位置.現(xiàn)在兩個人在這樣的一個有向圖上玩游戲，首先在一個初始位置x0上放置了一個棋子，然后 他們將按照如下規(guī)則進行游戲：首先由選手I從初始位置x0進行移動.兩個選手交替移動.在一個位置x,選手可以將棋子移到位置y上，其中yex.如果輪到某一個選手移動時棋子處在一個結(jié)束位置，那么這個選手就會因為無法繼續(xù)移動棋 子而被判輸?shù)暨@局游戲.對于給定的有向圖和初始位置，請你判斷出選手I與選手II誰會獲勝.樓天城淺談一類博弈問題的解法 局面Max局面Min局面 終結(jié)局面 局面估價函數(shù) Alpha-Beta 剪枝 A Multiplicatio

33、n Game (ZOJ1893)Stan和Ollie 一起做游戲.游戲的內(nèi)容是將一個整數(shù)p乘上2到9中的任一個數(shù).Stan總是從 p=1開始,然后兩個人交替相乘.在游戲開始前，兩個人訂了一個數(shù)n(1N 最大公約數(shù)最小公倍數(shù) 歐幾里得輾轉(zhuǎn)相除 int gcd ( int a , int b) return b gcd(b,a%b):a;int lcm ( int a , int b) return a / gcd (a , b) * b;篩選法求質(zhì)數(shù)表Eratosthenes(埃拉托色尼)篩選法：每次求出一個新的素數(shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去.在實現(xiàn)的時候,對于一個素數(shù)p, 只需要篩去等就

34、可以了，因為已經(jīng)在q的第一個素因子被找到的時候被篩去了 #define N 100#define M 100int p M , plist = 0;int init()memset( p , 0 , sizeof( p );for ( int i = 2; i = 0 ) i;if ( i 0 )return 0;for ( Min = i + 1 , j = i + 2; j a i & a j a Min )Min = j;swap( a i,a Min );for ( intj=i+1; j =4),那么該圖稱為弦圖 Fishing Net (ZOJ 1015)判斷一個圖是否是弦圖 計算

35、幾何判兩條線斷相交 判點在多邊性內(nèi)部 二維凸包 叉乘OJ是什么Online Judge 的簡稱一種通過網(wǎng)絡(luò)信息交互在線判題的系統(tǒng) 它模擬了 ICPC比賽真實的情況當(dāng)前世界上規(guī)模比較大的OJUVAZOJURALUSACOZhejiang university online judge HYPERLINK 推薦使用： gcc + vi vs2003/vs2005Submission Error -提交使用了不正確的隊名，題號等.No Such Problem -檢查題號有沒有填錯 Compile Error -程序不能通過編譯.Run Time Error -程序運行過程中出現(xiàn)非正常中斷.Memory Limit Exceeded -內(nèi)存使用量超過裁判規(guī)定的上限.Output Limit Exceeded -輸出數(shù)據(jù)量過大，多半死循環(huán)了Time Limit Exceeded -運行超過時限還沒有得到輸出結(jié)果. Wrong Answer -答案錯誤.Presentation Error -輸出格式不對，可檢查空格,回車等等細節(jié)