出版時間:2010-6 出版社:浙江大學出版社 作者:陳合力//游光輝 頁數(shù):312
Tag標簽:無
內(nèi)容概要
本書是為廣大參加信息學奧林匹克聯(lián)賽的學生和指導老師精心準備的一本書。本書內(nèi)容全面,基本涵蓋了復賽涉及的所有知識點,著重于實用與實戰(zhàn),在算法分析和應用上,簡明扼要,細致清晰,便于學生自學和教師上課;在習題指導上,提供詳細的解題步驟、標程及測試數(shù)據(jù),便于學生上機練習。全書共分為三個模塊,分別為經(jīng)典問題與算法設計、模擬訓練題和模擬訓練題分析及參考程序。
書籍目錄
經(jīng)典問題與算法設計 第1講 時空分析 第2講 排序算法 第3講 線性數(shù)據(jù)結(jié)構(gòu) 第4講 樹型結(jié)構(gòu)的應用 第5講 并查集 第6講 區(qū)間問題 第7講 最小生成樹問題 第8講 最短路徑問題 第9講 分治法 第10講 搜索法 第11講 貪心法 第12講 離散優(yōu)化 第13講 Hash優(yōu)化 第14講 線性動態(tài)規(guī)劃 第15講 區(qū)間型動態(tài)規(guī)劃 第16講 坐標型動態(tài)規(guī)劃 第17講 背包型動態(tài)規(guī)劃 第18講 樹型動態(tài)規(guī)劃模擬訓練題 全國信息學分區(qū)聯(lián)賽模擬試題(一) 全國信息學分區(qū)聯(lián)賽模擬試題(二) 全國信息學分區(qū)聯(lián)賽模擬試題(三) 全國信息學分區(qū)聯(lián)賽模擬試題(四) 全國信息學分區(qū)聯(lián)賽模擬試題(五) 全國信息學分區(qū)聯(lián)賽模擬試題(六) 全國信息學分區(qū)聯(lián)賽模擬試題(七) 全國信息學分區(qū)聯(lián)賽模擬試題(八) 全國信息學分區(qū)聯(lián)賽模擬試題(九) 全國信息學分區(qū)聯(lián)賽模擬試題(十)模擬訓練題分析及參考程序 全國信息學分區(qū)聯(lián)賽模擬試題(一) 全國信息學分區(qū)聯(lián)賽模擬試題(二) 全國信息學分區(qū)聯(lián)賽模擬試題(三) 全國信息學分區(qū)聯(lián)賽模擬試題(四) 全國信息學分區(qū)聯(lián)賽模擬試題(五) 全國信息學分區(qū)聯(lián)賽模擬試題(六) 全國信息學分區(qū)聯(lián)賽模擬試題(七) 全國信息學分區(qū)聯(lián)賽模擬試題(八) 全國信息學分區(qū)聯(lián)賽模擬試題(九) 全國信息學分區(qū)聯(lián)賽模擬試題(十)
章節(jié)摘錄
第1講 時空分析信息學競賽有個特色,它的題目原型與計算機無關(guān),而是與學習、生活息息相關(guān)。拿到題目后,需要把題目的模型轉(zhuǎn)換成能用程序語言描述的算法或數(shù)據(jù)結(jié)構(gòu)。在設計解決問題的方法時,可以采用不同的算法,例如最小生成樹有Prim、Kruskal算法,排序有快排、桶排、插入排序等算法。方法不一樣,程序計算的工作量就不一樣。采用什么樣的方法,才是有效的?評價一個方法的好壞,可以從時間復雜度和空間復雜度來判別。有的方法只需耗時l秒鐘,有的方法卻需耗時10秒鐘;有的方法只需耗費10MB的空間,有的方法卻需耗費1GB的空間。我們認為耗費時間、空問越小,算法越優(yōu)。一、時間復雜度時間復雜度又稱計算復雜度,是指執(zhí)行程序的計算工作量。同一問題,采用不同的算法,程序的計算工作量是不一樣的。衡量一個算法的時間復雜度,可以采用兩種方法:執(zhí)行時間和執(zhí)行運算次數(shù)。執(zhí)行時間,指在計算機上運行程序從開始到結(jié)束所花費的時間。執(zhí)行時間與計算機配置有關(guān),配置越高的機器,運算速度越快,執(zhí)行時間就越少,反之越多。因計算機配置差異太大,這種方法可取性不高。執(zhí)行運算次數(shù)是根據(jù)程序中執(zhí)行指令條數(shù)和語句條數(shù)來度量的,它大致等于計算機執(zhí)行一種簡單操作所需時間與算法中簡單操作次數(shù)的乘積。這種方法不以計算機的配置為依據(jù),而以算法中的操作次數(shù)總耗時為依據(jù),耗時越少,執(zhí)行時間越快;耗時越多,執(zhí)行時間越慢。這種方法已經(jīng)被作為衡量時間復雜度的最有效方法。每年NOl的所有比賽,中國計算機學會(CCF)都會把評測機的詳細配置放在NOl官網(wǎng)上,供選手們根據(jù)算法來預測程序的執(zhí)行時間。……
編輯推薦
《全國青少年信息學競賽培訓教材:復賽》由浙江大學出版社出版。
圖書封面
圖書標簽Tags
無
評論、評分、閱讀與下載