王晨昊

【摘 要】近年來，信息技術(shù)產(chǎn)業(yè)引發(fā)越來越多的關(guān)注。其中包含的一些思想或方法得到人們的重視，值得學(xué)習(xí)與借鑒。此文對(duì)比信息學(xué)中所體現(xiàn)的思想方法與數(shù)學(xué)學(xué)科核心素養(yǎng)的相同之處，以一些經(jīng)典問題作為例論，強(qiáng)調(diào)了信息學(xué)思想與方法在數(shù)學(xué)學(xué)科中的重要性，并最終上升到研究與學(xué)習(xí)方法層面，得出信息學(xué)思想與方法值得學(xué)習(xí)與借鑒的結(jié)論。

【關(guān)鍵詞】條件處理;轉(zhuǎn)化化歸;數(shù)據(jù)分析

中圖分類號(hào)： R197.3 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2019）04-0285-002

DOI：10.19694/j.cnki.issn2095-2457.2019.04.111

0 引言

對(duì)于中學(xué)生而言，與信息技術(shù)接觸最緊密的當(dāng)屬“五大競(jìng)賽”中的信息學(xué)競(jìng)賽。盡管與面向?qū)ο缶幊蹋∣OP）與函數(shù)式編程（FP）等編程范式（programming paradigm）中內(nèi)容有所不同，但信息學(xué)競(jìng)賽在服務(wù)于自己的題目的同時(shí)，也在其它學(xué)科中流露出相似的思想方法與思考過程。這使得許多競(jìng)賽選手回歸課堂后，在其他科目中對(duì)題目的分析與解答上，獲得了很大的提升。在數(shù)學(xué)這個(gè)與信息學(xué)聯(lián)系最為緊密的學(xué)科中，這種影響尤為顯著。

1 對(duì)條件的分類與處理

信息學(xué)競(jìng)賽作為一種將思維方式與解題方法轉(zhuǎn)化為計(jì)算機(jī)語(yǔ)言的競(jìng)賽，邏輯的講求尤為重要。通常，在編寫代碼的過程中均需出現(xiàn)多個(gè)用邏輯連接詞與判斷語(yǔ)句表示的判斷與選擇分支。通過此類分支的選用，結(jié)合題目要求與條件間關(guān)系（即并列關(guān)系，對(duì)應(yīng)關(guān)系，對(duì)立關(guān)系），再加上合適算法的選擇，我們就可以得到一個(gè)“正解”。從簡(jiǎn)單的“A+B Problem”到復(fù)雜的高級(jí)數(shù)據(jù)結(jié)構(gòu)，利用分支結(jié)構(gòu)對(duì)條件間關(guān)系的處理無處不在。

將這種條件分類處理方法類比到數(shù)學(xué)學(xué)科中，將題目所述條件可分析整合為上述三種關(guān)系。一般地，在數(shù)學(xué)學(xué)科中對(duì)前兩種關(guān)系的處理通常歸為一類，即較為常見的分析法和綜合法，進(jìn)而轉(zhuǎn)化問題為對(duì)并列關(guān)系與對(duì)應(yīng)關(guān)系之間優(yōu)先級(jí)（順序結(jié)構(gòu)）的處理;而后一種，數(shù)學(xué)學(xué)科經(jīng)常利用其對(duì)立關(guān)系（非此即彼）來“否定反面來肯定正面”，即反證法。反證法的應(yīng)用十分巧妙，在許多難題，尤其在證明一些P或NP問題去掉某些約束后無法在多項(xiàng)式時(shí)間內(nèi)完成證明或解答（即屬于NPC類問題）中得到了廣泛應(yīng)用。比如，在證明命題“TSP問題在去掉代價(jià)函數(shù)c滿足三角不等式的假設(shè)，則不可能在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)好的近似旅行路線，除非P=NP”[2]時(shí)用到的方法即反證法。在對(duì)條件整合后，我們根據(jù)條件關(guān)系會(huì)更明確地找到解答方向。

