面向復雜工程問題的算法系列課程教學案例選擇與設計方法探討

摘 要：案例教學是算法系列課程行之有效的一種教學方式，有效的教學案例是案例教學取得成功的重要標志。針對教學案例選取不具代表性、案例分析不到位等問題，該文提出相應的解決方案。該方案從復雜工程問題與教學案例之間的關系入手，圍繞如何解決復雜工程問題組織教學過程，形成“選擇案例、分析案例、形成解題思路、撰寫算法、編寫程序、運行程序、驗證案例”的案例教學過程，提出案例選擇等7個原則，以及基于枚舉法的教學案例分析方法，舉例說明論文所提方法的具體實施過程。該文所提原則和方法對其他課程教學案例的選擇與分析具有一定的借鑒意義。

關鍵詞：算法設計與分析；復雜工程問題；案例教學；教學案例；教學設計

中圖分類號：G640 文獻標志碼：A 文章編號：2096-000X（2024）26-0110-04

Abstract： Case teaching is an effective teaching method of algorithm series courses. Reasonable and effective teaching cases are the basic conditions and guarantees for the success of case teaching. In view of the unrepresentative selection of teaching cases and other problems， the corresponding solution is proposed. The solution starts from the relationship between complex engineering problems and teaching cases， organizes the teaching process around how to solve complex engineering problems， and forms the case teaching process of "selecting cases， analyzing cases， forming problem-solving ideas， writing algorithms， writing programs， running programs and verifying cases". Six principles of case selection and teaching case analysis method based on enumeration method are put forward. Examples are given to illustrate the concrete implementation process of the method proposed in this paper. The principles and methods proposed in this paper have certain reference significance to the selection and analysis of other teaching cases.

Keywords： Algorithm Design and Analysis; complex engineering problems; case-based teaching; teaching case; instructional design

算法課程是計算機類及其相關類專業課程體系中一門非常重要的必修課，該課程的教學目的是以能力培養為導向，著力培養學生綜合融合多種算法設計技術編寫出解決復雜工程問題的應用程序[1]。同一個問題可以有多種解決方案（算法），不同方案所編程序的大小、效率可能相差較大，因此，一個好的算法功底可以為學生打下扎實的有效設計解決復雜工程問題方案的基礎。與此同時，算法基礎也是一些ICT企業面試時必問的內容。

瑞士心理學家皮亞杰認為，學習結果不是學生接受了多少知識，而是學生個體知識經驗得到了重組[2]。同樣，算法課程不僅要使學生掌握動態規劃法、貪心法、分治策略與遞歸法、分支限界法和回溯法等知識點，更要培養學生如何使用算法設計技術解決實際復雜工程問題的能力[3]，即解決一個個問題實例（案例）的能力。簡單地講，不會解決問題實例（案例）就設計不出正確有效的算法，當然也編不出正確的程序，由此可見，案例教學是算法課程行之有效的一種教學方式。

案例教學（case-based teaching）是由美國哈佛法大學學院前院長克里斯托弗·哥倫布·朗代爾于1870年首創，是一種非常成功的教育方式。1980年開始案例教學引入我國，目前在我國的推廣實施已有40多年。案例教學可以引導學生增強學習的積極性和主動性，提高學生自主分析問題和解決問題的能力，促進真實場景下的真學真做，是一種開放式、互動式的新型教學方式。

