學(xué)習(xí)空間理論的ACM競(jìng)賽關(guān)鍵學(xué)習(xí)路徑算法

何秋紅，孫文,鄭文彬,朱月秀

(1.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院,福建 漳州 363000;2.閩南師范大學(xué) 福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室,福建 漳州 363000;3.汕頭大學(xué) 理學(xué)院,廣東 汕頭 515000)

學(xué)習(xí)空間理論(Learning Spaces Theory,簡(jiǎn)稱LST)源于知識(shí)空間理論(Knowledge Spaces Theory,簡(jiǎn)稱KST),是由美國(guó)數(shù)學(xué)心理學(xué)家Jean-Claude Falmagne和比利時(shí)數(shù)學(xué)心理學(xué)家Jean-Paul Doignon(以下簡(jiǎn)稱JCF和JPD)于1985年提出并完善的組合數(shù)學(xué)理論,為用機(jī)器自動(dòng)評(píng)估學(xué)生知識(shí)的應(yīng)用提供了一個(gè)完整的理論框架。它通過(guò)分析學(xué)生對(duì)某個(gè)專(zhuān)業(yè)領(lǐng)域中一系列精挑細(xì)選的難易程度不同問(wèn)題的解答情況,盡可能精確而高效地判定學(xué)生對(duì)該領(lǐng)域知識(shí)和技能的掌握程度。后來(lái)發(fā)現(xiàn)知識(shí)評(píng)估機(jī)器其實(shí)可以作為一種教學(xué)技術(shù)的核心組件,因?yàn)闇?zhǔn)確地判斷學(xué)生的知識(shí)狀態(tài)正是教學(xué)過(guò)程的關(guān)鍵一環(huán),從而把焦點(diǎn)從評(píng)估轉(zhuǎn)向教學(xué),就引出了一個(gè)特殊的知識(shí)空間,即“學(xué)習(xí)空間”[1-2]。JCF和JPD不僅提出了理論,還開(kāi)發(fā)了體現(xiàn)這一理論的數(shù)學(xué)教學(xué)軟件ALEKS(Assessment and Learning in Knowledge Spaces,https:∥www.aleks.com)。目前ALEKS教學(xué)軟件提供數(shù)學(xué)、化學(xué)和物理課程,用以評(píng)估學(xué)生在這些科目的知識(shí)狀態(tài)并指導(dǎo)他們的學(xué)習(xí)過(guò)程。這套系統(tǒng)已經(jīng)在數(shù)千所學(xué)校的100門(mén)以上的課程中得到廣泛應(yīng)用,數(shù)百萬(wàn)學(xué)生因此在某些專(zhuān)業(yè)領(lǐng)域受益。受到ALEKS的啟發(fā),還誕生了一些類(lèi)似的系統(tǒng):RATH(1998)、APeLS(2002)、iClass(2008)、MedCAP(2009)、Lee(2014)等[3-4]。

國(guó)內(nèi)關(guān)于學(xué)習(xí)空間理論研究主要有三個(gè)方面:(1)知識(shí)空間理論擴(kuò)展的研究。研究員孫波于2004年對(duì)知識(shí)空間理論進(jìn)行擴(kuò)展,提出包含技能結(jié)構(gòu)、技能空間以及技能層次相關(guān)概念的擴(kuò)展知識(shí)空間理論,并概述該理論在測(cè)評(píng)系統(tǒng)中的相關(guān)運(yùn)用[5]。同年,孫波提出了基于擴(kuò)展知識(shí)空間理論的自適應(yīng)測(cè)評(píng)的詳細(xì)步驟,并對(duì)其中的關(guān)鍵過(guò)程做了進(jìn)一步的優(yōu)化[6]。2006年孫波的合作者傅騫按照擴(kuò)展知識(shí)空間理論的觀點(diǎn),提出新一代教育資源平臺(tái)應(yīng)該把資源分成問(wèn)題對(duì)象、技能(知識(shí)點(diǎn))對(duì)象和學(xué)習(xí)對(duì)象三個(gè)既相對(duì)獨(dú)立又密切聯(lián)系的部分,從而使教育資源庫(kù)不再單一地為教師的教學(xué)服務(wù),還為學(xué)生的自主學(xué)習(xí)、自我評(píng)價(jià)服務(wù)[7]。(2)部分學(xué)者致力于應(yīng)用該理論到輔助教學(xué)。比如應(yīng)用學(xué)科已有計(jì)算機(jī)[8-10]、物理化學(xué)[11-13]、語(yǔ)文英語(yǔ)[14]等。為國(guó)內(nèi)研究者更好地掌握應(yīng)用學(xué)習(xí)空間理論,JCF和JPD所著的學(xué)習(xí)空間中譯本已于2016年由胡祥恩教授和王泰合作完成[15]。2019年,牟智佳等開(kāi)發(fā)了基于知識(shí)空間理論的學(xué)習(xí)預(yù)警工具[16]。(3)部分學(xué)者把學(xué)習(xí)空間理論與其他學(xué)科建立聯(lián)系,高純從粒計(jì)算的視角將知識(shí)空間理論與粗糙集理論建立起有意義的聯(lián)系[17];2019年,李進(jìn)金教授綜述了通過(guò)知識(shí)基建立知識(shí)空間和形式背景之間的聯(lián)系[18]。

目前學(xué)習(xí)空間理論應(yīng)用主要集中在邏輯性強(qiáng)的理工專(zhuān)業(yè)領(lǐng)域的學(xué)習(xí)和教學(xué),但是該理論的應(yīng)用前景非常遠(yuǎn)大,它還可以用于競(jìng)賽。競(jìng)賽比教學(xué)更具挑戰(zhàn)性,因?yàn)楦?jìng)賽綜合了多門(mén)專(zhuān)業(yè)課知識(shí),不僅知識(shí)點(diǎn)多而且難度大,例如ACM考核知識(shí)點(diǎn)達(dá)300多個(gè)。因此,應(yīng)用學(xué)習(xí)空間理論對(duì)競(jìng)賽解答情況分析尤其重要。

主要貢獻(xiàn)包括4個(gè)方面:

1) 推測(cè)關(guān)系確定題目難度等級(jí);

