1
藍橋杯青少年創意編程C++組
賽前集訓教程包
版本-190919
藍橋杯大賽組
2
目錄
第01 課基本數據類型及運算符................................................................................................... 4
1.1、基本數據類型及類型轉換.............................................................................................. 4
1.2、變量與常量.......................................................................................................................5
1.3、字符與字符串...................................................................................................................6
1.4、運算符...............................................................................................................................6
第02 課基本程序結構....................................................................................................................8
2.1、順序結構程序設計...........................................................................................................8
2.2、分支結構程序設計...........................................................................................................9
2.3、循環結構程序設計........................................................................................................ 12
第03 課數組................................................................................................................................. 16
3.1、一維數組及二維數組.................................................................................................... 16
3.2、數組的輸入和輸出........................................................................................................ 18
3.3、數組元素的遍歷............................................................................................................ 20
3.4、數組元素排序................................................................................................................ 20
3.5、字符數組........................................................................................................................ 24
第04 課函數................................................................................................................................. 25
4.1、函數的定義和使用........................................................................................................ 25
4.2、函數的遞歸調用............................................................................................................ 27
3
4.3、變量的作用域：局部變量和全局變量........................................................................27
第05 課簡單算法......................................................................................................................... 28
5.1、進制轉換........................................................................................................................ 28
5.2、模擬算法........................................................................................................................ 29
5.3、枚舉算法........................................................................................................................ 31
第06 課基本數據結構................................................................................................................. 34
6.1、結構體............................................................................................................................ 34
6.2、棧.................................................................................................................................... 35
6.3、隊列................................................................................................................................ 38
6.4、樹.................................................................................................................................... 41
6.5、圖.................................................................................................................................... 47
第07 課指針................................................................................................................................. 48
7.1、概念................................................................................................................................ 48
7.2、引用與運算.................................................................................................................... 49
7.3、指針與數組。................................................................................................................ 50
第08 課基本算法......................................................................................................................... 51
8.1、高精度算法.................................................................................................................... 51
8.2、遞推算法........................................................................................................................ 52
8.3、分治算法........................................................................................................................ 52
8.4、貪心算法........................................................................................................................ 53
8.5、搜索算法（寬度優先搜索、深度優先搜索）............................................................54
8.6、動態規劃算法................................................................................................................ 55
4
第01 課基本數據類型及運算符
1.1、基本數據類型及類型轉換
1. 基本數據類型
整型：int、longlong
int 與long long 的存儲范圍不同，一般情況下我們用int 即可，但是如果題目
中給的數據范圍較大，則選擇使用long long。
布爾型：bool
布爾類型只有兩個值，false 和true。通常用來判斷條件是否成立。
字符型：char
char 類型的變量代表的是單個字符，
例如：
char a;//定義一個字符型變量
cin>>a;//從鍵盤輸入一個字符存入變量a 中。
a=‘*’；//給變量a 賦一個字符’*’。
注意：字符是用單引號來表示’’。
實型：float、double
float 與double 的精確度不同，如果題目沒有特別要求，我們一般使用double，
如果題目明確告訴你使用單精度浮點數數據類型或者float，則要使用float。
2. 數據類型的轉換
5
（1）自動類型轉換（隱式類型轉換）
在不同數據類型的混合運算中，編譯器會隱式地進行數據類型轉換，稱為自動類
型轉換。
自動類型轉換遵循下面的規則：
①若參與運算的數據類型不同，則先轉換成同一類型，然后進行運算。
②轉換按數據長度增加的方向進行，以保證精度不降低。例如int 類型和long
類型運算時，先把int 類型轉成long 類型后再進行運算。
③在賦值運算中，賦值號兩邊的數據類型不相同時，將把右邊表達式值的類
型轉換為左邊變量的類型。如果右邊表達式值的數據類型長度比左邊長時，將丟
失一部分數據。
④在賦值語句中，賦值號兩邊數據類型一定是相兼容的類型，如果等號兩邊
數據類型不兼容，語句在編譯時會報錯。
（2）強制類型轉換（顯示類型轉換）
自動類型轉換不能實現目的時，可以顯式進行類型轉換，稱為強制類型轉換。
一般形式：（數據類型）（表達式）
注意：數據類型加小括號這個整體才是強制類型轉換的符號，后面的表達式可以
加小括號，也可以不加，如果不加的話則遵循就近原則，誰離得強制類型轉換符
號近，系統則強制類型轉換誰。
例：int a;a=(int)1.5;a 的值為1。
1.2、變量與常量
1. 變量
6
變量可以看作是存儲數據的小盒子，一個小盒子里面只能存放一個具體的值，而
且這個值可以改變。
例如：inta= 3；a 就是一個變量
2. 常量
常量是固定值，在程序執行期間不會改變。這些固定的值，又叫做字面量。
常量可以是任何的基本數據類型，可分為整型數字、浮點數字、字符、字符串和
布爾值。
常量就像是常規的變量，只不過常量的值在定義后不能進行修改。
1.3、字符與字符串
1、字符就是單個字符，字符串就是多個字符的集合。
2、單個空白字符和空白字符串是兩個概念，在C++中字符就是單個字符，字符
串是用\0 結尾的，字符和字符串在操作上也不同，復制等等是不一樣的。
字符串簡介：
字符串或串(String)是由數字、字母、下劃線組成的一串字符。一般記為
s="a1a2···an"(n>=0)。它是編程語言中表示文本的數據類型。在程序設計中，
字符串(string)為符號或數值的一個連續序列，如符號串(一串字符)或二進制數字
串(一串二進制數字)。
1.4、運算符
1. 賦值運算符
在C++里面，一個等號“=”代表的是賦值，賦值運算符是將賦值運算符右側
7
的值賦值給左側的變量。
2. 算術運算符
C++中有5 個基本的算術運算符：+（加）-（減）、*（乘）、/（除）、%（取余）。
注意：
① 兩個整數相除，得到的結果值保留整數位
② 取余運算符兩邊的數字必須都得是整數
3. 邏輯運算符
C++中有三個基本的邏輯運算符：&&（與）、||（或）、!（非）
邏輯非：經過邏輯非運算，其結果與原來相反。
邏輯與：若參加運算的某個條件不成立，其結果就不成立，只有當參加運算的所
有條件都成立，其結果才成立。
邏輯或：若參加運算的某個條件成立，其結果就成立，只有當參加運算的所有條
件都不成立，其結果才不成立。
4. 關系運算符
C++中有六個基本的關系運算符：>（大于）、>=（大于等于）、<（小于）、<=
（小于等于）、==（等于）、!=（不等于）
符號意義舉例
> 大于10>5
>= 大于等于10>=10
< 小于10<5
<= 小于等于10<=10
8
== 等于10==5
!= 不等于10!=5
第02 課基本程序結構
2.1、順序結構程序設計
1. 輸入語句：
cin 是C++的輸入語句，與cout 語句一樣，為了敘述方便，常常把由cin 和運
算符”>>”實現輸入的語句稱為輸入語句或cin 語句。
cin 語句的一般格式為：
cin>>變量1>>變量2>>……>>變量n；
與cout 類似，一個cin 語句可以分寫成若干行，如
cin>>a>>b>>c>>d；
也可以寫成
cin>>a;
cin>>b;
cin>>c;
cin>>d;
以上書寫變量值均可以以從鍵盤輸入：1 2 3 4
也可以分多行輸入數據：
1
2 3
9
4
2. 輸出語句：
cout 語句一般格式為：
cout<<項目1<<項目2<<…<<項目n；
功能：
（1）如果項目是表達式，則輸出表達式的值。
（2）如果項目加引號，則輸出引號內的內容。
輸出總結：
cout<<項目1<<項目2<<…<<項目n;
①輸出語句可以輸出多項內容，用<<連接;
②如果輸出項目是"2+3"，則輸出2+3;
③如果輸出項目是2+3，則輸出5;
④如果輸出遇到endl，則換行。
3. 輸出格式控制：
2.2、分支結構程序設計
1. if-else 語句
一般形式：if（表達式）{
語句塊1
}else{
語句塊2
10
}
判斷表達式的邏輯值，當表達式的值非0，則執行語句塊1，當表達式的值為0
的時候，執行語句塊2.
2. switch 語句
switch 語句是多分支選擇語句，也叫開關語句。switch 語句基本格式及框架圖
如下：
switch（表達式）{
case 常量表達式1：[語句組1] [break;]
case 常量表達式2：[語句組2] [break;]
……
case 常量表達式n：[語句組n] [break;]
[default:語句組n+1]
}
功能：首先計算表達式的值，case 后面的常量表達式值逐一與之匹配，當某一
個case 分支中的常量表達式值與之匹配時，則執行該分支后面的語句組，然后
順序執行之后的所有語句，直到遇到break 語句或switch 語句的右括號“}”為
止。如果switch 語句中包含default，default 表示表達式與各分支常量表達式
的值都不匹配時，執行其后面的語句組，通常將default 放在最后。
規則：
（1）合法的switch 語句中的表達式，其取值只能是整型、字符型、布爾型或者
枚舉型
（2）常量表達式是由常量組成的表達式，值的類型與表達式類型相同。
11
（3）任意兩個case 后面的常量表達式值必須各不相同，否則將引起歧義
（4）“語句組”可以使一個語句也可以是一組語句
（5）基本格式中的[ ]表示可選項
3. 分支語句嵌套
在if 語句中又包含一個或多個if 語句稱為if 語句的嵌套。一般形式如下：
if( )
if( )語句1
else 語句2
else
if( )語句3
else 語句4
應當注意if 與else 的配對關系。else 總是與它上面最近的、且未配對的if 配對。
假如寫成：
if( )
if( )語句1
else
if( )語句2
else 語句3
編程序者把第一個else 寫在與第一個if(外層if)同一列上，希望else 與第一個
if 對應，但實際上else 是與第二個if 配對，因為它們相距最近，而且第二個if
并未與任何else 配對。為了避免誤用，最好使每一層內嵌的if 語句都包含else
子句(如本節開頭列出的形式)，這樣if 的數目和else 的數目相同，從內層到外
12
層一一對應，不致出錯。
如果if 與else 的數目不一樣，為實現程序設計者的企圖，可以加花括號來確定
配對關系。例如：
if( )
{
if ( ) 語句1
} //這個語句是上一行if 語句的內嵌if
else 語句2//本行與第一個if 配對
這時{ }限定了內嵌if 語句的范圍，{ }外的else 不會與{ }內的if 配對。關系清楚，
不易出錯。
2.3、循環結構程序設計
1. while 語句
while 死循環結構:
（1）格式：
while(1) {
循環語句;
}
（2）功能
不斷地執行循環體中的語句。
代碼有兩部分：
（1）while(1)
13
（2）花括號{ 循環語句; }
while（表達式）語句的格式與功能
（1）格式
格式1：
while(表達式)
語句;
格式2：
while(表達式){
語句1;
語句2;
……
}
（2）功能
當表達式的值非0 時，不斷地執行循環體中的語句。所以，用while 語句實現的
循環被稱為“當型循環”。
2. for 語句
for 循環格式
格式1:
for(循環變量初始化;循環條件;循環變量增量)
語句;
格式2:
for(循環變量初始化;循環條件;循環變量增量) {
14
語句1;
語句2;
……
}
3. do-while 語句
do{
語句;
}while(表達式);
do-while 循環與while 循環的不同在于：它先執行循環中的語句，然后再判斷
表達式是否為真；如果為真則繼續循環，如果為假，則終止循環。因此，do-while
循環至少要執行一次循環語句。
4、循環結構嵌套
循環的嵌套：
（1）一個循環體內包含著另一個完整的循環結構，就稱為嵌套循環。
（2）內嵌的循環又可以嵌套循環，從而構成多重循環。
（3）三種循環可以相互嵌套。下面都是合法的嵌套。
①while() ②do ③for( ; ;)
{ … { …
{ …
while() do
for( ; ; )
{….. {…
15
{ …
} }while(); }
… ...
…
} }while();
}
④while() ⑤do
⑥for( ; ; )
{ … { …
{ …
do for( ; ;)
while()
{….. {…
{ …
}while(); } }
… ...
…
} }while();
}
注意：
①嵌套的循環控制變量不應同名，以免造成混亂。
②內循環變化快，外循環變化慢。
16
③正確確定循環體。
④循環控制變量與求解的問題掛鉤。
5. break 語句
break 語句的格式和用法
（1）格式
break；
（2）功能
中斷所在循環體，跳出本層循環。
第03 課數組
3.1、一維數組及二維數組
1. 一維數組
申請10 個整數數據類型的變量可以這么寫：int a[10];
int a[10];這行語句代表同時定義了10 個整型變量，就如同10 個“小房子”并
排放在了一起。
那么我們如何使用這些變量呢？
首先，[ ]里的數字表示需要定義的變量的個數，我們這里定義了10 個。這10
個變量分別用a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]、a[8]、a[9]來
表示。
注意：我們要表達數組中某一個元素的格式是：數組名[下標]。在C++中，下標
是從0 開始的，所以一個大小為n 的數組，它的有效下標是0~n-1。
17
0 是下標，a[0]用來存值
數組：由具有相同數據類型的固定數量的元素組成的結構。
例如：int a[10];
double b[10], c[5];
注意：數組定義時的一個關鍵點是數組的長度如何選擇。
數組元素的引用：
(1)下標可以是整型常量或整型表達式；
a[3]=3;
或: int i=3;
a[i]=3;
(2)下標在0~4 之內, 即a[0]~a[4]，
注意：下標不要超范圍
(3)可以單獨針對每個元素賦值，
如：a[4] = 5;
也可以這么用：
int i = 4;
a[i] = 5;
(4)每個元素都是一個變量，數組是“一組變量”，而不是一個變量。
2. 二維數組
二維數組定義的一般格式：
類型名數組名[常量表達式1][常量表達式2];
通常二維數組中的第一維表示行下標，第二維表示列下標。
18
行下標和列下標都是從0 開始的。例如：
int num[4][6];
二維數組的使用與一維數組類似，引用的格式為：
數組名[下標1][下標2]
使用數組時特別注意下標不能越界。
使用二維數組時，需要區分是處理行數據、列數據，還是處理所有數據的行列下
標。
遍歷一個二維數組要使用二重循環。
3.2、數組的輸入和輸出
1. 一維數組的輸入輸出。
利用一層for 循環實現控制下標的變化從而實現對一維數組元素的輸入以及輸
出。
例如：for(int i=0; i<5; ++i){
cin>> a[i];
}
利用循環實現了對一維數組元素的輸入。
2. 二維數組的輸入輸出
二維數組的輸入方式有兩種：
（1）按行輸入：
輸入n 行m 列數據(n、m 均小于100)：
int n, m, a[105][105];
19
cin>> n >> m;
for(int i=1; i<=n; i++){ //行數變化
for(int j=1; j<=m; j++){ //列數變化
cin>> a[i][ j]; //按行輸入
}
}
（2）按列輸入：
輸入n 行m 列數據(n、m 均小于100) ：
int n, m;
cin>> n >> m;
for(int j=1; j<=m; j++){ //列數變化
for(int i=1; i<=n; i++){ //行數變化
cin>> a[i][ j]; //按列輸入
}
}
二維數組的輸出我們只需要掌握住按行輸出即可：
for(int i=1;i<=n;i++){//控制行數
for(int j=1;j<=m;j++){
cout<<a[i][ j]<<" ";
}
cout<<endl;
}
20
3.3、數組元素的遍歷
1. 一維數組的遍歷
將存放在一維數組中的元素依次查看一遍并尋找符合條件的數的過程就是對一
維數組的遍歷。
2. 二維數組的遍歷
二維數組遍歷和一維數組遍歷類似，只不過在遍歷到一維元素時，由于元素是一
維數組還需要遍歷，構成雙重循環。使用雙重循環遍歷二維數組時，外層循環的
次數使用數組元素的行數來進行控制，內層循環的次數是使用每個一維數組的元
素的，也就是二維數組的列數來進行控制。
3.4、數組元素排序
1. 選擇排序
選擇排序：是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據
元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后，再從剩
余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類
推，直到全部待排序的數據元素排完。
例如，6 個數按照從小到大排序：
#include <iostream>
using namespace std;
int main( ) {
int a[6] , i , j , t;
for ( i=0 ; i<6 ; i++)
21
cin>> a[i];
for ( i=0 ; i<5; i++)
for ( j=i+1 ; j<6; j++)
if ( a[i]>a[ j] ) {
t=a[i] ;
a[i]=a[j] ;
a[j]=t ;
}
for ( i=0 ; i<6 ; i++)
cout<< a[i] << " ";
return 0；
}
可推廣到n 個數的選擇排序
2. 冒泡
冒泡排序是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的
元素列，依次比較兩個相鄰的元素，如果他們的順序錯誤就把他們交換過來。走
訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排
序完成。
這個算法的名字由來是因為越大（小）的元素會經由交換慢慢“浮”到數列的頂
端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一
樣，故名“冒泡排序”。
例如：5 個數按照從小到大排序：
22
#include <iostream>
using namespace std;
int main( ) {
int a[5] , i , j , t;
for ( i=0 ; i<5 ; i++)
cin>> a[i];
for ( i=0 ; i<4 ; i++)//比較了四輪
for ( j=0 ; j<4 ; j++)//每輪需要四次比較
if ( a[j]>a[j+1] ) {
t=a[ j] ;
a[j]=a[ j+1] ;
a[j+1]=t ;
}
for ( i=0 ; i!=5 ; i++)
cout<< a[i] << " ";
return 0;
}
可推廣到n 個數的冒泡排序。
3. 桶排序
現在如果需要將輸入的5 個數（范圍是0~9）從小到大排序，該怎么辦
例如輸入2 5 2 1 8，則輸出1 2 2 5 8。首先我們先申請一個大小為10 的數組,int
a[10],編號為a[0]~[9]，并初始化為0。
23
我們現在只需將“小房間的值加1”就可以了，例如：2 出現了，就將a[2]的
值加1。
實現過程：
#include<iostream>
using namespace std;
int main(){
int i,j,t, a[10]={0}; //數組初始化為0
for(i=1;i<=5;i++){ //循環讀入5 個數
cin>>t; //把每一個數讀到變量t 中
a[t]++; // t 所對應小房子中的值增加1
}
for(i=0;i<=9;i++){ //依次判斷0~9 這個10 個小房子
for(j=1;j<=a[i];j++) //出現了幾次就打印幾次
cout<<i<<‘‘;
}
return 0;
}
這種形式的排序就是桶排序，桶排序是要借助于數組來實現的，我們將每個數組
元素看作一個桶，每出現一個數，就在對應編號的桶里面放一個小旗子，最后只
要數一數每個桶里面有幾個小旗子就OK 了。
24
3.5、字符數組
1. 一維字符數組
我們將char 類型定義的數組叫做字符數組，也可以叫它字符串。
字符數組的定義格式如下：char 數組名[元素個數];
cin 和scanf 輸入方式是沒法讀入空格，回車，tab 的，如果我們的字符串中需
要空格，可以用gets()來讀入一行字符串
例如：
char a[10];
gets(a);
cout<<a;
注意：gets()函數可以保留空格，遇到回車結束，需要一個頭文件<cstdio>
字符數組初始化的兩種方式：
char a[10]；
（1）char a[10]={‘c’,’o’,’d’。,’u’,’c’,’k’};//一些單個字符
（2）char a[10]={“coduck"}; //一個字符串
輸入：
char a[10]；
（1）無空格的字符串輸入：
1.利用循環輸入：
for(int i=0;i<=9;i++){
cin>>a[i]; //輸入固定長度為10 的字符數組。
25
}
2.直接cin;
cin>>a; //可以輸入小于等于10 的字符數組
有空格的字符串輸入：
1.gets(a); //gets 函數可以保留空格，遇到回車結束！加頭文件<cstdio>
說明：遇到沒有空格的字符串，可以用cin>>數組名;來輸入。遇到有空格的字
符串，可以用gets(數組名);來輸入
輸出：
cout<<a;
說明：cout 輸出遇到‘\0’結束。
2. 二維字符數組
我們可以借助一個二維數組來存儲多個字符串，這個二維字符數組的每一行都是
一個單獨的字符串。
第04 課函數
4.1、函數的定義和使用
函數定義
前面我們用過了很多C++標準函數，但是這些標準函數并不能滿足所有
需求。當我們需要特定的功能函數時，這就需要我們要學會自定義函數,根據需
求定制想要的功能。
函數定義的語法：
26
返回類型函數名（參數列表）
{
函數體
}
關于函數定義的幾點說明：
（1）自定義函數符合“根據已知計算未知”這一機制，參數列表相當于已知，
是自變量，函數名相當于未知，是因變量。如1.1 參考代2 中max 函數的功能
是找出兩個數的最大數，參數列表中x 相當于已知——自變量，max 函數的值
相當于未知——因變量。
（2）函數名是標識符，一個程序中除了主函數名必須為main 外，其余函數的
名字按照標識符的取名規則命名。
（3）參數列表可以是空的，即無參函數，也可以有多個參數，參數之間用逗號
隔開，不管有沒有參數，函數名后的括號不能省略。參數列表中的每個參數，由
參數類型說明和參數名組成。如max 函數的參數列表數有兩個參數，兩個參數
類型分別是int，int，兩個參數名分別是a，b。
（4）函數體是實現函數功能的語句，除了返回類型是void 的函數，其他函數
的函數體中至少有一條語句是“return 表達式；”用來返回函數的值。執行函
數過程中碰到return 語句，將在執行完return 語句后直接退出函數，不去執行
后面的語句。
（5）返回值的類型一般是前面介紹過的int、double、char 等類型，也可以是
數組。有時函數不需要返回任何值，例如函數可以只描述一些過程用printf 向
屏幕輸出一些內容，這時只需定義的數返回類型為void，并且無須使用return
27
返回函數的值。
函數使用時，函數名必須與函數定義時完全一致，實參與形參個數相等，類型一
致，按順序一一對應。被調用函數必須是已存在的函數，如果調用庫函數，一定
要包含相對應的頭文件。
4.2、函數的遞歸調用
函數之間有三種調用關系：主函數調用其他函數、其他函數互相調用、函數遞歸
調用
C++程序從主函數開始執行，主函數由操作系統調用，主函數可以調用其他函
數，其他函數之間可以互相調用，但不能調用主函數，所有函數是平行的，可以
嵌套調用，但不能嵌套定義。
4.3、變量的作用域：局部變量和全局變量
作用域描述了名稱在文件的多大范圍內可見可使用。C++程序中的變量按作用
域來分，有全局變量和局部變量
全局變量：定義在函數外部沒有被花括號括起來的變量稱為全局變量。
全局變量的作用域是從變量定義的位置開始到文件結束。由于全局變量是在函數
外部定義的，因此對所有函數而言都是外部的，可以在文件中位于全局變量定義
后面的任何函數中使用。
局部變量：定義在函數內部作用域為局部的變量局部變量。函數的形參
和在該函數里定義的變量都被稱為該函數的局部變量。
注意：全局變量和局部變量都有生命周期，變量從被生成到被撤銷的這
28
段時間就稱為變量的生存期, 實際上就是變量占用內存的時間。局部變量的生命
周期是從函數被調用的時刻開始到函數結束返回主函數時結束。而全局變量的生
命周期與程序的生命周期是一樣的。若程序中全局變量與局部變量同名，且同時
有效，則以局部變量優先。即在局部變量的作用范圍內，全局變量不起作用。
第05 課簡單算法
5.1、進制轉換
1、r 進制數(非十進制數)轉化成十進制數：
各種進位制轉換為十進制的方法：分別寫出二進制數、八進制數和十六
進制數的按權展開式，再按十進制運算規則求和得到的值，即為轉換后的十進制
數。
2、十進制數轉化成r 進制數：
分整數和小數兩部分分別轉換處理，最后再求和。
整數部分的轉換方法是：不斷的除以r 取余數，直到商為0，余數從下
到上排列（除r 取余，逆序排列）；小數部分的轉換方法是：不斷乘以r 取整數，
整數從上到下排列（乘r 取整，順序排列）。
3、二進制、八進制、十六進制數間的轉換：
二進制、八進制、十六進制之間的對應規則如下：每3 位二進制對應1
位八進制數；每4 位二進制對應1 位十六進制數。
（1）二進制轉化成八(十六)進制：分為如下三個步驟
整數部分：小數點為基準從右向左按三(四)位進行分組
29
小數部分：小數點為基準從左向右按三(四)位進行分組
不足補零
（2）八（十六）進制轉換為二進制
八進制數轉換成二進制數：只需將1 位八進制數轉為3 位二進制數。
十六進制數轉換成二進制數：只需將1 位十六進制數轉為4 位二進制數。
5.2、模擬算法
在我們所解決的題目中，有一類問題是模擬一個游戲的對弈過程，或者模擬一項
任務的操作過程，進行統計計分，判斷輸贏等。這些問題很難建立數學模型用特
定算法解決，一般只能采用“模擬”法。用模擬法解決必須關注以下幾個問題：
審題要仔細，游戲規則不能錯；分析要全面，各種特例不能丟；編程要細心，測
試運行要到位。
例如：
有一天，一只蚱蜢像往常一樣在草地上愉快地跳躍，它發現了一條寫滿了英文字
母的紙帶。蚱蜢只能在元音字母（A、E、I、O、U）間跳躍，一次跳躍所需的能
力是兩個位置的差。紙帶所需的能力值為蚱蜢從紙帶開頭的前一位置根據規則調
到紙帶結尾的后一個位置的過程中能力的最大值。
蚱蜢想知道跳躍紙帶所需能力值（最小）是多少。如下圖所示，紙帶所需能
力值（最小）是4.
【輸入格式】
30
一行一個字符串，字符串場不超過100.
【輸出格式】
一行一個整數，代表（最小）能力值。
【輸入樣例】
KMLPTGFHNBVCDRFGHNMBVXWSQFDCVBNHTJKLPMNFVCKMLPTGFH
NBVCDRFGHNMBVXWSQFDCVBNHTJKLPMNFVC
【輸出樣例】
85
【問題分析】
從頭到尾枚舉紙帶的每一個字母，按照規則模擬蚱蜢在元音字母間跳躍的過程，
打擂臺記錄能力值。
【示例代碼】
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("grasshopper.in","r",stdin);
freopen("grasshopper.out","w",stdout);
string a;
cin>>a;
int ans=0,pre=0;
for(int i=0;i<a.length();i++){
if(a[i]=='A'||a[i]=='E'||a[i]=='I'||a[i]=='O'||a[i]=='U'||a[i]=='Y'){
31
if(ans<=(i+1-pre)){
ans=i+1-pre;
}
pre=i+1;
}
}
if(ans<=a.length()+1-pre){
ans=a.length()+1-pre;
}
cout<<ans<<endl;
return 0;
}
5.3、枚舉算法
計算機的特點之一就是運算速度快，善于重復做一件事?！案F舉”正是基于這一
特點的最古老的算法。它一般是在一時找不出解決問題的更好途徑，即從數學上
找不到求解的公式或規則時，根據問題中的“約束條件”，將解的所有可能情況
一一列舉出來，然后再逐個驗證是否符合整個問題的求解要求，從而求得問題的
可行解或者最優解。
例題：火柴棒等式
【問題描述】
給出n 根火柴棒，可以拼出多少個形如“A+B=C”的等式？
32
等式中的A、B、C 是用火柴棒拼出的整數（若該數非零，則最高位不能是0）。
用火柴棒拼數字0~9 的拼法如下圖所示。
需要注意以下幾點：
（1） 加號與等號各自需要兩根火柴棒。
（2） 如果A ≠ B，則A+B=C 與B+A=C 視為不同的等式（A、B、C 均大
于或等于0）。
（3） n 根火柴棒必須全部用上（n≤24）。
【輸入樣例】
14
【輸出樣例】
2
【樣例說明】
兩個等式分別為：0+1=1 和1+0=1。
【問題分析】
首先，預處理每個數字（0~9）需要用幾根火柴棒，存儲在數組f 中。然后，
窮舉a 和b，算出它們的和c，再判斷下列約束條件是否成立：f （a）+ f （b）
+ f （c）= n-4?，F在的問題是：a 和b 的范圍有多大？可以發現盡量用數字
1 拼成的數比較大，分析可知最多不會超過1111。程序實現時，分別用三個循
環語句預處理好所有兩位數、三位數、四位數構成所需要的火柴棒數量。
【示例代碼】
#include<bits/stdc++.h>
33
using namespace std;
int f[10000];
int main(){
freopen("matches.in","r",stdin);
freopen("matches.out","w",stdout);
f[0]=6;f[1]=2;f[2]=5;f[3]=5;f[4]=4;
f[5]=5;f[6]=6;f[7]=3;f[8]=7;f[9]=6;
for(int i=10;i<=99;++i){
f[i]=f[i/10]+f[i%10];
}
for(int i=100;i<=999;++i){
f[i]=f[i/100]+f[i/10%10]+f[i%10];
}
for(int i=1000;i<=9999;++i){
f[i]=f[i/1000]+f[i/100%10]+f[i/10%10]+f[i%10];
}
int n,total=0;
cin>>n;
for(int a=0;a<=1111;++a){
for(int b=0;b<=1111;++b){
int c=a+b;
if(f[a]+f[b]+f[c]==n-4){
34
total++;
}
}
}
cout<<total<<endl;
return 0;
}
第06 課基本數據結構
6.1、結構體
1、結構體的定義：
在存儲和處理大批量數據時，一般會使用數組來實現，但是每一個數據
的類型及含義必須一樣。如果需要把不同類型、不同含義的數據當作一個整體來
處理，比如1000 個學生的姓名、性別、年齡、體重、成績等，怎么辦？C++
提供了結構體。
C++中的結構體是由一系列具有相同類型或不同數據類型的數據構成的數
據集合。使用結構體，必須要先聲明一個結構體類型，再定義和使用結構體變量。
結構體類型的聲明格式如下：
struct 類型名{
數據類型1 成員名1；
數據類型2 成員名2；
35
…
}；
也可以把結構體類型聲明和變量定義在一起，格式如下：
struct 類型名{
數據類型1 成員名1；
數據類型2 成員名2；
…
}變量名；
2、結構體變量的使用：
結構體變量具有以下特點：
（1）可以對結構體變量的整體進行操作。例如，swap（a[i],a[ j]）。
（2）可以對結構體變量的成員進行操作。
引用結構體變量中的成員的格式為：結構體變量名.成員名
（3）結構體變量的初始化方法與數組類似。
student s={"xiaomming",'f',16,169};
6.2、棧
1、棧的基本概念：
棧（Stack）是限制在表的一端進行插入和刪除操作的線性表
后進先出LIFO（Last In First Out）
先進后出FILO（First In Last Out）
棧頂（Top）：允許進行插入、刪除操作的一端，又陳偉表尾。用棧頂指針（top）
36
來指示棧頂元素。
空棧：當表中沒有元素時稱為空棧。
2、棧的順序表示與實現：
棧的順序存儲結構簡稱為順序棧，和線性表類似，用一維數組來存儲棧。
3、棧的應用
（1）括號匹配檢查
【題目描述】
假設表達式中允許包含圓括號和方括號兩種括號，其嵌套的順序隨意，如([]())
或[([][])]等為正確的匹配，[(])或([]()或(()))均為錯誤的匹配。本題的任務是檢驗
一個給定的表達式中的括號是否匹配正確。
輸入一個只包含圓括號和方括號的字符串，判斷字符串中的括號是否匹配，
匹配就輸出“OK”，不匹配就輸出“Wrong”。
【輸入】
一行字符，只含有圓括號和方括號，個數小于255
【輸出】
匹配就輸出一行文本“OK“，不匹配就輸出一行文本”Wrong”
【樣例輸入】
[(])
【樣例輸出】
Wrong
【解決思路】
使用棧來實現，首先輸入字符串，遍歷字符串：
37
如果是左括號，進棧；
如果是右括號，跟棧頂數據比較
如果和棧頂的左括號匹配，出棧
如果不匹配，輸出“Wrong"
遍歷結束后，棧中還有括號，輸出“Wrong”；沒有，輸出“Ok”
【代碼示例】
#include<iostream>
#include<string>
using namespace std;
int main()
{
char a[256];
string s;
int i,top;
cin>>s;
top=0;
for(i=0;i<s.size();i++)
{
if(s[i]=='('||s[i]=='[')
{
a[++top]=s[i];;
}
38
if(s[i]==')')
{
if(a[top]=='(') top--;
else
{ top++; }
}
if(s[i]==']')
{
if(a[top]=='[') top--;
else
{ top++; }
}
}
if(top==0) cout<<"OK"<<endl;
else cout<<"Wrong"<<endl;
return 0;
}
（2）鐵軌問題
6.3、隊列
1、隊列定義
隊列是一種先進先出（FIFO）的線性表。只能在線性表的一端進行插入操作，
39
在另一端進行刪除操作。類似與生活中的排隊購票，先來先買，后來后買。
在不斷入隊、出隊的過程中，隊列將會呈現初以下幾種狀態：
隊滿：隊列空間已被全被占用
隊空：隊列中沒有任何元素。
溢出：當隊列滿時，卻還有元素要入隊，就會出現“上溢”；當隊列已
空，卻還要做“出隊”操作，就會出現“下溢”。兩種情況合在一起稱為隊列的
“溢出”。
2、隊列的應用
【題目描述】
假設在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，
依次從男隊和女隊的隊頭上各出一人配成舞伴。規定每個舞曲能有一對跳舞者。
若兩隊初始人數不相同，則較長的那一隊中未配對者等待下一輪舞曲?，F要求寫
一個程序，模擬上述舞伴配對問題。(0<m,n,k<1000)
【輸入】
第一行男士人數m 和女士人數n；
第二行舞曲的數目k。
【輸出】
共k 行，每行兩個數，表示配對舞伴的序號，男士在前，女士在后。
【樣例輸入】
2 4
6
40
【樣例輸出】
1 1
2 2
1 3
2 4
1 1
2 2
【解題思路】
顯然，舞伴配對的順序符合“先進先出”，所以用兩個隊列分別存放男士隊伍和
女士隊伍，然后模擬k 次配對：每次取各隊隊頭元素“配對”輸出，并進行“出
隊”和重新“入隊”的操作。
【代碼示例】
#include<iostream>
using namespace std;
int main(){
int a[10001],b[10001],f1=1,f2=1,r1,r2,k1=1;
int m,n,k;
cin>>m>>n>>k;
r1=m;r2=n;
for(int i=1;i<=m;i++) a[i]=i;
for(int j=1;j<=n;j++) b[j]=j;
while(k1<=k){
41
cout<<a[f1]<<" "<<b[f1]<<endl;
r1++;a[r1]=a[f1];f1++;
r2++;b[r2]=b[f2];f2++;
k1++;
}
return 0;
}
6.4、樹
1、樹
（1）樹的定義
樹(Tree)是n( n≥0 )個結點的有限集,它或為空樹( n=0) ;或為非空樹,對于非空樹
T:
有且僅有一個稱之為根的結點;
除根結點以外的其余結點可分為m(m> 0)個互不相交的有限集T1，T2, ...Tm,
其中每一個集合本身又是一棵樹，并且稱為根的子樹( SubTree )。
（2）基本術語
根——即根結點(沒有前驅)
葉子——即終端結點(沒有后繼)
森林——指m 棵不相交的樹的集合(例如刪除A 后的子樹個數)
有序樹——結點各子樹從左至右有序,不能互換(左為第一)
無序樹——結點各子樹可互換位置。
42
雙親——即上層的那個結點(直接前驅)
孩子——即下層結點的子樹的根(直接后繼)
兄弟——同一雙親下的同層結點(孩子之間互稱兄弟)
堂兄弟——即雙親位于同一層的結點(但并非同一雙親)
祖先——即從根到該結點所經分支的所有結點
子孫——即該結點下層子樹中的任一結點
結點——即樹的數據元素
結點的度——結點掛接的子樹數
結點的層次——從根到該結點的層數(根結點算第一層)
終端結點——即度為0 的結點,即葉子
分支結點——即度不為0 的結點(也稱為內部結點)
樹的度——所有結點度中的最大值
樹的深度——指所有結點中最大的層數
（3）樹的存儲結構
方法1:數組,稱為“父親表示法”
const int m = 10;//樹的結點數
struct node
{
int data, parent;//數據域、指針域
};
node tree[m];
43
優缺點:利用了樹中除根結點外每個結點都有唯一的父結點這個性質。很容易找
到樹根,但找孩子時需要遍歷整個線性表。
方法2:樹型單鏈表結構,稱為“孩子表示法”。每個結點包括一個數據域和一
個指針域(指向若干子結點)。稱為”孩子表示法”。假設樹的度為10 ,樹的結點
僅存放字符,則這棵樹的數據結構定義如下:
const int m = 10; / /樹的度
typedef struct node ;
typedef node *tree;
struct node
{
char data;//數據域
tree child[m];//指針域，指向若干孩子結點
}
tree t;
缺陷:只能從根(父)結點遍歷到子結點,不能從某個子結點返回到它的父結點。但
程序中確實需要從某個結點返回到它的父結點時;就需要在結點中多定義一個指
針變量存放其父結點的信息。這種結構又叫帶逆序的樹型結構。
方法3 :樹型雙鏈表結構,稱為”父親孩子表示法”。每個結點包括一個數據
域和二個指針域(一個指向若干子結點，一個指向父結點)。假設樹的度為10 ,樹
的結點僅存放字符,則這棵樹的數據結構定義如下:
const int m= 10; / /樹的度
typedef struct node;
44
typedef node *tree;//聲明tree 是指向node 的指針類型
struct node
{
char data; // 數據域
tree child[m]; //指針域,指向若干孩子結點
tree father ; / /指針域,指向父親結點
};
tree t;
方法4 :二叉樹型表示法,稱為”孩子兄弟表示法”。也是一種雙鏈表結構,但
每個結點包括一個數據域和二個指針域( 一個指向該結點的第一個孩子結點,一
個指向該結點的下一個兄弟結點)。稱為”孩子兄弟表示法”。假設樹的度為10 ,
樹的結點僅存放字符,則這棵樹的數據結構定義如下:
typedef struct node; ,
typedef node *tree;
struct node
{
char data; //數據域
tree firstchild, next;
//指針域,分別指向第一個孩子結點和下一個兄弟結點};
}；
tree t;
（4）樹的遍歷
45
在應用樹結構解決問題時,往往要求按照某種次序獲得樹中全部結點的信息,這種
操作叫作樹的遍歷。遍歷的方法有多種,常用的有:
A、先序(根)遍歷:先訪問根結點,再從左到右按照先序思想遍歷各棵子樹。如上圖
先序遍歷的結果為：125634789 ;
B、后序(根)遍歷:先從左到右遍歷各棵子樹,再訪問根結點。如上圖后序遍歷的結
果為: 562389741 ;
C、層次遍歷:按層次從小到大逐個訪問,同一層次按照從左到右的次序。如上圖
層次遍歷的結果為: 123456789 ;
D、葉結點遍歷:有時把所有的數據信息都存放在葉結點中,而其余結點都是用來
表示數據之間的某種分支或層次關系,這種情況就用這種方法。如上圖按照這個
思想訪問的結果為: 56389 ;
2、二叉樹
（1）二叉樹的定義
二叉樹( Binary Tree)是n( n≥0 )個結點所構成的集合,它或為空樹( n= 0) ;或為
非空樹,對于非空樹T:
a )有且僅有一個稱之為根的結點;
b )除根結點以外的其余結點分為兩個互不相交的子集T 和T2,分別稱為的左子樹
和右子樹，且和72 本身又都是二叉樹。
（2）二叉樹的基本特點
a)結點的度小于等于2
b)有序樹（子樹有序，不能顛倒）
46
二叉樹的五種不同的形態
（3）二叉樹的性質
性質1：在二叉樹的第i 層上之多有2^(i-1)個結點
性質2：深度為k 的二叉樹至多有2^k-1 個結點
性質3：對于任何一棵二叉樹，若2 度的結點數有n_2 個，則葉子數n_0 必定
為n_2+1（即n_0=n_2+1）
特殊形態的二叉樹
a)滿二叉樹：一顆深度為k 且有2^k-1 個結點的二叉樹。
b)完全二叉樹：深度為k 的，有n 個結點的二叉樹，當且僅當其每一個結點都
與深度為k 的滿二叉樹中編號從1 至n 的結點一一對應
性質4：具有n 個結點的完全二叉樹的深度必為[log_2?n ]+1
性質5：對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結點，其左
孩子編號必為2i，其右孩子編號必為2i+1;其雙親的編號為i/2;
（4）二叉樹的順序存儲
實現：按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素
（5）遍歷二叉樹
遍歷定義一一指按某條搜索路線遍訪每個結點且不重復(又稱周游)。
遍歷用途一一它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹
一切運算的基礎和核心。
DLR——先序遍歷,即先根再左再右
47
LDR——中序遍歷,即先左再根再右
LRD——后序遍歷,即先左再右再根
6.5、圖
1、圖的相關概念
（1）圖是由一個頂點的集合V 和一個頂點間關系的集合E 組成:記為G=(V,E)
V :頂點的有限非空集合。
E :頂點間關系的有限集合(邊集)。
存在一個結點v，可能含有多個前驅結點和后繼結點。
（2）圖中頂點之間的連線若沒有方向,則稱這條連線為邊,稱該圖為無向圖。
（3）圖中頂點之間的連線若有方向,則稱這條連線為弧,則稱該圖為有向圖。
（4）完全圖稠密圖稀疏圖
在一個無向圖中,如果任意兩頂點都有一條直接邊相連接,則稱該圖為無向完
全圖。一個含有n 個頂點的無向完全圖中，n(n-1)/2 條邊。
在一個有向圖中,如果任意兩頂點之間都有方向互為相反的兩條弧相連接,則
稱該圖為有向完全圖。在一個含有n 個頂點的有向完全圖中，n(n-1)條邊。
若一個圖接近完全圖,稱為稠密圖。邊數很少的圖被稱為稀疏圖。
（5）度
a)頂點的度( degree )是指依附于某頂點v 的邊數,通常記為TD(v)
結論:圖中所有頂點的度=邊數的兩倍
b)出度入度
對有向圖來說
48
頂點的出度:以頂點v 為始點的弧的數目,記為OD(v)。頂點的入度:以頂點v 為終
點的弧的數目,記為ID(v)。頂點的度: TD(v)=ID(v) + OD(v).
（6）權網絡
與邊有關的數據信息稱為權
邊上帶權的圖稱為網圖或網絡
弧或邊帶權的圖分別稱為有向網或無向網
（7）路徑
簡單路徑：序列中頂點不重復出現的路徑
簡單回路（簡單環）：除第一個頂點與最后一個頂點之外，其他頂點不重復出現
的回路。
2、圖的存儲結構
（1）鄰接矩陣（有向圖，無向圖，網圖分別如何存儲）
（2）鄰接表（了解）
鄰接矩陣：代碼書寫簡單，找鄰接點慢
鄰接表：代碼書寫較復雜，找鄰接點快
第07 課指針
7.1、概念
（1）指針也是一個變量。和普通變量不同的是，指針變量李存儲的數據是一個
內存地址。
（2）指針變量的定義：
49
類型名*指針變量名
int *p;
（3）指針變量賦值
a）先定義變量，再賦值
int a=3,*p;
p=&a;
b）定義變量的同時，進行賦值。
int a=3,*p=&a;
注意：只能用同類型變量的地址進行賦值
7.2、引用與運算
1、指針的引用
引用指針時，首先要理解指針變量與普通變量的區別和對應關系。例如，定義一
個指針變量“int *p;”和一個普通變量“int a;”，關于兩者之間的各種引用方
式對應關系如下：
（1）“p”等同于“&a”,表示的是內存地址
（2）“*p”等同于“a”,表示變量里存儲的實際數據
（3）“*p=3;”等同于“a=3;”，表示變量的賦值方式。
2、指針的運算
如果定義的是局部指針變量，其地址就是隨機的，直接操作會引發不可預測
的錯誤。所以，指針變量一定要初始化后才能引用。
由于指針變量存儲的是內存地址，所以也可以執行加法、減法運算，一般用
50
來配合數組進行尋址操作。
7.3、指針與數組。
在C++中，數組名在一定意義上可以被看成指針?！皵到M的指針”是指整
個數組在內存中的起始地址，“數組元素的指針”是數組中某個元素所占存儲單
元的地址。例如，"int a[10]，*p；p=a；“就表示定義了一個指針p，指向a
數組在內存中的起始地址a[0]。一般可以使用“下標法”訪問數組元素,如a[5]；
也可以使用“地址法”訪問數組元素，因為數組名就代表數組在內存中的起始地
址，也就是a[0]的地址，如a+4 就表示a[4]的地址；當然，也可以通過“指針
法”訪問數組元素，通過數組的指針或者數組元素的指針訪問數組元素,能使目
標程序質量更高，占用內存更少，運行速度更快。
四、函數指針及擴展
程序中需要處理的數據都保存在內存空間，而程序以及函數同樣也保存在內
存空間。C++支持通過函數的人口地址(指針)訪問函數。另一方面，有些函數在
編寫時要調用其他的輔助函數，但是尚未確定，在具體執行時，再為其傳遞輔助
函數的地址。比如排序函數sort(a，a+n，cmp)，其中的比較函數cmp 是根據
需要傳遞給sort 的，就是傳遞了一個函數指針。
函數指針就是指向函數的指針變量，定義格式如下:
類型名(*函數名) (參數);
例如，"int(*f) (int a，int b)；"，規范來說，此處的“函數名”應該稱為“指針
的變量名”。
51
第08 課基本算法
8.1、高精度算法
計算機最初、也是最重要的應用就是數值運算。在編程進行數值運算時,有時
會遇到運算的精度要求特別高,遠遠超過各種數據類型的精度范圍;有時數據又特
別大，遠遠超過各種數據類型的極限值。這種情況下,就需要進行“高精度運算”。
高精度運算首先要處理好數據的接收和存儲問題，其次要處理好運算過程中的
“進位”和“借位”問題。
【題目描述】
輸入n，輸出n!的精確值，n!=1x2x3......xn,1<n<1000
【輸入】
一個整數n
【輸出】
n！的值
【樣例輸入】
2
【問題分析】
假設已經計算好（n-1）!，那么對于求n!，就是用一個整數去乘以一個高精度
數。只要用n 乘以（n-1）!的每一位（從低位開始），同時不斷處理進位。
52
8.2、遞推算法
“遞推”是計算機解題的一種常用方法。利用“遞推法"解題首先要分析歸
納出“遞推關系”。比如經典的斐波那契問題，用f(i)表示第i 項的值，則
f(1)=0,f(2)=1，在n>2 時,,存在遞推關系:f(n)=f(n-1)+f(n-2) 。
在遞推問題模型中，每個數據項都與它前面的若干數據項(或后面的若干數據
項）存在一定的關聯，這種關聯一般是通過一個“遞推關系式”來描述的。求
解問題時，需要從初始的一個或若干個數據項出發，通過遞推關系式逐步推進，
從而推導出最終結果。這種求解問題的方法叫“遞推法”。其中，初始的若干數
據項稱為“遞推邊界”。
解決遞推問題有三個重點:一是建立正確的遞推關系式;二是分析遞推關系式
的性質;三是根據遞推關系式編程求解。
8.3、分治算法
“分治”是一種常用的解題策略。它是將一個難以直接解決的大問題,分解成若
干規模較小的、相互獨立的、相同或類似的子問題，分而治之，再合成得到問
題的解。根據“平衡子問題”的思想，一般會把問題分解成兩個規模相等的子問
題，也就是“二分法”，比如經典的二分查找(由半查找)問題。
例：找偽幣。
【問題描述】
給出16 個一模一樣的硬幣,其中有1 個是偽造的，并且那個傷造的硬幣比真的硬
幣要輕一些，本題的任務是找出這個偽造的硬幣。為了完成這一任務，將提供一
合可用來比較兩組硬幣重量的儀器，可以指導兩組硬幣孰輕孰重。
53
【問題分析】
方法1 窮舉法
依次比較硬幣1 與硬幣2、硬幣3 和硬幣4、硬幣5 和硬幣6……最多通過8 次
比較來判斷偽造幣的存在并找出這個偽幣。
方法2 二分法
把16 個硬幣的情況看成一個大問題。第一步,把這一大問題分成兩個小問題，
隨機選擇8 個硬幣作為第一組(A 組),剩下的8 個硬幣作為第二組(B 組)。第二步，
利用儀器判斷偽幣在A 組還是在B 組中,如果在A 組中則再把A 組中的8 個硬幣
隨機分成2 組，每組4 個再去判斷...這樣,只要(必須)4 次比較一定能找出偽幣。
方法3 三分法
把16 個硬幣分成3 組(A 組5 個、B 組5 個、C 組6 個),利用儀器比較A、B 兩
組，一次就可以判斷出偽幣在A、B 、C 哪一組中。假如在C 組中,則再把C 組
中的6 個分成3 組(2 個、2 個、2 個)，再用儀器比較一次判斷出在哪一組。然
后再比較1 次就能判斷出2 個硬幣中哪個是偽幣。這樣，只要2~3 次比較便能
找出偽幣。
8.4、貪心算法
貪心法的基本思想
貪心法是從問題的某個初始解出發，采用逐步構造最優解的方法，向給定的
目標前進。在每一個局部階段， 都做一個“看上去最優的決策，并期望通過每
一次所做的局部最優選擇產生出一個全局最優解。做出貪心決策的依據稱為“貪
心策略”。要注意的是，貪心策略一旦做出，就不可再更改。
54
與遞推不同的是，貪心嚴格意義上說只是一種策略或方法，而不是算法。推
進的每一步不是依據某一個固定的遞推式，而是做一個當時“看似最佳”的貪心
選擇(操作),不斷將問題歸納為更小的相似子問題。所以，歸納、分析、選擇正確
合適的貪心策略，是解決貪心問題的關鍵。
8.5、搜索算法（寬度優先搜索、深度優先搜索）
1、寬度優先搜索
寬度優先搜索的基本思想
寬度優先搜索（Breadth First Search, BFS），簡稱寬搜，又稱為廣度優先搜
索。它是從初始結點開始，應用產生式規則和控制策略生成第一層結點，同時檢
查目標結點是否在這些生成的結點中。若沒有，再用產生式規則將所有第一層結
點逐一拓展，得到第二層結點，并逐一檢查第二層結點是否包含目標結點。若沒
有，再用產生式規則拓展第二層結點。如此依次拓展，檢查下去，直至發現目標
結點為止。如果拓展完所有結點，都沒有發現目標結點，則問題無解。
在搜索的過程中，寬度優先搜索對于結點是沿著深度的斷層拓展的。如果要
拓展第n+1 層結點，必須先全部拓展完第n 層結點。對于同層結點來說，它們
對于問題的解的價值是相同的。所以，這種搜索方法一定能保證找到最短的解序
列。也就是說，第一個找到的目標結點，一定是應用產生式規則最少的。因此，
寬度優先搜索算法適合求最少步驟或者最短解序列這類最優解問題。
2、深度優先搜索
深度優先搜索(Depth First Search，DFS),簡稱深搜，其狀態“退回一步”的順
序符合“后進先出”的特點，所以采用“?！贝鎯顟B。深搜的空間復雜度較小，
55
因為它只存儲了從初始狀態到當前狀態的條搜索路徑。但是深搜找到的第一個解
不一定是最優解，要找最優解必須搜索整棵“搜索樹”。所以，深搜適用于要求
所有解方案的題目。
深搜可以采用直接遞歸的方法實現，其算法框架如下:
void dfs (dep:integer，參數表);{
自定義參數;
if(當前是目標狀態){
輸出解或者作計數、評價處理;
}else
for(i = 1; i <=狀態的拓展可能數; i++)
if(第i 種狀態拓展可行){
維護自定義參數;
dfs(dep+1,參數表);
}
}
8.6、動態規劃算法
動態規劃是一種將問題實例分解為更小的、相似的子問題,并存儲子問題的解
而避免計算重復的子問題,以解決最優化問題的算法策略。動態規劃實際上就是
一種排除重復計算的算法,更具體的說,就是用空間換取時間。
能采用動態規劃求解的問題的一般要具有3 個性質:
(1)最優化原理:問題的最優解所包含的子問題的解也是最優的
56
(2)無后效性:即某階段狀態一旦確定,就不受這個狀態以后決策的影響。
(3)有重疊子問題:即子問題之間是不獨立的,一個子問題在下一階段決策中可能
被多次使用到。
動態規劃問題的一般解題步驟
1、判斷問題是否具有最優子結構性質,若不具備則不能用動態規劃。
2、把問題分成若干個子問題(分階段)
3、建立狀態轉移方程(遞推公式)。
4、找出邊界條件。
5、將已知邊界值帶入方程。
6、遞推求解。

總結

以上是生活随笔為你收集整理的蓝桥杯青少年创意编程C++组赛前集训教程包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。