培養(yǎng)學(xué)生創(chuàng)新思維和能力算法案例

1、培養(yǎng)學(xué)生創(chuàng)新思維和能力算法案例摘要 高校教學(xué)中的創(chuàng)新性思維和能力的培養(yǎng)直接決定國(guó)家和民族的未來(lái)。通過(guò)對(duì)電路導(dǎo)通可能性和哥德巴赫猜想的算法實(shí)現(xiàn)，討論了算法的導(dǎo)通概率、對(duì)比分析了算法的T(n) 和 S(n) ，實(shí)際運(yùn)行結(jié)果表明，優(yōu)秀的算法案例或題庫(kù)結(jié)合 C/S 架構(gòu)的 MSSE能提高學(xué)生自我學(xué)習(xí)、考試和評(píng)估的效率，提高學(xué)生在算法實(shí)現(xiàn)和分析上的興趣和能力，從而增強(qiáng)學(xué)生在算法實(shí)現(xiàn)中的創(chuàng)新能力。關(guān)鍵詞電路導(dǎo)通；模擬；哥德巴赫猜想；算法分析科學(xué)技術(shù)的迅猛發(fā)展向高等教育提出了新的挑戰(zhàn)，目前各國(guó)在教學(xué)改革中無(wú)不把發(fā)展學(xué)生的創(chuàng)新能力作為教學(xué)過(guò)程的突出重點(diǎn)。培養(yǎng)學(xué)生的創(chuàng)造性思維，就是要培養(yǎng)學(xué)生善于學(xué)習(xí)新知識(shí)和運(yùn)用

2、知識(shí)解決實(shí)際問(wèn)題，成為適應(yīng)能力強(qiáng)，富有創(chuàng)造才能的專(zhuān)門(mén)人才：對(duì)計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生而言，就應(yīng)在算法設(shè)計(jì)、實(shí)現(xiàn)和分析方面，具備更強(qiáng)的獨(dú)立探求新技術(shù)和新方法的能力、創(chuàng)造能力和適應(yīng)能力 1 。 1 算法分析概述 算法分析是計(jì)算機(jī)專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)課程，它是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)原理等課程的重要基礎(chǔ)，主要介紹各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，存儲(chǔ)方法和基本運(yùn)算、排序和查找的原理和方法，以及研究非數(shù)值計(jì)算領(lǐng)域中計(jì)算機(jī)的操作對(duì)象及其內(nèi)在的邏輯關(guān)系，在計(jì)算機(jī)中的存儲(chǔ)方法和基本的算法設(shè)計(jì)與分析技術(shù)2 。在算法分析與設(shè)計(jì)過(guò)程中培養(yǎng)學(xué)生的創(chuàng)造性與發(fā)散思維，需要強(qiáng)化以下三個(gè)方面： （1）算法分析是軟件工程的基礎(chǔ)。學(xué)生重視了工程中

3、的技術(shù)細(xì)節(jié)和開(kāi)發(fā)的規(guī)范性，卻往往忽略了軟件的應(yīng)用領(lǐng)域的問(wèn)題復(fù)雜性，這也是導(dǎo)致軟件危機(jī)和不可預(yù)計(jì)的后期返工和開(kāi)發(fā)成本劇增的重要因素 3 ；應(yīng)用和學(xué)科的不斷分化和綜合、跨學(xué)科、邊緣學(xué)科的出現(xiàn) 1 對(duì)高校學(xué)生的知識(shí)覆蓋面和綜合能力提出了更高的要求。（ 2）算法分析與設(shè)計(jì)是一項(xiàng)講究條理和規(guī)范的技術(shù)專(zhuān)業(yè)。要盡量做到：使用 Option Explicit強(qiáng)制變量聲明、使用常量代替硬編碼、使用枚舉值、使用“ &”字符對(duì)字符串進(jìn)行合并操作、使用Select Case語(yǔ)句進(jìn)行取值比較和判斷、盡量避免使用Goto 語(yǔ)句、盡量縮小變量的作用域4 。（3）善于利用頭腦風(fēng)暴法、戈登技術(shù)等手段，將學(xué)生的直覺(jué)思維與

4、分析思維相結(jié)合、輻合思維與發(fā)散思維相結(jié)合、抽象思維與形象思維相結(jié)合 5 。算法分析與設(shè)計(jì)用例應(yīng)具有典型性、代表性、能發(fā)人深醒，不應(yīng)太淺顯、太難和范圍太廣，通過(guò)用例，應(yīng)充分發(fā)揮學(xué)生在再造想象基礎(chǔ)上的創(chuàng)造想象力。以下通過(guò)兩個(gè)具體應(yīng)用的算法分析來(lái)介紹學(xué)生的創(chuàng)造性思維的培養(yǎng)。2關(guān)于電路導(dǎo)通可能性的模擬算法經(jīng)過(guò)某段時(shí)間后，導(dǎo)體R1、 R2、R3和 R4因損壞而開(kāi)路的可能性均為50%，下面的三種電路連接方法中，哪些方案更能保證 A、B 間的電路導(dǎo)通？我們通過(guò)10000 次模擬試驗(yàn)來(lái)輸出試驗(yàn)結(jié)果，其實(shí)現(xiàn)的 Powerscript 如下：圖 1方案a圖 2方案b圖3 方案 cinteger R1 ，R2，R3