2) 提出兩種方案:學(xué)習(xí)路線方案和學(xué)習(xí)路徑方案:學(xué)習(xí)路徑是最大鏈,一次掌握一個(gè)問(wèn)題;學(xué)習(xí)路線并非最大鏈,一次可能掌握兩三個(gè)問(wèn)題,比路徑粒度更粗。當(dāng)問(wèn)題規(guī)模很大時(shí)選擇知識(shí)基導(dǎo)出若干學(xué)習(xí)路線更快速,且無(wú)須算法,操作更方便;

3) 設(shè)計(jì)MaxPath算法查尋關(guān)鍵、一般和個(gè)別學(xué)習(xí)路徑,實(shí)驗(yàn)結(jié)果證明關(guān)鍵學(xué)習(xí)路徑適合大眾認(rèn)知過(guò)程;

4) 關(guān)鍵學(xué)習(xí)路徑結(jié)合OJ平臺(tái)創(chuàng)新評(píng)價(jià)機(jī)制激發(fā)做題興趣和挑戰(zhàn)高難題,并用于評(píng)估選手水平,為后期重現(xiàn)賽和新賽定制個(gè)性化高效訓(xùn)練計(jì)劃。

1 ACM競(jìng)賽知識(shí)

ACM競(jìng)賽是國(guó)際計(jì)算機(jī)協(xié)會(huì)(Association for Computing Machinery,ACM)組織的年度賽,始于1970年,是全球歷史最悠久、規(guī)模和影響力最大的國(guó)際大學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽,被譽(yù)為計(jì)算機(jī)軟件領(lǐng)域的奧林匹克。在2018-2019賽季,全球6大洲的115個(gè)國(guó)家和地區(qū),共有3 233所大學(xué)的52 709名學(xué)生、5 411名教師、參加ACM-ICPC的各級(jí)預(yù)賽。根據(jù)規(guī)則,為了保證比賽的公平公正,每個(gè)學(xué)生每年只能參加2個(gè)賽點(diǎn)的比賽,終生只能參加5次大賽、2次世界總決賽,這些規(guī)則為選拔更多計(jì)算機(jī)優(yōu)秀人才創(chuàng)造了條件,使大賽成為培養(yǎng)未來(lái)計(jì)算機(jī)領(lǐng)軍人物的重要平臺(tái)之一。

受此啟發(fā),中國(guó)2015年始辦大學(xué)生程序設(shè)計(jì)競(jìng)賽(China Collegiate Programming Contest,簡(jiǎn)稱CCPC),CCPC是由教育部高等學(xué)校計(jì)算機(jī)類(lèi)專(zhuān)業(yè)教學(xué)指導(dǎo)委員會(huì)主辦的面向全國(guó)高校大學(xué)生的年度學(xué)科競(jìng)賽,旨在激發(fā)學(xué)生學(xué)習(xí)計(jì)算機(jī)領(lǐng)域?qū)I(yè)知識(shí)與技能的興趣,鼓勵(lì)學(xué)生主動(dòng)靈活地運(yùn)用計(jì)算機(jī)知識(shí)和技能解決實(shí)際問(wèn)題,有效提升算法設(shè)計(jì)、邏輯推理、數(shù)學(xué)建模、編程實(shí)現(xiàn)和計(jì)算機(jī)系統(tǒng)能力,培養(yǎng)團(tuán)隊(duì)合作意識(shí)、挑戰(zhàn)精神和創(chuàng)新能力。自從2015年首屆CCPC競(jìng)賽以來(lái),賽事規(guī)模發(fā)展迅猛,已經(jīng)有國(guó)內(nèi)600余所高校的20 000余名大學(xué)生和1 500余名一線教練參與賽事,競(jìng)賽影響力持續(xù)提升,為我國(guó)IT業(yè)的發(fā)展培養(yǎng)和選拔了大批人才。

ACM考核的知識(shí)點(diǎn)涵蓋四部分:(1)程序設(shè)計(jì)語(yǔ)言:輸入、處理、輸出;(2)數(shù)據(jù)結(jié)構(gòu):線性表、樹(shù)、圖;(3)算法:模擬、數(shù)論、組合數(shù)學(xué)、貪心、動(dòng)態(tài)規(guī)劃、高級(jí)數(shù)據(jù)結(jié)構(gòu)、計(jì)算幾何、博弈論;(4)程序設(shè)計(jì)解題策略:特定數(shù)據(jù)結(jié)構(gòu)或者優(yōu)化算法。競(jìng)賽題一般采用六級(jí)難度:Ⅰ簡(jiǎn)單題:程序設(shè)計(jì)語(yǔ)言題。Ⅱ準(zhǔn)簡(jiǎn)單題:數(shù)據(jù)結(jié)構(gòu)題。Ⅲ中等難度偏下:基礎(chǔ)算法、數(shù)學(xué)題。Ⅳ中等難度:算法、數(shù)學(xué)綜合題。Ⅴ中等難度偏上:含解題策略的算法、高級(jí)數(shù)學(xué)題。Ⅵ難題:高級(jí)綜合算法及復(fù)雜含解題策略的算法、大代碼量的模擬題。(本段引自ICPC亞洲第一訓(xùn)練委員會(huì)吳永輝主任課件)

2 學(xué)習(xí)空間理論基本定義在ACM競(jìng)賽的應(yīng)用

JCF和JPD認(rèn)為某一專(zhuān)業(yè)領(lǐng)域知識(shí)可以量化為精心設(shè)置的一系列難易不同問(wèn)題,所有問(wèn)題稱為域,用Q表示,學(xué)生能夠解決某個(gè)問(wèn)題表示掌握了相應(yīng)知識(shí),因此問(wèn)題的設(shè)置具有代表性。學(xué)生在理想條件下能正確解答的部分問(wèn)題集構(gòu)成一個(gè)知識(shí)狀態(tài),多個(gè)知識(shí)狀態(tài)加上Q和空集?形成知識(shí)結(jié)構(gòu),若有限知識(shí)結(jié)構(gòu)滿足封閉性就是知識(shí)空間,若知識(shí)空間還滿足兩個(gè)公設(shè):學(xué)習(xí)的順暢性(Learning Smoothness)和學(xué)習(xí)的持續(xù)性(Learning Consistency),稱為學(xué)習(xí)空間。