案例教學最早用于醫學教學，后來，該法被廣泛應用于管理、商業、法律和工學等領域[4-8]。案例教學是以教學案例為起點，教學案例是案例教學的核心，選擇恰當的教學案例是成功實施案例教學的前提，直接影響著教學效果。醫學界收集不同病癥的診斷及治療過程，用于基于案例的課堂分析，以培養學生的診斷推理能力[4]。法學界整理各種不同的判例記錄，形成法學案例，以培養學生的判案推理能力[5]。公共管理界搜集整理包含多項內容的公共管理和決策記錄，構成教學案例，以培養學生的分析、推理、決策等能力[2，6]。張帆[7]提出了教學案例需要體現學科交叉和融合，給出了教學案例庫的設計原則。梁淑軒等[8]對教學案例的收集與選擇進行研究探討，強化和規范了重點關鍵環節，培養并提高其解決復雜工程問題的能力。由此，目前已提出了一些教學案例選擇方法，但總的來說，案例教學僅局限于把教學案例用作課堂教學中的實例來分析。另外，可供選擇的優秀案例少，缺少完整的選擇原則，為此，本文以算法系列課程為背景，提出了教學案例的選擇原則和相應的教學案例分析方法，為案例教學營造了一個真實完整的工程場景，提高學生分析與解決復雜工程問題的能力。

一 復雜工程問題與教學案例

《華盛頓協議》用7個特征來刻畫復雜工程問題，其中第一條是必備的，第二到第七條是可選的[3]。

算法是指解決問題的方法、或過程、或指令序列，這里的問題至少包括《華盛頓協議》的第1個和第3個特征，是一個復雜工程問題，即課程所講述問題需要基于深入的數學、計算機科學、軟件工程知識和程序設計技能等基本原理，經過分析—設計—分析等過程才可以解決。另外，課程教學需要對復雜工程問題進行深入細致分析，建立合適的數學模型，以此進行算法設計與分析，最終編寫出解決工程問題的應用程序。

解決“復雜工程問題”是《華盛頓協議》的實質核心，不同于醫學、管理、法律和商業等領域問題，算法所涉及的問題包含一段文字描述、輸入和輸出。比如循環賽日程表安排問題，其文字描述為：有多個選手要進行單循環比賽，最少需要多少天？要求為：每個選手必須與其他選手各賽一次，每個選手每天只賽一次。該問題的輸入即為參賽人數，輸出即為循環賽日程安排方案。計算機求解問題的實質就是設計出用于解決該問題的程序或軟件，即把問題的輸入（程序或軟件的輸入）轉換成正確的問題輸出（程序或軟件的輸出）。程序或軟件的一次運行就是解決一個問題，在程序或軟件運行時，需要給定具體的輸入，如5位參賽人數、11位參賽人數等，因此程序或軟件的運行其實就是用來解決問題實例的，所謂問題實例是指輸入參數確定后的問題對象，問題和問題實例類似于C++語言中的類和類對象的關系。這里的問題實例就是算法課程中的教學案例，是一個真實、典型且含有復雜工程問題的事件，一個包含有疑難復雜工程問題的實際情景的描述。

二 教學案例的選擇原則

課程組長期從事算法系列課程教學工作，構建了算法設計與分析課程教學案例庫，提出了案例選擇的7個原則。

（一） 相關性原則

所選教學案例務必緊扣教學內容，關注教學內容的重點和難點。引入教學案例的目的是引導學生更好地理解、掌握和加深課程知識點，理清思路，化解難點，并運用所學知識解決實際復雜工程問題，因此，教學案例必須與課程內容高度吻合。

（二） 真實性原則

真實性最早來自于希臘語，意思為最初的、自己做的。真實性最早用于鑒別博物館中展品的真實性，判斷其價值是否符合某個價格。所謂案例真實性是指案例所描述的事件來自于現實世界，能最大限度地貼近當前生活，事件的經過和結果是真實的，如實反映現實世界事件的本來面目，是企業在研發、生產、銷售等中遇到的實際問題。

教學案例真實性營造了一個真實完整的工程場景，該場景可以將各方面因素相互作用而產生的沖突矛盾真實地呈現在學生面前，促進真實場景下的真學真做，給人以身臨其境之感，從而能夠培養學生解決現實世界所面臨的實際復雜工程問題的能力。如：棋盤覆蓋教學案例來源于現實世界中房間地磚鋪設方案；最長公共子序列教學案例來自于百度知道（百度百科）中兩段文字之間相似度計算方法；還有單源最短路徑、流水作業調度、活動安排問題等教學案例。這些教學案例都是來自于現實世界的真實情境或事件。算法和程序只是一種工具，學習的重點是用它來解決實際問題。如果不考慮實際問題來討論教學案例，只會用某種語言來實施教學案例，可能只是知道了語言成分的含義，知道正確的語法形式，不是真正的編程鍛煉。因此，教學案例一定要能最大限度地貼近當前生活。