5、， R4 ulong Plan_a ，Plan_b ，Plan_c Plan_a =0/初始化隨機(jī)導(dǎo)通的計(jì)數(shù)器。Plan_b = 0 Plan_c = 0randomize(0)/通過(guò)系統(tǒng)時(shí)鐘，得到隨機(jī)發(fā)生器的種子。for i =1 to 10000 R1 = RAND(101) ； R2 = RAND(101) ； R3 = RAND(101) ； R4 = RAND(101) if (R1 > 51 or R3 > 51) and (R2 > 51 or R4 > 51) thenPlan_a+/判斷連接方案 a 的導(dǎo)通性，并累加方案計(jì)數(shù)器。if (R1 >

6、51)or (R2 > 51 and R3 > 51 and R4 > 51) then Plan_b+ /判斷連接方案 b 的導(dǎo)通性，并累加方案計(jì)數(shù)器。 if (R1 > 51 and R2 > 51) or (R3 > 51 andR4 > 51) then Plan_c+ /判斷連接方案 c 的導(dǎo)通性，并累加方案計(jì)數(shù)器。next if Plan_a > Plan_b + 100 and Plan_a > Plan_c + 100 thenmessagebox("模擬結(jié)果 " ，" 方案 a 導(dǎo)通的可能性更

7、大 ")/輸出試驗(yàn)結(jié)果。 elseif Plan_b > Plan_a + 100 and Plan_b > Plan_c + 100then messagebox(" 模擬結(jié)果 " ， " 方案 b 導(dǎo)通的可能性更大 ") elseif Plan_c >Plan_a + 100 and Plan_c > Plan_b + 100 then messagebox("模擬結(jié)果 " ，"方案 c 導(dǎo)通的可能性更大 ") else messagebox("模擬結(jié)果 "

8、 ，" 測(cè)試結(jié)果 N/A")end if messagebox("隨機(jī)導(dǎo)通次數(shù) " ， "Plan_a ： " + string(Plan_a) +"Plan_b：" & + string(Plan_b) + "Plan_c：" +string(Plan_c)根據(jù)以下的概率統(tǒng)計(jì)公式和算法，計(jì)算出三種連接方案導(dǎo)通性的理論概率：通過(guò)對(duì)模擬算法程序的10 次運(yùn)行，我們將各方案的導(dǎo)通次數(shù)結(jié)果列表如下，以此證明模擬算法的較高仿真度。模擬算法的運(yùn)行結(jié)果或結(jié)論是：方案 a 與方案 b 的電路導(dǎo)通性并無(wú)

9、明顯區(qū)別，但他們都比方案c 易導(dǎo)通。表 1 導(dǎo)通性概率的量化對(duì)比分析連接方案12345678910平均值Plan_a55165587547655475542544456265634544355735539Plan_b55095657554955405509546055785624547955975550Plan_c428943704282430543174180442443704166430643013關(guān)于哥德巴赫猜想的局域驗(yàn)證算法德國(guó)數(shù)學(xué)家哥德巴赫在 1742 年提出一個(gè)猜想：每個(gè)大于 4 的偶數(shù)都是兩個(gè)奇素?cái)?shù)的和，試編寫(xiě)程序來(lái)驗(yàn)證歌德巴赫猜想在 100 以?xún)?nèi)的正確性： Ulong test

10、ed ，prime1 ，prime2 ， exclusion for tested = 4 to 100 step2/tested 為被測(cè)試的100 以?xún)?nèi)的大偶數(shù)。prime1 = 1A ：prime1+for exclusion = 2 tosqrt(prime1)/通過(guò) Sqrt(prime1)的循環(huán)上限來(lái)降低算法的時(shí)間復(fù)雜度 7 。if mod(prime1， exclusion)= 0 then goto A/ 判斷 Prime1 是一個(gè)質(zhì)數(shù)，否則，跳轉(zhuǎn)到A 處，判斷下一個(gè)數(shù)。 nextprime2 = tested -prime1/tested 這個(gè)大偶數(shù)可分解為一個(gè)質(zhì)數(shù) Prime