因此，信息學(xué)競(jìng)賽對(duì)條件的分類與處理思想在數(shù)學(xué)學(xué)科對(duì)條件的整合與利用中存在著導(dǎo)向作用，這二者間具有很多相似之處。

2 轉(zhuǎn)化與化歸思想

在信息學(xué)中，轉(zhuǎn)化與劃歸思想可謂重中之重。首先，選手們需要從題面（有許多無實(shí)際用處只為增添趣味的內(nèi)容）中過濾出有用的信息，并對(duì)篩選出的信息進(jìn)行分析。例如，權(quán)值是否有實(shí)際意義（是否需要離散化），n、m等代表元的含義，給出的邊是不是有向邊等等。分析后思考其中包含的模型，最后根據(jù)數(shù)據(jù)范圍來決定是否要在時(shí)間或空間上進(jìn)行優(yōu)化，要優(yōu)化哪一部分。下面以一類“線性規(guī)劃”題目為例：

給定n個(gè)實(shí)數(shù)變量與一些線性約束，確定這n個(gè)變量的值，使得某個(gè)線性函數(shù)最大化或最小化。[1]比如下面式子：

Maximum z=x1+2*x2-x3

2*x1+x2+x3≤14

4*x2+2*x2+3*x3≤28

2*x1+5*x2+5*x3≤30

x1，x2，x3≥0

為了方便，一般定義線性規(guī)劃的標(biāo)準(zhǔn)形式為：目標(biāo)函數(shù)最大化的;所有線性約束都為“左邊小于某個(gè)常數(shù)”形式的;所有變量均為非負(fù)的。如上面的式子就是標(biāo)準(zhǔn)形式。

