信息學競賽視角下培養計算思維的策略研究

丁雙林 廣東省中山市中山紀念中學

●計算思維及其特征

1.計算思維

隨著科學技術的發展，以計算機技術為基礎所形成的信息技術不斷融入人類的生活，在解決人類問題的過程中扮演著越來越重要的角色。在此背景下，計算機科學家周以真教授于2006年首次提出計算思維的概念，她認為計算思維是運用計算機科學的基礎概念進行問題求解、系統設計以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。目前，越來越多的專家學者認識到計算思維的重要性，將計算思維同理論思維、實驗思維并列為科學研究及解決問題的三大思維。

為適應時代的發展，《普通高中信息技術課程標準（2017年版）》及《義務教育信息科技課程標準（2022年版）》均將計算思維作為學科重要的核心素養之一，也就是說計算思維是中小學階段學生必備的核心素養。

2.計算思維的特征

計算思維的兩大核心特征是抽象建模和自動化。這兩大核心特征概括了計算機解決問題過程中的核心步驟。抽象建模特征是指在利用計算思維解決問題過程中需要將問題進行歸納、總結，發現其中的規律，然后基于規律建立問題模型，這是利用計算思維解決問題的基礎步驟。自動化特征是指將問題模型轉化為計算機自動執行的程序指令，程序指令是計算思維解決問題的關鍵步驟。

3.學科視角與競賽視角計算思維的異同

信息技術學科是中學生必須學習的學科之一，主要涉及包括信息技術的獲取、表示、傳輸、存儲、加工在內的各種技術及在信息技術基礎上所形成的信息社會、信息系統、信息安全等相關的內容。信息學競賽是信息技術學科內容的補充，競賽以設計算法、編寫程序為主要學習內容，重在培養學生分析問題、邏輯推理、抽象建模以及利用算法、程序解決問題的能力。信息學競賽和信息技術學科既有區別也有聯系。具體如下：

第一，教學內容的側重點不同。信息技術學科是從學科的視角培養學生計算思維的意識和能力，著重培養學生在解決問題過程中將問題進分析、抽象、建模、設計算法的能力，強調的是學生具備利用計算機解決問題所需要的思維能力。信息學競賽偏重于計算思維的算法設計和程序實現模塊，強調學生不僅要具備利用計算機解決問題的思維能力，還要具備將算法轉化為程序的能力，且所設計的程序可以在時間以及空間的限制下通過所有的測試數據。

第二，面向的教學對象不同。信息技術學科面向所有學生，計算思維是學生必須具備的核心素養之一，是面向所有學生開展的普適教育。信息學競賽主要面向學有余力且對該競賽感興趣的部分學生。

第三，教學時空不同。信息技術是每個學生必須學習的內容之一，學科核心素養—計算思維的培養主要依靠課堂教學。信息學競賽是一種課外活動，主要依靠課外時間學習相關的知識。

●信息學競賽培養學生計算思維的策略

信息學競賽的解題過程可以分為四步：分析問題、理解題意；梳理問題、建立數學模型；設計算法、時空復雜度分析；實現程序、調試程序。計算思維體現在以上各個方面，尤其在算法設計上，可以從以下三個方面提升學生計算思維的能力。

1.強化信息學和數學的融合

（1）強化數學知識的學習

信息學競賽解題過程中常用的數學知識主要分布于高等數學、離散數學、概率論。高等數學常用對數函數、指數函數中的知識，如利用對數函數對算法的時間復雜度進行分析。離散數學知識在信息學競賽中應用更為普遍，主要分布于數論、計數模塊，如數論中的素數、丑數、最大公約數、最小公倍數，計數模塊主要分布于排列組合、二項式定理、加法原理、減法原理、鴿巢原理等。

（2）強化數學方法的學習

數學方法、思想的學習對于信息學競賽同等重要，數學歸納、遞推是信息學競賽中常用的方法，也是發現問題中隱藏規律的重要方法。如數學中的遞推方法是理解遞歸程序的基礎，遞推是由已知推向未知的過程，是正向求解問題，遞歸是借助計算機函數調用的原理，由未知推向已知的過程，是逆向求解問題。

2.強化數據結構和算法知識學習

數據結構與算法是計算機學科的核心內容，是計算機解決問題過程中的必備知識。數據結構主要研究數據的組織、存儲的方式，也就是數據運算過程中邏輯主旨結構和物理存儲結構。任何一種算法都有對應的數據結構，算法本質上反映了對數據的操作，而數據又是通過某種數據結構進行存儲。例如，二分查找算法是一種效率較高的查找元素的方法，其要求線性表必須采用順序存儲結構，表中元素按關鍵字有序排列，數組數據結構恰好滿足二分查找的所有要求。信息學競賽常用的數據結構有數組、鏈表、堆棧、隊列、哈希表、堆、樹、圖表、線段樹等，常用算法有排序、查找、分治、貪心、遞歸、動態規劃、深度優先搜索、寬度優先搜索、拓撲排序。學生需要知道每種數據結構和算法的作用、特征，在解決問題的過程中根據實際需要選擇合適的數據結構和算法。

