算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)2023秋(信息)

信息科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)（分冊）鹽城師范學(xué)院信息科學(xué)與技術(shù)學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)課程組編2023.9《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計一、概述（一）課程設(shè)計的性質(zhì)、目的與作用數(shù)據(jù)結(jié)構(gòu)是計算機(jī)及其相關(guān)專業(yè)一門重要的核心課程，是學(xué)習(xí)計算機(jī)軟件設(shè)計的重要基礎(chǔ)課程。從實際工作需要來看，僅靠教學(xué)計劃安排的課內(nèi)實踐時間是難以滿足要求的，為了幫助同學(xué)扎實的掌握數(shù)據(jù)結(jié)構(gòu)內(nèi)容，提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)的方法解決實際問題的能力，有計劃、有目的、有系統(tǒng)地進(jìn)行必要的實踐訓(xùn)練，編寫了《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計這部分內(nèi)容。課內(nèi)的實驗是側(cè)重于對某一方面知識的學(xué)習(xí)，在解決實際問題時，可能涉及并運(yùn)用多個方面的知識，具有較強(qiáng)的綜合性，這就需要進(jìn)行一些綜合性的設(shè)計練習(xí)，來提高分析和解決實際應(yīng)用問題的能力。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的目的是利用本課程內(nèi)的以及到目前為止所學(xué)到的有關(guān)知識和技術(shù)解決一些不算太復(fù)雜卻具有綜合性的問題。通過課程設(shè)計，在建立問題模型、構(gòu)造求解算法、設(shè)計數(shù)據(jù)結(jié)構(gòu)、編寫程序代碼及上機(jī)調(diào)試等方面得到全面的鍛煉，從而能更深刻地理解《數(shù)據(jù)結(jié)構(gòu)》的精髓，為后續(xù)軟件課程的學(xué)習(xí)及軟件設(shè)計能力的提高奠定良好的基礎(chǔ)。包括，熟練掌握數(shù)據(jù)結(jié)構(gòu)的一些常用算法和經(jīng)典算法；熟練的運(yùn)用常用的算法和經(jīng)典算法解決具有一定規(guī)模和復(fù)雜程度的實際問題；熟練掌握分析問題和解決問題的方法，合理選擇數(shù)據(jù)結(jié)構(gòu)，學(xué)會分析算法的優(yōu)劣，分析算法的復(fù)雜度。（二）課程設(shè)計的要求在課程設(shè)計時，對要解決的問題，要注意以下幾個方面：正確性：設(shè)計的算法要嚴(yán)謹(jǐn)、正確，能正確解決實際問題，符合指定的要求；高效：有效的建立數(shù)學(xué)模型，合理的選擇數(shù)據(jù)結(jié)構(gòu)，編寫高效的程序代碼；清晰：算法和程序的結(jié)構(gòu)要清晰，算法要用流程圖來表示，程序代碼要加注解；設(shè)計報告：每一個問題解決后，要按統(tǒng)一的紙張及格式，完整、整潔地寫出設(shè)計報告，打印程序清單，拷貝所做設(shè)計的電子版文檔和程序。（三）設(shè)計報告格式在將綜合設(shè)計作為教學(xué)的一個環(huán)節(jié)時，設(shè)計報告一般包括以下幾個方面的內(nèi)容：設(shè)計任務(wù)、要求和所用的軟件環(huán)境和技術(shù)；設(shè)計思想及其簡要說明；設(shè)計的算法，以及算法可能由幾個模塊組成，算法用流程圖表示出來；使用說明，包括使用前提，所用軟件環(huán)境，文件清單；驗收時間，驗收情況說明等；通過課程設(shè)計的收獲以及對所用方法的分析和綜合；打印的程序清單以及結(jié)果，結(jié)果以貼圖的方式附在報告后。二、預(yù)備知識線性表的順序和鏈?zhǔn)奖硎竞蛯崿F(xiàn)棧和隊列的表示和實現(xiàn)以及應(yīng)用遞歸和非遞歸的轉(zhuǎn)化串的表示和實現(xiàn)數(shù)組的應(yīng)用樹及其二叉樹的表示、實現(xiàn)、遍歷和應(yīng)用圖的表示方法及其遍歷和應(yīng)用各種查找方法的實現(xiàn)和分析及應(yīng)用各種排序方法的實現(xiàn)和分析和應(yīng)用三、《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計課題說明：1、不限定開發(fā)語言，Java、Jsp、Asp、C、C#、C++等都行。重在答辯。2、相同情況下，選擇提高題、綜合題與運(yùn)用題的學(xué)生，我們給予10分鼓勵分，優(yōu)先給這三類學(xué)生評優(yōu)。3、要突出數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計思路步驟，代碼中的文檔注釋量不能低于代碼量。重在業(yè)務(wù)分析、模塊接口設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計與操作算法步驟設(shè)計。重在對分析問題、解決問題能力的培養(yǎng)與評定。4、課程設(shè)計報告請嚴(yán)格規(guī)定安格式書寫電子稿，并打印，沒有依格式寫的課程設(shè)計報告檢查后要重新打印，并扣態(tài)度分，打印前請認(rèn)真檢查?？晒┻x擇的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題：基礎(chǔ)題：以下選題為每題限選2人。【課題1】用貪婪法求解“貨郎擔(dān)問題”。所謂“貨郎擔(dān)問題”是指，給定一個無向圖，并已知各邊的權(quán)，在這樣的圖中，找一個閉合回路，使回路經(jīng)過圖中的每一個點，而且回路各邊的權(quán)之和為最小?！菊n題2】背包問題。從N件不同價值、不同重量的物品中選取一部分物品，在不超過規(guī)定重量的情況下，使這部分物品的總價值最大。【課題3】用十字鏈表表示稀疏矩陣，并實現(xiàn)稀疏矩陣加法?！菊n題4】馬的遍歷問題。設(shè)計程序完成如下要求：在中國象棋棋盤上，對任一位置上放置的一個“馬”．均能選擇一個合適的路線，使得該棋子能按象棋的規(guī)則不重復(fù)地走過棋盤上的每一位置。程序輸出8×8方陣，用1－64表示走過每個位置的次序，起始點標(biāo)為1?！菊n題5】編寫程序，初始從鍵盤輸入二叉樹的結(jié)點數(shù)據(jù)創(chuàng)建二叉樹，并將該二叉樹的數(shù)據(jù)以某種方式存儲到文件btree.dat中，以便程序此后運(yùn)行時從文件中讀取數(shù)據(jù)構(gòu)建該二叉樹；要求能根據(jù)指定結(jié)點求出其在二叉樹中所在的層數(shù)。【課題6】若某算術(shù)表達(dá)式采用后置法表示（即逆波蘭表達(dá)式），請編程計算該表達(dá)式的值。如：表達(dá)式(a+b*c)/d-e用后置法表示為abc*+d/e-?！菊n題7】最短路徑問題。用有向圖表示道路網(wǎng)，有向邊上的權(quán)表示兩地間的距離，要對如下圖求出從c1到各點的最短路徑（程序應(yīng)通用）?！菊n題8】若已知一棵二叉樹的先序序列和中序序列（如從鍵盤輸入），設(shè)計算法及程序?qū)崿F(xiàn)構(gòu)造其對應(yīng)的二叉樹?！菊n題9】利用二叉排序樹可以實現(xiàn)集合的插入、刪除和查找操作。編寫程序統(tǒng)計一份英文文獻(xiàn)中單詞使用的頻度。【課題10】設(shè)計程序完成如下功能：對給定的圖結(jié)構(gòu)和起點，產(chǎn)生其所有的深度優(yōu)先搜索遍歷序列（深度優(yōu)先搜索序列不唯一）?！菊n題11】設(shè)計程序完成如下功能：對給定的有向圖，用Kruskal算法的基本思想求解出所有的最小生成樹?！菊n題12】設(shè)計程序完成如下功能：對給定的AOV網(wǎng)，求出該AOV網(wǎng)所有的拓?fù)湫蛄小！菊n題13】設(shè)計程序以實現(xiàn)構(gòu)造哈夫曼樹的哈夫曼算法，并計算出所構(gòu)造的哈夫曼樹的帶權(quán)路徑長度?！菊n題14】設(shè)計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運(yùn)算符及SQR和ABS函數(shù)的任意整型表達(dá)式進(jìn)行求解。【課題15】選擇合適的存儲結(jié)構(gòu)表示圖，在此基礎(chǔ)上實現(xiàn)求解最短路徑的Dijkstra算法。【課題16】若二叉樹采用二叉鏈表存儲，利用棧實現(xiàn)中序線索化二叉樹的非遞歸算法?！菊n題17】設(shè)計一個簡單的文本編輯器，使其具有通常編輯器（如Notepad）具備的功能。【課題18】蘇州園林導(dǎo)游程序設(shè)計。用無向網(wǎng)表示蘇州園林的平面圖，圖中頂點表示著名園林，存放園林的編號、名稱、特色簡介等信息，圖中的邊表示園林間的通路，存放路徑長度等信息。要求實現(xiàn)以下功能：（1）根據(jù)園林名稱或編號查詢各園林的相關(guān)信息；（2）查詢圖中任意兩個園林間的最短路徑；（3）查詢圖中任意兩個園林間的所有路徑?！菊n題19】散列法的實驗研究。散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。給出程序及實驗數(shù)據(jù)對比、分析研究?！菊n題20】“吃金子”游戲在地下某處藏有金子（g），有一個精靈（¤）尋找并獲取金子。游戲者通過輸入四個方向鍵指揮精靈沿該方向移動去吃金子（每輸入一次方向鍵只移動一步）；金子是隨機(jī)地、每隔一段時間出現(xiàn)在不同的位置，游戲者需在金子消失前到達(dá)才能獲取它。游戲者的成績是看其在一定時間內(nèi)獲取的金子數(shù)量計算。如下圖示。所需知識：數(shù)組、隨機(jī)數(shù)、鍵盤輸入碼的識別¤gggg（提示：需要使用一些庫函數(shù)，如：①原型intbioskey(intcmd)所屬頭文件bios.h功能返回鍵盤讀取一個按鍵的ASCII值，兩字節(jié)。Cmd參數(shù)說明：參數(shù)cmd確定實際的操作，cmd取值為返回下一個鍵盤輸入的字符，如果低8位非0，則為ASCII碼；如果低8位為0，則高8位為擴(kuò)展鍵盤代碼—查PCASCII表。測試是否有可讀的輸入鍵，如果返回0，則表示沒有；否則返回下一個輸入鍵。鍵還保存，供下次參數(shù)cmd為0的bioskey調(diào)用返回。請求當(dāng)前移位(Shift)狀態(tài)…②原型voidgotoxy(intx,y)所屬頭文件conio.h功能將光標(biāo)移動到(x,y)坐標(biāo)處。屏幕的坐標(biāo)系左上角為(0,0)。）【課題21】五子棋游戲游戲者A、B對奕五子棋（規(guī)則略），百子用W、黑子用B表示，在一個n*n的棋盤上對奕，棋盤屏幕布局如下圖示例。所需知識：二維數(shù)組。123456789ABCDEFGHIJKLMNO2WBW3BWWBWBBPlayerA:X-Y-PlayerB:X-Y-【課題22】有若干生產(chǎn)者和消費(fèi)者，生產(chǎn)者負(fù)責(zé)生產(chǎn)商品、每生產(chǎn)處一個商品就放入一個環(huán)形緩沖區(qū)中的空閑緩沖區(qū)中供消費(fèi)者取商品消費(fèi)，并檢查是否有消費(fèi)者等待取商品，若有就喚醒他；如果沒有空閑的緩沖區(qū)則排入等待隊列等待消費(fèi)者取走商品后空出緩沖區(qū)。同樣，消費(fèi)者到環(huán)形緩沖區(qū)中找一個存有商品的緩沖區(qū)取商品，如果所有緩沖區(qū)均空（無商品可供消費(fèi)）則排入消費(fèi)者隊列等待，如果有商品可取、取出商品后查看生產(chǎn)者隊列是否有等待的生產(chǎn)者并喚醒他。環(huán)形緩沖區(qū)如下圖所示。所需知識：環(huán)形隊列、鏈隊列?！菊n題23】在網(wǎng)吧管理中，需要在每個客戶用時（下機(jī)）到達(dá)前5分鐘提醒客戶。由于當(dāng)前上機(jī)的用戶數(shù)目不確定、每個用戶的下機(jī)時間不同，所以需要采用鏈表結(jié)構(gòu)的間隔時鐘進(jìn)行管理。鏈表鐘頭節(jié)點中記錄的時間值是相對于當(dāng)前時間還需經(jīng)過的時間、而后繼節(jié)點中記錄的時間值是相對于其前趨節(jié)點的終止時間還需經(jīng)過的時間。系統(tǒng)設(shè)置一個時鐘中斷，時鐘中斷處理程序總是從頭節(jié)點開始檢查需要發(fā)布提醒信息的用戶（節(jié)點）并提醒之，并修改剩余節(jié)點中的間隔時間值（減去頭節(jié)點中的值）。所需知識：鏈表?！菊n題24】老鼠走迷宮。有一個n*n格的迷宮，有些格子是墻不能通過、而另一些是通道可以通行。整個迷宮有一個入口和一個出口，四周也是墻。老鼠從入口進(jìn)入順可以通行的通道前進(jìn)，當(dāng)遇到無法通行的墻時就需要嘗試另一方向前進(jìn)、……直到所有方向（除了進(jìn)入得方向）嘗試完還不能前行，就得后退再尋找出路。所需知識：數(shù)組、回溯程序設(shè)計。提示：用數(shù)組Maze[n][n]表示迷宮，標(biāo)志數(shù)組mark[][]用來記錄已走過的位置，還要能對下一步前進(jìn)方向計算出下已位置等。見下圖示。入口--0001111111111111100000110001010110110011000101011000100001010101100000110001010110000011110101011000001100010101100000110011010110000011000001011111111111110111【課題25】設(shè)有一算術(shù)表達(dá)式，參與運(yùn)算的數(shù)據(jù)均為1位數(shù)字、并且只使用加、減、乘、除四則運(yùn)算和圓括號，編程實現(xiàn)該表達(dá)式求值計算。所用知識：棧和字符串。提示：教材上有該題的算法，需具體實現(xiàn)。也可以參考其他方法。【課題26】將n個名字（每個名字步超過10個字符--可英文單詞表示）建立成一個單鏈表，節(jié)點中包含名字、原（輸入時的）序號、指向下一個節(jié)點的指針。然后將這些名字按字典順序排序。要求：將原名單按行輸出：名字、序號按排序后的名單順序輸出，包括：名字、原序號。所用知識：鏈表。思考：你所用的排序算法對于鏈表來說，性能如何？你認(rèn)為哪個算法更適合鏈表排序？【課題27】電腦搖獎。電視臺常從成千上萬的號碼中搖出獲獎?wù)?，設(shè)計一種存放這些號碼的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計兩種或兩種以上的算法對其搖獎，要求搖獎算法做到公平，比如，每次被選出的號碼與號碼存放的位置無關(guān)、分布均勻、每個號碼的獲獎機(jī)會均等。所需知識：表、查找或許還用到散列。【課題28】設(shè)計一個程序，完成以下功能：1）建立學(xué)生信息管理的數(shù)據(jù)文件stud.dat;文件中至少包含30個學(xué)生的信息；每個學(xué)生至少包括：學(xué)號、姓名、年齡、課程成績等5項內(nèi)容（另2項自定），當(dāng)程序運(yùn)行后發(fā)現(xiàn)數(shù)據(jù)文件不存在（如初始運(yùn)行）、應(yīng)從鍵盤輸入學(xué)生信息數(shù)據(jù)并創(chuàng)建數(shù)據(jù)文件；若數(shù)據(jù)文件已經(jīng)存在則從該文件中讀取數(shù)據(jù)；2）可以添加（插入、追加）學(xué)生信息；3）可以修改某個學(xué)生的某項信息；4）能統(tǒng)計并顯示某門課程不及格學(xué)生的信息?！菊n題29】設(shè)計一個程序，完成如下功能：從一個C語言源程序文件中，統(tǒng)計出該C程序中使用的關(guān)鍵字及其頻率。統(tǒng)計結(jié)果表格保存到文件keyword.txt中。【課題30】偶交換排序如下所述：第一趟對所有奇數(shù)i，將a[i]與a[i+1]進(jìn)行比較；第二趟對所有偶數(shù)i，將a[i]與a[i+1]進(jìn)行比較，若a[i]>a[i+1]則進(jìn)行交換；依此類推，繼續(xù)對奇數(shù)i和偶數(shù)i進(jìn)行上述比較和交換，直到整個序列有序為止。要求：程序在初始時從鍵盤輸入數(shù)據(jù)，將這些數(shù)據(jù)用偶交換排序，將排序后的數(shù)據(jù)存儲到文件even_sort.dat中，然后根據(jù)用戶輸入的關(guān)鍵字，將數(shù)據(jù)讀入內(nèi)存采用二分查找算法進(jìn)行查找，若存在則輸出其排序后的序號，否則顯示相關(guān)信息?！菊n題31】拼寫檢查。問題描述微軟的Word有一個拼寫檢查功能，如果你拼寫錯了單詞，它會用紅線標(biāo)出以示提醒，然后給出可能正確的單詞。現(xiàn)在要你編程實現(xiàn)類似的一個系統(tǒng)：給定一個詞表以及一個待檢查的單詞，判斷這個單詞是否在詞表中，如果不在詞表中，程序應(yīng)該給出一個相似的單詞。在尋找相似的單詞時，你只需要考慮如下幾個簡單的情況：1、漏寫了一個字母，如把a(bǔ)bacus誤拼寫為abacs2、多寫了一個字母，如把a(bǔ)bacus誤拼寫為abaacus3、將某處的一個字母寫成了另一個字母，如abacus誤拼寫為abacup編程實現(xiàn)這個系統(tǒng)。輸入格式輸入數(shù)據(jù)的第一行是一個由小寫字母組成的字符串，表示要進(jìn)行拼寫檢查的單詞第二行是一個數(shù)N（1<=N<=100）,表示詞表中詞的數(shù)目接下來有N行，每行都是一個由小寫字母組成的字符串，代表詞表中的每一個單詞所有字符串的長度在2到20之間輸出格式僅輸出一個字符串：1、如果要檢查的單詞在詞表中出現(xiàn)，則原樣輸出該單詞2、如果要檢查的單詞在詞表中未出現(xiàn)，但在詞表中找到相似的單詞，則輸出在詞表中和它相似的那個單詞。如果在此表中找到多個相似單詞，僅輸出在輸入文件中最靠前的一個。3、如果要檢查的單詞在詞表中未出現(xiàn)，并且在詞表中找不到與它相似的單詞，輸出NOANSWER樣例輸入abstaine4abacusabstractabstainabstainer樣例輸出Abstain【課題32】做明智的消費(fèi)者。問題描述鹽師里面有很多超市，但是有的商品在這個超市里便宜些，有的商品在另一個超市里便宜些。周末大購物的時候，超超想從1號超市逛到n號超市，然后把該買的東西(從1到m編號)都用最便宜的價格買到，你的任務(wù)是幫幫他決定在哪個超市應(yīng)該買什么商品。輸入格式輸入數(shù)據(jù)第一行是兩個數(shù)nm，表示有n個超市和m個該買的商品。(1<=n<=501<=m<=100)接下來是nXm的矩陣Aij，其中第i行第j列表示i號超市中j商品的價格（小于100的非負(fù)整數(shù)），Aij=0則表示j商品無法在i超市找到。輸入數(shù)據(jù)不能保證能買到所有商品。輸出格式輸出僅一行，包括m個數(shù)B1,B2...Bm，依次表示第i號商品該在Bi號超市中購買。如果買不到的話Bi為0。當(dāng)然啦，如果一個商品在i號超市與j號超市購買一樣便宜，超超更樂意大號超市了。嘻嘻，有興趣的話猜猜為什么。樣例輸入36530235890202340213樣例輸出310332【課題33】捉羊計劃。問題描述在經(jīng)歷了上千次失敗后，灰太狼終于研制出了性能完備的捉羊機(jī)器人?；姨窍Ｍ芾盟鼈冏プ⊙虼謇锼械难颍袁F(xiàn)在需要制定一個完美的計劃?；姨且呀?jīng)獲取了羊村的地圖。他發(fā)現(xiàn)羊村由N個交叉路口和N-1條雙向街道構(gòu)成，而且無論從哪個交叉路口出發(fā)沿著街道走都能到達(dá)其它的任何一個交叉路口。每條街道上都有房子，每個房子中都住著羊。為了保證計劃萬無一失，灰太狼選擇在半夜行動，因為這時所有的羊都會在自己的房子中睡覺?；姨怯媱潓⑺圃斐龅腒個機(jī)器人放在某個交叉路口處，機(jī)器人會沿著街道行走，并且可以在任何一個交叉路口停下，不同的機(jī)器人可以停在不同的位置。因為捉羊機(jī)器人的性能非常優(yōu)秀，所以每條街道只要被一個機(jī)器人走過一次，這條街道上住著的所有羊就都會被捉住。當(dāng)所有的羊都被抓住后，灰太狼的計劃就成功了。機(jī)器人在街道上移動需要耗費(fèi)非常多的能量。為了節(jié)約能源，灰太狼迫切想要知道所有機(jī)器人的移動路線長度之和的最小值。輸入格式輸入文件包含N行。第1行包含兩個正整數(shù)N、K，分別表示交叉路口的總數(shù)和機(jī)器人的個數(shù)。交叉路口的序號為1到N。第2行到第N行，每行包含三個用空格隔開的正整數(shù)A、B、C，表示有一條連接交叉路口A和交叉路口B的街道，且該街道的長度為C。輸出格式輸出文件包含N行，每行一個正整數(shù)，其中第i行的整數(shù)表示如果所有的機(jī)器人從序號為i的交叉路口出發(fā)，那么移動路線的長度之和最小是多少。輸入樣例531272353414358輸出樣例4239344242樣例說明若所有的機(jī)器人從1號路口出發(fā)，那么最優(yōu)路線為：1號機(jī)器人：1→2→3→5→3→4，長度為42。2號機(jī)器人：停留在出發(fā)點。3號機(jī)器人：停留在出發(fā)點?？傞L度為42。若所有的機(jī)器人從2號路口出發(fā)，那么最優(yōu)路線為：1號機(jī)器人：2→1，長度為7。2號機(jī)器人：2→3→4，長度為19。3號機(jī)器人：2→3→5，長度為13。總長度為39。若所有的機(jī)器人從3號路口出發(fā)，那么最優(yōu)路線為：1號機(jī)器人：3→2→1，長度為12。2號機(jī)器人：3→4，長度為14。3號機(jī)器人：3→5，長度為8?？傞L度為34。數(shù)據(jù)范圍對于10%的數(shù)據(jù)，N≤10，K≤2。對于20%的數(shù)據(jù)，N≤100，K≤6。對于35%的數(shù)據(jù)，N≤200，K≤12。對于50%的數(shù)據(jù)，N≤500，K≤18。對于65%的數(shù)據(jù)，N≤8000，K≤25。對于另外20%的數(shù)據(jù)，N≤15000，K≤2。對于全部的數(shù)據(jù)，N≤15000，K≤30。每條街道的長度都不超過100。【課題34】陶陶玩紅警。問題描述陶陶最近開始玩紅警了，他玩的是自己MOD的一個紅警版本。這個版本是這樣的：你只能造兩樣?xùn)|西，戰(zhàn)車工廠和坦克。最初你有一個戰(zhàn)車工廠，然后在接下來的每一秒內(nèi)你可以有兩種選擇(假設(shè)當(dāng)前有k個戰(zhàn)車工廠)：1，建造一個戰(zhàn)車工廠；2，建造k輛坦克。注意，戰(zhàn)車工廠和坦克是不能同時建造的。陶陶在玩了一個月紅警后，認(rèn)為自己紅警水平很厲害了。于是他向curimit發(fā)了一份挑戰(zhàn)書，他還囂張地說他會對curimit發(fā)動N次攻擊。第i次攻擊在第time[i]秒末，陶陶會使用num[i]輛坦克來進(jìn)攻，消滅掉curimit家里同等數(shù)量的坦克。如果此時curimit家里沒有這么多的坦克的話，那么curimit就死翹翹了。curimit接到戰(zhàn)書后看到看到陶陶如此強(qiáng)大的攻勢，被嚇得不輕。他想請你幫幫忙，幫他制定一份作戰(zhàn)計劃（什么時候造戰(zhàn)車工廠，什么時候造坦克）：curimit希望在抵擋了陶陶的N輪進(jìn)攻之后，在第final秒末發(fā)動最終的總攻擊，一舉殲滅陶陶的老家。他希望你的作戰(zhàn)計劃能夠在第final秒末造出最多數(shù)量的坦克。輸入格式第1行為兩個整數(shù)N，final，含義如題目中所述。接下來N行，第i行有兩個數(shù)time[i]和num[i]，含義如題目中所述。輸出格式輸出僅包含一行，如果curimit無法抵擋陶陶的進(jìn)攻，那么輸出“NoAnswer!”；否則輸出第final秒末curimit最多能擁有多少輛坦克。輸入樣例3105371394輸出樣例8樣例解釋第1秒：造戰(zhàn)車工廠。第2秒：造戰(zhàn)車工廠。第3秒：造戰(zhàn)車工廠。第4秒：造坦克，當(dāng)前坦克數(shù)：4。第5秒：造坦克，當(dāng)前坦克數(shù)：8。第5秒：陶陶帶了3輛坦克沖了進(jìn)來，當(dāng)前坦克數(shù)：5。第6秒：造坦克，當(dāng)前坦克數(shù)：9。第7秒：造坦克，當(dāng)前坦克數(shù)：13。第7秒：陶陶帶了13輛坦克沖了進(jìn)來，當(dāng)前坦克數(shù)：0。第8秒：造坦克，當(dāng)前坦克數(shù)：4。第9秒：造坦克，當(dāng)前坦克數(shù)：8。第9秒：陶陶帶了4輛坦克沖了進(jìn)來，當(dāng)前坦克數(shù)：4。第10秒：造坦克，當(dāng)前坦克數(shù)：8。在第10秒末，curimit家里最多有8輛坦克。數(shù)據(jù)范圍10%的數(shù)據(jù)中N≤5，final≤10；30%的數(shù)據(jù)中N≤1000，final≤1000；100%的數(shù)據(jù)中N≤100000，final≤109，0≤num[i]≤1018；100%的數(shù)據(jù)中1≤time[1]【課題35】光棱坦克。問題描述一個平面直角坐標(biāo)系上，有N個點，標(biāo)號為1到N，其中第i個點的坐標(biāo)為(x[i],y[i])。求滿足以下兩個條件的點列{p[i]}的數(shù)目（假設(shè){p[i]}的長度為M）：1)對任意1<=i<j<=M，必有y[p[i]]>y[p[j]]；2)對任意3<=i<=M，必有x[p[i-1]]<x[p[i]]<x[p[i-2]]或者x[p[i-2]]<x[p[i]]<x[p[i-1]]。求滿足條件的非空序列{p[i]}的數(shù)目，結(jié)果對一個整數(shù)Q取模。輸入格式第1行是兩個由空格隔開的整數(shù)：N和Q。第2行到第N+1行，每行有兩個整數(shù)。其中的第i行的兩個整數(shù)分別是x[i]和y[i]。輸出格式輸出文件只有一行，包含一個整數(shù)，表示序列{p[i]}的數(shù)目對Q取模的結(jié)果。輸入樣例410022311443輸出樣例14樣例說明一共4個點，位置如下：如果M=4,那么只有1種序列符合要求,如下圖所示：如果M=3，那么有3種序列符合要求，如下圖：如果M=2，那么有6種序列符合要求，如下圖：如果M=1，也就是點列只包含一個點的情況。那么有4種序列。明顯都符合要求。所以一共就有1+3+6+4一共14種序列符合要求。數(shù)據(jù)范圍對于25%的數(shù)據(jù)，N<=50；對于40%的數(shù)據(jù)，N<=700；對于60%的數(shù)據(jù)，N<=2000；對于70%的數(shù)據(jù)，N<=4000；對于100%的數(shù)據(jù)，1<=N<=7000。對于100%的數(shù)據(jù)，有1<=Q<=1000000000。對于50%的數(shù)據(jù)，保證對任何的i，x[i]和y[i]是1到N之間的整數(shù)；對于100%的數(shù)據(jù)，保證對任何的i，x[i]和y[i]都是1到2000000000之間的整數(shù)。對于100%的數(shù)據(jù)，保證有當(dāng)i!=j時，有x[i]!=x[j]且y[i]!=y[j]?！菊n題36】Ekaterinburg城到Sverdlovsk城有直線形的鐵路線。兩城之間還有其他一些?？空?總站數(shù)為N。各站按照離Ekaterinburg城的距離編號。Ekaterinburg城編號為1，Sverdlovsk城編號為N。給定起點站和終點站，求出要從起點到終點最少要花多少錢。某兩站之間車票價格由這兩站的距離X決定.當(dāng)0<X<=L1時，票價為C1元.當(dāng)L1<X<=L2時，票價為C2元.當(dāng)L2<X<=L3時，票價為C3元.當(dāng)兩站距離大于L3時沒有直達(dá)票，所以有時候要買幾次票做幾次車才行。比如，在上面的例圖中，2-6沒有直達(dá)票，有幾種買票方法可以從2-6，其中一種是買C2元的2-3車票，再買C3元的3-6車票?！菊n題37】單詞爭霸。問題描述農(nóng)夫約翰(FarmerJohn)的奶牛們平時喜好一起學(xué)習(xí)英文單詞。奶牛Bessie是其中最聰明的牛，她發(fā)明了一個游戲，叫做《單詞爭霸》。這個游戲是由兩個人來玩，兩人輪流進(jìn)行。輪到每個人時，他要說出一個正確的單詞（即字典中的單詞），要求這個單詞在之前沒有被他或他的對手說過，并且這個單詞不是之前他或他的對手說過的某個單詞的前綴。如果輪到一個人，他無法說出這樣的單詞，那么他被判敗。顯然，擁有詞匯量較多的奶牛玩起這個游戲來更有優(yōu)勢，因為他有更多的單詞可以說。這樣，奶牛們天天玩這個游戲，他們的詞匯量越來越大……直到有一天，Bessie發(fā)現(xiàn)他們已經(jīng)把世界上所有的英文單詞學(xué)會了，因此她再也無法依賴自己較大的詞匯量取勝了。她是記憶單詞的天才，但并不是游戲好手，所以她來請教聰明的你。她告訴你，這個世界上一共有N個英文單詞，每個單詞的長度不超過maxLen。她將這些單詞按字典序排列，并輸入。她想知道如果她是先手，那么她是否能取得勝利。你需要做的是，判斷在給定字典的情況下，先手是否有必勝策略。如果沒有，那么告訴Bessie:“Can’twinatall!!”，否則，你需要確定先手在第一回合可以說出哪些單詞，為了讓Bessie多一些思考的樂趣，你決定不把這些單詞一一列舉。你把這些單詞按某個排列連接起來，組成一個大的字符串，當(dāng)然，不同的排列可能得到不同的串，你要告訴Bessie那個字典序最先的串，記作answerString。為了使輸出更加美觀，如果那個串的長度大于50,你要分行輸出，除了最后一行以外，其他行每行50個字符，最后一行不多于50個字符。輸入格式輸入的第一行包含兩個整數(shù),N和maxLen,用一個空格隔開。接下來的N行，每行為一個長度不大于maxLen的字符串。輸出格式按題目描述中的要求輸出：可能為一行,“Can’twinatall!!”(不包含引號)或者多行，除了最后一行之外每行50個字符，最后一行不超過50個字符，將所有行的字符連接起來是answerString。樣例輸入129wordwordcraft樣例輸出1wordcraft樣例1解釋先手說出單詞“wordcraft”之后,后手沒有單詞可說，因為單詞“word”是單詞“wordcraft”的子串。樣例輸入259accarcarecarefulcarefully樣例輸出2careful樣例2解釋先手說“careful”之后，后手只能說“ac”或者“carefully”。如果他說了前者，那么先手說后者；反之，如果他說了后者，那先手說前者。之后，后手都將無單詞可說。樣例輸入32100noonecansolvethisproblemthisproblemisverydifficult樣例輸出3Can’twinatall!!樣例輸入498thewordathewordbthewordctheworddthewordethewordfthewordgthewordhthewordi樣例輸出4thewordathewordbthewordctheworddthewordethewordfthewordgthewordhthewordi數(shù)據(jù)范圍輸入數(shù)據(jù)中的所有單詞均由小寫字母構(gòu)成。輸入數(shù)據(jù)保證所有單詞按字典序排列。輸入數(shù)據(jù)保證所有單詞互不相同。10%的數(shù)據(jù)中N≤20,maxLen≤20；30%的數(shù)據(jù)中N≤500,maxLen≤50；50%的數(shù)據(jù)中N≤2000,maxLen≤50；70%的數(shù)據(jù)中N≤5000,maxLen≤100；100%的數(shù)據(jù)中N≤100000,maxLen≤100。【課題38】Asthenewtermcomes,theIgnatiusTrainStationisverybusynowadays.Alotofstudentwanttogetbacktoschoolbytrain(becausethetrainsintheIgnatiusTrainStationisthefastestallovertheworld).Butherecomesaproblem,thereisonlyonerailwaywhereallthetrainsstop.Soallthetrainscomeinfromonesideandgetoutfromtheotherside.Forthisproblem,iftrainAgetsintotherailwayfirst,andthentrainBgetsintotherailwaybeforetrainAleaves,trainAcan'tleaveuntiltrainBleaves.Thepicturesbelowfigureouttheproblem.Nowtheproblemforyouis,thereareatmost9trainsinthestation,allthetrainshasanID(numberedfrom1ton),thetrainsgetintotherailwayinanorderO1,yourtaskistodeterminewhetherthetrainscangetoutinanorderO2.InputTheinputcontainsseveraltestcases.Eachtestcaseconsistsofaninteger,thenumberoftrains,andtwostrings,theorderofthetrainscomein:O1,andtheorderofthetrainsleave:O2.Theinputisterminatedbytheendoffile.MoredetailsintheSampleInput.OutputTheoutputcontainsastring"No."ifyoucan'texchangeO2toO1,oryoushouldoutputalinecontains"Yes.",andthenoutputyourwayinexchangingtheorder(youshouldoutput"in"foratraingettingintotherailway,and"out"foratraingettingoutoftherailway).Printalinecontains"FINISH"aftereachtestcase.MoredetailsintheSampleOutput.SampleInput31233213123312SampleOutputYes.inininoutoutoutFINISHNo.FINISH【課題39】Startingfromapositiveintergern(1<=n<=2001).Ontheleftoftheintegern,youcanplaceanotherintegermtoformanewintegermn,wheremmustbelessthanorequaltohalftohalfoftheintegern.Ifthereisanintegrklessthanorequaltohalfofm,youcanplacekontheleftofmntoformanewintegerkmn,…，andsoon.Forexample,youcanplace12ontheleftof30toformaninteger1230,andyoucanplace6totheleftof1230toformaninteger61230,…，andsoon.Forexample,startfromn=8.Youcanplaceintegers1,2,3and4totheleftof8togetintegers18,28,38,48.Fornumber18,youcanformanewintegerusingtheproceduredescribedasabove.Fornumber28and38,youcanformnewintegrers128and138.Fornumber48,youcanplace1and2ontheleftof48togetnewintergers148and248.Fornumber248,youcanplace1ontheleftofittogetanewinteger1248.Intotal,youcanhavethefollowing10integers(includingtheintegeryoustartwith):8182838481281381482481248Givenanintegern,findthenumberofintegersyoucangetusingtheproceduredescribedabove.Input:AnintegernOutput:Anintegerwhichrepresentsthenumberofintegersyoucanget.SampleInput:8SampleOutput:10【課題40】求01矩陣中最大的全零矩形給定一個M*N的01矩陣，求其中全部由0組成的面積最大的矩形（輸出面積即可）?！菊n題41】營業(yè)額統(tǒng)計給定N（1≤N≤32767）天的營業(yè)額a1,a2,a3,……an.定義最小波動值：該天的最小波動值=min{|該天以前某一天的營業(yè)額-該天營業(yè)額|}.特別地，第一天的最小波動值即為a1. 試求N天的最小波動值之和?！菊n題42】瑰麗華爾茲 給定一個N行M列的矩陣，矩陣中的某些方格上有障礙物。有一個人從矩陣中的某個方格開始滑行。每次滑行都是向一個方向最多連續(xù)前進(jìn)c格（也可以原地不動）（兩次滑行的c值不一定相同）。但是這個人在滑行中不能碰到障礙物?，F(xiàn)按順序給出K次滑行的方向（東、南、西、北中的一個）以及對應(yīng)的c，試求這個人能夠滑行的最長距離（即格子數(shù)）。 數(shù)據(jù)范圍：1≤N,M≤200，K≤200，≤40000提高題：以下選題為每題限選2人。【課題1】對給定文檔，依據(jù)下面的思想設(shè)計聚類算法，并實現(xiàn)，輸出聚類結(jié)果。無向加權(quán)圖G=＜V，E，W＞，V={d1，d2，…，dn}；其表示形式為一對稱矩陣：[wij]n×n，其中W={w1，w2，…，wm}是邊權(quán)重代表兩個文本間相似度。計算文檔的詞頻以及文檔間的相似度，將文檔粗化的聚成無關(guān)或是相關(guān)度極小的c個文檔子類。首先除去在所有文檔中出現(xiàn)的高頻詞；然后提取剩下詞匯的短語存入詞根表中。收集這些短語形成一個索引短語集T。短語t在文檔di中權(quán)重為：tfit定義為短語t在文檔中di出現(xiàn)的頻率；dft定義為含有短語t的文檔數(shù)量；L定義為文檔di中包含的索引短語的數(shù)量；N定義為文檔的數(shù)量。p_term_documen（tt，di）的值代表著短語t在文檔di中的重要性，取值范圍是[0，1]。計算出短語的權(quán)重，可以將短語表示成向量：di=（wi1，wi2，…，wis），其中0≤wij≤1，s代表索引短語表中詞的數(shù)量。則兩個文檔di與dj的相似度可定義為：由Wij=sim（di，dj），建立模糊相似矩陣W∈Rn×n，其中當(dāng)i=j時，令Wii=0。由相似矩陣求得傳遞閉包t(W)，選取一個合適的λ值得到一個λ截集，得到的將是一個0，1矩陣，記為t(R)。由此矩陣可以分成c個文檔類，即A={A1，A2，…，Ac}，滿足了文檔類間的相似性極小，將c個文本集看成c個子圖。判斷各個文檔子類中如果存在只有一個文檔的類，將其并入其他與其相似度最高的子類中，變成c*個子圖。輸入c*個子圖，用基于譜圖分割簡單的譜聚類算法對每個子圖G的頂點集Vk=（v1，v2，…，vn）進(jìn)行聚類，得到每個子圖的聚類結(jié)果及其對應(yīng)的類別數(shù)ki，其中i∈[1，c*]。計算出ki的和即為總的聚類數(shù)K。輸入一個數(shù)據(jù)集X={x1，x2，…，xk}，輸出由以上的數(shù)據(jù)集分割出來的k個子集。計算每個子圖的親密矩陣S，當(dāng)i≠j時，Sij=exp（-d（xi-x）j/2σ2），Sii=0。構(gòu)造Laplacian矩陣L，L=D-1/2SD-1/2，其中D為對角陣。計算L的前k個特征值特征向量ζ1，ζ2，…，ζk（重復(fù)特征值取其互相正交的特征向量），按照大小順序?qū)⑾鄳?yīng)的特征向量排列構(gòu)成矩陣U=[ζ1，ζ2，…，ζk]∈Rn×k，初始化聚類數(shù)m=2。令ki=m。取U的前ki個列向量構(gòu)成矩陣Y，即Y=U（：，1：k），歸一化Y為矩陣V，其中在ki維空間里，每個坐標(biāo)軸的正負(fù)方向分別標(biāo)記一個聚類。把V的行向量看作是ki維空間的點，將其標(biāo)記為距離最近的坐標(biāo)軸所標(biāo)記的聚類。這樣最多可以產(chǎn)生2ki個聚類。除去空聚類和只有少數(shù)點的聚類，可以得到此時的聚類數(shù)m≤2k。比較m和ki，如果兩者不等，重復(fù)上面過程。如果m=ki，則所得到的m就是確定的聚類數(shù)，同時得到相應(yīng)聚類數(shù)下V的行向量聚類。當(dāng)且僅當(dāng)V的第i行為聚類j時，則原始數(shù)據(jù)點xi為第j類。計算ki的和得到總的聚類數(shù)k，和聚類結(jié)果。【課題2】依據(jù)給定值，求解下面方程x的近似計算解。ai＝a[i]，m為a[0]-a[n]的平均值。(ai－m)＝０a[92]={74,72,69,62,64,61,74,70,64,74,46,82,60,86,70,67,70,68,60,65,62,73,60,60,80,71,68,60,81,60,74,70,55,76,88,51,82,68,80,63,65,47,72,62,60,68,81,43,60,69,76,72,72,68,68,60,75,40,60,78,82,75,67,60,60,95,69,65,64,60,60,64,62,72,66,42,74,71,81,70,77,63,69,41,65,69,73,60,69,80,81,75}。【課題3】設(shè)計一套CUP與內(nèi)存使用率實時監(jiān)控與利用軟件，能依據(jù)計算機(jī)CUP與內(nèi)存使用率實時調(diào)整對給定數(shù)據(jù)處理算法的采樣率，保證最大限度地充分利用CUP與內(nèi)存進(jìn)行對給定數(shù)據(jù)的實時處理（即數(shù)據(jù)處理速度不變，如1000條數(shù)據(jù)/秒）?！菊n題4】對給定數(shù)據(jù)，依據(jù)下面的思想設(shè)計兩數(shù)據(jù)集相似性算法，并實現(xiàn)，輸出相似度。設(shè)給定數(shù)據(jù)集用期望Ex、熵En和超熵He來表征，期望Ex反映給定數(shù)據(jù)集的確定性，代表給定數(shù)據(jù)集的最典型抽象樣本；熵En反映給定數(shù)據(jù)集的不確定性，代表給定數(shù)據(jù)集的可被接受的取值范圍（集中性），也即給定數(shù)據(jù)集的離散程度；超熵He給定數(shù)據(jù)集的取值范圍的穩(wěn)定性，也即給定數(shù)據(jù)集的取值范圍的凝聚性。分析以下兩數(shù)據(jù)集的確定性、集中性和穩(wěn)定性，進(jìn)而由此分析該兩數(shù)據(jù)集的相似度。設(shè)樣本點xi，如給定數(shù)據(jù)集所示。1、根據(jù)xi計算樣本的平均值，一階樣本絕對中心矩，樣本方差；2、Ex=；3、En=；4、He=a[92]={74,72,69,62,64,61,74,70,64,74,46,82,60,86,70,67,70,68,60,65,62,73,60,60,80,71,68,60,81,60,74,70,55,76,88,51,82,68,80,63,65,47,72,62,60,68,81,43,60,69,76,72,72,68,68,60,75,40,60,78,82,75,67,60,60,95,69,65,64,60,60,64,62,72,66,42,74,71,81,70,77,63,69,41,65,69,73,60,69,80,81,75}a[92]={64,62,69,62,64,61,84,70,64,74,46,82,60,86,70,67,77,68,60,65,62,73,60,60,80,71,68,60,81,60,74,70,55,76,88,51,82,68,80,63,65,47,72,62,60,68,81,43,60,69,76,72,72,68,68,60,75,40,60,78,82,75,67,60,60,95,69,65,94,60,60,65,62,72,66,42,74,71,81,70,78,63,69,41,65,69,73,60,69,80,81,75}?！菊n題5】假定每一段都有段落中心，段落中心句是與本段中所有其它語句相關(guān)度最高的語句，找段落的中心句。每個句子看成為一個文檔，其相關(guān)度的計算思想如下：設(shè)為第i個文檔，為第i個文檔對應(yīng)的第m個短語，為第i個文檔中第m個短語的特征，則文檔與的相關(guān)度為：其中：i=1，2，3，4包含關(guān)系計算：L為包含關(guān)系存在的層次。概念主類計算：α=1為兩個概念主類。義原在Taxonomy樹上的距離節(jié)點相似計算如下：同層相同節(jié)點的計算：為同層相同節(jié)點數(shù)為同層最大節(jié)點數(shù)是層次數(shù)動態(tài)角色domain處理（兩個det中都存在domain）：=a為相同domain節(jié)點個數(shù)為兩個det的最深層兩個det相同節(jié)點數(shù)與總節(jié)點數(shù)的計算：=a:相同節(jié)點個數(shù):第1個det的節(jié)點數(shù):第2個det的節(jié)點數(shù)主類義原相的計算，計算方法同。懲罰因子：1；否定關(guān)系0.3；其它指定關(guān)系0.35短語特征值（tim）短語的平均權(quán)重標(biāo)題短語權(quán)重最高，次標(biāo)題短語權(quán)重次之，內(nèi)容短語權(quán)重最低，專業(yè)短語權(quán)重比普通短語高。t:不重復(fù)短語數(shù)為短語平均頻率文檔中短語出現(xiàn)的次數(shù)文檔中短語總數(shù)短語平均深度短語第一次出現(xiàn)原短語數(shù)文檔中短語總數(shù)文檔（包含短語）的文檔頻率包含短語的文檔數(shù)所有文檔總數(shù)【課題6】為限制某給定軟件系統(tǒng)只能在一臺機(jī)器上使用，需為制某給定軟件系統(tǒng)加密與生成序列號。這個給EXE程序加密的算法程序稱之為一機(jī)一碼加殼算法程序。1、由網(wǎng)絡(luò)或自己開發(fā)的獲取客戶端的CPU序列號程序獲取客戶端的CPU序列號；2、采用以下算法設(shè)計開發(fā)加殼算法程序生成一機(jī)一碼的20位序列號(共5段)例如12345-56785-15234-55678-12534：將CPU序列號分為三部分，取其中三部分以適當(dāng)變換加密，作為其中三段；另外兩段可用固定數(shù)據(jù)源(可包含字符)進(jìn)行變換得到；以能進(jìn)行解殼。解密變換包括移位、加減、等一一映射方式。3.生成的新EXE文件能通過所有主流殺軟的掃描和運(yùn)行時保護(hù)（原軟件能通過）。4.不影響原軟件的性能。綜合題：以下選題為每題限選3人。【課題1】“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺。每個交巡警服務(wù)平臺的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個實際課題。試就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立模型分析研究下面的問題：（1）附件中的附件圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件。請為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警（警車的時速為60km/h）到達(dá)事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。（2）針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P（第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案?！菊n題2】設(shè)計一套試卷排版軟件，要求能依據(jù)給定的模板和要求，對沒有按要求規(guī)范排版的試卷(word)進(jìn)行規(guī)范化排版。具體要求有：1、所有選擇題選項用表格固定嚴(yán)格對齊；2、能完成數(shù)學(xué)公式、圖片在試卷中的排版；3、英文為TimesNewRoman；4、標(biāo)點符號為全角；5、試卷內(nèi)容全部使用小四、宋體、行間距為1.5倍。【課題3】找qq群的貼主、群主和專家。對一段時期的群聊天記錄進(jìn)行分析，將每一個ID對應(yīng)的聊天記錄看成是一個文本，對所有的文本進(jìn)行分詞；將分詞后的文本依據(jù)單詞的相似性進(jìn)行聚類，得到若干主題類；對每個主題進(jìn)行分析，發(fā)貼量最大的ID稱為該主題的貼主，其余的貼稱為貼主的跟隨貼，跟隨貼數(shù)稱貼主的影響因子；占有主題最多的貼主稱為該群這一時期的群主。設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)與算法，找出貼主與群主，并給出其影響因子。對不同時期的同一群的聊天記錄進(jìn)行分析，對不同時期的主題進(jìn)行比較，不同時期內(nèi)相同的主題數(shù)，稱為該群的專業(yè)絕對系數(shù)，專業(yè)絕對系數(shù)除以總主題數(shù)(不相同)，稱為該群的專業(yè)相對系數(shù)，專業(yè)相對系數(shù)越大，則該群越專業(yè)；在不同時期內(nèi)相同主題的具有最多的相同貼主數(shù)，則該貼主稱為該主題的專家，設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)與算法，找出該群的若干時期內(nèi)的所有專家，并給出該群的相對專業(yè)系數(shù)。運(yùn)用題：以下選題為每題限選5人?！菊n題1】銀行業(yè)務(wù)處理模擬平臺Thisisasimulationofasetofcustomeroperationsatabank.Itisintendedtoimplementandtestvarioustransactions.Thereisnouserinputintotheprogram.Alloftheoperationsareautomated.Therearenovisualelementstotheprogram.Theentireprogramrunsusingaconsolewindow.Alloutputwillbetextbasedanddirectedtowardstheconsolewindow.Thisisanindividualprojectandnogroupworkispermitted.Donotdivergefromtheassignmentspecification.Ifyoudonotconformtotheassignmentspecificationthenyouwilllosemarks.Ifyoudowanttomakesomeadditiontotheapplicationandyouareunsurewhetherthechangewillbreakthespecificationthencheckitwithmefirst.Theformatoftheprogramoutputisgiveninthespecification.Youmustadheretothisformat.Exampleoutputisgivenattheendoftheassignment.Youcanthereforetestyouroutputagainsttheexpectedoutput.PlagiarismYouwillbeheldresponsibleifsomeonecopiesyourwork-unlessyoucandemonstratethathavetakenreasonableprecautionsagainstcopying.LearningOutcomesMakeaninformedchoiceofimplementationmethodforagivenproblem(cedural,console,event-driven,object-orientedetc.)ImplementanddocumentastructuredprogramtomeetagivenspecificationSelectandapplyappropriatedatastructuresandalgorithmstoagivenproblemCriticallyevaluateacomputerprogramwithregardtorobustness,usability,maintainability,readabilityandefficiencyProjectFilesThisassignmenthasthreeassociatedfiles:Thereisadatafile.ThefilecanbefoundinsidethemodulepageonWeb-CT.Thefileiscalled"customers.txt".ThedatafileisanASCIIfilecontainingdataaboutthecurrentcustomersofthebank.Thereiscodewhichyoumustusetogeneraterandomnumbers.Thecodeisgivenin“Random.cpp”.Thereisastyleguide.ThestyleguidecanbefoundinsidethemodulepageonWeb-CT.Thefileiscalled"styleguide.doc".