對(duì)于非標(biāo)準(zhǔn)形式線性規(guī)劃問題，如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式呢？如果目標(biāo)函數(shù)是最小化的，目標(biāo)函數(shù)取個(gè)相反數(shù)即可;約束A≥B寫成B≤A;約束A=B拆成兩個(gè)約束A≤B和B≥A（如果左邊有變量則移項(xiàng)到右邊）;而對(duì)于沒有非負(fù)約束的變量xi，拆成兩個(gè)變量xi=（xi`-xi``）。轉(zhuǎn)化為標(biāo)準(zhǔn)線性規(guī)劃后，我們就可以用統(tǒng)一的方法如單純形法求解了。

相似的，如果一個(gè)系統(tǒng)由n個(gè)變量和m個(gè)約束條件組成，形成m個(gè)形如ai-aj≤k的不等式（i，j∈[1，n]，k為常數(shù)），則稱其為差分約束系統(tǒng)?，F(xiàn)需尋找一個(gè)滿足所有約束的a的最大值或最小值。以尋找最大值為例，我們注意到每個(gè)約束可寫成ai+k≥aj（k為常數(shù)）的形式。此種形式讓人想起了最長(zhǎng)路中的轉(zhuǎn)移d[i]+w≥d[j]（其中d[k]，k∈[1，n]表示從初始點(diǎn)出發(fā)到達(dá)點(diǎn)k的路徑最大值，w為點(diǎn)i到點(diǎn)j邊權(quán)）。我們?nèi)魧?duì)于每個(gè)約束建立一條i到j(luò)的邊權(quán)值為a，最終得到一張無向圖則將其轉(zhuǎn)化為點(diǎn)1到點(diǎn)n的最長(zhǎng)路來求解。這是求解關(guān)于一組變量的特殊不等式組的方法。

無論是線性規(guī)劃還是差分約束，在其變形或處理過程中，轉(zhuǎn)化與劃歸思想發(fā)揮了很大作用。

對(duì)應(yīng)到數(shù)學(xué)學(xué)科上來，這兩種核心思想也對(duì)應(yīng)數(shù)學(xué)核心素養(yǎng)——數(shù)學(xué)建模與數(shù)學(xué)抽象。在傳統(tǒng)題目“哥尼斯堡七橋問題”中，這兩種思想得到了完美結(jié)合。

題目敘述：1736年，年僅29歲的數(shù)學(xué)家歐拉來到普魯士的古城哥尼斯堡。普瑞格爾河正好從市中心流過，河中心有兩座小島，島和兩岸之間建筑有七座古橋。現(xiàn)問是否有一走法使得每座橋恰好走過一遍并回到原出發(fā)點(diǎn)。

首先，我們注意到題目并不是用數(shù)學(xué)語(yǔ)言敘述的;對(duì)于用非數(shù)學(xué)語(yǔ)言敘述的題面，我們應(yīng)該先將其轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言并過濾出有用信息。以此題為例，題目描述經(jīng)過整合后可以歸納為，給出一張無向（可相互到達(dá)）聯(lián)通圖，詢問是否存在一筆畫的方法？

其次，對(duì)于這個(gè)略顯復(fù)雜的圖，我們可以將地點(diǎn)抽象為點(diǎn)，而把連接他們的橋看作無向邊，從而忽略無用的信息（如形狀，面積等）就得到了一個(gè)簡(jiǎn)單得多的圖如下。

接下來，我們考慮假設(shè)每座橋都恰好走過一次，那么對(duì)于A、B、C、D四個(gè)頂點(diǎn)中的每一個(gè)頂點(diǎn)，需要從某條邊進(jìn)入，同時(shí)從另一條邊離開。進(jìn)入和離開頂點(diǎn)的次數(shù)是相同的，即每個(gè)頂點(diǎn)有多少條進(jìn)入的邊，就有多少條出去的邊，也就是說，每個(gè)頂點(diǎn)相連的邊是成對(duì)出現(xiàn)的，即每個(gè)頂點(diǎn)的相連邊的數(shù)量必須是偶數(shù)。所以問題至此轉(zhuǎn)換為判斷圖中是否存在連接奇數(shù)條邊的點(diǎn)。若存在連接奇數(shù)條邊的點(diǎn)，那么由上述證明結(jié)果可得，該途中一定沒有符合條件的（歐拉）路徑;反之則至少存在一條。

由于上圖中A、B兩點(diǎn)為連接奇數(shù)條邊（即奇數(shù)度數(shù)）的點(diǎn)，所以上圖中不存在一條符合條件的路徑。

從這個(gè)問題的求解中不難看出，面對(duì)一道題面用非數(shù)學(xué)語(yǔ)言敘述且包含許多無用信息的題，我們應(yīng)先運(yùn)用數(shù)學(xué)抽象方法把問題用數(shù)學(xué)語(yǔ)言敘述;然后對(duì)剩余信息進(jìn)行分析來進(jìn)行數(shù)學(xué)建模，從自己的知識(shí)庫(kù)中尋找相似結(jié)構(gòu)從而確定研究問題的大致方向;再沿大致方向完成已知結(jié)構(gòu)到目標(biāo)形式的轉(zhuǎn)化。在轉(zhuǎn)化過程中需重視二者之間的差異性，通過差異來選取合適的變形方法，最終得到目標(biāo)結(jié)論，該題的解答也就完成了。

3 數(shù)據(jù)處理與運(yùn)算結(jié)合

在信息學(xué)競(jìng)賽中，某些題目需要選手們對(duì)小規(guī)模數(shù)據(jù)暴力求解出的結(jié)果進(jìn)行分析，從而得出不易直接由數(shù)學(xué)推導(dǎo)證明出的結(jié)論。例如下面這道題（HNOI2009）：

題目描述：

我們稱一個(gè)長(zhǎng)度為2n的數(shù)列是有趣的，當(dāng)且僅當(dāng)該數(shù)列滿足以下三個(gè)條件：

（1）它是從1到2n共2n個(gè)整數(shù)的一個(gè)排列{ai};

（2）所有的奇數(shù)項(xiàng)滿足a1

（3）任意相鄰的兩項(xiàng)a2i-1與a2i（1≤i≤n）滿足奇數(shù)項(xiàng)小于偶數(shù)項(xiàng)，即：a2i-1

現(xiàn)在的任務(wù)是：對(duì)于給定的n，請(qǐng)求出有多少個(gè)不同的長(zhǎng)度為2n的有趣的數(shù)列。因?yàn)樽詈蟮拇鸢缚赡芎艽?，所以只要求輸出答?mod P的值。

對(duì)小規(guī)模數(shù)據(jù)暴力模擬輸出后，我們不難發(fā)現(xiàn)這一列數(shù)其實(shí)是卡特蘭數(shù)。這使得我們聯(lián)想到出棧序列問題（結(jié)果同為卡特蘭數(shù)），但題目敘述與出棧序列問題描述相差甚遠(yuǎn)，因此不妨嘗試在不改變滿足題目約束的前提下進(jìn)行變化，使得題目變?yōu)榍蟪鰲Ｐ蛄蟹桨笖?shù)的問題。

考慮令從左到右依次處理時(shí)，把一個(gè)數(shù)放在奇數(shù)項(xiàng)看作入棧，放在偶數(shù)項(xiàng)看作出棧，則不難注意到棧中數(shù)（列）滿足遞增規(guī)律，棧外剩余數(shù)（列）也為遞增數(shù)列，且一定滿足對(duì)于序號(hào)相同的元素，棧內(nèi)元素小于棧外元素。至此題目轉(zhuǎn)化為求出棧序列方案數(shù)問題，完成了模型之間的轉(zhuǎn)換。結(jié)果可用卡特蘭數(shù)通項(xiàng)公式求解。（正確性證明略）

數(shù)學(xué)上，這種通過以少量特殊性結(jié)論來猜想一般性結(jié)論的方法被稱為數(shù)學(xué)歸納法。我們可以根據(jù)猜想得出的一般性結(jié)論找到證明方向，返回來證明猜想的正確性。這種數(shù)學(xué)歸納法與證明結(jié)合的方法，其實(shí)質(zhì)是將數(shù)學(xué)運(yùn)算與數(shù)據(jù)分析相結(jié)合，先通過數(shù)據(jù)分析找出規(guī)律，判斷處理方向，再利用數(shù)學(xué)運(yùn)算證明。我們需對(duì)一些常見模型足夠熟悉才能靈活運(yùn)用此方法解題。這種基于假設(shè)的方法，在證明不等式成立等問題中有廣泛應(yīng)用。

4 結(jié)語(yǔ)

信息競(jìng)賽作為“五大競(jìng)賽”中唯一脫離中學(xué)課程之外的競(jìng)賽，其許多思想與方法在各學(xué)科中均有體現(xiàn)，并不局限于數(shù)學(xué)。在理工類科目中，結(jié)合信息技術(shù)，可以模擬實(shí)驗(yàn)結(jié)果，對(duì)物理模型或概念模型的正確性進(jìn)行驗(yàn)證;在社科類科目中，結(jié)合信息技術(shù)可通過建立合適的模型來預(yù)測(cè)結(jié)果或進(jìn)行大數(shù)據(jù)分析。有人曾設(shè)想以元胞自動(dòng)機(jī)為原型制造一個(gè)模擬經(jīng)營(yíng)系統(tǒng)以找到己方公司最優(yōu)的發(fā)展方法;理論上來說這種設(shè)想是完全正確的。此外，在編程中體現(xiàn)出的“優(yōu)化到極致”以提高性能的思想更是體現(xiàn)在生活中的方方面面。因此，我們對(duì)信息學(xué)中體現(xiàn)出的思想與方法應(yīng)有足夠的重視。至少，作為學(xué)生我們可以把原來單科獨(dú)立學(xué)習(xí)轉(zhuǎn)變?yōu)閺淖约簝?yōu)勢(shì)學(xué)科中提煉解題方法與內(nèi)涵，將其中的方法與思想推廣到其他科的學(xué)習(xí)中去。

【參考文獻(xiàn)】

[1]劉汝佳，陳鋒.算法競(jìng)賽入門經(jīng)典——訓(xùn)練指南[I].北京：清華大學(xué)出版社，2012.

[2]（美）托馬斯·科爾曼，（美）查爾斯·雷瑟爾森等.算法導(dǎo)論（第三版）[I].殷建平，徐云等譯.北京：機(jī)械工業(yè)出版社，2013.