（三） 適度性原則

適度性原則包括兩個方面的內容，一是指案例難易要適中，算法案例千千萬，例如兩個數相加、人機對弈均是一個基于真實性原則的教學案例，顯然這兩個案例是不合適的，一個是過于簡單，一個是過于復雜，過于簡單的教學案例分析不出問題所包含的知識點和算法思想，過于復雜的教學案例會打擊學生學習的積極性，講解起來也很費力。可以根據學生特點，選擇那些“跳一跳，夠得著”難度的教學案例，教學案例要具有一定的“挑戰度”。

二是指我們所選擇的教學案例規模并非越大越好，在規模上必須保證大小適度。一方面教學案例必須達到一定的規模，規模過小體現不出問題的求解思路。如矩陣連乘問題中規模為1或2的教學案例顯然分析不出問題的解題思想，對其進行講解毫無意義和價值。另一方面，教學案例的規模不能過大，這會導致講解過程非常冗長。如矩陣連乘問題中選擇規模為20甚至更大的教學案例，分析求解過程非常繁瑣，不具教學效果。

一般情況下，教學案例可以采用板書教學，規模最多控制在一個板書內，做到一案例一板書，這樣可以了解教學案例的內在邏輯結構和解題過程，非常清晰。

（四） 代表性原則

除滿足真實性原則、適度性原則外，教學案例要具有一定的代表性，具有舉一反三、觸類旁通的作用。代表性教學案例是指該教學案例的解決方案包含了問題所面臨的所有可能，具有問題解決方案的普遍性和一般性，能幫助我們完整、系統地理解問題的本質。對此，在對問題進行分析時，需要分析出問題出現的各種可能，以此來作為選擇具有代表性教學案例的依據，其解決方案能夠完整地反映所有其他教學案例的解題思路，由此可以推斷其他教學案例的規律和特征，進而給出問題的解決方案或算法。

代表性教學案例的選擇是一個非常具有挑戰性的工作，需要考慮問題出現的方方面面，列舉出問題所包含的所有教學案例，從中選擇出代表性教學案例。下面以循環賽日程表安排問題為例，給出一種代表性教學案例的選擇方法，該方法在對問題進行分析時，對問題所涉及參數進行分類，分析并歸納出每一類的特點，以達到縮小教學案例范圍的目的。循環賽日程表安排問題所涉及到的參數包括參賽人數、上（下）半場參賽人數。

1）參賽人數，從理論上來講，參賽人數可以是1、2、……、100、……，參賽人數可以分為兩類，即奇數和偶數，參賽人數為奇數的解決方法包含了參賽人數為偶數的解決方法，因此代表性教學案例中參賽人數可以設為奇數。另外，參賽人數為偶數的解決方案中，參賽人數又可分為2n和非2n，非2n參賽人數的解決方法包含了參賽人數為2n的解決方法，因此代表性教學案例中參賽人數不應為2n-1，如不要選擇3、7、15。由此，教學案例中的參賽人數應選擇非2n-1的奇數。

2）上（下）半場參賽人數可以是1、2、……、100、……，同樣，上（下）半場參賽人數可以分為兩類，即奇數和偶數，同樣，上（下）半場參賽人數為奇數的解決方法包含了上（下）半場參賽人數為偶數的解決方法，因此應該選擇上（下）半場參賽人數為奇數的參賽人數，如5、9、11等，不要選擇8、12等。

