碩士課程“算法設計與分析”案例教學探究

［摘 要］ 在中國高等教育領域“雙一流”建設大環境下，一流大學建設離不開一流學科建設，一流學科建設離不開一流專業和一流課程建設，而一流課程教學案例庫建設為一流專業和一流課程建設提供了有力保障。“算法設計與分析”是軟件工程學科專業學位碩士研究生課程教學體系中的核心課程，探索其案例教學及其建設具有積極意義。以基于割圓隨機化方法的圓周率計算問題為例，構建了分割算法與近似算法相結合的原創性教學案例，結合課程中著名問題，融入思政元素，突出實踐性與原創性。由此系統地培養學生發現問題、分析問題和解決問題的能力，為進一步培養應用型高級軟件人才打下堅實的基礎。

［關鍵詞］ 案例教學；算法設計與分析；圓周率；割圓術；隨機化方法

［基金項目］ 2024年度新疆大學研究生教育教研項目“碩士研究生課程‘算法設計與分析’精品示范課程研究”（XJDX2024YJPK15）；2022年度新疆大學研究生教育教研項目“碩士研究生課程‘算法設計與分析’教學案例庫建設研究”（XJDX2022YALK11）

［作者簡介］ 朱小亮（1980—），女，安徽合肥人，博士，新疆大學軟件學院高級工程師，主要從事數字圖像處理研究；張 濤（1976—），男，新疆烏魯木齊人，學士，新疆大學軟件學院高級工程師，主要從事人工智能與大數據研究；孫 華（1978—），女，山東煙臺人，博士，新疆大學軟件學院副教授，主要從事人工智能與大數據研究。

［中圖分類號］ G642.0 ［文獻標識碼］ A ［文章編號］ 1674-9324（2024）29-0125-04 ［收稿日期］ 2023-06-12

案例建設與實踐教學密不可分，在課程中引入案例教學，建立并不斷豐富教學案例庫，進一步深化產學研結合，為深化專業學位研究生培養模式改革，優化專業學位研究生教育結構及健全完善專業學位研究生教育課程體系，提供了可靠的理論基礎。“算法設計與分析”課程作為軟件工程學科碩士研究生必修的核心課程，對于學生邏輯思維能力的培養、自主創新能力的提升，具有至關重要的作用。該門課程的教學案例建設及案例教學不僅有利于激發學生的學習熱情與創新的積極性，還有利于培養學生的專業實踐能力，更加有利于進一步提高授課教師的教育教學水平與實踐創新能力，從而有助于提高專業學位建設與研究生教育質量，促進軟件工程領域學科發展與軟件產業科技進步。這對于助力“雙一流”建設具有舉足輕重的社會意義［1-2］。

本文設計并開發了基于割圓隨機化方法圓周率區間求解問題的教學案例。本案例以圓周率問題求解為導向，提出一種割圓隨機化方法，即從圓以及圓外切正多邊形與圓內接正多邊形入手，探索圓周率取值范圍，這種取值范圍會隨著正多邊形邊數的增加而使得圓周率估值區間越來越小，越來越接近精確值。在傳授專業知識的同時，還將思政教育融入其中以啟迪思維，根據案例背景人物祖沖之的學術生平與科研貢獻事跡得出人生感悟與啟示。

一、案例教學設計

本案例由案例主題與背景、問題描述、案例分析、啟示以及結尾共五個部分組成。由案例背景引入主題、描述問題，圍繞主題進行問題的求解與分析，最后由案例背景故事得出人生啟示與感悟。

（一）案例主題與背景

古今中外，圓周率計算是個古老而又前沿的話題。最初圓周率計算是為了社會生產生活實踐，后來逐漸演變成一門科學研究，發展至今天，已變成人們的一種興趣和情懷，一種計算先進性的較量與烘托［3］。在這一過程中誕生了很多先驅級別人物，如古希臘的阿基米德，我國古代的劉徽、祖沖之等。其中南北朝時期的祖沖之做出了突出性的貢獻，如采用割圓術將圓周率值精確到小數點后的第7位，比西方國家大約早了一千年，并且祖沖之還開創了圓周率的約率和密率。圓周率計算問題及其求解方法探析是“算法設計與分析”碩士研究生課程中比較著名的問題。自古以來，圓周率計算就有諸多方法，割圓術與隨機投點法是其中比較經典的方法，前者體現了分割與逼近思想，后者體現了概率論思想［4-6］。本文將這兩種思路結合在一起，提出一種同時采用割圓術與隨機投點法來估算圓周率的區間值的方法，并以案例的形式呈現，探索一種圓周率計算問題的新思路以及研究生課程案例教育教學的新模式。

（二）圓周率計算問題

