基于生成樹的學生互校驗簽到應用研究

王 芳，蔡 沂

?

基于生成樹的學生互校驗簽到應用研究

王 芳，蔡 沂

（華南理工大學 廣州學院計算機工程學院，廣東 廣州 510800）

文中提出了一種課堂簽到方案，主要思路是通過學生座位信息之間的相互校驗來驗證簽到的真實性。首先，文中描述了該簽到方案的工作流程；然后設計了基于生成樹的相互校驗算法；最后分析了該簽到方案的優勢。分析和測試結果表明：該簽到方案能夠快速產生簽到結果、防止代簽、減少遲到早退；基于該方案的簽到系統實現簡單，具有很強的實用性和推廣價值。

簽到；生成樹；選座；相互校驗；考勤

0 引言

大學課堂簽到可以粗略地分為人工簽到和自動簽到兩類。人工簽到或點名不僅消耗了課堂時間，而且具有較大的局限性，遲到、早退、代簽等現象時有發生。隨著移動互聯網技術的發展，近年來涌現出大批手機簽到系統，如使用無線局域網和手機IMEI的簽到系統[1]、使用藍牙技術和二維碼技術的點名軟件[2]、基于微信公眾號的簽到[3]、基于WIFI的室內定位簽到[4]、基于WIFI熱點和MAC地址的手機簽到[5-6]、基于GPS定位的簽到[7-8]等，但都存在無法精確判斷學生是否在教室內、是否簽到后離開等問題。還有些方案依賴于特定的手機操作系統和網絡設備的支持，在學校推廣和普及的難度較大。

本文提出一種基于生成樹的學生互校驗簽到方案。該方案要求學生在規定時間內提交自己的座位號，并且通過掃碼獲取前后左右的位置信息。系統通過課堂上所有簽到學生位置信息之間的相互校驗生成簽到座位表，簽到座位表直觀地展示了學生的入座情況，方便教師使用手機快速查看和操作。為縮短簽到位置信息的校驗時間，本文提出一種基于生成樹的相互校驗算法。最后，文章分析了基于本方案的課堂簽到系統的優勢。

1 系統設計與功能描述

本文針對大學課堂準確并快速簽到設計一種簽到方案，能較大程度上避免學生抱著僥幸心理逃課、遲到、早退。主要包括學生選座、教師考勤、學生確認入座、系統校驗簽到信息、系統生成簽到座位表、教師管理考勤記錄等功能，所有操作都在手機上完成。圖1給出了此課堂簽到方案的工作流程圖。

圖1 系統工作流程

功能描述如下：（1）學生選座：學生選擇即將要上的課程，進入對應教室座位表頁面選座；（2）開始考勤：教師選擇正在上的課程，進入對應教室座位表頁面查看選座情況，可開始考勤；（3）學生確認入座：教師開始考勤后，教室座位表頁面顯示確認入座倒計時，學生通過掃碼提交前后左右同學的位置信息完成確認入座；（4）系統校驗簽到信息：確認入座倒計時結束，系統通過所有學生位置信息的相互校驗得出每個學生的簽到結果；（5）系統生成簽到座位表：系統根據簽到結果將簽到有效的學生姓名顯示在教室座位表上；（6）教師確認簽到座位表：教師查看簽到座位表，并可修改簽到座位表以應對特殊情況；（7）結束考勤：教師點擊結束考勤按鈕表示完成本次課堂考勤，系統保存本次課堂考勤記錄；（8）管理考勤記錄：課后學生可查看自己的考勤記錄；教師可管理相關課程的考勤記錄，教師還可以登錄PC端后臺完成考勤記錄的統計、匯總和導出等。

2 互校驗簽到理論依據與算法設計

2.1 座位表與選座

大學教室座位一般為m*n型，m為座位行數，n為座位列數。作者所在的學校已存在教室座位表系統，可直接使用。每個座位的座位號按行號和列號來編排，i-j表示第i行第j列座位的座位號（1≤i≤m, 1≤j≤n)。圖2為一個8行8列教室座位示意圖。

圖2 教室座位表

Fig.2 Classroom seating chart