每場(chǎng)比賽命題組一般會(huì)出8～13題。賽后有最終排行榜(解答情況),先按答對(duì)題數(shù)排名,題數(shù)相同按做對(duì)題目時(shí)間總和排名,總時(shí)間小的排前,若答對(duì)題目多次提交才通過(guò),每一次未通過(guò)的提交要加20分鐘罰時(shí),罰時(shí)加到總時(shí)間。根據(jù)解答情況把每隊(duì)選手的答對(duì)題集轉(zhuǎn)為一個(gè)知識(shí)狀態(tài),所有選手的知識(shí)狀態(tài)加上?和Q構(gòu)成ACM知識(shí)結(jié)構(gòu),在該知識(shí)結(jié)構(gòu)上做封閉運(yùn)算得到ACM知識(shí)空間,對(duì)知識(shí)空間應(yīng)用學(xué)習(xí)空間理論定理補(bǔ)充部分知識(shí)狀態(tài)張成ACM學(xué)習(xí)空間。

2.1 ACM解答情況數(shù)據(jù)集

數(shù)據(jù)集來(lái)源于2019年7月7日ACM-CCPC江西省程序設(shè)計(jì)大賽,該大賽由中國(guó)教育部計(jì)算機(jī)類(lèi)專(zhuān)業(yè)教學(xué)指導(dǎo)委員會(huì)、中國(guó)大學(xué)生程序設(shè)計(jì)競(jìng)賽組委會(huì)主辦,南昌大學(xué)承辦,是江西省首屆CCPC省賽,省內(nèi)高校83支隊(duì)伍展開(kāi)激烈角逐,同時(shí)還吸引了來(lái)自省外高校的21支隊(duì)伍參加,一共有104支隊(duì)伍,每支有三名隊(duì)員。比賽出11道題目A-K組成問(wèn)題域Q,A:Cotree聯(lián)合樹(shù);B:Math數(shù)學(xué);C:Trap陷阱;D:Wave波浪;E:Packing包裝;F:String字符串;G:Traffic交通;H:Rng隨機(jī)數(shù)發(fā)生器;I:Budget預(yù)算;J:Worker工人;K:Class上課。采用二進(jìn)制表示和存儲(chǔ)ACM數(shù)據(jù)集,選手答對(duì)某道題記錄為1,答錯(cuò)為0,從而得到選手在各道題的解答情況。例如,某隊(duì)在11道題中答對(duì)前五題和最后題,該隊(duì)知識(shí)狀態(tài)為[1,1,1,1,1,0,0,0,0,0,1]。將解答情況轉(zhuǎn)換為形式背景,如表1所示。

2.2 ACM數(shù)據(jù)集的推測(cè)關(guān)系和題目難度等級(jí)

推測(cè)關(guān)系表示問(wèn)題間的位次(precedence)關(guān)系,問(wèn)題有高低位次之分,低位次是高位次的基礎(chǔ),因而掌握高位次問(wèn)題也就可以解決低位次問(wèn)題[19]。從表1得知問(wèn)題域Q={A, B, C, D, E, F, G, H, I, J, K}的知識(shí)空間X={?, {K}, {F, K}, {I, K}, {F, I, K}, {F, J, K}, {I, J, K}, {F, I, J, K}, {F, G, J, K}, {D, F, I, J, K}, {F, G, I, J, K}, {D, F, G, I, J, K}, {A, D, F, G, I, J, K}, {D, F, G, H, I, J, K}, {A, D, F, G, H, I, J, K}, {A, C, D, F, G, H, I, J, K}, Q},共17個(gè)知識(shí)狀態(tài)。公設(shè)[19]:如果K是Q的一個(gè)屬于族X(qián)的非空子集,那么K中存在某個(gè)q,使得K{q}是X的一個(gè)狀態(tài)。根據(jù)公設(shè)X增加了兩個(gè)知識(shí)狀態(tài),得到學(xué)習(xí)空間X’=X∪{A, B, C, D, F, G, H, I, J, K} ∪ {A, C, D, E, F, G, H, I,J, K},共19個(gè)知識(shí)狀態(tài)。計(jì)算可得學(xué)習(xí)空間推測(cè)關(guān)系:∩KK={K};∩KF={F, K}?KF;∩KI={I, K}?KI;∩KJ={J, K}?KJ;∩KG={G, K, F, J}?KG, FG, JG;∩KD={D, K, F, I, J}?KD, FD, ID, JD;∩KA={A, K, F, I, J, G, D}?KA, FA, IA, JA, GA, DA;∩KH={H, K, F, I, J, G, D}?KH, FH, IH, JH, GH, DH;∩KC={C, K, F, I, J, G, D, A, H}?KC, FC, IC, JC, GC, DC, AC, HC;∩KB={B, K, F, I, J, G, D, A, H, C}?KB, FB, IB, JB, GB, DB, AB, HB, CB;∩KE={E, K, F, I, J, G, D, A, H, C}。E推測(cè)關(guān)系同B略。參見(jiàn)表2和圖1。

表1 2019 CCPC江西省程序設(shè)計(jì)正式賽排行榜

表2 競(jìng)賽題的推測(cè)關(guān)系

圖1 競(jìng)賽題的推測(cè)關(guān)系Fig.1 Surmise relation of contest questions

特別注意的是圖1中I和G沒(méi)有推測(cè)關(guān)系,但I(xiàn)和D有推測(cè)關(guān)系,故I無(wú)法嚴(yán)格劃分難度等級(jí),把I難度稍微提高,得到ACM數(shù)據(jù)集的推測(cè)關(guān)系學(xué)習(xí)路線:K→F,J→I,G,D→A,H→C→B,E。根據(jù)該路線結(jié)合命題組的試題分檔規(guī)則分七級(jí)難度:Ⅰ中下簡(jiǎn)單題K是基礎(chǔ)程序設(shè)計(jì)解方程。Ⅱ中等簡(jiǎn)單題F是程序設(shè)計(jì)字符串加乘法原理、中簡(jiǎn)單題J是按比例分配。Ⅲ中上簡(jiǎn)單題I是程序設(shè)計(jì)浮點(diǎn)數(shù)。Ⅳ中等難度偏下D和G都是基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)線性表加上基礎(chǔ)算法暴力法。Ⅴ中等難度A是數(shù)據(jù)結(jié)構(gòu)樹(shù)加上深度優(yōu)先算法、H是數(shù)學(xué)求逆元。Ⅵ中等難度偏上C是高級(jí)數(shù)學(xué)互質(zhì)、容斥原理加上暴力法。Ⅶ難題B是高級(jí)數(shù)據(jù)結(jié)構(gòu)圖上隨機(jī)游走的模型加上概率動(dòng)態(tài)規(guī)劃法、難題E是高級(jí)算法動(dòng)態(tài)規(guī)劃法。

