一、研究背景及意義

隨著信息技術的飛速發(fā)展，編程已成為現(xiàn)代社會的一項重要技能。在大學教育中，編程課程作為計算機科學與技術等相關專業(yè)的基礎課程，其重要性不言而喻。然而，傳統(tǒng)的編程教育過于注重語法和語言本身的教授，忽視了對學生計算思維的培養(yǎng)。計算思維作為一種基本技能，在解決復雜問題、提升創(chuàng)新能力和邏輯推理能力等方面具有重要意義。同時，數(shù)學作為一門基礎學科，其賦予學生的邏輯推理能力和抽象思維能力對于提升學生的編程能力也有不可忽視的作用。因此，將計算思維與數(shù)學思維有機融人大學編程教育，具有重要的理論和實踐意義，具體如下：

（一）提高編程教學質量

計算思維與數(shù)學思維的融合，有助于學生更好地理解和掌握編程知識，提高編程教學質量。

（二）培養(yǎng)創(chuàng)新型人才

計算思維與數(shù)學思維的融合，有助于培養(yǎng)學生的創(chuàng)新意識和解決復雜問題的能力，滿足社會對創(chuàng)新型人才的需求。

（三）促進跨學科交流與合作

計算思維與數(shù)學思維的融合，有助于不同學科之間的交流與合作，推動計算機科學與技術等相關學科的發(fā)展。

（四）完善教育體系

研究計算思維與數(shù)學思維的融合，有助于完善我國大學編程教育體系，提高教育質量。

（五）為政策制定提供依據(jù)

通過實證研究，為教育部門制定相關政策提供理論依據(jù)和實踐參考，推動編程教育的改革與發(fā)展。

二、計算思維與數(shù)學思維概述

（一）計算思維定義與特點

計算思維（ComputationalThinking）是由周以真（JeannetteWing）教授于2006年提出的一個概念，它是指一種解決問題和設計系統(tǒng)的思維方式，涉及問題的表示、解決方案的制定，以及問題的自動解決。計算思維具有以下特點。1.抽象性：能夠從具體問題中抽象出核心概念和模型。2.模式識別：能夠識別問題中的模式和規(guī)律，形成解決問題的通用方法。3.算法思維：能夠設計一系列清晰、有序的步驟來解決問題。4.自動化：能夠利用計算機等技術自動執(zhí)行解決方案。

（二）數(shù)學思維的定義和特點

數(shù)學思維是一種以數(shù)學概念和邏輯推理為基礎的思維方式，它強調邏輯的嚴密性和證明的必要性。數(shù)學思維具有以下特點：1.邏輯性：數(shù)學思維強調使用邏輯推理來證明和解決問題。2.抽象性：能夠從具體事物中抽象出數(shù)學概念和結構。3.一般性：數(shù)學思維尋求一般化的規(guī)律和定理，適用于廣泛的情境。4.結構性：數(shù)學思維關注數(shù)學對象之間的關系和結構。5.創(chuàng)造性：數(shù)學思維鼓勵創(chuàng)造新的數(shù)學概念和方法來解決未知問題。

（三）計算思維與數(shù)學思維的關系

計算思維與數(shù)學思維雖然有不同的側重點，但它們之間存在緊密的聯(lián)系和相互支持的關系。

1.相互補充：計算思維中的算法設計和自動化執(zhí)行需要數(shù)學思維中的邏輯推理和證明來確保解決方案的正確性。同時，數(shù)學思維中的問題建模和結構分析也受益于計算思維中的抽象和模式識別能力。

2.交叉應用：在解決實際問題的過程中，計算思維和數(shù)學思維常常交叉應用。例如，在算法設計中，數(shù)學思維用于分析算法的復雜性和正確性；在數(shù)學研究中，計算思維則可以幫助進行大規(guī)模計算和模擬。

3.共同目標：計算思維和數(shù)學思維都旨在解決問題和創(chuàng)造知識。它們共同為科學、工程和日常生活中的問題提供解決方案和理論基礎。