學生上課之前，根據課程信息進入相應教室座位表頁面選座。圖3為某堂課選座座位表，灰色表示該座位已被某學生選中。

圖3 選座座位表

每個選座的學生都將產生一條如表1所示的選座記錄。表中省略了與課程相關的教室和上課時間等信息，本文暫不討論簽到記錄與課程相關信息的關聯。

2.2 確認入座與位置信息

上課后，教師可開始考勤，學生需要確認入座。

表1 選座記錄

Tab.1 Seat selection record

一次有效的簽到需要得到鄰座同學位置信息的證明，確認入座是為了讓學生提交其前后左右位置同學的信息（學生通過掃描鄰座同學的二維碼來提交其位置信息）。由于方向的相對性，當某學生的前方位置有人時，他把前方學生的信息填入自己的‘前位’中，同時他也將被前方位置的學生填入其‘后位’中；當某學生的左方位置有人時，他把左方學生的信息填入自己的‘左位’中，同時他也將被左方位置的學生填入其‘右位’中。左右位置與前后位置同理，不再累述。

系統可設置確認入座時間段，比如學生必須在教師開始考勤后的5分鐘內完成確認入座操作。在確認入座時間段內，已選座的學生還可以重新選座（換座）。學生要確保自己前后左右至少有一個位置有學生坐，這樣才能被他人填入位置信息中，才能使自己得到校驗。學生在確認入座時填寫位置信息后將產生一條如表2所示的位置信息記錄。

表2 某學生的位置信息記錄

Tab.2 A student's location information record

表2為學生‘周圍’的位置信息記錄。根據表2以及前后左右座位的特點，可以由學生‘周圍’確認入座的位置信息得到表3所示的座位對應關系。

表3 由表2得出的學生座位對應關系

Tab.3 The seat correspondence of students is obtained from table 2

用表3的座位對應關系與表1的選座記錄進行對比，不僅校驗了學生‘周圍’的簽到記錄，同時也校驗了學生‘張倩’和‘李悠’。由此可知，并不需要所有的學生都提交前后左右的位置信息，有些學生是主動驗證，如學生‘周圍’；有些學生是被動驗證，如學生‘張倩’和‘李悠’。

接下來我們要討論的問題是：如何利用最少的位置信息驗證選座座位表中所有位置的簽到記錄。

2.3 位置信息的數學表示

2.3.1 無向圖

定義1 無向圖G=，其中：V是非空集合，稱為頂點集；E是V中元素構成的無序二元組的集合，稱為邊集[9]。

若將選擇座位號i-j的學生看成頂點vi, j，圖3的選座座位表可轉化為圖4。

圖4 頂點化的選座座位表

若用座位前后左右的相鄰關系表示邊，則可能與頂點vi, j有關的邊為(vi–1, j, vi, j)、(vi, j, vi+1, j)、(vi, j–1, vi, j)、(vi, j, vi, j+1)，其中1≤i–1, i, i+1≤m，1≤j–1, j, j+1≤n。因此，圖4的選座座位表可表示成一個非連通的無向圖G，G有3個連通分量：G1、G2、G3，如圖5。

由此可得，所有的選座座位表都可以表示成類似圖5的無向圖，連通分量的個數大于等于1。又因為每個學生的前后左右至少有一個位置有同學坐，所以每個連通分量至少包含2個頂點。

2.3.2 生成樹

引理1 如果連通圖 G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹（Spanning Tree）。生成樹是連通圖的包含圖中的所有頂點的極小連通子圖[10]。

引理2 若G是非連通的無向圖，則要若干次從外部調用DFS（Depth First Search深度優先搜索）或BFS（Breadth First Search 廣度優先搜索）算法，才能完成對G的遍歷。每一次外部調用，只能訪問到G的一個連通分量的頂點集，這些頂點和遍歷時所經過的邊構成了該連通分量的一棵DFS或BPS生成樹。G的各個連通分量的DFS或BFS生成樹組成了G的DFS或BFS生成森林[10-11]。

圖5 無向圖G，連通分量G1、G2、G3