2.3 ACM數(shù)據(jù)集的知識(shí)基學(xué)習(xí)路線

下面定義四個(gè)重要概念:

定義1學(xué)習(xí)路徑[19]。一個(gè)知識(shí)結(jié)構(gòu)(Q,K)(有限或者無(wú)限)的學(xué)習(xí)路徑是偏序集(K,?)中一個(gè)最大鏈L。

定義2最大鏈[19]。對(duì)于所有的C,C’∈L,C?C’或者C’?C,對(duì)于某個(gè)狀態(tài)鏈L’,只要L?L’,都有L=L’。

一個(gè)最大鏈必然包含?和Q。例如,當(dāng)有限域Q包含m個(gè)問(wèn)題時(shí),一條學(xué)習(xí)路徑的形式可能是這樣:??{q1}?{q1,q2}? …?{q1,q2, …,qm}=Q,即滿足任意相鄰知識(shí)狀態(tài)中右狀態(tài)真包含左狀態(tài)的從?(零知識(shí))到Q(所有知識(shí))最長(zhǎng)知識(shí)狀態(tài)序列,從?到Q之間的學(xué)習(xí)路徑有很多條。

定義3關(guān)鍵學(xué)習(xí)路徑(critical learning path)[12]。根據(jù)知識(shí)狀態(tài)的數(shù)量通過(guò)一系列概率計(jì)算,具有最大概率的學(xué)習(xí)路徑。

關(guān)鍵學(xué)習(xí)路徑是反映學(xué)生群體學(xué)習(xí)某領(lǐng)域知識(shí)情況的重要方面。

定義4學(xué)習(xí)路線。一個(gè)知識(shí)結(jié)構(gòu)(Q,K)(有限或者無(wú)限)的學(xué)習(xí)路線是偏序集(K,?)中一個(gè)非最大鏈。

知識(shí)空間的基簡(jiǎn)稱知識(shí)基,它是知識(shí)空間的最小生成組,蘊(yùn)含了知識(shí)空間所有信息。所有問(wèn)題的原子得到知識(shí)基Base={{K}, {F, K}, {I, K}, {F, J, K}, {I, J, K}, {F, G, J, K}, {D, F, I, J, K}, {A, D, F, G, I, J, K}, {D, F, G, H, I, J, K}, {A, C, D, F, G, H, I, J, K}, {A, B, C, D, F, G, H, I, J, K}, {A, C, D, E, F, G, H, I, J, K}},共12個(gè)狀態(tài)。當(dāng)問(wèn)題規(guī)模很大時(shí),可以考慮由基直接得到類(lèi)似學(xué)習(xí)路徑的學(xué)習(xí)路線,因?yàn)橹R(shí)基通常規(guī)模比知識(shí)空間小很多,可以節(jié)約計(jì)算量和存儲(chǔ)空間。學(xué)習(xí)路線比學(xué)習(xí)路徑粒度更粗,本案得到4條學(xué)習(xí)路線參見(jiàn)表3。

2.4 知識(shí)結(jié)構(gòu)圖

圖2采用R語(yǔ)言繪制知識(shí)結(jié)構(gòu)圖:fs<-kfamset(set(set("K"), set("I", "K"), set("F", "K"),set("F", "I", "K"), set("F", "J", "K"), set ("I", "J", "K"), set("F","I", "J", "K"), set("F", "G", "J", "K"), set("D", "F", "I", "J", "K"), set("F", "G", "I", "J", "K"), set("D", "F", "G", "I", "J", "K"), set("A", "D", "F", "G", "I", "J", "K"), set("D", "F", "G", "H", "I", "J", "K"), set("A", "D", "F", "G", "H", "I", "J", "K"), set("A", "C", "D", "F", "G", "H", "I", "J", "K"), set("A", "B", "C", "D", "F", "G", "H", "I", "J", "K"), set("A", "C", "D", "E", "F", "G", "H", "I", "J", "K")))if(require("Rgraphviz")){plot(fs)}。

2.5 ACM數(shù)據(jù)集的MaxPath學(xué)習(xí)路徑算法

為了查尋學(xué)習(xí)路徑,首先用一個(gè)有向圖模型G=(V, E)來(lái)描述知識(shí)空間圖,即從圖2抽象出數(shù)據(jù)結(jié)構(gòu)的有向圖,其中:V是圖G中頂點(diǎn)的集合,E是圖G中邊的集合,每個(gè)頂點(diǎn)表示一個(gè)知識(shí)狀態(tài),每條邊表示兩個(gè)距離最近知識(shí)狀態(tài)的真包含,邊上的權(quán)值表示上面知識(shí)狀態(tài)的隊(duì)伍數(shù),如圖3所示,v2到v4({K}到{F, K})權(quán)值為4,表示有四支隊(duì)伍成績(jī)?yōu)閧F, K}。V(G)={v1,v2, …,v19},E(G)={, , …, }。v1=?,v2={K},v3={I,K},v4={F, K},v5={I, J, K},v6={F, I, K},v7={F, J, K},v8={F, I, J, K},v9={F, G, J, K},v10={D, F, I, J, K},v11={F, G, I, J, K},v12={D, F, G, I, J, K},v13={A, D, F, G, I, J, K},v14={D, F, G, H, I, J, K},v15={A, D, F, G, H, I, J, K},v16={A, C, D, F, G, H, I, J, K},v17={A, B, C, D, F, G, H, I, J, K},v18={A, C, D, E, F, G, H, I, J, K},v19=Q。在有向圖模型中設(shè)計(jì)MaxPath算法求解?到Q的非帶權(quán)最長(zhǎng)路徑為一般學(xué)習(xí)路徑。

圖2 競(jìng)賽題的知識(shí)結(jié)構(gòu)圖Fig.2 The knowledge structurediagram of contest questions

表3 學(xué)習(xí)路線與學(xué)習(xí)路徑比較

圖3 帶權(quán)有向圖GFig.3 Directed graph with weight

