王晨昊

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

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

中圖分類號： R197.3 文獻標識碼： A 文章編號： 2095-2457（2019）04-0285-002

DOI：10.19694/j.cnki.issn2095-2457.2019.04.111

0 引言

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

1 對條件的分類與處理

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

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

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

2 轉化與化歸思想

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

給定n個實數(shù)變量與一些線性約束，確定這n個變量的值，使得某個線性函數(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ī)劃的標準形式為：目標函數(shù)最大化的;所有線性約束都為“左邊小于某個常數(shù)”形式的;所有變量均為非負的。如上面的式子就是標準形式。

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

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

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

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

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

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

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

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

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

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

3 數(shù)據(jù)處理與運算結合

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

題目描述：

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

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

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

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

現(xiàn)在的任務是：對于給定的n，請求出有多少個不同的長度為2n的有趣的數(shù)列。因為最后的答案可能很大，所以只要求輸出答案 mod P的值。

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

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

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

4 結語

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

【參考文獻】

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

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