碩士課程“算法設(shè)計(jì)與分析”案例教學(xué)探究

［摘 要］ 在中國高等教育領(lǐng)域“雙一流”建設(shè)大環(huán)境下，一流大學(xué)建設(shè)離不開一流學(xué)科建設(shè)，一流學(xué)科建設(shè)離不開一流專業(yè)和一流課程建設(shè)，而一流課程教學(xué)案例庫建設(shè)為一流專業(yè)和一流課程建設(shè)提供了有力保障?！八惴ㄔO(shè)計(jì)與分析”是軟件工程學(xué)科專業(yè)學(xué)位碩士研究生課程教學(xué)體系中的核心課程，探索其案例教學(xué)及其建設(shè)具有積極意義。以基于割圓隨機(jī)化方法的圓周率計(jì)算問題為例，構(gòu)建了分割算法與近似算法相結(jié)合的原創(chuàng)性教學(xué)案例，結(jié)合課程中著名問題，融入思政元素，突出實(shí)踐性與原創(chuàng)性。由此系統(tǒng)地培養(yǎng)學(xué)生發(fā)現(xiàn)問題、分析問題和解決問題的能力，為進(jìn)一步培養(yǎng)應(yīng)用型高級(jí)軟件人才打下堅(jiān)實(shí)的基礎(chǔ)。

［關(guān)鍵詞］ 案例教學(xué)；算法設(shè)計(jì)與分析；圓周率；割圓術(shù)；隨機(jī)化方法

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

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

［中圖分類號(hào)］ G642.0 ［文獻(xiàn)標(biāo)識(shí)碼］ A ［文章編號(hào)］ 1674-9324（2024）29-0125-04 ［收稿日期］ 2023-06-12

案例建設(shè)與實(shí)踐教學(xué)密不可分，在課程中引入案例教學(xué)，建立并不斷豐富教學(xué)案例庫，進(jìn)一步深化產(chǎn)學(xué)研結(jié)合，為深化專業(yè)學(xué)位研究生培養(yǎng)模式改革，優(yōu)化專業(yè)學(xué)位研究生教育結(jié)構(gòu)及健全完善專業(yè)學(xué)位研究生教育課程體系，提供了可靠的理論基礎(chǔ)?！八惴ㄔO(shè)計(jì)與分析”課程作為軟件工程學(xué)科碩士研究生必修的核心課程，對(duì)于學(xué)生邏輯思維能力的培養(yǎng)、自主創(chuàng)新能力的提升，具有至關(guān)重要的作用。該門課程的教學(xué)案例建設(shè)及案例教學(xué)不僅有利于激發(fā)學(xué)生的學(xué)習(xí)熱情與創(chuàng)新的積極性，還有利于培養(yǎng)學(xué)生的專業(yè)實(shí)踐能力，更加有利于進(jìn)一步提高授課教師的教育教學(xué)水平與實(shí)踐創(chuàng)新能力，從而有助于提高專業(yè)學(xué)位建設(shè)與研究生教育質(zhì)量，促進(jìn)軟件工程領(lǐng)域?qū)W科發(fā)展與軟件產(chǎn)業(yè)科技進(jìn)步。這對(duì)于助力“雙一流”建設(shè)具有舉足輕重的社會(huì)意義［1-2］。

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

一、案例教學(xué)設(shè)計(jì)

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

（一）案例主題與背景

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

（二）圓周率計(jì)算問題

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

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

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

正6邊形（m=6）面積對(duì)應(yīng)圓面積情況：首先分別觀察圓外切正6邊形、圓內(nèi)接正6邊形以及圓的相關(guān)屬性。半徑為r的圓外切正6邊形邊長為（2**r）/3、邊心距為r、面積為S外=（2**r2），該外切正6邊形內(nèi)含有ω個(gè)隨機(jī)點(diǎn)數(shù)；該圓內(nèi)接正6邊形邊長為圓半徑r、邊心距為（*r）/2、面積為S內(nèi)=3**r2/2，其內(nèi)部含有μ個(gè)隨機(jī)點(diǎn)數(shù)；該圓半徑為r、面積為S圓=πr2，圓內(nèi)含有Ι個(gè)隨機(jī)點(diǎn)數(shù)。接下來，S外/S圓=（2**r2）/（π*r2）=ω/Ι? π=（2*）*Ι/ω，S內(nèi)/S圓=（（3/2）**r2）/（π*r2）=μ/Ι?π=（（3/2）*）*Ι/μ，所以得出當(dāng)ω＜（4/3）*μ時(shí)，那么有（3*）*Ι/μ＜（4*）*Ι/ω?π∈［*Ι/μ，2*Ι/ω］。

