noi2004選拔賽試卷

《noi2004選拔賽試卷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、NOI’2004福建省選手選拔賽試卷考生須知*若試卷中試題字跡不清，考生可以在審題時舉手請求解釋，由考務(wù)人員加以說明。涉及題意理解問題，則不得提問且考務(wù)人員不予解答。*考生上機編程時應(yīng)在指定目錄下工作，并請每隔5分鐘存盤一次。發(fā)生機器故障時由考務(wù)人員確認補給修復(fù)時間，且最長不超過10分鐘。*對考生答題測試有嚴(yán)格時間限制，若超時則該測試項判為0分?？忌鷳?yīng)注意優(yōu)化算法。*考生應(yīng)嚴(yán)格遵守考場規(guī)則，不得違紀(jì)。*考試時間為8時30分至12時，計210分鐘（其中30分鐘為審題時間）。試卷滿分為100分試題一、猜數(shù)游戲(本題滿分30分)?問題描述：猜數(shù)游戲是一個古老的智力游戲。一

2、個游戲者A首先想出一個數(shù)x（1￡x￡n），讓另一個游戲者B來猜?，F(xiàn)在由你扮演游戲者B，用盡可能少的次數(shù)猜出x，并且你所猜的數(shù)中大于x的數(shù)不能超過m個。為了更全面測試你的程序的性能，游戲者A可能會想出多個不同的數(shù)，讓你來猜。你必須依次猜出每一個數(shù)。?交互方式：本題是一道交互式題目，你的程序應(yīng)當(dāng)和測試庫進行交互，而不得訪問任何文件。測試庫提供兩個函數(shù)：Init，Ask，它們的作用和用法如下：?Init(m,n)必須首先調(diào)用，用它來獲得正整數(shù)m,n的值，并且讀入第一個待猜的數(shù)。(1￡m￡n，1￡n￡10000)。?Ask(num)的作用是詢問。其中1￡num￡n。表示詢問

3、num是否是A所想的x。若函數(shù)返回0，表示num=x；若函數(shù)返回-1，表示numx。當(dāng)num=x時，測試庫會自動讀入下一個待猜的數(shù)，如果所有的數(shù)都已經(jīng)被猜出，測試庫會自動終止你的程序，切記你的程序不得自行終止。當(dāng)num>x的次數(shù)超過m次，或者出現(xiàn)num>n，num<1的情況，程序?qū)划惓＝K止。對于每一個待猜的數(shù)，調(diào)用Ask函數(shù)的次數(shù)不能超過50次。?一個成功交互的例子：函數(shù)調(diào)用返回值說明Init(m,n)m=2,n=31￡x￡3，所猜的數(shù)中大于x的數(shù)不能超過2Ask(3)13>x，所猜的數(shù)大于x次數(shù)：1次Ask(1)-11

4、(2)02=x，猜數(shù)成功。猜數(shù)次數(shù)=3，自動讀入下一個待猜的數(shù)Ask(3)13>x，所猜的數(shù)大于x次數(shù)：1次Ask(2)12>x，所猜的數(shù)大于x次數(shù)：2次Ask(1)01=x，猜數(shù)成功。猜數(shù)次數(shù)=3，程序自動結(jié)束?對Pascal程序員的提示：你的程序應(yīng)當(dāng)使用下列語句引用測試庫：usesmylib;測試庫提供的函數(shù)/過程原型為：procedureInit(varm,n:integer);functionAsk(num:integer):integer;?對C/C++程序員的提示：你應(yīng)當(dāng)建立一個工程，把文件mylib.obj包含進來，然后在程序頭加上一行：#includ

5、e“mylib.h”測試庫提供的函數(shù)原型為：voidInit(int*m,int*n);intAsk(intnum);?評分方法：如果你的程序有下列情況之一，得0分：?訪問了任何文件(包括臨時文件)或者自行終止；?非法調(diào)用庫函數(shù)；?讓測試庫異常退出。否則，每個測試點你的得分將按照本組中猜數(shù)次數(shù)最多的一那個數(shù)據(jù)來評分：1.如果你的猜數(shù)次數(shù)小于或等于我們提供的參考次數(shù)，你將得到100%的分?jǐn)?shù)。2.如果你的猜數(shù)次數(shù)等于參考次數(shù)+1，你將得到50%的分?jǐn)?shù)。3.否則你將得到30%的分?jǐn)?shù)。?如何測試程序：1.在工作目錄下建立一個文本文件guess.in，文件第一行包括兩個整數(shù)m

6、，n，其后若干行每行一個整數(shù)，表示待猜的數(shù)。用整數(shù)0表示輸入結(jié)束。2.在工作目錄下建立一個文本文件guess.ans，文件第一行包括兩個整數(shù)，表示本測試的總分s和參考比較次數(shù)t。3.執(zhí)行你的程序，此時測試庫會產(chǎn)生輸出文件guess.log，記錄每個數(shù)的猜數(shù)次數(shù)。4.如果程序正常結(jié)束，你的得分將會顯示在屏幕上。如果程序非法退出，則會在屏幕上顯示:“Error”。輸入文件示例輸出示例guess.inguess.ansYourworstcallingtimes:323210102Yourscore:5試題二、達爾文芯片問題（本題滿分30分）?問題描述：人的大腦里發(fā)生的一切

7、是神奇的，甚至是不可理解的，正是這種神奇使得人具有自我意識。如果用普通硅片、電路、傳感器制成的機器人也能進化，從而能有意識的行動，那么是否有一天，機器人也會變得和人一樣有意識？電腦的硬件也許能像自然界人類和其他生物進化的方式進行進化這一想法，早在上世紀(jì)60年代就被提出，但如何著手是到1998年，因美籍華裔計算機科學(xué)家的一個靈感，才得以突破。這一靈感就是被稱為達爾文芯片的高集成度可編程集成電路塊，簡稱為DPGA。最近，福州大學(xué)計算機學(xué)院計算機神經(jīng)學(xué)研究小組的科學(xué)家們發(fā)現(xiàn)，對達爾文芯片的關(guān)鍵邏輯元進行重組后產(chǎn)生一種奇特的現(xiàn)象。將若干關(guān)鍵邏輯元按照電路板平面坐標(biāo)系2維