資源簡介

教學(xué)設(shè)計(jì)
課程基本信息
課題 4 項(xiàng)目挑戰(zhàn) 利用二叉樹實(shí)現(xiàn)信息加密
教學(xué)目標(biāo)
1.對于給定的問題，能自覺、主動(dòng)地尋求恰當(dāng)?shù)姆绞絹慝@取與處理信息。 2.根據(jù)實(shí)際任務(wù)的需要，恰當(dāng)?shù)剡x擇數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)問題解決中的各種數(shù)據(jù)。 3.在解決問題的過程中，界定問題、抽象特征、建立模型，運(yùn)用合理的方法形成解決問題的方案。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 1. 二叉樹遍歷的相關(guān)技能。 2. 加密與解密過程的實(shí)現(xiàn)。 教學(xué)難點(diǎn)： 1. 從問題中抽象出恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。 2. 設(shè)計(jì)程序?qū)崿F(xiàn)信息加密和解密功能。
教學(xué)過程
1.情景導(dǎo)入： 學(xué)校創(chuàng)新社團(tuán)將舉辦信息安全競賽，你和同學(xué)決定參加“利用二叉樹實(shí)現(xiàn)信息加密”的競賽項(xiàng)目。你(甲方，也就是加密方)需以二叉樹作為載體按照指定的規(guī)則對一個(gè)二進(jìn)數(shù)序列進(jìn)行加密；之后將二叉樹的遍歷序列和密文發(fā)送給同學(xué)。同學(xué)(乙方，也就是解密方)綜合各種信息推導(dǎo)出該二叉樹的結(jié)構(gòu)，完成解密。 2.熟悉加密規(guī)則： 甲乙雙方共同熟悉加密規(guī)則，同時(shí)做以下約定： (1)用數(shù)組表示二叉樹，二叉樹的左孩子邊用“0”表示，右孩子邊用“1”表示 (2)甲方將向乙方發(fā)送二叉樹的前序和中序遍歷序列 設(shè)計(jì)意圖：熟悉加密規(guī)則，確定推導(dǎo)二叉樹的依據(jù)。 3.知識儲(chǔ)備： (1)正確書寫二叉樹的前序、中序和后序遍歷序列。 (2)依據(jù)二叉樹的前序和中序遍歷序列，準(zhǔn)確推導(dǎo)出二叉樹的形態(tài)，并可以用數(shù)組表示。 通過觀察分析各節(jié)點(diǎn)之間的索引關(guān)系，歸納總結(jié)如下結(jié)論： 若當(dāng)前節(jié)點(diǎn)的索引是index，則其左孩子節(jié)點(diǎn)索引是2*index+1，右孩子節(jié)點(diǎn)索引是2*index+2 若某節(jié)點(diǎn)索引是奇數(shù)，則說明其是左孩子節(jié)點(diǎn)，反之則是右孩子節(jié)點(diǎn)。 若當(dāng)前節(jié)點(diǎn)的索引是index，則其父節(jié)點(diǎn)索引是（index-1）//2 設(shè)計(jì)意圖：掌握二叉樹的前序遍歷、中序遍歷和后序遍歷。角色互換，各個(gè)角色的技能提前掌握。 4.項(xiàng)目實(shí)施之前，甲乙雙方需明確各自分工。 甲方需要完成以下內(nèi)容： (1)構(gòu)造合適的二叉樹，并能用數(shù)組表示。 (2)模擬出該二叉樹的三種遍歷序列，并將前序和中序遍歷序列發(fā)給乙方。 (3)基于該二叉樹，對二進(jìn)制數(shù)序列（明文）進(jìn)行加密，并將加密后的密文發(fā)給乙方。 乙方需要完成以下內(nèi)容： (1)根據(jù)甲方發(fā)來的二叉樹的前序和中序遍歷序列，推導(dǎo)出二叉樹的形態(tài)。 (2)依據(jù)加密規(guī)則，基于推導(dǎo)出的二叉樹形態(tài)，對密文進(jìn)行解密。 設(shè)計(jì)意圖：明確項(xiàng)目任務(wù)，逐步實(shí)施。 5.項(xiàng)目實(shí)施 (1)抽象與建模（甲方） 從二叉樹的根節(jié)點(diǎn)開始，遍歷二進(jìn)制數(shù)序列，找準(zhǔn)對應(yīng)的左孩子或右孩子節(jié)點(diǎn)。 若孩子節(jié)點(diǎn)為空，則其父節(jié)點(diǎn)編號即為本輪的密文，同時(shí)回到根節(jié)點(diǎn)開始下一輪編碼。 若二進(jìn)制數(shù)序列遍歷結(jié)束，則當(dāng)前節(jié)點(diǎn)編號即為本輪的密文。 (2)設(shè)計(jì)算法（甲方） ①從二叉樹的根節(jié)點(diǎn)開始，遍歷二進(jìn)制數(shù)序列，若為“0”則遍歷二叉樹的左孩子節(jié)點(diǎn)，若為“1”則遍歷右孩子節(jié)點(diǎn)。 ②若節(jié)點(diǎn)非空，繼續(xù)遍歷二進(jìn)制數(shù)序列；若節(jié)點(diǎn)為空，其父節(jié)點(diǎn)編號即為本輪的密文，結(jié)束本輪編碼，同時(shí)回到根節(jié)點(diǎn)，重新開始新一輪的遍歷。 ③若二進(jìn)制數(shù)序列遍歷結(jié)束，當(dāng)前節(jié)點(diǎn)編號即為本輪的密文。加密過程結(jié)束。 (3)編寫程序并測試（甲方） (4)設(shè)計(jì)算法（乙方） ①遍歷密文，若該編碼節(jié)點(diǎn)為左孩子節(jié)點(diǎn)則用字符“0”記錄路徑，若為右孩子節(jié)點(diǎn)則用字符“1”記錄路徑，自下至上直至找到根節(jié)點(diǎn)為止，逆序記錄路徑串，路徑串即為該編碼解密出的二進(jìn)制數(shù)序列（明文）。 ②繼續(xù)遍歷密文，將各輪解密出的二進(jìn)制數(shù)序列（明文）進(jìn)行迭代，直至密文遍歷結(jié)束，最后輸出解密出的二進(jìn)制數(shù)序列（明文）。解密過程結(jié)束。 (5)編寫程序并測試（乙方） 設(shè)計(jì)意圖：甲方與乙方合作實(shí)現(xiàn)加密和解密過程，驗(yàn)證結(jié)果的正確性，若有誤，需反演并找出錯(cuò)誤原因，彌補(bǔ)知識漏洞。 6.項(xiàng)目總結(jié) 最后從熟悉加密規(guī)則、構(gòu)建二叉樹、如何生成明文、如何解密等方面進(jìn)行總結(jié)回顧，編寫成果報(bào)告。

展開更多......

收起↑