11、1和 Prime2。for exclusion = 2 tosqrt(prime2)if mod(prime2 ， exclusion) = 0 then goto A/ 判斷 另一個(gè)數(shù) Prime2 是一個(gè)質(zhì)數(shù)，否則，next/ 跳轉(zhuǎn)到 A 處，判斷下一個(gè)數(shù)。 messagebox(“驗(yàn)證結(jié)果”，string(tested) +“ = “ + string(prime1) +“ + “ +string(prime2)/ 通過(guò) messagebox輸出驗(yàn)證結(jié)果 next該算法的漸近時(shí)間復(fù)雜度為：由于算法中的額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，因此，在空間復(fù)雜度方面屬于原地工作模式。我們通過(guò)調(diào)用

12、 Cpu() 函數(shù)來(lái)報(bào)告 Powerbuilder 應(yīng)用程序從運(yùn)行之初到調(diào)用處所流逝的 CPU時(shí)間，單位為毫秒。驗(yàn)證算法的效率應(yīng)由以下 5 個(gè)因素來(lái)決定：算法選用的策略、針對(duì)問(wèn)題的規(guī)模、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量、機(jī)器執(zhí)行指令的速度和書(shū)寫(xiě)程序的語(yǔ)言，對(duì)于同一算法，通常實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低，表2 中，列出了在相同計(jì)算機(jī)硬件環(huán)境下， Powerbuilder和 Quick Basic 代碼在猜想的局域驗(yàn)證上花銷(xiāo)的時(shí)間。表 2 不同語(yǔ)言平臺(tái)的驗(yàn)證算法在相同問(wèn)題規(guī)模下的效率對(duì)比( 單位：毫秒 )問(wèn)題規(guī)模100010，000100，0001000， 00010，000，000Quick

13、 Basic59598171414910908927336Powerbuilder1625063903137966538594 3.1對(duì)稱(chēng)奇素?cái)?shù)的個(gè)數(shù)設(shè)不大于偶數(shù) N 的合數(shù)的個(gè)數(shù)有 F 個(gè)，則：N >F(1)設(shè)不大于偶數(shù)N的奇素?cái)?shù)的個(gè)數(shù)有 （N）個(gè)，它等于 N個(gè)正整數(shù)的對(duì)稱(chēng)奇素?cái)?shù)的個(gè)數(shù)。又設(shè) （ N） 個(gè)奇素?cái)?shù)的對(duì)稱(chēng)奇素?cái)?shù)的個(gè)數(shù)為（ S），不大于偶數(shù) N的 F 個(gè)合數(shù)的對(duì)稱(chēng)奇素?cái)?shù)的個(gè)數(shù)有 （F）個(gè)，則：(2) 3.2奇素?cái)?shù)的對(duì)稱(chēng)奇素?cái)?shù)設(shè)不大于偶數(shù) N 的奇素?cái)?shù)是 si ，則 N-si稱(chēng)為 si 的對(duì)稱(chēng)數(shù)。若 N-si 是奇素?cái)?shù)，則稱(chēng)為 si 的對(duì)稱(chēng)奇素?cái)?shù)，偶數(shù) N 表示為： N=si+

14、(N-si)(3) 綜上所述，得到的結(jié)論是：對(duì)于 N=si+(N-si) ，在奇素?cái)?shù) si 的對(duì)稱(chēng)數(shù) N-si 里面，至少有一個(gè)是奇素?cái)?shù)，它與其對(duì)稱(chēng)奇素?cái)?shù)之和為大偶數(shù) N8 。 4 結(jié)束語(yǔ) 在創(chuàng)新性思維的培養(yǎng)過(guò)程中，教師應(yīng)通過(guò)示范性試驗(yàn)使學(xué)生獲得知識(shí)、鞏固知識(shí)并發(fā)展觀察能力，然后由教師提出有創(chuàng)新和啟發(fā)性的算法題目，指導(dǎo)學(xué)生去獨(dú)立探索和創(chuàng)造性地實(shí)現(xiàn)算法。我們結(jié)合由 Powerbuilder 和 ASA開(kāi)發(fā)的 MSSE（Management System of Self-study andEducational Administration ） 6 的題庫(kù)管理和題庫(kù)輸入模塊，實(shí)現(xiàn)了學(xué)生在算法分析和學(xué)習(xí)過(guò)程中的自主性、激發(fā)了學(xué)生對(duì)算法分析的學(xué)習(xí)積極性、培養(yǎng)和加強(qiáng)了學(xué)生的創(chuàng)新和發(fā)散性思維。 MSSE的實(shí)際運(yùn)行結(jié)果也表明，高質(zhì)量的考試題庫(kù)結(jié)合 CAE能以最低的運(yùn)行成本實(shí)施因材施教，并提高學(xué)生獨(dú)立處理實(shí)際問(wèn)題的興趣和能力。 參考文獻(xiàn) 1 李成良，顧美玲 . 大學(xué)教學(xué)理論與方法 M. 貴陽(yáng)：貴州教育出版社， 1995 2 胡學(xué)鋼 . 數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo) M. 北京：清華大學(xué)出版社， 1999 3 楊明，馬帥 . 軟件測(cè)試和軟件質(zhì)量保證 M. 北京：珠海市豪邁實(shí)業(yè)有限公司， 2003 4 楊明，遙遠(yuǎn) .VB 高級(jí)編程 M. 北京：珠海市豪邁實(shí)業(yè)有限公司， 2003 5