目錄
第一章 初等數論1
1.1 概述1
1.1.1 數論的起源1
1.1.2 整除2
1.1.3 最大公約數與最低公倍數2
1.1.4 勾股數3
1.1.5 套用舉例3
1.2 同餘32
1.2.1 同餘的概念32
1.2.2 同餘的性質32
1.2.3 套用舉例32
1.3 素數34
1.3.1 素數的概念34
1.3.2 初步套用35
1.3.3 素數的幾個定理41
1.3.4 綜合套用44
1.4Catalan數52
1.4.1 Catalan數的基本形式52
1.4.2 套用舉例52
1.5 px+qy類命題56
1.5.1 px+qy類的基本命題56
1.5.2 套用舉例58
1.6 中國剩餘定理60
1.7 實數問題的轉換61
1.7.1 基本概念61
1.7.2 套用舉例62
1.8 N進制數及套用73
本章習題80
第二章數學歸納93
2.1 概述93
2.2 級數求和95
2.2.1 級數求和公式95
2.2.2 套用舉例96
2.3 極值定理101
2.3.1 極大極小值定理101
2.3.2 最小數原理101
2.3.3 套用舉例101
2.4 二項式定理及套用103
2.5 數列105
2.5.1 數列的基本概念105
2.5.2 數列的產生方式106
2.5.3 套用舉例106
2.6 計數原理113
2.6.1 配對原理113
2.6.2 容斥原理113
2.6.3 算兩次113
2.6.4 polya計數114
2.6.5 套用舉例114
2.7 遞推關係116
2.7.1 建立遞推關係116
2.7.2 遞推的最佳化120
2.8 表達式處理130
2.8.1 中綴/前綴/後綴表達式132
2.8.2 套用舉例132
2.9 綜合套用143
本章習題174
第三章組合數學及其套用186
3.1 概述186
3.1.1 對應原理（對應原則）186
3.1.2 抽屜原理（鴿巢原理）186
3.1.3 容斥原理186
3.1.4 加法原理187
3.1.5 乘法原理187
3.1.6 套用舉例187
3.2 組合問題193
3.2.1 存在性問題：判斷滿足某種條件的情況或狀態是否存在193
3.2.2 計數性問題：存在多少種滿足某種條件的情況或狀態195
3.2.3 構造性問題：如果已判斷出滿足某種條件的狀態是存在的，那么如何構造出來195
3.2.4 最最佳化問題：找出某種評價標準下的最佳（或較佳）構造方案196
3.3 排列196
3.3.1 排列的概念197
3.3.2 條件排列202
3.3.3 錯位排列202
3.3.4 相異元素可重複排列205
3.3.5 不全相異元素的排列205
3.3.6 圓排列205
3.4 組合206
3.4.1 組合的概念206
3.4.2 可重複組合209
3.4.3 組合公式209
3.4.4 套用舉例210
本章習題227
第四章 母函式及其套用232
4.1 概述232
4.2 普通型母函式233
4.3 指數型母函式236
4.4 套用舉例238
本章習題242
第五章機率的初步套用243
5.1 概述243
5.2等可能事件的機率244
5.3 互斥事件有一個發生的機率245
5.4相互獨立事件同時發生的機率245
5.5 獨立重複試驗246
5.6 套用舉例247
本章習題253
第六章計算幾何258
6.1 概述258
6.2 計算幾何的基礎——矢量259
6.3 計算幾何的基本算法272
6.4 計算幾何的經典算法278
6.4.1 求平面凸包279
6.4.2 求任意多邊形的面積292
6.4.3 求兩個凸多邊形的交集面積294
6.5 離散化296
6.6 套用舉例300
本章習題304
第七章數學建模319
7.1 概述319
7.2 數學建模的基本步驟321
7.3 數學建模的思維特點322
7.4 套用舉例324
本章習題338
第八章 習題解答340
第一章習題解答340
第二章習題解答342
第三章習題解答344
第四章習題解答344
第五章習題解答345
第六章習題解答347
第七章習題解答348
參考文獻349
……
序言
得益於計算機工具的特殊結構，以計算機技術為核心的信息技術現在已在整個社會發展中起到了極其重要的作用。同時，由於信息技術的本質在於不斷創新，因而人們將21世紀稱為信息世紀。根據人類生理特徵，青少年時期正處於思維活躍、充滿各種幻想的黃金年代，孕育著創新的種子和潛能。長期的實踐活動告訴我們，青少年信息學奧林匹克競賽可以讓廣大的青少年淋漓盡致地展現其思維的火花，享受創新帶來的美感。因此，該項活動得到了全國各地廣大青少年朋友的喜愛，越來越多的青少年朋友懷著濃厚的興趣加入到這項活動中來。
從本質上看，計算機學科是一種思維學科，正確地思維訓練可以播種持續創新的優良種子。相對於其他學科的競賽，信息學競賽覆蓋知識面更為寬廣，涉及了數學、數據結構、算法、計算幾何、人工智慧等相關的專業知識，如何在短時間內有效地掌握這些知識的主體，並靈活地套用其解決實際問題，顯然是一個值得認真思考的問題。
知識學習與知識套用基於兩種不同的思維策略，且這兩種策略的統一本質上依賴於選手自身的領悟，但是如何建立兩種策略之間的橋樑、快速地促進選手自身的領悟，顯然是教材以及由其延伸的教學設計與實施過程所應考慮的因素。競賽訓練有別於常規的教學，要在一定的時間內得到良好的效果，需要有一定的技術方法，而不應拘泥於規範。從學習的本質看，各種顯性知識的學習是相對容易的，或者說，只要時間允許，總是可以消化和理解的；然而，隱性知識的學習和掌握卻是較難的。由於隱性知識的學習對競賽和能力的提高起到決定性的作用，因此，僅僅依靠選手自身的感悟，而不從隱性知識的層面重新組織知識體系，有目的地輔助選手自身主動建構，顯然是不能提高競賽能力的。基於上述認識，結合多年來開展青少年信息學競賽活動的經驗，我們組織了一批有長期一線教學經驗的教練員和專家、教授編寫出版了這套《青少年信息學奧林匹克競賽實戰輔導叢書》。