由此，參賽人數為5、9、11、13和17等的教學案例均可以選作代表性教學案例，根據適度性原則，最終可以選擇參賽人數為5或9的教學案例，經分析驗證，這兩個教學案例確實包含了問題出現的每一種可能，具有一般性和普遍性。

（五） 復雜性原則

每個教學案例僅關注于一個知識點，盡量簡化教學案例的復雜度，以滿足教學知識模塊的要求，做到一教學案例對應于一知識點。待學生已經掌握了多個知識點后選擇含有多個知識點的綜合教學案例，以提高學生綜合運用多個知識點創造性地解決實際復雜工程問題的能力。

（六） 多樣性原則

一方面，如有可能，同一個知識點應該準備多個有矛盾沖突的教學案例，培養學生基于相同知識點來解決不同實際工程問題的能力。另一方面，教學案例應該只有問題描述，沒有處理方法和結果，某些教學案例可以有不同的處理方法，當然不同的方法所產生結果應該是一樣的，為此，可以選擇一題多解的教學案例，培養學生基于不同知識點來解決同一個實際復雜工程問題的能力。

（七） 新穎性原則

選擇和采用新鮮、別致、有創新感的教學案例，由此可以增加案例教學的吸引力，喚起學生學習的動力和熱情，提高案例教學的效果。

三 教學案例分析

案例教學是在教師指導下，以學生為中心，以案例為基礎，通過具體的、真實發生過的案例來引導師生共同進行分析、研究和討論，將理論與實踐緊密結合起來，引導學生理解問題、分析問題、解決問題，從而更好地掌握知識點，形成問題的解決方案。由此，算法案列教學過程主要包括選擇案例、分析案例、形成解題思路、撰寫算法、編寫程序、運行程序和驗證案例等，案例分析是其中一個非常重要的步驟，案例分析是否準確直接關系到算法、程序的正確性。

一般情況下，一個算法教學案例包含有具體的輸入數，如11個參賽人數的循環賽日程表教學案例的輸入為11、6個矩陣連乘教學案例的的輸入是6等，每一個教學案例有許多不同的執行方案，從理論上來講，案例分析需要考慮到每一種可能，否則程序可能會出現BUG。對此，可以考慮使用枚舉法列出所有可能，即采用枚舉法事先枚舉出教學案例所有的可能，根據問題要求逐個檢驗，從中選擇滿足要求的最終方案。枚舉法的不足是當規模很大時，運算量也很大，效率非常低。其優點是其正確性可以得到驗證，其思路也易于理解，并可以求出教學案例的所有解，枚舉法的優點為教學案例分析提供了一種思路。下面以動態規劃、貪心算法中的兩個教學案例為例，說明枚舉法在教學案例分析的應用技巧。

（一） 石子歸并問題

石子歸并問題的描述：有n堆石子排成一排，每堆石子有一定的數量。將n堆石子并成為一堆，每次只能合并相鄰的兩堆石子，合并的花費為這兩堆石子的總數。經過n-1次合并后成為一堆，求總的最小花費。

這是一個復雜工程問題，該問題的輸入為n堆石子，有多種方法可以解決該問題，其中動態規劃是解決該問題的一種行之有效方法，構造出最優子結構并證明其正確性是問題分析的核心。所謂最優子結構性質是指問題的最優解包含著其子問題的最優解，其實質就是原問題可以分解為一些規模較小的相同子問題以及如何分解？

顯然，問題的最優歸并肯定是存在的，假如每次只執行一個歸并（這是可行的），那么該歸并需要歸并n-1次，這n-1次歸并必然有個執行順序，我們可以以歸并順序中的最后一個歸并點作為枚舉對象，列出該對象的所有可能，即有n-1種可能，每個歸并點將原問題分解成為2個規模縮小的相同子問題。n-1種可能可以將原問題分解為2（n-1）個規模縮小的相同子問題。根據如上思路，最優子結構性質的證明順理成章。另外，可以很方便地給出n為6或11時的教學案例的執行過程，由此思路就可以寫出解決該問題的算法。

（二） 活動安排問題

