數(shù)學(xué)思想方法解決NOIP試題的探究

鐘文耀

【摘要】? NOIP是一項(xiàng)全國(guó)性的信息學(xué)競(jìng)賽，其試題主要包含計(jì)算機(jī)編程和算法，運(yùn)用數(shù)學(xué)思想方法可以幫助解答NOIP試題，其中數(shù)形結(jié)合是最重要的數(shù)學(xué)思想方法之一，運(yùn)用數(shù)形結(jié)合分析和解決NOIP試題，可以為教學(xué)提供參考和借鑒。

【關(guān)鍵詞】? 數(shù)學(xué)思想方法 NOIP 數(shù)形結(jié)合

【中圖分類(lèi)號(hào)】? G633.6 ? ? ? ? ? ? ? ? ?? ? 【文獻(xiàn)標(biāo)識(shí)碼】? A 【文章編號(hào)】? 1992-7711（2020）25-139-02

一、研究背景

全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽（National Olympiad in Informatics in Provinces簡(jiǎn)稱(chēng)NOIP）吸引了全國(guó)眾多中學(xué)生參與，NOIP分為普及組和提高組，普及組面向初中學(xué)生，提高組面向高中學(xué)生。二十多年，NOIP促進(jìn)了計(jì)算機(jī)知識(shí)的普及和發(fā)展，為高校輸送了許多有計(jì)算機(jī)特長(zhǎng)的優(yōu)秀學(xué)生，為社會(huì)培養(yǎng)了一批優(yōu)秀的計(jì)算機(jī)人才。

近年來(lái)，學(xué)科知識(shí)競(jìng)賽逐漸被取消或被淡化，但學(xué)科知識(shí)競(jìng)賽對(duì)選拔優(yōu)秀人才，促進(jìn)學(xué)生綜合素質(zhì)的發(fā)展有特殊的作用。信息學(xué)競(jìng)賽是五大學(xué)科競(jìng)賽之一，相比其它學(xué)科的奧林匹克的競(jìng)賽，信息學(xué)競(jìng)賽參與的人數(shù)比較少，影響范圍比較窄。NOIP的試題難度大、要求高，初學(xué)者往往對(duì)試題束手無(wú)策，這是因?yàn)榻忸}需要選手掌握系統(tǒng)的計(jì)算機(jī)科學(xué)知識(shí)，擁有快速編程解題的綜合能力，這對(duì)許多信息技術(shù)教師而言也是一項(xiàng)艱難的挑戰(zhàn)。從NOIP試題分析入手，深挖解題方法，提高教學(xué)效率，對(duì)普及計(jì)算機(jī)科學(xué)有重要的意義和作用。

二、研究依據(jù)

NOIP考察選手掌握計(jì)算機(jī)科學(xué)的基礎(chǔ)知識(shí)及編寫(xiě)程序解決問(wèn)題的能力，其題目經(jīng)常涉及一些數(shù)學(xué)知識(shí)，如奇數(shù)、偶數(shù)、素?cái)?shù)、因子、最大公因數(shù)等，解題需要運(yùn)用數(shù)學(xué)思想方法。NOIP試題以編寫(xiě)程序?yàn)橹?，程序設(shè)計(jì)的過(guò)程包括分析問(wèn)題、建立數(shù)學(xué)模型、設(shè)計(jì)算法、編寫(xiě)程序、調(diào)試程序等五個(gè)步驟，其中建立數(shù)學(xué)模型就是重要的數(shù)學(xué)思想方法之一。建立數(shù)學(xué)模型的實(shí)質(zhì)是對(duì)具體的問(wèn)題進(jìn)行抽象、近似和簡(jiǎn)化，使之表示成一些可以求解的數(shù)學(xué)公式，建立數(shù)學(xué)模型，才能確定算法，然后才能編寫(xiě)程序。

“數(shù)學(xué)思想方法”有俠義和廣義之分，俠義的理解認(rèn)為“數(shù)學(xué)思想方法研究的對(duì)象是數(shù)學(xué)本身的論證、運(yùn)算以及應(yīng)用的思想、方法和手段”，廣義的理解認(rèn)為“除了上述內(nèi)容外，數(shù)學(xué)思想方法研究的對(duì)象還包括數(shù)學(xué)的對(duì)象、性質(zhì)、特征、作用及其產(chǎn)生發(fā)展的規(guī)律”。中學(xué)數(shù)學(xué)包含著較多的數(shù)學(xué)思想方法，其中函數(shù)和方程、數(shù)形結(jié)合、配方法、圖像法等，其中數(shù)形結(jié)合是最重要的數(shù)學(xué)思想方法之一。數(shù)形結(jié)合是根據(jù)數(shù)量與圖形之間的對(duì)應(yīng)關(guān)系，將抽象的數(shù)量與直觀的圖形相互轉(zhuǎn)化，使復(fù)雜的問(wèn)題具體化、形象化、簡(jiǎn)單化。

三、數(shù)形結(jié)合的運(yùn)用