由引理1和引理2可知，對于由選座座位表轉換成的無向圖G，通過對G的遍歷找到G的每個連通分量的生成樹，就找到了每個連通分量中連接所有頂點的最短連通路徑。

圖的生成樹不惟一。從不同的頂點出發進行遍歷，可以得到不同的生成樹。[11]對于圖5中無向圖G的連通分量G3，若從頂點v6,1出發進行遍歷，圖6為G3的一棵生成樹，v6,1為樹的根節點。

對于圖5生成樹中的節點，只要父節點位置所代表的學生提交其子節點位置的學生信息，就可以完成對圖中8個節點位置所代表的學生簽到信息的校驗。

2.4 位置信息的收集

根據生成樹中節點之間的父子關系和節點本身的位置關系，系統向每個選座的學生發送收集位置信息的指令。由圖6和表4，座位號6-1的學生接收到的指令為“請提交后方和右方同學信息”，座位號6-2的學生接收到的指令為“請提交前方和右方同學信息，并將你的信息提供給左方同學”，座位號8-2的學生接收到的指令為“請將你的信息提供給左方同學”，諸如此類。根據指令收集到的位置信息如表5所示。

圖6 連通分量G3的生成樹

表4 圖6樹的父子節點關系

Tab.4 The parent-child relationship of the tree in figure 6

表5 收集的位置信息

Tab.5 Collected location information

如果選座座位號為5-2的學生沒來，那么他將不會出現在座位號為6-2的學生的前方位置信息中。

如果選座座位號為8-2的學生沒來，那么他將不會出現在座位號為8-1的學生的右方位置信息中。而座位號為8-1的學生收到了“請提交右方學生信息”的指令卻無信息可填，此時8-1的學生應填寫有人坐的一個方向的同學信息來證明自己的存在（因為每個學生的前后左右至少有一個位置有同學坐，這是學生確認入座的必要條件）。座位號8-1的學生應提交補充信息“前方同學的信息：XXX”。

如果選座座位號為7-1的學生沒來，那么他將不會出現在座位號為6-1的學生的前方位置信息中。而座位號為7-2的學生收到了“請將你的信息提供給左方同學”的指令，當他發現自己的信息無法被填入時（左方位置7-1無人），應填寫有人坐的一個方向的學生信息來證明自己的存在。座位號7-2的學生應提交補充信息“前方同學的信息：XXX”或“后方同學的信息：XXX”。

由此可知，對于由選座座位表轉換成的無向圖G的生成森林，只要生成樹中每個父節點位置所代表的學生填寫其子節點位置的學生信息，且當有節點發現自己的信息無法被填入并且也沒有接收到填入他人信息的指令時能填寫補充信息來證明自己，就能收集到足夠的位置信息與選座座位表進行對比校驗，得出簽到結果。收集位置信息的過程即為獲取簽到記錄的過程，校驗位置信息的過程即為驗證簽到真實性的過程。

2.5 基于生成樹的互校驗簽到算法設計

為了獲得足夠的位置信息與選座座位表進行對比校驗，系統要向選座的學生發送收集位置信息的指令。要向哪些學生發送指令？分別給他們發送什么樣的指令呢？這兩個問題才是獲取位置信息的關鍵所在。

算法1 基于生成樹的互校驗簽到算法。

第1步：根據選座座位表生成無向圖G

第2步：調用DFS（或BFS）算法遍歷無向圖G，生成森林

第3步：對生成森林中的每棵生成樹，根據樹的生成路徑，調用generateOrders算法（見算法2）生成要發送給每個節點的指令

第4步：向每個節點表示的學生發送對應的指令

第5步：獲取學生根據指令提交的位置信息

第6步：將位置信息與選座座位表進行對比，生成簽到座位表

算法1第3步中對每棵生成樹調用名為gen-erate-Orders的算法：數組nodeArr[]用于存儲其生成路徑的節點信息，是算法1第2步的輸出；哈希表orderMap用于存儲節點與應發送給節點的指令列表的鍵值對，初始情況下所有節點對應的指令列表都為空。

算法2generateOrders生成指令算法。

for each fnode in nodeArr[]

for each snode in sonArr[]