活動安排問題是指從n個活動集中選出最大的相容活動子集[9]。

這是一個離散性問題，可以使用窮舉法法來確定問題的解，其時間復雜度為O（n！），屬指數級別。為此，我們可以改變枚舉對象，設一個最大相容活動子集為a1、a2、……、ak，其中k為最大相容活動數。現以a1為枚舉對象，顯然，a1屬于{1，2，…，n}，共有n種可能，a1的每一種可能i將原問題轉化為為1個規模較小的相同子問題，i {1，2，…，n}，即第一個得到安排的活動為i，余下的子問題是從這n-1個活動集中選出最大的相容活動子集。更深一步，假設按每個活動的結束時間非減序排列，則有第i個子問題的時間段包含了第i+1個子問題的時間段，第i個子問題所需安排活動包含了第i+1個子問題所需安排的活動。因此，第i個子問題的解不小于第i+1個子問題的解，因而第一個子問題的解最大，即以完成時間為貪心指標，每次選擇需安排活動集中的第一個活動，貪心選擇性質的證明也顯得非常容易。根據如上思路，可以很方便地給出n為6時的教學案例的執行過程，由此思路就可以寫出解決該問題的算法。

由此可見，靈活選擇枚舉法中的枚舉對象可以演示教學案例的執行過程，從而為問題的解決提供了一種思路，同時也為算法的正確性證明提供了保障。

盡管枚舉法的運算量較大，但規模適中的教學案例的執行效率是可以接受的，應用枚舉法來分析教學案例是完全有效可行的。

四 結束語

案例教學法是一種以案例為基礎的教學法，如何選擇周密的教學案例是確保案例教學達到預期目標的關鍵所在。本文以算法設計與分析課程為背景，提出了教學案例的7個選擇原則，以及基于枚舉法的教學案例分析方法，原則和方法對其他課程教學案例的選擇與分析有著一定的借鑒意義。算法設計與分析課程是一門集理論、應用于一體的實踐性課程，課程難度大，課時數少，而教學案例千千萬，如何精選教學案例永遠是一個值得深入探討的課題。另外，如何因材擇案例也是今后進一步研究的課題。

參考文獻：

[1] 教育部高等學校教學指導會員會.普通高等學校本科專業類教學質量國家標準[S].北京：高等教育出版社，2018：321-329.

[2] 韓寶珍.“保險學”案例教學：案例選擇與過程設計[J].黑龍江教育（高教研究與評估），2018（11）：25-27.

[3] 蔣宗禮.培養計算機類專業學生解決復雜工程問題的能力[M].北京：清華大學出版社，2018：169-176.

[4] 肖邦，朱怡卿，陳美婷，等.案例教學法在醫學遺傳學教學中的應用[J].基礎醫學教育，2022，24（10）：733-736.

[5] 閔菁.辯護律師違規退庭的法律研究——基于典型案例的分析[D].重慶：西南政法大學，2019.

[6] 魏娟玲，張鑫.公共管理案例體系整體性構建研究[J].教育理論與實踐，2021，41（18）：53-55.

[7] 張帆.數字圖像處理課程案例庫建設及案例驅動教學法應用[J].計算機教育，2022（1）：34-37.

[8] 梁淑軒，趙春霞，張金超，等.產教融合下案例教學構建實施中關鍵問題研究[J].高教學刊，2023（1）：135-138.

[9] 朱玉全，鄒婷婷，黃承寧.融合計算思維的算法設計與分析課程教學探索[J].計算機教育，2022（10）：165-168.

基金項目：教育部產學合作協同育人項目“面向計算機類專業的算法系列課程師資能力提升研究”（202002320002）；江蘇大學2023年高等教育教改研究課題立項建設項目“算法思維遞進式案例教學方法研究與實踐”（2023JGYB015）

第一作者簡介：朱玉全（1965-），男，漢族，江蘇常州人，博士，教授。研究方向為數據挖掘、機器學習等。