信息學(xué)奧林匹克競賽國際國內(nèi)分類試題精解

前言

信息技術(shù)對人類社會的發(fā)展產(chǎn)生著深遠的影響，已成為21世紀的一個標志。作為人類集體智慧的結(jié)晶，信息技術(shù)已成為一種時代文化。“計算機的普及要從娃娃抓起”成為“科教興國”的一項重要內(nèi)容。一個國家、一個民族要立足于世界先進民族之林，關(guān)鍵在于擁有高素質(zhì)的人才。綜合國力的競爭，說到底是人才的競爭，培養(yǎng)和造就一大批優(yōu)秀信息技術(shù)人才是當(dāng)務(wù)之急。信息時代，信息技術(shù)已成為現(xiàn)代科學(xué)與技術(shù)的基礎(chǔ)核心，成為人類的“通用智力工具”，在青少年中普及信息技術(shù)教育具有重要和深遠的意義。中國計算機學(xué)會從1984年起，就組織青少年參加信息學(xué)奧林匹克競賽。二十余年，學(xué)會通過組織競賽推動信息技術(shù)普及，促進青少年掌握信息技術(shù)知識，并提高他們的邏輯思維和解決問題的能力。為了培養(yǎng)和造就更多高素質(zhì)的信息技術(shù)人才，中國計算機學(xué)會特別推出一套信息學(xué)奧林匹克系列指導(dǎo)叢書。

內(nèi)容概要

　　《中國計算機學(xué)會信息學(xué)奧林匹克系列叢書》由中國計算機學(xué)會信息學(xué)奧林匹克學(xué)委員會主編，由全國著名專家學(xué)者精心編著而成。　　本書收錄了2003－2004年國際國內(nèi)信息學(xué)奧林匹克的大部分試題。全書對試題進行了類型歸納，并分上、下兩冊出版。上冊包括基礎(chǔ)類試題、數(shù)據(jù)結(jié)構(gòu)類試題、搜索類試題和動態(tài)程序設(shè)計類試題。下冊包括計算幾何類試題和構(gòu)造類試題。全書對每種類型試題做了簡要的介紹，所有的試題都給出了具體的算法分析和相應(yīng)的源代碼?！　”緯冗m合教師輔導(dǎo)學(xué)生使用，也適合參加信息學(xué)奧林匹克競賽的學(xué)生自學(xué)，同時也是大專院校的計算機愛好者學(xué)習(xí)編程的優(yōu)秀參考書。

書籍目錄

第6章　計算幾何類試題　6.1　女神　6.2　多邊形　6.3　降雨量　6.4　最優(yōu)切割　6.5　衛(wèi)星探測　6.6　衛(wèi)星探測　6.7　可視邊界第7章　構(gòu)造類試題　7.1　逆向輸出　7.2　公式編輯器　7.3　零件裝配　7.4　猜牛游戲　7.5　沙丘　7.6　信使　7.7　石器時代　7.8　數(shù)字搜索

章節(jié)摘錄

只要我們能夠設(shè)計出狀態(tài)轉(zhuǎn)移方程f和f'，便可以通過動態(tài)程序設(shè)計方法解出此題。有興趣的讀者不妨試一試。另外，如果變換試題條件的話，則可以拓展出許多開放性問題和探究性問題。例如：·如果要找一個邊平行于坐標軸，且內(nèi)含的點數(shù)（包括兩個給定的對角點）在至多有T個點的前提下盡可能大的矩形，怎么辦？·如果要找的矩形，內(nèi)含點的要求不變，但邊不平行于坐標軸（邊與坐標軸的角度限定在某范圍內(nèi)），怎么辦？·如果要找的是內(nèi)含點數(shù)（包括圓弧上的點）在至少有T個點的前提下盡可能小的一個圓，怎么辦？等等。如果通過對這些相近、相關(guān)問題（即形式不同、本質(zhì)類似的一類問題）的歸納，能揭示出內(nèi)在的聯(lián)系，概括出解決類似問題的一般規(guī)律，并得到高度抽象、概括的模型的話，其意義自然超過解題本身。6.2  多邊形【問題描述】多邊形是由其邊線上及邊線范圍內(nèi)的所有點構(gòu)成的。凸多邊形有如下特征，即連接該多邊形任意兩點的線段是在多邊形的內(nèi)部。本題中的多邊形都是指至少有兩個頂點的凸多邊形，所有的頂點都是整數(shù)坐標，并且各不相同，且沒有三點共線以下“多邊形”指的都是這樣的凸多邊形。假定有兩個多邊形A和B（線段也算是特殊的多邊形，但一個點不是多邊形）。對于多邊形A和B，它們的Minkowski和由（x1+x2，y1+y2）圖形中的所有的點構(gòu)成，其中（xl，y1）是A中的一個點，（x2，y2）是B中的一個點。因此，Minkowski和也是一個多邊形。圖6-9給出了兩個三角形及它們的Minkowski和。插圖：

編輯推薦

《信息學(xué)奧林匹克競賽-國際國內(nèi)分類試題精解(2003-2004)下冊》既適合教師輔導(dǎo)學(xué)生使用，也適合參加信息學(xué)奧林匹克競賽的學(xué)生自學(xué)，同時也是大專院校的計算機愛好者學(xué)習(xí)編程的優(yōu)秀參考書。

圖書封面

評論、評分、閱讀與下載

---

    信息學(xué)奧林匹克競賽國際國內(nèi)分類試題精解 PDF格式下載

---