張秀梅 王賀 楊陽
摘? 要:“數(shù)據(jù)結構”是軟件工程專業(yè)的核心專業(yè)基礎課,通過學習培養(yǎng)學生能夠分析數(shù)據(jù)對象特征,根據(jù)問題的需要,確定邏輯結構并選擇合適的存儲結構,實現(xiàn)典型算法設計及性能分析的能力。針對數(shù)據(jù)結構抽象性比較強的特點,文章采用對數(shù)的認識逐步遞進的方式進行相關算法設計,不僅可以提升課程教學效率及質(zhì)量,而且有利于提高學生學習的主動性和創(chuàng)新性。
關鍵詞:數(shù)據(jù)結構;素數(shù);素數(shù)環(huán);魔方陣;數(shù)獨
中圖分類號:TP311.1? ? ? ?文獻標識碼:A 文章編號:2096-4706(2020)07-0024-03
Design of Data Structure Algorithm Based on Number
ZHANG Xiumei,WANG He,YANG Yang
(School of Computer Science and Software Engineering,University of Science and Technology Liaoning,Anshan? 114051,China)
Abstract:“Data Structure” is the core professional basic course of software engineering major,through learning to train students to be able to analyze the characteristics of data objects,according to the needs of the problem,determine the logical structure and choose the appropriate storage structure,to achieve the ability of typical algorithm design and performance analysis. In view of the characteristics of abstract data structure,this paper adopts the logarithmic method to design the relevant algorithm step by step,which can not only improve the teaching efficiency and quality,but also improve the initiative and innovation of students.
Keywords:data structure;prime number;prime ring;magic square;Sudoku
0? 引? 言
“數(shù)據(jù)結構”作為計算機專業(yè)的專業(yè)基礎課程,是計算機考研的必考科目之一,是計算機軟件水平考試、計算機等級考試等相關考試的必考內(nèi)容之一,還是“操作系統(tǒng)”“編譯原理”“數(shù)據(jù)庫”“軟件工程”“人工智能”等其他課程的基礎。“數(shù)據(jù)結構”課程的教學內(nèi)容比較多,知識點相對分散,目前該課程的教學活動都是按照線性結構、樹形結構、圖形結構、查找和排序[1]的順序進行,其教學過程往往是單向灌輸,沒有師生間的雙向互動,沒有足夠時間和空間讓學生進行深層次思考,很少注重學生思維判斷能力以及分析、解決問題能力的培養(yǎng)。同時,由于前期程序設計語言課程掌握得不好,導致學習該課程時感到無從下手,而且“數(shù)據(jù)結構”內(nèi)容比較枯燥,很難激發(fā)學生的學習熱情[2,3]。鑒于此,在課程教學中如何選擇適當?shù)捻椖浚饶芗ぐl(fā)學生的學習興趣,又能培養(yǎng)學生的邏輯思維能力,考慮引入現(xiàn)實中有關數(shù)的問題,以“有趣的數(shù)”開始展開教學活動來拓展學生思維,培養(yǎng)了學生實際動手能力和分析解決問題能力,為今后其他課程的學習打下良好的基礎。
1? 算法設計
數(shù)據(jù)結構指導著各種程序設計語言如何編寫程序,而算法是數(shù)據(jù)結構的靈魂,是貫穿整個“數(shù)據(jù)結構“課程的主線,如何把生活中的實際問題通過分析問題、建立模型、設計算法、編制程序、調(diào)試優(yōu)化等步驟用計算機實現(xiàn)是學習該課程的核心所在。而算法的設計跟數(shù)學是分不開的,一個高效的算法要選取合適的數(shù)據(jù)結構,它們之間是相輔相成的,因此將一些有趣的數(shù)進行歸納,并延伸來設計相應的算法。
1.1? 簡單的數(shù)
自然數(shù)有奇數(shù)、偶數(shù),奇偶的判斷在計算機中用模運算(%)來實現(xiàn),如何判斷一個數(shù)是否為素數(shù)(只能被1和自身整除的數(shù)),進而引申出:
(1)一個大于2的偶數(shù)可以表示為兩個素數(shù)的和,即哥德巴赫猜想;
(2)如果一組整形數(shù)組任何兩個相鄰元素的和為素數(shù),并且首尾的和也為素數(shù),即為素數(shù)環(huán)。
上面的數(shù)據(jù)涉及到的是一個數(shù)或一行數(shù)據(jù),接下來看看工程上應用比較多的矩陣,即多行數(shù)據(jù)。數(shù)字填充游戲——魔方陣(幻方),幻方游戲的規(guī)則:將1到n2的數(shù)字組成n*n階方陣,每條對角線,每行與每列的數(shù)字和都相等,和為n*(n2+1)/2。
根據(jù)n的奇偶性幻方分為:
(1)n為奇數(shù)時稱為奇幻方;
(2)n為偶數(shù)且是4的倍數(shù)時稱為雙偶幻方;
(3)n為偶數(shù)且不是4的倍數(shù)時稱為單偶幻方(圖1為6階幻方)。
單偶幻方算法描述如下:
(1)編寫奇數(shù)幻方,采用“左上行法”,即在當前元素的左上角位置填充元素;
(2)將單偶幻方的方格分割成四個區(qū)間,按照順時針編號為A、B、C、D四個區(qū)間;
(3)每一個區(qū)間實現(xiàn)一個奇數(shù)幻方的填充,填充順序為A、D、B、C;
(4)分別將A、D區(qū)間和B、C區(qū)間的指定元素交換:
A, D區(qū)間交換
line是中間行,magic[row][k + m]和magic[n / 2 + row][k + col]互換;
其它行, magic[row][m]和magic[n / 2 + row][col]互換;
B, C區(qū)間交換
magic[col][3 * n / 4 - l]和magic[n / 2 + col][3 * n / 4 - row]交換
1.2? 數(shù)獨
更進一步地對另一個益智游戲——數(shù)獨(如圖2所示為初級數(shù)獨)進行介紹。數(shù)獨是由9個3*3子矩陣組成的9*9矩陣,每個子矩陣由1~9的數(shù)字組成,且每行每列不能有重復數(shù)字。該算法需要綜合運用表結構來設計,并且采用回溯算法實現(xiàn)對重復元素的判定,回溯法也叫試探法,每次試著往前走,一直走到不通,然后撤回,再重新試探。
算法詳細描述如下:
(1)如圖2所示,建立一個9*9整形矩陣作為數(shù)獨棋盤結構,分割成9個3*3的小宮格(數(shù)獨又稱為九宮格),每一個元素稱為數(shù)格。對每個數(shù)格設計一個候選數(shù)列表,里面包含的候選數(shù)為1~9的數(shù)字,對于已經(jīng)確定的,列表里就只有一個已知數(shù),而對于待填數(shù)格,則將所有可能的候選數(shù)填入;
(2)預處理查詢候選數(shù)列表每一行、列和宮格查找已知數(shù)和候選數(shù)有沖突的項,并將沖突項從列表移走。繼續(xù)執(zhí)行此過程修訂列表,直到候選數(shù)列表的值不再變化;
(3)查找包含有最少候選數(shù)的列表,并隨機選取一個數(shù)作為正確的數(shù)進行猜想。候選數(shù)列表中只有一個數(shù)字時為數(shù)格賦值。同時注意要有標識,以便在后續(xù)的執(zhí)行過程中如果有回退可以恢復;
(4)在每一次可能的猜測過程中,通過回溯遞歸回到步驟(2)。通過這種方式,若當前情況無解的時候回溯,直到所有的候選數(shù)列表有唯一候選數(shù);
(5)當所有的猜測都嘗試之后如果沒有解,則返回false。相反,如果宮格都被填滿,并且驗證通過,則表示數(shù)獨謎題有解。
處理相關單元格核心代碼如下:
bool flag = true;
Cell cell = table[index / 9][ index % 9];
for (inti = 0; i< 9; i++)
{ if (i != index / 9) //同列單元格,可以排除兩個宮格
flag&= cellMethod(table, i, index % 9, index);
if (i != index % 9) //同行單元格,可以排除兩個宮格
flag&= cellMethod(table, index / 9, i, index);
}
//九宮內(nèi)的其它四個單元
for (inti = nineCells[index / 9]; i {for (int j = nineCells[index % 9]; j if (i != index / 9 && j != index % 9) flag&= cellMethod(table, i, j, index); } if (cellMethod == RecoverCellCandidate) cell.Value = 0; return flag; 2? 結? 論 針對應用型本科人才的培養(yǎng)目標,注重實踐能力的教學要求,通過對生活中的數(shù)進行算法設計容易吸引學生的注意力,激發(fā)學生的學習興趣,活躍課堂氣氛,使學生將先驗知識與新知識結合起來,由被動接受知識轉變?yōu)橹鲃咏邮堋⒅鲃犹剿?,知識得到內(nèi)化,這不僅增強了學生對課程的興趣和學習信心,同時增強了學生的自主學習能力和探究能力,并且將上述題目在程序評測系統(tǒng)中展示,學生按照題目要求編寫程序并提交源代碼,評測系統(tǒng)編譯運行程序。通過給定的輸入數(shù)據(jù),由提交程序進行處理,產(chǎn)生輸出結果,系統(tǒng)將該輸出結果與標準的輸出結果進行比對,必須毫無差別才算正確,這需要學生心思縝密、考慮周到?!皵?shù)據(jù)結構”教學內(nèi)容與實際問題有機結合,并將其作為Online Judge System軟件平臺上的實驗項目,學生完成情況較好,還培養(yǎng)了學生的團隊精神,使各層次的學生學習積極性均有提高,較好地完成了教學目標。 參考文獻: [1] 劉小晶,杜選.數(shù)據(jù)結構(Java語言描述) [M].北京:清華大學出版社,2011. [2] 王曉明.基于學生自主和協(xié)作學習的數(shù)據(jù)結構實驗教學模式探索與實踐 [J].高教學刊,2015(22):229-230. [3] 劉家瑛,郭煒,李文新.算法基礎與在線實踐 [M].北京:高等教育出版社,2017. [4] SAHNI S,汪詩林,孫曉東.數(shù)據(jù)結構、算法與應用:C++語言描述 [M].北京:機械工業(yè)出版社,2001. 作者簡介:張秀梅(1978—),女,漢族,遼寧鞍山人,講師,碩士研究生,研究方向:中文信息處理。