orderList_of_fnode.add(orderStr_of_fnode), orderList_of_snode.add(orderStr_of_snode)//將前面構造的指令字符串添加到對應的指令列表中

orderMap.set(fnode, orderList_of_fnode), o-r---d-er-Map.set(snode, orderList_of_snode)//分別更新orderMap中key為fnode和snode的value

end for

end for

通過調用算法2，哈希表orderMap中存儲了要向node節點所表示的學生發送指令列表orderList。

3 系統分析與實現

3.1 算法時間復雜度

算法1第2步，調用DFS和BFS算法遍歷無向圖G，若用鄰接矩陣來實現，時間復雜度均為O(n2)，其中n為頂點數。

算法1第3步，對每棵生成樹調用算法2。因為每棵生成樹至少有2個節點，所以生成樹的數量一定小于n/2。而算法2中，因為每個節點最多有4個子節點，所以時間復雜度為O(n*4)。因此，算法1第3步的時間復雜度為O(n*4*n/2)=O(n2)。

算法1第6步，將位置信息與選座座位表進行對比，時間復雜度也為O(n2)。

因為算法1的時間復雜度集中體現在第2步、第3步和第6步，所以基于生成樹的互校驗簽到算法的時間復雜度為O(n2)[11]。

n為頂點數，即為一堂課上的學生數量。大學課堂一般為兩個行政班合并為一個教學班，人數在120人左右，對于時間復雜度為O(n2)的算法都能很快執行完畢。算法1第4步為發送指令，第5步為表單提交，系統可設置學生必須在發送指令后的5分鐘內完成確認入座。

3.2 實現確認入座

為了防止簽到作弊，教師開始考勤后，系統給每個選座的學生生成限本次考勤使用的二維碼，并設置有效時間，學生通過掃描二維碼來獲取指令中要求提供的鄰座同學的位置信息。如座位號6-1的學生接收到的指令為“請輸入后方和右方同學信息”，表示他要掃描后方和右方位置同學的二維碼；座位號6-2的學生接收到的指令為“請輸入前方和右方同學信息，并將你的信息提供給左方同學”，表示他要掃描前方和右方位置同學的二維碼，并將自己的二維碼提供給左方位置的同學掃描。

3.3 獲得簽到座位表

將學生在確認入座時間段內提交的位置信息與選座座位表進行對比校驗，可得出簽到座位表如 圖7。

圖7 簽到座位表

教師可查看并修改簽到座位表，以應對特殊情況的出現。如有學生忘帶手機，教師可幫學生簽到。當教師認為不再需要修改簽到座位表時，可確認簽到座位表以完成本次考勤。

3.4 非正常簽到分析

開始考勤后，系統向選座的學生發送收集位置信息的指令，學生根據指令提交位置信息以確認入座，學生必須在規定時間段完成確認入座。教師可自主選擇考勤的時間，遲到或早退的學生很可能不能按時完成確認入座，也就無法簽到成功。

系統根據選座記錄和確認入座記錄快速生成簽到結果，教師可以實時查看簽到座位表。教師在確認簽到座位表之前可以修改簽到座位表，如教師在上課過程中發現有位置完成簽到卻無人，可判斷為早退，可點擊相應座位取消其簽到或修改成早退狀態。

4 結語

本文提出基于生成樹的學生互校驗簽到方案，利用學生之間的位置信息進行相互校驗，不但提高了簽到的效率，而且保證了簽到的真實性。基于該方案的簽到系統不依賴除手機之外的其他設備、不限于某種手機操作系統。系統全部采用web實現，使它能快速集成到如微信、智慧校園、課程表等其他學生廣泛使用的應用系統或平臺中，具有很強的實用性和推廣價值。

簽到的前提是選座，類似于電影院選座。對于一些有較多學生感興趣、教師授課方式生動的課程，可能會出現“前排搶座”現象，在線選座也達到了在線搶座的目的。從心理學的角度來說，選座（搶座）行為可以提高學生上課的積極性。[12]

