第三屆全國青少年信息學（計算機）奧林匹克分區(qū)聯賽高中復賽試題

1、第三屆全國青少年信息學（計算機）奧林匹克分區(qū)聯賽復賽試題第三屆全國青少年信息學（計算機）奧林匹克分區(qū)聯賽復賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時）1在 N*N 的棋盤上（1N10） ，填入 1，2，N*N 共 N*N 個數，使得任意兩個相鄰的數之和為素數。 （30%） 例如：當 N=2 時，有： 當 N=4 時，一種可以填寫的方案如下：121615131410 在這里我們約定：左上角的格子里必須填數字 1。 程序要求： 輸入：N； 輸出：如有多種解，則輸出第一行、第一列之和為最小的排列方案；若無解，則輸出“NO！” 。2代數表達式的定義如下： 例如，下面的式子是合法的代數

2、表達式： a；其相鄰數的和為素數的有：1+2，1+4，4+3，2+3acb字母 a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代數表達式：ab; a+a*/(b+c); 程序要求： 輸入：輸入一個字符串，以“；”結束， “；”本身不是代數表達式中字符，僅作為結束） ； 輸出：若表達式正確，則輸出“OK” ；若表達式不正確，則輸出“ERROR” ，及錯誤類型。錯誤類型約定：1 式了中出現不允許的字符；2 括號不配對；3 其它錯誤。 例如：輸入：a+(b); 輸出：OK 例如：輸入：a+(b+c*a; 輸出：ERROR 23騎士游歷： 設有一個 n*m 的棋盤（2n50，2m50）

3、 ，如下圖，在棋盤上左下角有一個中國象棋馬。 （n,m） (1,1)馬走的規(guī)則為：（1）馬走日字；（2）馬只能向右走即如下圖如示： 任務 1：當 n,m 輸入之后，找出一條從左下角到右上角的路徑。 例如，輸入：n=4，m=4 輸出：路徑的格式：(1,1)(2,3)(4,4)。若不存在路徑，則輸出NO 任務 2：當 n，m 給出之后，同時給出馬起點的位置和終點的位置，試找出從起點到終點的所有路徑的數目。 例如：（n=10,m=10） ， （1，5） （起點） ， （3，5） （終點）馬(4,4)(1,1) 輸 出：2（即由（1，5）到（3，5）共有 2 條路徑） 輸入格式：n,m,x1,y1,x

4、2,y2 (分別表示 n,m,起點坐標，終點坐標) 輸出格式：路徑數目（若不存在從起點到終點的路徑，輸出 0）第三屆全國青少年信息學（計算機）奧林匹克分區(qū)聯賽第三屆全國青少年信息學（計算機）奧林匹克分區(qū)聯賽復賽測試數據（高中組）復賽測試數據（高中組） 賽區(qū) 學校題號輸入輸出實際輸出得分11N=1NO12N=2 1 2 4 313N=3NO14N=4 1 2 11 12 1 2 11 12 4 15 8 5 4 9 8 5 7 16 3 14 7 10 3 14 6 13 10 9 6 13 16 1515N=5 1 2 3 4 7 1 2 3 4 7 6 5 14 15 16 6 5 14 1

5、5 1613 24 23 8 21 13 24 23 8 2110 19 18 11 20 10 19 18 11 20 9 22 25 12 17 9 22 25 12 17總計=2+6+2+9+11=30 分題號輸入輸出實際輸出得分21a+xError 122(b+c)Ok23a+b(c+a)Error 324(a+(b+c)Error 225a+)b+c(Error 2109876543211 2 3 4 5 6 7 8 9 10總計=5+5+7+7+6=30 分題號任 務 一 31N=9，M=5（1，1）-（3，2）-（5，1）（6，3）-（7，1）-（8，3）-（9，5）（答案不唯一

6、）32N=3，M=3NO 任 務 二 33N=30，M=30（1，15） ， （3，15）234N=30，M=30（1，15） ， （5，15）835N=30，M=30（1，15） ，（10，15）46036N=50，M=50（1，25） ，（40，25）3，323，759，302，857，476總計=8+3+6+6+7+10=40 分NOI 分區(qū)聯賽分區(qū)聯賽 - 1997 年第三屆高中組試題年第三屆高中組試題解析解析注意：解析和源程序均為 OIBH 站長劉汝佳所寫，疏漏在所難免，但至少程序均通過了比賽時使用的測試數據，所以還是可以一看。一.在 N*N 的棋盤上(1=N=10)填入 1,2,.

7、N*N 共 N*N 個數,使得任意兩個相鄰的數之和為素數.(30%)例如,當 N=2 時,有1 24 3其相鄰數的和為素數的有:1+2,1+4,4+3,2+3當 N=4 時,一種可以填寫的方案如下:12 11 1216 15 8513 49 1467 10 3在這里我們約定:左上角的格子里必須放數字 1程序要求:輸入:N輸出:若有多種解,則需輸出第一行,第一列之和均為最小的排列方案;若無解,則輸出NO!分析本題的題意有一點不明確。第一行，第一列之和均為最小。這是不一定能夠達到的要求。這里，我理解成，第一行之和最小的情況下第一列之和最小。典型的搜索問題，我就不多說了。自上而下，自左向右搜索，每次

8、僅檢查與上方，左方（如果存在的話）之和是否為素數。利用數組 used 確定數字是否已經用過。二.代數表達式的定義如下:(30%)代數表達式: 項:因子:字母: 例如,下面式子是合法的代數表達式:a;a+b*(a+c);a*a/(b+c);下列式子是不合法的代數表達式:ab;a+b*(c+d); 因子中無字母 d程序要求:輸入:輸入一個字符串,以;結束,(;本身不是代數表達式中字符,僅作為結束符號)輸出:若表達式正確,則輸出:OK; 若表達式不正確,則輸出ERROR,及錯誤類型錯誤類型約定:1.式子中出現不允許的字符;2.括號不配對;3.其他錯誤例如:輸入 a+(b); 輸出:OK例如:輸入 a

9、+(b+c*a; 輸出 error 2分析個人認為比較好的題目，不難，但是要考慮全面卻不大容易。第一類錯誤好說，可以出現的字符只有(除了最后的;)：a,b,c,+,-.*./,(,)。注意，如果不在末尾的;也是非法的。第二類用棧來實現。自左向右看，遇到左括號就入棧（其實只修改指針就可以了）,右括號就出棧。出棧時棧空，或者最后棧非空都是 error 2第三類情況比較多。例如存在以下子字符串的都是此類錯誤：(緊跟運算符，如 a+(+b)，運算符緊跟)，如 (c/)*b兩個運算符連在一起，如+,-/等。兩個字母連在一起，如 ab字母以后緊跟(,如 a+b(c+d), )以后緊跟字母，如(c-d)a+b兩個括號連在一起，如(),(,), 因為括號只能在作為因子時才能使用。三.騎士游歷:設有一個 n*m 的棋盤(2=n=50,2=m(2,3)-(4,4) 若不存在路徑,則輸出no任務 2:當 N,M 給出之后,同時給出馬起始的位置和終點的位置,試找出從起點到終點的所有路徑的數目.例如:(N=10,M=10),(1,5)(起點),(3,5)(