原文連結請點這：
一、單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正确答案。）
1、 關于圖靈機下面的說法哪個是正确的：（ D）
A.圖靈機是世界上最早的電子計算機。
B.由于大量使用錄音帶操作，圖靈機運作速度很慢。
C.圖靈機是英國人圖靈發明的，在二戰中為破譯德軍的密碼發揮了重要作用。
D.圖靈機隻是一個理論上的計算模型。
【解析】所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顔色。有一個機器頭在紙帶上移來移去。機器頭有一組内部狀态，還有一些固定的程式。在每個時刻，機器頭都要從目前紙帶上讀入一個方格資訊，然後結合自己的内部狀态查找程式表，根據程式輸出資訊到紙帶方格上，并轉換自己的内部狀态，然後進行移動。
2、關于計算機記憶體下面的說法哪個是正确的：（ B）
A.随機存儲器（RAM）的意思是當程式運作時，每次具體配置設定給程式的記憶體位置是随機而不确定的。
B.1MB記憶體通常是指1024*1024位元組大小的記憶體。
C.計算機記憶體嚴格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。
D.一般記憶體中的資料即使在斷電的情況下也能保留2個小時以上。
【解析】A項： RAM不是位置随機，而是随時通路。所謂“随機存儲”，指的是“當存儲器中的消息被讀取或寫入時，所需要的時間與這段資訊所在的位置無關。”
B項：1MB=1024KB , 1KB=1024 B
C項：計算機記憶體包括嚴格來說包括隻讀存儲器（RAM）、随機存儲器（ROM）和高速緩存（CACHE）。如果不嚴格來說隻包含隻讀存儲器和随機存儲器。
D項：記憶體中的資料斷電立即丢失。
3、關于BIOS下面說法哪個是正确的：（A）
A.BIOS是計算機基本輸入輸出系統軟體的簡稱。
B.BIOS裡包含了鍵盤、滑鼠、聲霸卡、顯示卡、列印機等常用輸入輸出裝置的驅動程式。
C.BIOS一般由作業系統廠商來開發完成。
D.BIOS能提供各種檔案拷貝、複制、删除以及目錄維護等檔案管理功能。
【解析】BIOS是英文”Basic Input Output System”的縮略詞，直譯過來後中文名稱就是”基本輸入輸出系統。是以A對。
它是一組固化到計算機内主機闆上一個ROM晶片上的程式，B錯。
因為是存在主機闆上（硬體）的一個程式，是以跟作業系統沒關系，是電腦生産廠家決定的，C錯。
BIOS主要功能：（1）通電自檢（2）初始化和檢測（3）引導程式。不具備檔案拷貝等功能，D錯。
4、關于CPU下面哪個說法是正确的：（A ）
A.CPU全稱為中央處理器（或中央處理單元）。
B.CPU可以直接運作彙編語言。
C.同樣主頻下，32位的CPU比16位的CPU運作速度快一倍。
D.CPU最早是由Intel公司發明的。
【解析】
A：CPU（central processing unit）全稱中央處理器，
B：CPU不可以直接執行彙編語言，彙編語言雖然是低級語言但也是語言，CPU隻認機器碼，要編譯成以後才可以運作。
C：相比16而言，32位擁有更大的尋址能力，而且能提取比16多一倍的的資料，是以比16位快，更快的執行速度，更大的記憶體管理（隻能說處理字長不同，但速度難說誰快，因為還受到記憶體等其他條件限制）
D：肯定不是intel。是由半導體時代一步一步演化而來，查爾斯巴比其、‘巴丁、傑克.基爾比、泰德.霍夫等人對CPU的誕生做出了巨大貢獻。泰德.霍夫認為是制成第一塊電腦CPU。
5、關于ASCII，下面哪個說法是正确的：（ B）
A.ASCII碼就是鍵盤上所有鍵的唯一編碼。
B.一個ASCII碼使用一個位元組的記憶體空間就能夠存放。
C.最新擴充的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。
D.ASCII碼是英國人主持制定并推廣使用的。
【解析】
Ａ項：ASCII碼和鍵盤沒有對應關系。
B項: ASCII碼是用一個位元組儲存的，八位二進制０～１２７編碼
C項:擴充的ASCII碼用兩個位元組，漢字編碼不是擴充ASCII的内容
D項: ASCII碼是美國标準資訊交換碼。
6、下列軟體中不是計算機作業系統的是： （ Ｄ）
A) Windows B) Linux C) OS/2 D) WPS
【解析】
A項：windows 是微軟的作業系統
B項：Linux 是一款開源的作業系統
C項: OS/2是蘋果的一款作業系統
D項: WPS 是金山公司的一款文字處理系統，模仿微軟的office三件套的
7、關于網際網路，下面的說法哪一個是正确的：（ C）
A.新一代網際網路使用的IPv6标準是IPv5标準的更新與補充。
B.網際網路的入網主機如果有了域名就不再需要IP位址。
C.網際網路的基礎協定為TCP/IP協定。
D.網際網路上所有可下載下傳的軟體及資料資源都是可以合法免費使用的。
【解析】
A項:IPV6是IPV4的更新，IPV5是一個實驗性的資源預留協定。
B項:域名的存在就是為了解決IP不好記的問題，域名會指向一個具體的IP
C項:主要的基礎協定是TCP/IP協定，TCP是傳輸層的檔案傳輸協定，IP是網絡層的網際協定。
D項:網際網路上有盜版軟體，還有共享軟體。
8、關于HTML下面哪種說法是正确的：（ B）
A.HTML實作了文本、圖形、聲音乃至視訊資訊的統一編碼。
B.HTML全稱為超文本标記語言。
C.網上廣泛使用的 Flash動畫都是由HTML編寫的。
D.HTML也是一種進階程式設計語言。
【解析】
A項：文本，圖形，聲音等都是自己各自不同的編碼，沒有統一
B項:HTML（HyperText Make-up Lauguage）即超文本标記語言，是構成網頁文檔的主要語言，
C項:Flash是由軟體公司Adobe做的，開始逐漸退出曆史舞台
D項:HTML是一種标記類語言，腳本類與，不是進階程式設計語言
9、關于程式設計語言，下面哪個說法是正确的：（C）
A.加了注釋的程式一般會比同樣的沒有加注釋的程式運作速度慢。
B.進階語言開發的程式不能使用在低層次的硬體系統如：自控機床或低端手機上。
C.進階語言相對于低級語言更容易實作跨平台的移植。
D.以上說法都不對。
【解析】
A項:注釋會在編譯的時候被忽略掉，不影響程式運作。
B項:進階開發語言可以在低層次的硬體上運作，隻不過是不經常用。
C項:一些進階語言像JAVA等都可以跨平台使用。像.net 誕生之初不能跨平台，但是這幾年的.net core 已經可以跨平台了
10、已知大寫字母A的ASCII編碼為65（10進制），則大寫字母J的10進制ASCII編碼為：（D）
A.71 B) 72 C) 73 D) 以上都不是
【解析】
Ａ是65，B是66，以此類推，J是74，是以選D
11、十進制小數125.125對應的8進制數是（C）
A) 100.1 B) 175.175 C) 175.1 D) 100.175
【解析】
間接法：先把十進制轉換成二進制，再把二進制轉換成八進制
直接法：整數部分：除8取餘。小數部分，乘8取餘。
125/8=15餘5； 15/8=1餘7； 1 /8=0餘1 ； 整數部分：175（反着）
0.125*8=1.000 小數部分1 （正着）
12、有六個元素FEDCBA 從左至右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可能是合法的出棧序列？ （C）
A.EDCFAB B) DECABF C) CDFEBA D) BCDAEF
【解析】
A項：F進棧，E進棧，E出棧，D進棧，D出棧，C進棧，C出棧，F出棧，B進棧，A進棧，A出棧，B出棧。
B項：F進棧，E進棧，D進棧，D出棧，E出棧，C進棧，C出棧，B進棧，A進棧，Ａ出棧，Ｂ出棧,F出棧。
C項：F進棧，E進棧，D進棧，C進棧，C出棧，D出棧，此時棧頂是E，F無法先出棧。C錯。
D:項：F進棧，E進棧，D進棧，C進棧，B進棧，B出棧，C出棧，D出棧，Ａ進棧，A出棧，E出棧,Ｆ出棧。
13、 表達式a*(b+c)-d的字尾表達式是： （B）
A.abcd*± B) abc+d- C) abc+d- D) -+*abcd
【解析】
中綴表達式轉字尾，一共三種方法。①畫二叉樹 ②堆棧法 ③畫括号
主要介紹第二種，規則如下：
（1）如果遇到操作數，我們就直接将其輸出。
（2）如果遇到操作符，則我們将其放入到棧中，遇到左括号時我們也将其放入棧中。
（3）如果遇到一個右括号，則将棧元素彈出，将彈出的操作符輸出直到遇到左括号為止。注意，左括号隻彈出并不輸出。
（4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，從棧中彈出元素直到遇到發現更低優先級的元素(或者棧為空)為止（即把優先級高的彈出）。彈出完這些元素後，才将遇到的操作符壓入到棧中。有一點需要注意，隻有在遇到” ) “的情況下我們才彈出” ( “，其他情況我們都不會彈出” ( “。
（5）如果我們讀到了輸入的末尾，則将棧中所有元素依次彈出。
讀入字元 棧内 棧外 說明
ａ 空 ａ 操作數，直接輸出
＊ ＊ ａ 操作符，入棧
（ ＊（ ａ 左括号，入棧
ｂ ＊（ ａｂ 操作數，直接輸出
＋ ＊（＋ ａｂ 操作符，入棧
ｃ ＊（＋ ａｂｃ 操作數，直接輸出
） ＊ ａｂｃ＋ 遇到右括号，一直輸出直到左括号
－ － ａｂｃ＋＊ 操作符，＊号的優先級比－号高，輸出優先級高的，把優先級低的入棧
ｄ － ａｂｃ＋＊ｄ 操作數，直接輸出
ａｂｃ＋＊ｄ－ 沒有符号，按照順序把棧内符号輸出
14、一個包含n個分支結點（非葉結點）的非空二叉樹，它的葉結點數目最多為：（D）
A) 2n + 1 B) 2n-1 C) n-1 D) n+1
【解析】
根據二叉樹的性質３：對于任何一棵二叉樹，如果其葉結點數為N0(N0表示度為0的點也就是葉子結點)，而度為2的結點為N2，則N0=N2+1。
推算過程如下：
已知樹的分支結點總數為n，（分支結點就是指度為1或者度為2點），則有N1+N2=N;
将N0=N2+1帶入得N1+N0-1=N
移項得：N0=N+1-N1。當N1為0時，N0有最大值為N+1
也可以用特殊值帶入求解。
15、快速排序最壞情況下的算法時間複雜度為： （D）
A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)
【解析】
快排平均時間複雜度O(nlog2n)，最好O(nlog2n)，最壞O(n2)
- 有一個由4000個整數構成的順序表，假定表中的元素已經按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能确定是否存在所查找的元素： （B）
A) 11次 B) 12次 C) 13次 D) 14次
【解析】
首先要記住2^10= 1024
2^11-1=2047, 2^12-1=4095 , 2047<4000<4095,是以為12。
17、排序算法是穩定的意思是關鍵碼相同的記錄排序前後相對位置不發生改變，下列哪種排序算法是不穩定的：（D）
A) 冒泡排序 B) 插入排序 C) 歸并排序 D) 快速排序
【解析】
ABC都是穩定的排序。
A項：冒泡就是把小的元素往前調，比較的是相鄰的兩個元素，交換也是發生在兩個元素之間，即使兩個元素相等，也不會進行交換，是以相同元素的前後順序沒有改變，是一種穩定排序的算法。
B項：插入排序是在一個已經有小序列的基礎上，一次插入一個元素。碰到相等的元素就把想插入的元素插入到相等元素的後面，是以相同元素的前後順序沒有改變，是一種穩定的排序算法。
C項：歸并排序就是把序列有序的分成短序列（最終1個或者2個）。然後把各個有序的短序列合并成有序的長序列。在有1個元素或者2個元素時，1個元素不會交換，2個元素大小相等也可以不交換。短序列合并成長序列過程中，保證兩個元素相等時，把處在前面的序列元素儲存在結果序列的前面，這樣就保證了穩定性。
D項：快排的思想是標明一個基準，比基準小的就往左放，比基準大的就往右放。實際上，在交換a[i]和基準時，很有可能把前面元素的穩定性打亂。例如：5 3 3 4 3 8 9 10 11。如果基準元素5和3交換，就會把元素3的穩定性打亂。是以快速排序是一個不穩定的排序算法。
18、已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？（A）
A) n B) n+1 C) n-1 D) n*(n-1)
【解析】
性質：有n個頂點的有n個頂點的強連通圖最多有n（n-1）條邊，最少有n條邊。
最多的情況：即n個頂點兩兩相連。
最少的情況：即n個頂點圍城一個圈。
19、全國資訊學奧林匹克的官方網站為參與資訊學競賽的老師同學們提供相關的資訊和資源，請問全國資訊學奧林匹克官方網站的網址是：（C）
A) http://www.noi.com/ B) http://www.noi.org/
C) http://www.noi.cn/ D) http://www.xinxixue.com/
【解析】
C項：不做解釋。官網。com結尾的一般表示商業公司。org結尾的一般表示教育組織。
20、在參加NOI系列競賽過程中，下面哪一種行為是 不 被嚴格禁止的：（B）
A.攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。
B.在聯機測試中通過手工計算出可能的答案并在程式裡直接輸出答案來擷取分數。
C.通過網際網路搜尋取得解題思路。
D.在送出的程式中啟動多個程序以提高程式的執行效率。
【解析】
A項：比賽中，有時候會允許帶書寫工具和手表等的。
C項：不會連外網
D項：會造成伺服器當機。
二．問題求解（共2題，每空5分，共計10分）
1．小陳現有2個任務A，B要完成，每個任務分别有若幹步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳隻能專心做某個任務的一個步驟。但是如果願意，他可以在做完手中任務的目前步驟後，切換至另一個任務，從上次此任務第一個未做的步驟繼續。每個任務的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟後，就停工回家吃飯了。當他回來時，隻記得自己已經完成了整個任務A，其他的都忘了。試計算小陳飯前已做的可能的任務步驟序列共有 70 種。
【解析】排列組合
A=a1->a2->a3，
B=b1->b2->b3->b4->b5
從b1開始，而且完成了任務A，b1—a1—a2—a3–， 剩餘四個空，就是從剩餘的空中往裡插入元素即可。
方式1：
可以推論，n個物體要放到m個位置上，并滿足a[1]<a[2]<a[3]…<a[n],可以推論出，a[1]<a[2]<a[3]<…<a[n]<n+1; 實際上就是在n+m-1個位置中選n個位置。
方式2：
b1在第一個位置，其前方沒有任何數，但a1,a2,a3前方可以有數字，就可以了解成，B中的某些任務和a1,a2,a3一共需要占多個空，隻要把B中任務挑選位置放好，剩餘的自然是A的任務。
是以分類讨論
(1)假設完成任務A：隻有1種（順序選擇B剩餘任務）
(2)假設完成任務A和b2。則(a1,a2,a3,b2)四種，已知a1,a2,a3順序不能颠倒，是以用插空法，b2插到a1,a2,
a組成的4個空中，C(4,1)=4種
(3)假設完成任務A和b2,b3。C(5,2)=10種。可以按照方式1，2個物體放到4個位置上，也可也了解，a1,a2,a3,b1,b2一共組成5個位置，從中選出2個位置給b1,b2。剩餘的A隻有一種方法。
(3)假設完成任務A和b2,b3,b4。 C(6,3)=20種
(4)假設完成任務A和b2,b3,b4,b5。C(7,4)=35種
一共1+4+10+20+35=70種
2．有如下的一段程式：
- a=1;
- b=a;
- d=-a;
- e=a+d;
- c=2*d;
- f=b+e-d;
- g=a*f+c;
現在要把這段程式配置設定到若幹台（數量充足）用電纜連接配接的PC上做并行執行。每台PC執行其中的某幾個語句，并可随時通過電纜與其他PC通訊，交換一些中間結果。假設每台PC每機關時間可以執行一個語句，且通訊花費的時間不計。則這段程式最快可以在 5 機關時間内執行完畢。注意：任意中間結果隻有在某台PC上已經得到，才可以被其他PC引用。例如若語句4和6被分别配置設定到兩台PC上執行，則因為語句6需要引用語句4的計算結果，語句6必須在語句4之後執行。
【解析】
需要畫圖，注意引用順序。
a=1
b=a
d=-a
e=a+d
c=2+d
f=b+e-d
g=a*f+c
例如，b的執行需要a，則至少需要1個機關時間；因為要做并行執行是以b和d可以同步完成，e的執行需要a,在第一步已經有值，不需要耗費時間，隻需要計算d到e的時間。
三．閱讀程式寫結果（共4題，每題8分，共計32分）
1．
#include
using namespace std;
int a,b;
int work(int a,int b){
if (a%b)
return work(b,a%b);
return b;
}
int main(){
cin >> a >> b;
cout << work(a,b) << endl;
return 0;
}
輸入：20 12
輸出：4_
【解析】簡單的函數遞歸調用。
if(),括号中表示條件表達式，如果條件表達式成立就執行下面的語句，也就是括号中不為零就繼續。如果a對b取餘的結果不為0，那麼就傳回(b,a%b)。否則傳回b
傳入20，12後，20%12=8，return(12,8)
傳入12，8後，12%8=4，return(8,4)
傳入8，4後，12%4=0，結果為0，return b;
2．
#include
using namespace std;
int main()
{
int a[3],b[3];
int i,j,tmp;
for (i=0;i<3;i++)
cin >> b[i];
for (i=0;i<3;i++)
{
a[i]=0;
for (j=0;j<=i;j++)
{
a[i]+=b[j];
b[a[i]%3]+=a[j];
}
}
tmp=1;
for (i=0;i<3;i++)
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
cout << tmp << endl;
return 0;
}
輸入：2 3 5
輸出：416
【解析】數組加循環
b[a[i]%3] 這個要記住數組的隻是，不論怎樣中括号中是個數字，表示數組的下标，先計算最裡面括号中的。
過程如下：
b[0]=2,b[1]=3,b[2]=5
b[j] a[i]+=b[j]; a[j] a[i]%3 b[a[i]%3]+=a[j];
i=0 j=0 2 2 2 2 b[2]=5+2=7
i=1 j=0 2 2 2 2 b[2]=7+2=9
j=1 3 5 5 2 b[2]=9+5=14
i=2 j=0 2 2 2 2 b[2]=14+2=16
j=1 3 5 5 2 b[2]=16+5=21
j=2 21 26 26 2 b[2]=21+26=47
第二個for循環
a[i] a[i]%10 b[i] b[i]%10 a[i]+b[i] tmp*=a[i]+b[i]
i=0 2 2 2 2 4 4
i=1 5 5 3 3 8 32
i=2 26 6 47 7 13 416
3．
#include
using namespace std;
const int c=2009;
int main()
{
int n,p,s,i,j,t;
cin >> n >> p;
s=0;t=1;
for(i=1;i<=n;i++)
{
t=t*p%c;
for(j=1;j<=i;j++)
s=(s+t)%c;
}
cout << s << endl;
return 0;
}
輸入：11 2
輸出： 782
【解析】
i t j s
1 2 1 2
2 4 1 6
2 10
3 8 1 18
2 26
3 34
4 16 1 50
2 66
3 82
4 98
5 32 1 130
2 162
3 194
4 226
5 258
6 64 1 322
2 386
3 450
4 514
5 578
6 642
7 128 1 770
2 898
3 1026
4 1154
5 1282
6 1410
7 1538
8 256 1 1794
2 41
3 297
4 553
5 809
6 1065
7 1321
8 1577
9 512 1 80
2 592
3 1104
4 1616
5 119
6 631
7 1143
8 1655
9 158
10 1024 1 1182
2 197
3 1221
4 236
5 1260
6 275
7 1299
8 314
9 1338
10 353
11 39 1 392
2 431
3 470
4 509
5 548
6 587
7 626
8 665
9 704
10 743
11 782
可以看出s變化的值每次都是加上t的值。這期間不論s和t誰大于2009，就要變小
4．
#include
using namespace std;
const int maxn=50;
void getnext(char str[])
{
int l=strlen(str),i,j,k,temp;
k=l-2;
while(k>=0&&str[k]>str[k+1]) k–;
i=k+1;
while(i<l&&str[i]>str[k]) i++;
temp=str[k];
str[k]=str[i-1];
str[i-1]=temp;
for(i=l-1;i>k;i–)
for(j=k+1;j<i;j++)
if(str[j]>str[j+1])
{
temp=str[j];
str[j]=str[j+1];
str[j+1]=temp;
}
return ;
}
int main()
{
char a[maxn];
int n;
cin >> a >> n;
while(n>0)
{
getnext(a);
n–;
}
cout << a << endl;
return 0;
}
輸入：NOIP 3
輸出： NPOI
【解析】
變化過程如下（按執行順序）：
n a k str[k] str[k+1] i str[k] str[k+1] a輸出
3 NOIP 2 I O 3 P I NOPI
2 NOPI 2 P O 2 P O NPIO
1 NPOI 2 I P 3 O I NPOI
實際上就是每次傳入四個字母，按照要求把字母進行位置調換。
四．完善程式 (前8空，每空3分，後2空，每空2分，共28分)
1.（最大連續子段和）給出一個數列（元素個數不多于100），數列元素均為負整數、正整數、0。請找出數列中的一個連續子數列，使得這個子數列中包含的所有元素之和最大，在和最大的前提下還要求該子數列包含的元素個數最多，并輸出這個最大和以及該連續子數列中元素的個數。例如數列為4，-5，3，2，4時，輸出9和3；數列為1 2 3 -5 0 7 8時，輸出16和7。
#include
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg;
int main() {
cin >> n;
for (i=1; i<=n; i++)
cin >> a[i]; //4,-5,3,2,4
tmp=0;
ans=0; //結果
len=0; //長
beg= ① ;
for (i=1; i<=n; i++) {
if (tmp+a[i]>ans) { //
ans=tmp+a[i]; //很明顯，ans是用來存儲一段最大的和
len=i-beg;
}
else if ( ② && i-beg>len)
len=i-beg
if (tmp+a[i] ③ ) {
beg= ④ ;
tmp=0;
}
else
⑤ ;
}
cout << ans << ” ” << len << endl;
return 0;
}
【整體思路】
選擇一個新數，如果比原來大，那麼就指派給最大值，如果和原來一樣，原值保留。如果加起來後比原來還小，則抛棄掉此值，同時把 “前面數的和“ 還有 “個數“ 全部重置（和重置為0，個數變為目前的i），其餘情況保留目前值即可。
【①】 0 ； 很明顯，變量初始化，指派為0，送分題
【②】 tmp+a[i]ans 或者 a[i]+tmpans 或者ans==a[i]+tmp ； 已知ans初值為0，根據上個if的條件，判斷的是tmp+a[i]和tmp的大于關系
那麼此空判斷的應該是tmp+a[i]和tmp的等于關系。
【③】 <0 ; 上面的填完了大于和等于的情況，這裡應該填小于的情況，但是不能填ans。因為ans有指派，這裡的意思就是如果出現了負數，
【④】 i； 下方tmp重置為0，是以beg這個時候也是重置，但是重置為i
【⑤】tmp+=a[i] 或者 tmp=temp+a[i] ； 其餘情況把a[i]累加到tmp中，讓tmp在循環中起作用
- (國王放置) 在n*m的棋盤上放置k個國王，要求k個國王互相不攻擊，有多少種不同的放置方法。假設國王放置在第(x,y)格，國王的攻擊的區域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個數n,m,k，輸出答案。題目利用回溯法求解。棋盤行标号為0n-1，列标号為0m-1。
【整體思路】
跟八皇後類型類似，遞歸回溯。
遞歸回溯法兩種結構：
結構1： int Search(int k)
{
for (i=1;i<=算符種數;i++)
if (滿足條件)
{ 儲存結果
if (到目的地) 輸出解;
else Search(k+1);
恢複：儲存結果之前的狀态{回溯一步 }
}
}
結構2： int Search(int k)
{
if (到目的地) 輸出解;
else
for (i=1;i<=算符種數;i++)
if (滿足條件)
{
儲存結果;
Search(k+1);
恢複：儲存結果之前的狀态{回溯一步}
}
}
這個題目采用的結構2的方法，此題需要對遞歸和回溯法有了解。
x-1,y-1 X-1,y X-1,y+1
X,y-1 X,y X,y+1
X+1,y-1 X+1,y x+1,y+1
#include
using namespace std;
int n,m,k,ans;
int hash[5][5]
void work(int x,int y,int tot){ // 函數參數，x和y表示坐标，tot表示國王總數量
int i,j;
if (totk){ //如果檢測到放完了8個國王，數量加1，遞推停止
ans++;
return;
}
do{
while (hash[x][y]){ // 這裡的意思是當hash[x][y]不為0的時候繼續下面的循環，可以猜想，下面的代碼肯定會有讓 hash[x][y] 不為0的。
y++;
if (ym){
x++;
y= ① ;
}
if (xn)
return;
}
for (i=x-1;i<=x+1;i++) //周遊行的左側和右側
if (i>=0&&i<n) //如果沒有到邊界
for (j=y-1;j<=y+1;j++) //周遊列的上下兩側
if (j>=0&&j<m) //如果沒有到邊界
② ;
③ ;
//下面的代碼是回溯過程
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
④ ;
y++;
if (ym){
x++;
y=0;
}
if (x==n)
return;
}
while (1);
}
int main(){
cin >> n >> m >> k; //n和m表示範圍，k表示國王數量
ans=0; //ans 表示多少種方法
memset(hash,0,sizeof(hash));
⑤ ;
cout << ans << endl;
return 0;
}
【①】0；這段while代碼實際上是在周遊hash數組，y到了m後，x增加1，同時y重置為0，下面的x如果到頭了，直接傳回。
【②】 hash[i][j]++ 或者 hash[i][j] = hash[i][j]+1 或者++ hash[i][j] ； 上面的嵌套for循環實際上在标記某個點的八個方向，把這個點進行加1操作，這樣下次周遊的時候就可以認為這個已經通路過了，進而通路别的點。
【③】work(x,y,tot+1) ； 上面表示放置了一個國王，是以這個地方開始放置下一個國王，遞推做法，開始放置下一個國王。
【④】hash[i][j]– 或者 hash[i][j] = hash[i][j]-1 或者– hash[i][j] ； 【解析】後退一步，是以hash[i][j]– 。也可以看出下方的代碼和上面的部分代碼一緻，表示回溯一步之後的下一個點看其是否符号條件。
【⑤】work(0,0,0) ；主函數内，初始化之後，是函數的調用，而且本文定義了一個函數，從來沒用過，這個地方是函數調用。根據後面函數參數猜想，這個地方應該是x和y坐标，還有國王的數量。
![資訊學奧賽入門算法合集——遞歸和分治算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)