圓周率是無限循環的“超越數”，簡單直觀地說，圓周率就是圓的周長與其直徑的比值，是計算圓面積、球形體積及圓柱體體積等幾何體的重要值。無論圓的大小如何，這個比值都是固定的，常用希臘字母π表示。

（三）案例算法分析與描述

本文采用割圓法與隨機投點法相結合的思路估算圓周率的區間值。根據算法流程圖1得到本文算法設計與分析。令正多邊形邊數為m，本文算法首先求出半徑為r的圓外切正m（m≥6并且m∈N）邊形面積與該圓面積之比，圓內接正m邊形面積與該圓面積之比；其次將這二者進行比較，估算出圓周率π的區間值。該算法流程從m=6開始不斷迭代，逐步縮小其估算區間，為求解圓周率問題提供了一種新的思考方式。

正6邊形（m=6）面積對應圓面積情況：首先分別觀察圓外切正6邊形、圓內接正6邊形以及圓的相關屬性。半徑為r的圓外切正6邊形邊長為（2**r）/3、邊心距為r、面積為S外=（2**r2），該外切正6邊形內含有ω個隨機點數；該圓內接正6邊形邊長為圓半徑r、邊心距為（*r）/2、面積為S內=3**r2/2，其內部含有μ個隨機點數；該圓半徑為r、面積為S圓=πr2，圓內含有Ι個隨機點數。接下來，S外/S圓=（2**r2）/（π*r2）=ω/Ι? π=（2*）*Ι/ω，S內/S圓=（（3/2）**r2）/（π*r2）=μ/Ι?π=（（3/2）*）*Ι/μ，所以得出當ω＜（4/3）*μ時，那么有（3*）*Ι/μ＜（4*）*Ι/ω?π∈［*Ι/μ，2*Ι/ω］。

當m=12，24，48，…時繼續更替迭代。正m邊形（m=12，24，48，…）面積對應圓面積情況：首先分別觀察圓外切正m邊形、圓內接正m邊形以及圓的相關屬性。半徑為r的圓外切正m邊形面積為S外=m*tan（π/m）*r2，該外切正m邊形內含有ω個隨機點數；該圓內接正m邊形面積為S內=（1/2）*m*sin（2π/m）*r2，其內部含有μ個隨機點數；該圓半徑為r、面積為S圓=πr2，圓內含有Ι個隨機點數。接下來，觀察以下兩個比值表達式：

S外/S圓=（m*tan（π/m）*r2）/（π*r2）=ω/Ι? π=（m*tan（π/m））*Ι/ω，

S內/S圓=（（（1/2）*m*sin（2π/m））*r2）/（π*r2）=μ/Ι?π=（（1/2）*m*sin（2π/m））*Ι/μ，有rto=（m*tan（π/m））/（（1/2）*m*sin（2π/m））=2*tan（π/m）/sin（2π/m）=Ι/（cos（π/m））2。

當m增大時，π/m減小，cos（π/m）增大，rto減小。因為π/m→0，（cos（π/m））2→1，所以rto→1+。當ω＜rto*μ時，π∈［（0.5*m*sin（2π/m））*Ι/μ，（m*tan（π/m））*Ι/ω］。而且，隨著m的增大，圓外切正m邊形面積、圓內接正m邊形面積越來越接近圓面積，區間［（（1/2）*m*sin（2π/m））*Ι/μ， （m*tan（π/m））*Ι/ω］減小。

（四）案例背景人物及其人生啟示

圓周率先驅人物南北朝時期的祖沖之最著名的學術成就就是對圓周率的計算方面所做出的杰出貢獻。縱觀祖沖之一生非凡的學術成就，可以感受到的啟示如下。

1.“成長環境建設”是素質教育的必修課。祖沖之的祖父是那個時代數一數二的土木工程專家，父親學識淵博經常出席皇家禮會。因為祖輩、父輩的言傳身教，祖沖之自幼養成了愛讀書、勤思考的好習慣。

2.興趣與專注是成就科研事業最好的導師。祖沖之天資聰穎、興趣廣泛，在數學、天文、機械等理工科領域表現出極高的天賦，再加上后天的專注與投入，祖沖之在以上方面均取得了卓著的成就。

3.批判性思維是科研創新的源動力，祖沖之視野開闊、文理兼長，常常從多角度、多層次、多方面分析問題，更容易發現前人學術成果中的漏洞之處，不會輕易接受存在質疑的前人觀點，并且給出合理解釋。反過來，這種情況又可以促進科研創新。

（五）結尾

本案例結合圓周率計算的兩種方法即割圓術與隨機投點法為圓周率π的近似值估算提供了一種思路。本文算法時間復雜度為迭代次數，假設迭代次數為n，那么本算法的時間復雜度為O（n）。

二、案例教學實踐