簽到活動的第二步是確認入座，由教師主動發起。教師可根據實際情況決定是否對本堂課考勤，開始考勤才會有確認入座流程。簽到活動由學生通過互動完成，確認入座增強了學生簽到的主動性，是一種積極的心理暗示。

大學課堂的座位選擇與教學情況緊密相關。教師預覽系統生成的簽到座位表，可以加深教師對學生的了解，使教師更好地把握課堂教學。系統將累計產生大量選座數據，這些數據不但可以用來分析學生上課時的座位分布對學生成績的影響[13]，而且可以分析教師的授課形式和授課質量對學生學習積極性的影響。分析學生上課時的座位分布對學生成績的影響，讓老師更加了解學生，對成績不好的學生進行勸導；分析教師的授課形式和授課質量對學生學習積極性的影響，讓老師對自己的教學方式和手段進行反思，推動教學改革。[14]

[1] 劉冬梅, 任亞平, 周杰等. 基于Android的手機簽到系統[J]. 科技資訊, 2017, 14: 17-18.

[2] 陳三清, 殷鵬. 基于Android手機的課堂點名軟件設計與實現[J]. 電腦知識與技術, 2017, 7, 95-99.

[3] 陳東偉, 譚建新, 溫家成等. 基于微信的考勤信息管理系統設計與實現[J]. 信息技術, 2017, 5, 85-88.

[4] 蔣航, 蔡秋楓. 基于室內定位的學生簽到系統設計[J]. 電腦知識與技術, 2017, 1, 54-55.

[5] 趙靚, 張玉. 基于WIFI熱點的手機簽到系統設計[J]. 計算機編程技巧與維護, 2017, 6, 59-61.

[6] 肖俊生, 劉俊娟. 基于WI-FI的學生考勤系統研究與設計[J]. 工業控制計算機, 2017, 1, 114-115.

[7] 張勁波, 周澤崇, 李雅杰等. 基于Android的上課簽到軟件分析與設計[J]. 電腦編程技巧與維護, 2017, 2(3), 28.

[8] 徐寧. 基于微信平臺的并行簽到考勤管理系統[J]. 電腦知識與技術, 2016, 30, 77-79.

[9] 耿素云, 屈婉玲, 張立昴. 離散數學[M]. 北京: 清華大學出版社, 2013.

[10] 李明哲等. 圖論及其算法[M]. 北京: 機械工業出版社, 2010.

[11] 嚴蔚敏, 吳偉民. 數據結構(C語言版)[M]. 北京: 清華大學出版社, 2011.

[12] 王會廷, 張艷平, 閻慧. 大學生課堂行為的心理學研究[J]. 安徽工業大學學報: 社會科學版, 2012, 29(3): 37-38.

[13] 王映學, 段寶軍, 張曉州. 大學課堂座位選擇與學業成績的關系研究[J]. 重慶高教研究, 2017, 5(3): 65-72.

[14] 程永佳. 大學課堂有效教學的影響因素及提高策略[J]. 教育與教學研究, 2012, 26(5): 22-25.

Research on Class Sign_in Application Based on Validation between Classmates using Spanning Tree

WANG Fang, CAI Yi

(Guangzhou College of South China University of Technology, Guangzhou 510800, Guangdong, China)

In this paper, we put forward a class sign-in solution which verify the authenticity of sign-in by the seat information of classmates. Firstly, the work flow of this solution is described; secondly, the mutual validation algorithm based on Spanning Tree is described; finally, the greatest strengths of our solution are analyzed. Analysis results and test results show that using our solution can produce accurate sign-in results, prevent cheating, reduce arrive late and leave early, and the class sign-in system based on our solution is simple and very practical and has strong promotional value.

Class sign-in; Spanning Tree; Seat selection; Mutual validation; Attendance

TP311

A

10.3969/j.issn.1003-6970.2018.07.002

廣東省高等學校特色專業建設項目(JY170102)

王芳(1986-)，女，助教，主要研究方向：軟件工程、大數據技術；蔡沂，(1978-)，女，副教授，主要研究方向：網絡工程、信息安全。

本文著錄格式：王芳，蔡沂. 基于生成樹的學生互校驗簽到應用研究[J]. 軟件，2018，39（7）：06?-11