3.深化原理認知并重視思維發展

信息學競賽的知識既與數學有關，又有自己的特征。教師在教學過程中不僅要傳授知識，更要注重知識的傳遞方式。教學過程圍繞理解概念、認識原理、證明過程、應用練習、創新應用5個步驟展開，讓學生知道每一個算法設計的理論依據，加深學生對經典算法的理解，同時，還要通過學練結合、鞏固應用等環節，強化知識。

4.一題多解、多題一解

一題多解就是從不同的視角分析問題，從不同的層次理解問題，進而用不同的知識解決問題，加深學生對知識的理解。一題多解需要學生具有較強的知識整合能力，將已有的知識和方法靈活運用。通過一題多解可以有效培養學生的創造性思維、發散思維。多題一解就是看似不同的題目可以用同一種方法進行問題求解。信息學競賽的題目是無限的，方法、思路是有限的。多題一解是對知識總結反思的過程，通過多題一解將問題的類型進行歸納總結。

信息學教學過程中通過“一題多解和多題一解”的教學策略可提升學生學習的效率，拓寬學生的解題思路，培養學生自主探究的學習意識和能力。

PCR產物用1%的瓊脂糖凝膠電泳檢測判斷是否為陽性擴增。樣品和Marker的上樣量為4 μL。設定電壓為150 V，電泳時間15 min。接通電極，PCR產物由陰極向陽極移動。電泳結束后紫外成像觀察，結果見圖1。

●計算思維導向下的信息學教學實踐

信息學競賽中解決問題的過程為分析問題、抽象建模、設計算法、編寫程序和調試程序。下面以集合的劃分習題為例，探究該問題的解決過程。

問題描述：

設S是一個具有n個元素的集合，S={a1,a2,……,an}，現將S劃分成k個滿足下列條件的子集合S1，S2，……，Sk，且滿足：

①Si≠?

②Si∩Sj=?

③S1∪S2∪S3……∪Sk=S，則稱S1，S2，……，Sk是集合S的一個劃分。求滿足條件的劃分數。

1.分析問題

樣例在信息學解題過程中具有重要的作用，信息學問題的描述一般比較抽象，樣例是將抽象描述具體化的過程。從小樣例出發，分析問題，發現樣例中隱藏的一般規律是解決信息學競賽習題常用的方法。設集合S有4個元素分別為1，2，3，4，劃分為3個子集合的個數。也就是集合S={1，2，3，4}，k＝3，不難得出S有6種不同的劃分方案。具體方案為：

{1，2}∪{3}∪{4}，{1，3}∪{2}∪{4}，{1，4}∪{2}∪{3}，

{2，3}∪{1}∪{4}，{2，4}∪{1}∪{3}，{3，4}∪{1}∪{2}

當S的元素個數較少的時候，通過人工枚舉可以發現S的子集合個數。當S較大時，顯然無法直接枚舉S的子集合的個數，需利用數學歸納的方法發現該問題的本質，建構模型，設計算法，充分利用計算機運算快速的特征達到利用計算機解決問題的目標。

2.抽象建模

集合的劃分問題，可以轉化為集合之間的映射問題，該問題滿足第二類斯特林模型。假設原集合為A，元素個數為n，劃分之后的集合為B，元素個數為m，集合B中的元素均被集合A中的元素所指向，求集合A到集合B的滿射的個數。通過強化信息學和數學的融合促進計算思維的培養。

第二類斯特林數的遞推式為：s(n，m)=s(n-1，m-1)＋m*s(n-1，m)，1≤m≤n。

3.設計算法

基于第二類斯特林數學模型，設計算法如下：

①A集合中的元素單獨構成一個子集合{an}，那么剩下的n-1的元素構成m-1個子集合，即共有子集合個數f(n-1，m-1)。

②第n個元素和別的元素一起構成子集合，即剩下的n-1個元素構成m個子集合，共有子集合個數f(n-1，m)，然后再將第n個元素放到m個子集合中，則有m種選擇，最終共有子集合個數m*f(n-1，m)。由離散數學的加法原理得知最終的子集合個數為f(n，m)=f(n-1，m-1)＋m*f(n-1，m)。其中，當n＜m時或者m=0時，顯然沒有答案。當m=1或者m=n時，顯然只有一個答案。

劃分之后的情況依然滿足原問題的規律，僅僅是減少了問題的規模，并且找到了算法結束的條件，從而將該問題轉化為計算機遞歸模型，當然也可以從遞推的視角解決問題，一題多解。

4.編寫程序、調試程序

下圖為算法的核心模塊。其中n表示原來集合的個數，m表示劃分的子集合的個數。

●結語

本研究以具體實踐為例，從強化信息學和數學的融合、強化數據結構和算法知識學習、深化原理認知并重視思維發展、一題多解等維度，探討如何通過信息學競賽培養學生的計算思維，提升學生核心素養。