當(dāng)m=12，24，48，…時(shí)繼續(xù)更替迭代。正m邊形（m=12，24，48，…）面積對(duì)應(yīng)圓面積情況：首先分別觀察圓外切正m邊形、圓內(nèi)接正m邊形以及圓的相關(guān)屬性。半徑為r的圓外切正m邊形面積為S外=m*tan（π/m）*r2，該外切正m邊形內(nèi)含有ω個(gè)隨機(jī)點(diǎn)數(shù)；該圓內(nèi)接正m邊形面積為S內(nèi)=（1/2）*m*sin（2π/m）*r2，其內(nèi)部含有μ個(gè)隨機(jī)點(diǎn)數(shù)；該圓半徑為r、面積為S圓=πr2，圓內(nèi)含有Ι個(gè)隨機(jī)點(diǎn)數(shù)。接下來，觀察以下兩個(gè)比值表達(dá)式：

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

S內(nèi)/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。

當(dāng)m增大時(shí)，π/m減小，cos（π/m）增大，rto減小。因?yàn)棣?m→0，（cos（π/m））2→1，所以rto→1+。當(dāng)ω＜rto*μ時(shí)，π∈［（0.5*m*sin（2π/m））*Ι/μ，（m*tan（π/m））*Ι/ω］。而且，隨著m的增大，圓外切正m邊形面積、圓內(nèi)接正m邊形面積越來越接近圓面積，區(qū)間［（（1/2）*m*sin（2π/m））*Ι/μ， （m*tan（π/m））*Ι/ω］減小。

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

圓周率先驅(qū)人物南北朝時(shí)期的祖沖之最著名的學(xué)術(shù)成就就是對(duì)圓周率的計(jì)算方面所做出的杰出貢獻(xiàn)。縱觀祖沖之一生非凡的學(xué)術(shù)成就，可以感受到的啟示如下。

1.“成長環(huán)境建設(shè)”是素質(zhì)教育的必修課。祖沖之的祖父是那個(gè)時(shí)代數(shù)一數(shù)二的土木工程專家，父親學(xué)識(shí)淵博經(jīng)常出席皇家禮會(huì)。因?yàn)樽孑叀⒏篙叺难詡魃斫?，祖沖之自幼養(yǎng)成了愛讀書、勤思考的好習(xí)慣。

2.興趣與專注是成就科研事業(yè)最好的導(dǎo)師。祖沖之天資聰穎、興趣廣泛，在數(shù)學(xué)、天文、機(jī)械等理工科領(lǐng)域表現(xiàn)出極高的天賦，再加上后天的專注與投入，祖沖之在以上方面均取得了卓著的成就。

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

（五）結(jié)尾

本案例結(jié)合圓周率計(jì)算的兩種方法即割圓術(shù)與隨機(jī)投點(diǎn)法為圓周率π的近似值估算提供了一種思路。本文算法時(shí)間復(fù)雜度為迭代次數(shù)，假設(shè)迭代次數(shù)為n，那么本算法的時(shí)間復(fù)雜度為O（n）。

二、案例教學(xué)實(shí)踐

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

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

結(jié)語

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

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

參考文獻(xiàn)

［1］李春葆.算法設(shè)計(jì)與分析［M］.2版.北京：清華大學(xué)出版社，2018：2-38.

［2］陳爭光，唐永生，關(guān)海鷗，等.專業(yè)學(xué)位算法設(shè)計(jì)與分析課程案例庫建設(shè)與實(shí)踐［J］.高師理科學(xué)刊，2021，41（4）：102-105.

［3］劉霞.圓周率精確到小數(shù)點(diǎn)后62.8萬億位［N］.科技日?qǐng)?bào)，2021-08-19（4）.

［4］趙晴，徐震.基于割圓術(shù)的DV-Hop全局優(yōu)化WSNs節(jié)點(diǎn)定位算法改進(jìn)研究［J］.河南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，42（2）：127-133.

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

［6］張夏禹，陳小平.基于目標(biāo)的域隨機(jī)化方法在機(jī)器人操作方面的研究［J］.計(jì)算機(jī)應(yīng)用研究，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