4.教育融合：在教育實踐中，計算思維和數(shù)學思維的融合有助于學生更全面地理解問題解決的整個過程，能夠提高學生的綜合分析和創(chuàng)新能力。

通過在編程教育中融入這兩種思維方式，學生不僅能夠學會如何編寫代碼，還能夠學會如何使用計算工具來探索數(shù)學概念，以及如何運用數(shù)學知識來設計和分析算法。這種融合有助于培養(yǎng)既具備編程技能又具備數(shù)學素養(yǎng)的復合型人才。

三、大學編程教育存在的問題與挑戰(zhàn)

（一）計算思維與數(shù)學思維融合不足

在目前的編程教育中，計算思維和數(shù)學思維的融合不夠深入。學生難以將數(shù)學知識應用于編程問題的解決中。

（二）創(chuàng)新能力培養(yǎng)不足

編程教育往往注重語法和技能的教授，而忽視了培養(yǎng)學生的創(chuàng)新能力和解決復雜問題的能力。

（三）跨學科交流與合作不足

編程教育往往局限于計算機專業(yè)內部，與其他學科的交叉融合不足，限制了編程技術的廣泛應用和創(chuàng)新。

為了解決這些問題，需要對編程教學進行深化改革。

具體而言，應創(chuàng)新教育方法和內容，加強計算思維與數(shù)學思維的融合，提高編程教育的實踐性和創(chuàng)新性。本文第四部分將展示如何實現(xiàn)計算思維與數(shù)學思維在編程教學中的融合。

四、計算思維與數(shù)學思維的融合教學實踐—以Huffman算法為例

（一）理解并描述現(xiàn)實需求

計算機中存在許多大型文件，為了方便存儲，需要對其進行無損壓縮。即：大幅減小文件尺寸，并在需要時能恢復文件中存儲的全部信息

（二）利用數(shù)學思維建立簡化的計算模型

文件通常分為音視頻、圖片、文本文件。本文選取文本文件作為簡化研究對象。文本文件中存儲英文、中文等各種文字，本文僅選取英文作為簡化研究對象。英文又分為大小寫、數(shù)字、標點符號，為了便于研究，簡化為只含有4個字母： 的文本文件，并假定文件存儲的內容是：aaaabbbccd。

直觀的做法是將a、b、c、d四個字母進行等長編碼，最終得到00、01、10、11，這樣可將存儲空間從10字節(jié)減少到20比特，其對應的是圖1的滿二叉樹（每個字符的編碼是從樹根走到字符結點的路徑上0、1形成的串）。為了進一步壓縮文件，考慮將 的編碼變?yōu)?、1。這樣，存儲空間減少到 4 + 3 + 2 × 2 + 1 × 2 = 1 3 比特，對應著圖2的二叉樹。但這樣的編碼存在如下問題：ba將被編碼為10，解碼時可以解碼為 b a ，也可以解碼為 ∣ c ∣ ，從而產(chǎn)生了歧義。究其原因，是因為 b 的編碼1是 ∣ c ∣ 的編碼10的前綴。

觀察圖1和圖2可以看到，圖1的編碼沒有歧義，是因為圖1中所有被編碼的字符都是樹的葉節(jié)點，到達每一個被編碼字符的路徑唯一且不經(jīng)過其他被編碼字符，而圖2存在被編碼字符是樹的分支節(jié)點，到達 c 、d必定經(jīng)過b，解碼時將產(chǎn)生歧義。

觀察圖3，存儲空間減少為 4 × 1 + 3 × 2 + 2 × 3 + 1 × 3 =

19比特，比圖1對應編碼所占存儲空間要小，究其原因，是圖3使用變長編碼，使得出現(xiàn)頻度越高的字符的編碼越短，從而減少了編碼長度。將字符出現(xiàn)的頻度作為結點的權值，設二叉樹具有 個帶權值的葉結點，那么，從根結點到各個葉結點的路徑長度 l i 與相應結點權值wi的乘積的和，叫作二叉樹的帶權路徑長度，即 由此可知越優(yōu)的編碼方案對應的二叉樹的WPL越小。