MaxPath算法思想:設(shè)置一個(gè)集合Set存放已經(jīng)找到最長(zhǎng)路徑的頂點(diǎn),Set的初始狀態(tài)只包含源點(diǎn)v1(即?),對(duì)vi∈V-Set,假設(shè)從源點(diǎn)v1到vi的有向邊為最長(zhǎng)路徑。以后每求得一條最長(zhǎng)路徑v, …,vk,就將vk加入集合Set中,并將路徑v, …,vk,vi與原來(lái)的假設(shè)相比較,取路徑長(zhǎng)度較大者為最長(zhǎng)路徑。重復(fù)上述過(guò)程,直到集合V中全部頂點(diǎn)加入集合Set中。該算法時(shí)間復(fù)雜度為O(n^2),屬于多項(xiàng)式有效時(shí)間,其中n為頂點(diǎn)數(shù)。

MaxPath算法:查尋關(guān)鍵、一般和個(gè)別學(xué)習(xí)路徑。

Input:競(jìng)賽題知識(shí)空間有向圖

Output:從?到Q的最長(zhǎng)路徑

1)初始化數(shù)組dist、path、num;

2) while(元素個(gè)數(shù)num

3) 在dist[n]中求最大值,其下標(biāo)為k;

4) 輸出dist[k]和path[k];

5) 修改數(shù)組dist和path;

6) dist[k]=0表示已找到源點(diǎn)?到頂點(diǎn)k的最長(zhǎng)路徑。

(注:數(shù)組dist[n]:每個(gè)分量dist[i]表示當(dāng)前所找到的始點(diǎn)v1到終點(diǎn)vi的最長(zhǎng)路徑的長(zhǎng)度。初態(tài)為v1到vi弧上權(quán)值;無(wú)弧dist[i]=-∞。

數(shù)組path[n]:path[i]是一個(gè)字符串,表示當(dāng)前所找到的始點(diǎn)v1到終點(diǎn)vi的最長(zhǎng)路徑頂點(diǎn)串。初態(tài)為v1vi;無(wú)弧path[i]=“ ”,空串。)

首先,程序運(yùn)行非帶權(quán)圖找到兩條一般學(xué)習(xí)路徑(非帶權(quán)指所有邊的權(quán)值為1)。其次,在帶權(quán)圖上分別查找更符合大眾和少數(shù)人認(rèn)知規(guī)律的關(guān)鍵學(xué)習(xí)路徑和個(gè)別路徑,還是應(yīng)用MaxPath算法求解從?到Q的帶權(quán)最長(zhǎng)路徑。最多選手(權(quán)值總和最大)的學(xué)習(xí)路徑就是關(guān)鍵學(xué)習(xí)路徑,而最少選手(權(quán)值總和最小)的學(xué)習(xí)路徑是個(gè)別學(xué)習(xí)路徑。運(yùn)行結(jié)果找到一條關(guān)鍵學(xué)習(xí)路徑和一條個(gè)別學(xué)習(xí)路徑,因此,加權(quán)學(xué)習(xí)路徑比一般學(xué)習(xí)路徑更收斂。

3 實(shí)驗(yàn)結(jié)果與討論

本次比賽共11題,每題答對(duì)得一分,104支隊(duì)伍的平均分為5.298分,標(biāo)準(zhǔn)差為1.961,成績(jī)服從正態(tài)分布,該場(chǎng)比賽成績(jī)改變以往的寶塔狀分布,尤其是K題,百分百通過(guò),得到一致好評(píng)。以下結(jié)合學(xué)習(xí)空間理論的關(guān)鍵學(xué)習(xí)路徑，指導(dǎo)如何在競(jìng)賽中提高大學(xué)生程序設(shè)計(jì)創(chuàng)新與解決實(shí)際問(wèn)題的能力。

3.1 學(xué)習(xí)路線與學(xué)習(xí)路徑比較

從實(shí)驗(yàn)結(jié)果得知各有五條學(xué)習(xí)路徑和路線,共十條,如表3所示。分別以答對(duì)率降序?qū)W習(xí)路徑和推測(cè)關(guān)系學(xué)習(xí)路線作為參考基準(zhǔn),若兩個(gè)問(wèn)題順序與它們?cè)趨⒖蓟鶞?zhǔn)的順序前后相反稱一個(gè)逆序,同級(jí)別問(wèn)題或者兩個(gè)無(wú)推測(cè)關(guān)系問(wèn)題出現(xiàn)一前一后均不算逆序。首先,以答對(duì)率路徑作為基準(zhǔn),關(guān)鍵學(xué)習(xí)路徑：0逆序;個(gè)別學(xué)習(xí)路徑3個(gè)逆序:J→I、G→I和A→H;一般學(xué)習(xí)路徑一：4個(gè)逆序:I→F、J→F、D→G和A→H;一般學(xué)習(xí)路徑二：3個(gè)逆序:I→F、J→F和D→G;推測(cè)關(guān)系路線：1個(gè)逆序:I→J;知識(shí)基學(xué)習(xí)路線一：2個(gè)逆序G→I和A→H;路線二：3個(gè)逆序:J→I、D→G和A→H;路線三：3個(gè)逆序:J→F、D→G和A→H;路線四：2個(gè)逆序:J→F和D→G。其次,以推測(cè)關(guān)系學(xué)習(xí)路線作為參考基準(zhǔn),答對(duì)率降序和關(guān)鍵學(xué)習(xí)路徑有同1個(gè)逆序:I→J;個(gè)別學(xué)習(xí)路徑0逆序;一般學(xué)習(xí)路徑一和二有相同2個(gè)逆序:I→J、I→F;知識(shí)基路線一和二0逆序;三和四有同1個(gè)逆序:I→J。統(tǒng)計(jì)共29個(gè)逆序:7個(gè)I→J、5個(gè)A→H和D→G、4個(gè)I→F和J→F、2個(gè)G→I和J→I,分析原因:1. 作為基準(zhǔn)的答對(duì)率和推測(cè)關(guān)系本身有一個(gè)逆序I→J或者J→I,I比較特殊無(wú)法嚴(yán)格劃分難度級(jí);2. IJ、AH、DG、IF、JF、GI之間本來(lái)就都沒(méi)有推測(cè)關(guān)系,原因是兩題考查內(nèi)容沒(méi)有邏輯關(guān)系難度卻相似,比如,A是數(shù)據(jù)結(jié)構(gòu)樹(shù)加深度優(yōu)先算法H是數(shù)學(xué)求逆元,AH考查內(nèi)容不同,同理DG、FJ、GI和FI,所以出現(xiàn)以上逆序。因此有些題目難度很相似不容易區(qū)分,這些題目集中在中等難題及中等簡(jiǎn)單題之間。