DeliverablesNotethattheprogramincludesarandomnumbergenerator.Theseedforthegeneratorisreadfromthefile"seed.txt".CD,orotherelectronicformatcontaining:ExecutableprogramofyoursolutionAllthesourceandprojectfilesrequiredtobuildtheexecutable.TheprojectmustbesetuptoruninVisualStudio2005or2023.AllfilesshouldbesensiblynamedandinworkingorderThedatafileshouldbeplacedintotheworkingdirectorysothatIcanjustruntheprogram.Aprintedreportaboutyourprogram.Testingstrategyandresults.Thiscanbesubmittedinelectronicformat.However,youmustalsoincludeawrittenreportdescribingyourteststrategyandanalysisofresults.UMLClassdiagramofyourprogram.DescriptionYouarerequiredtoimplementasimulationofabankandsixcustomers.Threeofthecustomersareprivatecustomers.Threeofthecustomersarebusinesscustomers.Eachcustomerhasanid,aname,thevalueoftheircurrentaccountandthevalueoftheirsavingsaccount.Theinitialdataforthecustomersisgiveninthefollowingtable:NumberNameTypeofcustomerCurrentaccountSavingsaccount32Pennyprivate100010002Sueprivate200003Angusprivate1001004ToysForAllbusiness400030005LettersandStationarybusiness300020006John'sGaragebusiness50001000Theinitialdataforalloftheaccountsisgivenin“customers.txt”.Iwilltestyourprogramwithdifferentdata.Soensurethatyoufullytestarangeofvalueswithyourapplication.Thefirsttestoccurs發(fā)生beforethesimulationproperbegins.Thisisasimpletestofremovingandaddingacustomertothebank:Customer32("Penny")closesheraccount.Immediatelyafterthisanewcustomer("Betty")opensaprivateaccountwithaninitialdepositof￡4000inhercurrentaccountand￡3000inhersavingsaccount.Herbankidwillbe1.Thesimulationrunsover20rounds.Ineachroundonetransactionoccurs.Atransactionwillbeperformedbyonecustomer.Thetransactionsincludesuchthingsasdepositmoneyintoasavingsaccount,createastandingorderandwithdrawmoneyfromacurrentaccount.Every10roundstherewillbebankphase,i.e.afterround10(butbeforeround11)andafterround20.Duringthisphasethebankwillapplyinterestchargestoalloftheaccounts.Ifanystandingordersexistthentheseareappliedandmoniestransferredfromoneaccounttoanother.Ineachroundanumberbetween1and6isgenerated.Thisisthebankidofthecustomerwhowillperformthetransaction.Assumethatthebankhasunlimitedfunds.Acustomermaygo"intothered",i.e.theirbalancecanbenegative.Theapplicationisrunasasimulationrequiringnouserinput.Runthesimulationforonly20rounds.Foreachtransactionanumberbetween1and6isgenerated.Thiswillbeusedtoselectthetypeoftransactiontobeperformed.Thenumberandnameofthetransactionsaregiveninthefollowingtable:NumberTransactionname1Depositintocurrentaccount2Withdrawalfromcurrentaccount3Depositintosavingsaccount4Withdrawalfromsavingsaccount5Paymonies6CreateastandingorderWhentheapplicationisstarted,awelcomemessageisdisplayed.Theformatofthemessageis:'WelcometoMyBank'Foreachround,theidandnameofthecustomerisgiven.Outputthemessage:'Customer<id>:<customer>'Onthenextlinethegeneratednumberandthenameofthetransactionaredisplayed.Outputthemessage:'Transaction<number>:<transactionname>'Whenacustomerdepositsmoneyintotheircurrentaccountthefollowinghappens:Add￡100totheircurrentaccount.Whenacustomerwithdrawsmoneyfromtheircurrentaccountthefollowinghappens:Subtract￡100fromtheircurrentaccount.Whenacustomerdepositsmoneyintotheirsavingsaccountthefollowinghappens:Subtract￡100fromtheircurrentaccount.Add￡100totheirsavingsaccount.Whenacustomerwithdrawsmoneyfromasavingsaccountthefollowinghappens:Subtract￡100fromtheirsavingsaccount.Add￡100totheircurrentaccount.??當(dāng)應(yīng)用程序啟動時，一個值得歡迎的消息顯示。該郵件的格式是：Whenacustomerpaysmoniestheyareimmediatelytransferringmoneyfromtheircurrentaccounttothecurrentaccountofoneoftheothercustomers.Generateanumberbetween1and6tosaywhichcurrentaccountthecustomerwillbepayinginto.Obviouslyacustomershouldnotpaymoneytohimorherself,socarryongeneratingnumbersuntilyouobtainavalidid.Thefollowingthenhappens:Subtract￡100fromthecurrentaccountofthecustomerperformingthetransaction.Add￡100tothecurrentaccountofthecustomertowhomtheyaremakingpayment.Whenacustomercreatesastandingordertheycommitthemselvestopaying￡100fromtheircurrentaccounttoabusinesscurrentaccountduringeachbankphase.Generateanumberbetween4and6tosaywhichbusinesscurrentaccountthecustomerwillbepayinginto.Obviouslyabusinessshouldnotpaymoneytoitself,socarryongeneratingnumbersuntilyouobtainabusinessotherthantheonesettingupthestandingorder.Acustomercanhavemultiplestandingorderswithabusiness.(Thiswillsimplifythesimulation).Attheendofeachtransactionyoumustoutputthemessage:'<customer>has'Current:￡<currentaccountbalance>.Savings:￡<savingsaccountbalance>’Thebanktreatsprivateandbusinessaccountsdifferently.Everytransactionthatabusinessaccountmakes,incursacostof￡5fromthecustomer'scurrentaccount.Therearebenefitstohavingabusinessaccount,buttheseareoutsidethescopeofthecurrentscenarioandcanbeignored.BankPhaseThebankphrasehappensafterevery10rounds.Displaytheaccountdetailsofallofthecustomers.Foreachcustomerfirstoutputtheidandnameofthecustomer.Outputthemessage:'Customer<id>:<customer>'Onanewlineoutputtheaccountdetails.Outputthemessage:'Current:￡<currentaccountbalance>.Savings:￡<savingsaccountbalance>’Implementallofthestandingorders.Foreverystandingorderthatacustomerhaspay￡100fromtheircurrentaccounttoacurrentaccountoftheappropriatebusiness.Outputeachofthestandingor