因此，為解決1中描述的問題，本文建立如下數(shù)學圖模型：1.被編碼字符全作為二叉樹葉節(jié)點，字符出現(xiàn)的頻度作為葉節(jié)點的權值；2.分支結點指向左子樹的邊附著0，分支結點指向右子樹的邊附著1。被編碼字符的編碼為樹根到葉結點路徑上0和1組成的串；3.目標是求出WPL最小的二叉樹（這樣的樹被稱為Huffman樹或最優(yōu)樹）。

（三）計算思維探索解決辦法

根據(jù)（二）中的思路，應該讓頻度越高的字符離根節(jié)點越近，所以，解決辦法是從頻度最小的字符開始，依次向上兩兩合并，形成如圖3的二叉樹。其本質是犧牲頻度低的字符的編碼長度，換取頻度高的字符的編碼盡可能短，這是局部貪心的思想。觀察圖4發(fā)現(xiàn)，圖4右（形如圖3）的 W P L = 4 6 ，大于圖4左（形如圖1）的W P L = 4 4 可見，局部貪心未必能導致全局最優(yōu)。此處的問題在于， 的頻度與 、b的頻度差距較小。在這樣的情況下，過于犧牲 ∣ c ∣ ！ d 的編碼長度來成全a、b的編碼，將導致過猶不及。因此，需要適當顧及c、 d 的編碼。從計算思維的角度來看，應當存在一個閾值，當?shù)陀陂撝禃r可以完全忽視 ∣ c ∣ 、d，而高于閾值時就必須顧及c、d。

設a、b、c、 d 四個結點的權值依次減小，對比分析以上形態(tài)的二叉樹可知，閾值應選為 ∣ c ∣ ！ 權值之和與 權值的大小關系，即：當 ∣ c ∣ 、d權值之和大于 的權值時，需要顧及；當 c ， d 權值之和小于 a 的權值時，不需要顧及;

而當 c ， d 權值之和與 權值相當時，則處于臨界點。即：閾值是 ∣ c ∣ 、d權值之和是否仍然是最小的兩個權值之一。

因此計算辦法改變?yōu)椋?.個字符形成具有 n 棵樹的森林，每棵樹的權值為字符的權值；2.按權值從小到大的順序依次合并2棵樹為1棵樹，新樹的權值為2棵子樹的權值之和；3.當森林中僅剩1棵樹時，計算結束。這棵樹就是求得的最優(yōu)樹。

按照計算思維的慣例，在小規(guī)模范圍內對上述解決辦法進行窮舉，發(fā)現(xiàn)該解決辦法完全正確。因此，有理由相信，該辦法大概率是正確的。

（四）數(shù)學思維證明解決辦法

無法在大規(guī)模范圍內對（三）中的方法進行窮盡驗證，因此，需要對其正確性進行嚴格的數(shù)學證明。

引理1：最優(yōu)二叉樹中不可能存在度為1的結點；

引理2：必存在一棵最優(yōu)二叉樹，權值最小的2個結點在該樹中為兄弟。

下面，用數(shù)學歸納法證明3種方法求得的二叉樹（下文稱Huffman樹）就是最優(yōu)二叉樹：

當 n = 2 時（只有2個字符），只有一種形態(tài)的二叉樹（^型），所以其必是最優(yōu)二叉樹，而Huffman樹正是該最優(yōu)二叉樹。

歸納假設：當 n = k 時（有 k 個字符），Huffman樹是最優(yōu)二叉樹。

當 n = k + 1 時（有 k+1 個字符），記滿足引理2的最優(yōu)二叉樹為 s k+1 ，記Huffman樹為 H k+1 ，則 和H k+1 有完全相同的葉節(jié)點，且權值最小的2個葉結點（a和b）在 s k+1 和 H k+1 中均互為兄弟，記這2個葉結點的權值為wa和 。

把 S k+1 中權值最小且互為兄弟的2個葉結點向上求和得到的二叉樹記為 S k ，則WPL （ S k+1 ） = W P L （Sk）+ w a + w b

把 H k+1 中權值最小且互為兄弟的2個葉結點向上求和得到的二叉樹記為 H k ，則WPL （Hk） 0