3.2 三種競(jìng)賽學(xué)習(xí)路徑與答對(duì)率比較

除了一般學(xué)習(xí)路徑,個(gè)別和關(guān)鍵路徑均加入概率計(jì)算,從圖4可得,概率效果更好,尤其是關(guān)鍵學(xué)習(xí)路徑,與推測(cè)關(guān)系和答對(duì)率完全符合,采用關(guān)鍵學(xué)習(xí)路徑研究ACM競(jìng)賽學(xué)習(xí),這也與麥裕華[12]和何慶輝[13]在高中化學(xué)的氧化還原反應(yīng)和離子反應(yīng)的研究結(jié)果一致。麥認(rèn)為知識(shí)空間理論提供的關(guān)鍵學(xué)習(xí)路徑是基于學(xué)生知識(shí)和能力具體表現(xiàn)的量化建議,它可以在“補(bǔ)救”和“預(yù)防”這兩方面產(chǎn)生作用,教師可以依據(jù)節(jié)點(diǎn)(題目)的出現(xiàn)順序,依次對(duì)排列較后的節(jié)點(diǎn)進(jìn)行補(bǔ)救教學(xué),補(bǔ)救不是從學(xué)科知識(shí)的邏輯結(jié)構(gòu)出發(fā),而是從學(xué)生實(shí)際的認(rèn)知需求出發(fā),這更加適合學(xué)生的學(xué)習(xí)需求和產(chǎn)生預(yù)期的學(xué)習(xí)效果;在預(yù)防方面,教師備新課時(shí)參考關(guān)鍵學(xué)習(xí)路徑,調(diào)整常規(guī)教學(xué)順序和優(yōu)化教學(xué)設(shè)計(jì),從源頭降低學(xué)習(xí)難度。何討論了從兩方面進(jìn)行補(bǔ)救教學(xué),一是根據(jù)關(guān)鍵學(xué)習(xí)路徑優(yōu)化教學(xué)設(shè)計(jì),二是制作離子反應(yīng)的系列微課供學(xué)生個(gè)性化自學(xué),微課有助于解決教師教學(xué)目標(biāo)定位和學(xué)生學(xué)習(xí)需求存在落差的教學(xué)矛盾;再者何也發(fā)現(xiàn)關(guān)鍵學(xué)習(xí)路徑可為教師的新課備課提供參考。

3.3 OJ平臺(tái)介紹

ACM競(jìng)賽題型只有編程題,每一道題都是一個(gè)實(shí)際應(yīng)用問(wèn)題,要求每支隊(duì)伍三位選手互相配合在五個(gè)小時(shí)內(nèi)綜合運(yùn)用所學(xué)知識(shí)分析和解決問(wèn)題,編寫(xiě)并提交可運(yùn)行程序。這體現(xiàn)ACM競(jìng)賽理念,重點(diǎn)考察知識(shí)的綜合運(yùn)用和編程能力。難點(diǎn)在于知識(shí)的運(yùn)用和編程能力的培養(yǎng),為了攻克難點(diǎn),大部分高校都有自己的ACM競(jìng)賽平臺(tái)——Online Judge,簡(jiǎn)稱OJ。OJ是ACM競(jìng)賽的在線評(píng)判網(wǎng)站,第一次使用需注冊(cè)賬號(hào)和密碼,然后用自己熟悉的語(yǔ)言(Python/Pascal/C/C++/Java)寫(xiě)好源代碼提交,網(wǎng)站實(shí)時(shí)自動(dòng)返回判別結(jié)果:正確通過(guò)AC(Accepted)或者錯(cuò)誤返回,常見(jiàn)錯(cuò)誤:編譯錯(cuò)(Compilation Error)、答案錯(cuò)WA(Wrong Answer)、格式錯(cuò)PE(Presentation Error)、超時(shí)TLE(Time Limit Exceeded)等,只有AC才算做對(duì)一題。選手在第一時(shí)間知道答題結(jié)果,并根據(jù)網(wǎng)站提示信息進(jìn)行程序的再次修改與提交。通常每個(gè)平臺(tái)提供了成千上萬(wàn)道編程題,題目多且雜。選手一般選擇幾個(gè)平臺(tái)來(lái)刷題,國(guó)內(nèi)知名平臺(tái)有北大POJ、浙大ZOJ、杭電HDU、計(jì)蒜客和?？偷?國(guó)外知名平臺(tái)有俄羅斯的Ural州立大學(xué)(http:∥acm.timus.ru/)和俄羅斯薩拉托夫大學(xué)(https:∥codeforces.com/)。后來(lái)出現(xiàn)虛擬在線評(píng)判VJ(Virtual Judge,https:∥vjudge.net/https:∥vjudge.net/),VJ并非常規(guī)OJ平臺(tái),它通過(guò)爬取其他OJ網(wǎng)站題目,選手可以直接在VJ上查找并提交各種OJ網(wǎng)站的題目,然后將題目通過(guò)VJ賬號(hào)在真正的OJ上提交并把結(jié)果返回,相當(dāng)于OJ平臺(tái)的中介,目前VJ網(wǎng)站已經(jīng)包含了35個(gè)OJ平臺(tái),選手使用VJ較為普遍。

3.4 關(guān)鍵學(xué)習(xí)路徑結(jié)合OJ平臺(tái)創(chuàng)新評(píng)價(jià)機(jī)制激發(fā)做題興趣