在數(shù)形結(jié)合的思想方法中，數(shù)包括數(shù)值、方程、函數(shù)、代數(shù)式和不等式，形包括圖形、圖表和圖象。通過(guò)畫(huà)數(shù)軸，或者建立平面直角坐標(biāo)系建立數(shù)與形的對(duì)應(yīng)關(guān)系，這是最常見(jiàn)的數(shù)形結(jié)合的運(yùn)用。

1.單循環(huán)程序結(jié)構(gòu)

循環(huán)結(jié)構(gòu)的執(zhí)行過(guò)程，可借助數(shù)軸來(lái)表示循環(huán)初值、終值和步長(zhǎng)，例如for i=1 to 5 step 1（變量i從1到5的遞增，每一步增加1）可以用圖1的數(shù)軸表示。

2.簡(jiǎn)單雙循環(huán)程序結(jié)構(gòu)

在兩重循環(huán)中，建立平面直角坐標(biāo)系，將兩個(gè)變量分別表示橫坐標(biāo)和縱坐標(biāo)上的值，并描出對(duì)應(yīng)的點(diǎn)，按數(shù)值變化過(guò)程連線和用箭頭標(biāo)明順序，例如for i=1 to 4 for j=1 to 3（變量i從1到4遞增，每一步增加1，同時(shí)變量j隨i遞增，j從1到3的遞增，每一步增加1）可以用圖2的坐標(biāo)系表示。

3.復(fù)雜雙循環(huán)程序結(jié)構(gòu)

循環(huán)變量的初值或終值需要根據(jù)上一層循環(huán)變量的值來(lái)確定，例如for i=1 to 4 for j=i to 4（變量i從1到4，同時(shí)變量j從i到4）用圖3的坐標(biāo)系表示。

用數(shù)軸和直角坐標(biāo)的圖形來(lái)表示程序執(zhí)行循環(huán)的過(guò)程，讓抽象的程序變得直觀和具體，可以加深了對(duì)程序執(zhí)行過(guò)程的理解，對(duì)問(wèn)題的解決提供了工具。

4、最短路徑問(wèn)題

數(shù)形結(jié)合的思想方法，不僅可以用在程序的循環(huán)分析中，也可以用在求最短路徑的算法分析上。標(biāo)號(hào)法是一種形象直觀的求最短路徑的算法，用數(shù)軸上的點(diǎn)表示圖的頂點(diǎn)，用數(shù)值表示邊的權(quán)值。

例1（NOIP2008普及組初賽）有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為

分析：求最短路徑的方法有很多，而標(biāo)號(hào)法是一種非常直觀的算法。在初中數(shù)學(xué)中，我們經(jīng)常用數(shù)軸上的點(diǎn)來(lái)表示位置，用兩點(diǎn)之間的距離是數(shù)軸上數(shù)值的差。這就是用到了數(shù)形結(jié)合的數(shù)學(xué)思想方法。同樣我們也可以用一個(gè)數(shù)軸來(lái)表示城市，為了方便表示用C1、C2、C3、C4、C5、C6分別表示這6個(gè)城市，解題的過(guò)程如下：

（1）以城市1為0點(diǎn)，展開(kāi)與其相鄰的點(diǎn)，并在數(shù)軸中標(biāo)出。

（2）因?yàn)镃4離起點(diǎn)C1最近，再確定C4點(diǎn)為當(dāng)前展開(kāi)點(diǎn)，展開(kāi)與C4想連的C2'、C3'、C5'和C6。

（3）由數(shù)軸可見(jiàn)，C3與C3'點(diǎn)相比，C3離原點(diǎn)近，因而保留C3，刪除C3'，相應(yīng)的，C2、C2'點(diǎn)保留C2點(diǎn)，C5、C5'保留C5，C6、C6'保留C6'，得到下圖：

（4）此時(shí)再以離原點(diǎn)最近的未展開(kāi)的C2，處理后，以此類(lèi)推展開(kāi)C3、C5，處理后得到最后結(jié)果：

由圖可以得出結(jié)論：C4、C2、C3、C5、C6就是C1到它們的最短路徑。這些路徑不是經(jīng)過(guò)了所有城市，而是只經(jīng)過(guò)了其中的若干城市，而且到每一個(gè)城市的那條道路不一定相同，至于經(jīng)過(guò)哪些城市，則可以記錄上述過(guò)程。由此，可以知道C1到C6的最短距離為7。

總之，借助數(shù)形結(jié)合的方法可以分析和解決NOIP試題中的程序或算法問(wèn)題，這是借助數(shù)學(xué)工具解決實(shí)際問(wèn)題的運(yùn)用，同時(shí)也是數(shù)學(xué)思想方法的運(yùn)用。這有助于學(xué)生理解、分析、解決NOIP試題，為NOIP教學(xué)提供了借鑒和參考。

[ 參? 考? 文? 獻(xiàn) ]

[1]方文祺.青少年信息學(xué)奧林匹克出擊競(jìng)賽輔導(dǎo)（第二版）[M].天津：南開(kāi)大學(xué)出版社，2007：1

[2]周全英，徐南昌.數(shù)學(xué)思想方法選講[M].南京：南京大學(xué)出版社，1991：1

[3]顧建東.程序設(shè)計(jì)教學(xué)中的數(shù)學(xué)造[J].中學(xué)教學(xué)參考，2009.12：127