由于 和 H k+1 有完全相同的葉節(jié)點，所以， S k 和Hk也有完全相同的葉節(jié)點。同時，由于求Huffman樹的方法每次迭代都是選取權值最小的2棵子樹進行合并，所以，Hk必然是有 k 個字符的Huffman樹。由歸納假設可知：WPL （ H k ） ? W P L （Sk），兩邊同時加上 W a 和 W b 得到WPL（ H k+1 ）和 ，從而有WPL（ H k+1 ）= W P L （ H k ） + w a + w b ? W P L （Sk） + w a + w b = W P L （ S k+1 ）。

又由于 s k+1 是最優(yōu)二叉樹，所以WPL（ $＼ { ＼cal H } k { + } 1 ＼ ） ＼ gt; ＼ =$

WPL（ S k+1 ）。因此WPL （ s k+1 ），這表明具有 個結點的Huffman樹 H k+1 是最優(yōu)二叉樹

（五）計算思維設計算法方案及其分析和改進

huffman樹若有 n 個葉節(jié)點，則總結點數(shù)為 2 × n - 1，因此，采用共 2 × n-1 個元素的靜態(tài)二叉樹樹表（數(shù)組）作為Huffman樹的存儲結構（前n個元素存放葉節(jié)點，后 個元素存放分支節(jié)點）。

構造Huffman編碼時，從葉節(jié)點出發(fā)，沿著前面增加的父節(jié)點字段，向上上溯到根節(jié)點就可獲得編碼的逆序。構造Huffman樹及構造Huffman編碼的算法偽碼，參見文獻 ；構造Huffman樹的算法針對葉結點數(shù)共兩重循環(huán)，因此時間復雜度為 。

（六）編程思維實現(xiàn)算法方案

由于數(shù)組元素的下標不可能為-1，因此，將Parent設置為-1表示該結點是樹根。通過遍歷數(shù)組并檢測Parent是否為-1，可快速定位當前森林中的樹根結點，從而篩選出權值最小和次小的兩棵樹進行合并。

此外，Huffman編碼的生成需從葉節(jié)點逆序回溯至根節(jié)點，若需正序輸出編碼，可通過?；騽討B(tài)數(shù)組逆序存儲二進制編碼，進一步提升算法實現(xiàn)的工程適用性。

五、總結與啟示

通過Huffman算法的完整實踐，學生能夠清晰感知計算思維與數(shù)學思維的協(xié)同作用：數(shù)學思維通過權值模型和歸納證明為算法設計提供理論框架，計算思維則通過貪心策略與數(shù)據(jù)結構實現(xiàn)將抽象模型轉化為可執(zhí)行的代碼。這一過程不僅深化了學生對算法設計與優(yōu)化的理解，還強化了其跨學科知識遷移能力。此外，案例中數(shù)學證明與算法實現(xiàn)的緊密結合，為后續(xù)動態(tài)規(guī)劃、圖論等復雜算法的教學提供了可復用的范式。在未來的教學實踐中，可通過擴展更多算法類型（如最短路徑、背包問題），進一步驗證兩種思維融合的普適性，并為編程教育改革積累實證依據(jù)。本研究通過理論分析與實踐探索，系統(tǒng)論證了在大學編程教育中融合計算思維與數(shù)學思維的必要性與可行性。以Huffman算法為例，具體展示了如何通過數(shù)學建模建立最優(yōu)編碼問題的抽象模型，并利用計算思維設計高效算法解決方案。研究表明，兩者的深度融合能夠有效幫助學生從數(shù)學邏輯中提煉問題本質，通過算法設計與優(yōu)化提升解決實際問題的綜合能力，同時培養(yǎng)創(chuàng)新思維與跨學科應用能力。

作者單位：楊鑄陽清利 周剛 四川大學錦江學院計算機學院

參考文獻

[1]張萬里，龍莆均.算法設計及編程教學與數(shù)學素養(yǎng)的培養(yǎng)[J].電腦知識與技術，2020，16（19）：137-138[2]李春葆.數(shù)據(jù)結構教程（第5版）[M].北京：清華大學出版社，2017.