從表4可知競(jìng)賽題關(guān)鍵學(xué)習(xí)路徑上每題對(duì)應(yīng)的答對(duì)率、難度和具體知識(shí)點(diǎn)(詳見(jiàn)附錄)。ACM競(jìng)賽題目涵蓋了程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)學(xué)四門(mén)學(xué)科的理論知識(shí)和方法,更重要的是將這四門(mén)學(xué)科的知識(shí)融合在一起分析和解決問(wèn)題。首先,采用本案的技術(shù)對(duì)更多歷年賽題查尋關(guān)鍵學(xué)習(xí)路徑,從易到難解析具體知識(shí)點(diǎn)及其相關(guān)應(yīng)用題目,通過(guò)關(guān)鍵學(xué)習(xí)路徑結(jié)合選手的等級(jí)和積分(后面介紹)從易到難地推送適合選手個(gè)人水平的題目,即先AC簡(jiǎn)單題才能做難題,循序漸進(jìn)地培養(yǎng)選手從計(jì)算機(jī)角度思考和解決問(wèn)題的能力,這是參考ALEKS網(wǎng)站。其次,AC每一道題根據(jù)題目難度獎(jiǎng)勵(lì)積分,每做完一個(gè)專(zhuān)題升一級(jí)并按積分兌換獎(jiǎng)品,獎(jiǎng)品是進(jìn)階的學(xué)習(xí)資料包括模擬比賽、測(cè)試數(shù)據(jù)、解題分析、視頻、微課和標(biāo)準(zhǔn)解答程序等,類(lèi)似游戲機(jī)制激發(fā)選手做題興趣,改變傳統(tǒng)評(píng)價(jià)機(jī)制,選手通過(guò)等級(jí)和積分了解個(gè)人實(shí)力。游戲之所以吸引人,一個(gè)重要原因就是它能夠激發(fā)人戰(zhàn)勝困難的勇氣,越是有挑戰(zhàn),挑戰(zhàn)的難度越大,就越能激發(fā)勇者的斗志[20]?？傊?關(guān)鍵學(xué)習(xí)路徑結(jié)合OJ平臺(tái)的創(chuàng)新使得選手不依賴教練的提醒和監(jiān)督,完全能對(duì)自己的訓(xùn)練現(xiàn)狀進(jìn)行準(zhǔn)確的分析和評(píng)價(jià),并進(jìn)一步培養(yǎng)選手的做題興趣、挑戰(zhàn)勇氣和實(shí)戰(zhàn)能力。

3.5 效果分析

關(guān)鍵學(xué)習(xí)路徑與OJ線上平臺(tái)充分結(jié)合。首先,統(tǒng)計(jì)選手們?cè)贠J平臺(tái)的歷史競(jìng)賽和平時(shí)訓(xùn)練數(shù)據(jù),從AC題型和數(shù)量?jī)蓚€(gè)維度對(duì)選手知識(shí)水平特征進(jìn)行向量化描述,評(píng)估選手水平并進(jìn)行等級(jí)劃分;然后,根據(jù)選手群體的競(jìng)賽成績(jī)構(gòu)建學(xué)習(xí)空間;而后,采用貪心算法MaxPath從學(xué)習(xí)路徑中挖掘出關(guān)鍵學(xué)習(xí)路徑,并推送合適難度等級(jí)題給相應(yīng)等級(jí)的選手,為其平時(shí)訓(xùn)練提供個(gè)性化支持服務(wù),關(guān)鍵學(xué)習(xí)路徑可有效提升選手的訓(xùn)練效率、競(jìng)賽成績(jī)和訓(xùn)練滿意度,有利于選手對(duì)知識(shí)的主動(dòng)建構(gòu)、內(nèi)化及遷移,僅靠個(gè)人的精力與智慧難以找到關(guān)鍵學(xué)習(xí)路徑;最后,在OJ平臺(tái)上設(shè)置獎(jiǎng)勵(lì)積分和升級(jí)激勵(lì)引發(fā)選手做題興趣,像玩游戲一樣地訓(xùn)練。該方法可以從爆炸式增長(zhǎng)的繁復(fù)的學(xué)習(xí)資源和活動(dòng)中生成簡(jiǎn)潔、精準(zhǔn)的個(gè)性化學(xué)習(xí)路徑,既能有效解決選手的學(xué)習(xí)迷航與認(rèn)知過(guò)載問(wèn)題,還能促進(jìn)學(xué)習(xí)資源的高效利用。知識(shí)空間理論的發(fā)展為學(xué)習(xí)路徑的實(shí)現(xiàn)提供了理論指引和技術(shù)支撐,使每位選手獲得最適合自己知識(shí)水平的學(xué)習(xí)資料,從而實(shí)現(xiàn)精準(zhǔn)訓(xùn)練。然而對(duì)雙方結(jié)合還處在探索階段,對(duì)于如何結(jié)合雙方以獲得更高效訓(xùn)練效果,仍要從更多細(xì)節(jié)進(jìn)一步研究和實(shí)踐。

4 結(jié)論與討論

提出學(xué)習(xí)空間理論在ACM競(jìng)賽的應(yīng)用框架和技術(shù)路線,主要有三個(gè)方面:(1)競(jìng)賽解題情況轉(zhuǎn)換為形式背景,答對(duì)為1,答錯(cuò)為0,得到二維數(shù)據(jù)表。(2)由(1)得到所有學(xué)生知識(shí)狀態(tài),加上?和Q構(gòu)成知識(shí)結(jié)構(gòu),知識(shí)結(jié)構(gòu)并封閉形成知識(shí)空間,最后根據(jù)公設(shè)張成學(xué)習(xí)空間。(3)在(2)得到的學(xué)習(xí)空間上應(yīng)用貪心算法MaxPath查尋學(xué)習(xí)路徑,應(yīng)用關(guān)鍵路徑結(jié)合OJ平臺(tái)激發(fā)選手做題興趣和挑戰(zhàn)勇氣。未來(lái)工作繼續(xù)學(xué)習(xí)空間理論在ACM的應(yīng)用,結(jié)合關(guān)鍵學(xué)習(xí)路徑與OJ平臺(tái)以獲得更好的訓(xùn)練效果,進(jìn)一步完善技術(shù)細(xì)節(jié)以及改進(jìn)算法。

致謝

胡祥恩教授指導(dǎo)搭建R語(yǔ)言平臺(tái),配置運(yùn)行KST程序環(huán)境,下載所需要的程序包。胡教授作出重要貢獻(xiàn),特致謝忱。

附錄

問(wèn)題B:Math數(shù)學(xué)(解析:圖上隨機(jī)游走的模型、概率動(dòng)態(tài)規(guī)劃法) Avin向客戶出售機(jī)器人,在第二個(gè)0時(shí),Avin拿著機(jī)器人位于數(shù)字軸位置(0,0),他想和機(jī)器人一起去(L,0),他每秒走一單位距離,并且只能停在整數(shù)坐標(biāo),現(xiàn)在他決定遵循以下步行規(guī)則直到他和機(jī)器人一起到達(dá)(L,0):(1)如果Avin隨身攜帶機(jī)器人,則機(jī)器人可能會(huì)以概率p掉落。(2)如果Avin丟下了機(jī)器人,他將以q的概率撿起它,如果Avin到達(dá)(L,0)沒(méi)有機(jī)器人,他將立即轉(zhuǎn)身。(3)如果Avin的機(jī)器人沒(méi)有掉落,則向右走一步;不然他就往左走直到他和機(jī)器人在同一位置?，F(xiàn)在求Avin和機(jī)器人到達(dá)(L,0)所需步行時(shí)間的期望?