經過案例教學理論分析，本案例擬實現以下教學目標。（1）正確理解割圓術與隨機投點法的概念，掌握隨機化方法的一般設計思想。（2）正確理解割圓法與隨機投點法的特性，掌握由割圓隨機化方法實現的圓周率近似值求解問題，并且能夠從故事中獲得人生啟示。（3）深刻領悟圓周率計算的意義，客觀看待圓周率求解精度對社會生產生活實踐、對科學技術水平的影響，以及與高性能計算力的關系，并能夠從中獲得更多啟發。

課堂教學及時間安排：本案例課堂教學共3學時，學時分配如下。（1）割圓法與隨機投點法概念的描述與講解為0.5學時。（2）基于割圓隨機投點法的圓周率計算問題求解思路的描述與講解為1.5學時。（3）配套思考題的講解為1學時。另外，還要做好課前預習和課中課后討論安排。首先是布置課前預習內容，包括割圓術與隨機投點法的概念定義、割圓隨機化方法實現的圓周率近似值區間估算問題及配套思考題。然后是討論安排，課堂授課方式以教師教授為主，配合與學生線上（雨課堂）、線下互動教學，有一對一方式互動，也有一對多方式互動。課后，教師持續線上（QQ、微信）輔導學生。經過兩個教學周期的課堂教學，學生評分為優秀，學生感受獲益匪淺。

結語

在圓周率計算經典將其問題的基礎上，將割圓術與隨機投點法相結合并將其引入具體案例背景中，并傾注思想與情感，融入課程思政元素，滲入情境教學，鼓勵課程交叉與思想原創。該案例教學可以為課程教學帶來如下積極影響。（1）有利于進行教學改革，改革傳統意義上“注入式”的教學方式。改革“注入式”教學所導致的學生學不透徹、悟不明白的缺陷，通過案例教學，引導學生學會將理論應用于實踐，運用知識去解決實際問題。（2）有利于激發學生的學習積極性，將主體的學生與客體的案例有機結合，發揮學生主人翁精神，使學生在學習上化被動為主動。案例教學是一種動態開放式的教學模式，問題的答案不是封閉的、一成不變的，鼓勵學生探索創新。（3）有利于提高學生善于發現問題、分析問題以及解決問題的實際能力。

案例教學可以實現將知識掌握與智能發展相結合，將教學中掌握知識點由特殊到一般、再到特殊的過程，上升到掌握普通事物的發展規律，從而提升學生認識、理解客觀世界的能力。有利于培養學生形成正確的世界觀、人生觀和價值觀，案例教學可以實現將知識傳授與思想教育相結合。注重融入課程思政元素、弘揚人文精神，使得學生以正確三觀學習文化知識，掌握專業技能。還有利于教師教育教學觀念的轉變，促進教師創新性思維習慣的養成和專業綜合素質的全面提升。

參考文獻

［1］李春葆.算法設計與分析［M］.2版.北京：清華大學出版社，2018：2-38.

［2］陳爭光，唐永生，關海鷗，等.專業學位算法設計與分析課程案例庫建設與實踐［J］.高師理科學刊，2021，41（4）：102-105.

［3］劉霞.圓周率精確到小數點后62.8萬億位［N］.科技日報，2021-08-19（4）.

［4］趙晴，徐震.基于割圓術的DV-Hop全局優化WSNs節點定位算法改進研究［J］.河南理工大學學報（自然科學版），2023，42（2）：127-133.

［5］高博，陳琳，嚴迎建.基于TSDM的抗時間維度隨機化方法研究［J］.電子技術應用，2023，49（2）：86-91.

［6］張夏禹，陳小平.基于目標的域隨機化方法在機器人操作方面的研究［J］.計算機應用研究，2022，39（10）：3084-3088.

Case Teaching Research on Master’s Course Algorithm Design and Analysis： Taking the PI Calculation Problem as an Example

ZHU Xiao-liang， ZHANG Tao， SUN Hua， ZHANG Yan-fang

（School of Software， Xinjiang University， Urumqi， Xinjiang 830008， China）

Abstract： In the environment of “Double first-class” construction in China’s higher education， the construction of first-class universities derives from the construction of first-class disciplines; the construction of first-class disciplines derives from the construction of first-class majors and courses; and the construction of first-class course teaching case database provides a strong guarantee for the construction of first-class majors and first-class courses. Algorithm Design and Analysis is the core course in the teaching system of master’s degree in software engineering. It is of positive significance to explore its case teaching. In this paper， the PI calculation problem based on circle cutting randomization method is taken as an example to construct an original teaching case combining segmentation algorithm and approximate algorithm. This case combines the famous problems in the course， integrates ideological and political elements， highlighting the practicality and originality. Thus， students’ ability to find， analyze and solve problems is systematically cultivated， laying a solid foundation for further training applied senior software talents.

Key words： case teaching; algorithm design and analysis; circumstance ratio; circle cutting algorithm; randomization