問(wèn)題C:Trap陷阱(解析:數(shù)論互質(zhì)、容斥原理、暴力法) Avin正在研究等腰梯形,等腰梯形是凸四邊形有兩條相對(duì)平行的線,兩條等長(zhǎng)的腰和正面積。在這個(gè)問(wèn)題中,我們要進(jìn)一步求兩個(gè)腰不平行(就是標(biāo)準(zhǔn)等腰梯形)。給定n條線,請(qǐng)你找出等腰梯形的數(shù)量,這些等腰梯形都要滿足:他們的4條邊長(zhǎng)度的最大公約數(shù)是1。兩個(gè)全等等腰梯形僅計(jì)數(shù)一次。

問(wèn)題D:Wave波浪(解析:基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)線性表、暴力法)Avin正在研究系列(series),如果滿足以下條件則一個(gè)系列稱為“Wave”:(1)它至少包含兩個(gè)元素;(2)奇數(shù)位置的所有元素都相同;(3)偶數(shù)位置的所有元素都相同;(4)奇數(shù)位置的元素與偶數(shù)位置的元素不同。你得到的序列長(zhǎng)度為n,Avin請(qǐng)你找到最長(zhǎng)“Wave”子系列,子系列是系列的子序列。

問(wèn)題E:Packing包裝(解析:高級(jí)算法動(dòng)態(tài)規(guī)劃法)Avin的倉(cāng)庫(kù)有一條帶m個(gè)出口的包裝線,總共有n種貨物都不在包裝線上,第i個(gè)貨物將在時(shí)間ti發(fā)送到xi出口,Avin每秒可以從一個(gè)出口發(fā)送最多一個(gè)貨物到包裝線。對(duì)于出口i,有一個(gè)關(guān)聯(lián)的緩沖區(qū)大小為ai,貨物可以放在緩沖區(qū)中。但是,在每秒結(jié)束時(shí),如果出口的貨物數(shù)量b大于ai,Avin必須支付使用費(fèi)b-ai。由于Avin想省錢(qián),他請(qǐng)你找到一個(gè)方案,以最低的使用費(fèi)將所有貨物發(fā)送到包裝線。為了完成今天的工作,Avin必須將所有貨物送至包裝線,在時(shí)間ti到達(dá)的貨物可以立即在ti時(shí)刻送到包裝線上。

問(wèn)題F:String字符串(解析:乘法原理)Avin有一個(gè)字符串,他想從中均勻隨機(jī)地選擇四個(gè)字符(允許選擇重復(fù)的字符),請(qǐng)你計(jì)算出四個(gè)字符為“avin”的概率(順序不可顛倒)。

問(wèn)題G:Traffic交通(解析:基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)線性表、暴力法)Avin在十字路口觀察汽車(chē),他發(fā)現(xiàn)有n輛汽車(chē)在東西方向上行駛,第i輛汽車(chē)在ai時(shí)刻通過(guò)交叉路口,南北方向也有m輛車(chē)在跑,第i輛汽車(chē)在時(shí)刻bi經(jīng)過(guò)交叉路口,如果兩輛車(chē)同時(shí)經(jīng)過(guò)交叉路口,將會(huì)發(fā)生交通事故,為了實(shí)現(xiàn)世界愛(ài)與和平,所有在南北方向的車(chē)都會(huì)等待相同的一段時(shí)間,使得任何一輛車(chē)都不會(huì)發(fā)生相撞,請(qǐng)問(wèn)最短的等待時(shí)間。

問(wèn)題H:Rng隨機(jī)數(shù)發(fā)生器(解析:數(shù)學(xué)線性求逆元)Avin正在研究如何分析數(shù)據(jù),給定一個(gè)整數(shù)n,他使用以下公式來(lái)構(gòu)造一個(gè)區(qū)間:首先隨機(jī)等概率地生成一個(gè)介于1和n(含1和n)之間的整數(shù)r,然后均勻地生成另一個(gè)介于1和r(含1和r)之間的整數(shù)l,這樣就構(gòu)造出了一個(gè)區(qū)間[l,r]。Avin使用上述方法構(gòu)造了兩個(gè)區(qū)間,他問(wèn)你兩個(gè)區(qū)間相交的概率是多少?你應(yīng)該輸出p·(q＾(-1))(MOD1,000,000,007)(如果你不知道這意味著什么,請(qǐng)百度逆元),而p/q表示這兩個(gè)區(qū)間相交的概率。

問(wèn)題I:Budget預(yù)算(解析:最低位決定答案)Avin的公司有許多正在進(jìn)行的項(xiàng)目且預(yù)算不同,他公司的預(yù)算四舍五入到小數(shù)點(diǎn)后三位。但是,該公司正在更新系統(tǒng),所有預(yù)算都會(huì)四舍五入到小數(shù)點(diǎn)后兩位,例如,1.004將四舍五入至1.00,而1.995將四舍五入至2.00,Avin想知道由更新引起總預(yù)算的差值。

問(wèn)題J:Worker工人(解析:按比例分配)Avin今天遇到一位有錢(qián)客戶,如果Avin能解決一個(gè)難題,他將獲得一百萬(wàn)美元?，F(xiàn)在有n個(gè)倉(cāng)庫(kù)和m個(gè)工人,第i個(gè)倉(cāng)庫(kù)中的任何工人每天都可以處理ai個(gè)訂單,客戶想知道是否存在一種方案滿足每個(gè)倉(cāng)庫(kù)都處理相同數(shù)量的訂單,請(qǐng)注意每個(gè)工人都要被分配到倉(cāng)庫(kù),沒(méi)有工人可以偷懶。

問(wèn)題K:Class上課 (解析:基礎(chǔ)程序題解方程)Avin有兩個(gè)數(shù)a和b,給出x=a+b,y=a-b,你能計(jì)算出a×b嗎?