有限狀態(tài)機(jī)應(yīng)用

1大作業(yè)-文件IO版本設(shè)計(jì)思路2/7/20232大作業(yè)文件IO版本模塊結(jié)構(gòu)圖模型內(nèi)部狀態(tài)控制器策略算法結(jié)果記錄寫入文件狀態(tài)變化事件改變狀態(tài)文件輸入讀取請(qǐng)求事件時(shí)間同步2/7/20233大作業(yè)文件IO版本程序框架/*大作業(yè)文件IO版本的程序主體結(jié)構(gòu)*/structSTATE{…}//電梯或銀行的運(yùn)行狀態(tài)structLIST{…}//請(qǐng)求隊(duì)列鏈表節(jié)點(diǎn)structREQ{…}//暫存每次獲得的請(qǐng)求事件intmain(){inttimeCount=0;//計(jì)時(shí)器，每循環(huán)一次模擬2msstructREQtheReq={};//暫存每次獲得的請(qǐng)求事件structSTATEpreST,theST={}; //保存電梯或銀行的運(yùn)行狀態(tài)structLIST*headp=NULL;//存請(qǐng)求隊(duì)列鏈表頭指針File*fpin,*fpout;2/7/20234大作業(yè)文件IO版本程序框架openFile(**fpin,**fpout);//打開輸入輸出文件theReq=get_fileInput(fpin);//讀取第一個(gè)請(qǐng)求while(!(endInput(fpin)&&isIdle(theST))){ //當(dāng)文件輸入結(jié)束，且電梯或營業(yè)廳空閑才退出 if(theReq.time==timeCount){

headp=addServList(headp,theReq,theST,1); /*當(dāng)請(qǐng)求事件發(fā)生的時(shí)間到，添加請(qǐng)求事件到服務(wù)隊(duì)列中,策略參數(shù)為1對(duì)應(yīng)先來先服務(wù)，2對(duì)應(yīng)順便服務(wù)*/ theReq=get_fileInput(fpin); //讀取文件中的下一個(gè)請(qǐng)求事件 }//endif

2/7/20235大作業(yè)文件IO版本程序框架

preST=theST; theST=runService(preST,&headp,timeCount);

if(theST.state!=preST.state) set_fileOutput(fpout,timeCount,theST, headp); /*當(dāng)狀態(tài)變化，將當(dāng)前時(shí)間、狀態(tài)和等待隊(duì)列的情況寫入到文件中。*/ timeCount++; }//endwhile closeFile(fpin,fpout);//關(guān)閉輸入輸出文件 return0;}//endmain2/7/20236大作業(yè)文件IO版本函數(shù)接口intendInput(File*fp)//判斷文件輸入是否結(jié)束intisIdle(structSTATEstate)//判斷電梯或營業(yè)廳當(dāng)前狀態(tài)是否空閑structREQget_fileInput(File*fp)//順序讀取文件中的一個(gè)請(qǐng)求事件structLIST*addServList(structLIST*hp,structREQreq,structSTATEstate,intmode);//按照策略，將新請(qǐng)求插入請(qǐng)求隊(duì)列中structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根據(jù)狀態(tài)、請(qǐng)求和時(shí)間條件，運(yùn)行電梯或營業(yè)廳服務(wù)。運(yùn)行服務(wù)后將改變的狀態(tài)返回。注意當(dāng)服務(wù)完一個(gè)請(qǐng)求后，刪除該節(jié)點(diǎn)并修改頭指針！*/2/7/20237大作業(yè)文件IO版本函數(shù)接口structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根據(jù)狀態(tài)、請(qǐng)求和時(shí)間條件，運(yùn)行電梯或營業(yè)廳服務(wù)。運(yùn)行服務(wù)后將改變的狀態(tài)返回。注意當(dāng)服務(wù)完一個(gè)請(qǐng)求后，刪除該節(jié)點(diǎn)并修改頭指針！*/voidset_fileOutput(File*fp,inttime,structSTATEstate,structLIST*hp)/*將當(dāng)前時(shí)間、狀態(tài)和等待隊(duì)列的情況順序?qū)懭胛募?/2/7/20238輸入文件格式定義：電梯輸入用電梯請(qǐng)求文件格式：文本文件，每一行表示一個(gè)時(shí)刻發(fā)生的電梯請(qǐng)求。格式定義如下： T=<請(qǐng)求發(fā)生時(shí)間>,CallF=<樓層請(qǐng)求><\n>例:T=1,CallF=4UT=2,CallF=4U5T請(qǐng)求發(fā)生時(shí)間：按程序運(yùn)行的系統(tǒng)時(shí)鐘時(shí)間，單位秒.樓層請(qǐng)求：由呼叫方向(U/D/T)和數(shù)字（1～9）組成，同時(shí)有多個(gè)請(qǐng)求時(shí)用空格分割。如2U5D6T，表示2層上行呼叫、5層下行呼叫、6層目標(biāo)?？?。2/7/20239輸出文件格式定義：電梯電梯運(yùn)行結(jié)果記錄文件格式：文本文件，每一行表示一個(gè)電梯?？炕騿?dòng)、轉(zhuǎn)向動(dòng)作，當(dāng)前樓層和目標(biāo)樓層，以及排隊(duì)的樓層請(qǐng)求。格式定義如下： T=<當(dāng)前時(shí)間>,State=<電梯狀態(tài)>,NowF=<電梯當(dāng)前樓層>,GoalF=<電梯目標(biāo)樓層>,StopT=<停靠時(shí)間>,WaitF=<未響應(yīng)的樓層請(qǐng)求><\n>例:T=3,State=UP_RUN,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5D6TT=3,State=UP,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5T6U9D8D2/7/202310輸出文件格式定義：電梯當(dāng)前時(shí)間：程序開始運(yùn)行的系統(tǒng)時(shí)鐘時(shí)間，單位秒。電梯狀態(tài)：UP_RUN表示向上運(yùn)行、DOWN_RUN表示向下運(yùn)行、UP_STOP表示上行?？?、DOWN_STOP表示下行?？?、IDLE表示空閑。電梯當(dāng)前樓層：1.0-9.0。?？繒r(shí)間：記錄電梯已經(jīng)?？康臅r(shí)間,單位秒。只有在?？繝顟B(tài)下，該信息才大于0。未響應(yīng)的樓層請(qǐng)求：按照電梯控制策略，按響應(yīng)順序?qū)⑸形错憫?yīng)的呼叫請(qǐng)求和目標(biāo)樓層列出來。是由呼叫方向(U/D/T)和數(shù)字（1～9）組成的序列，中間用一個(gè)空格分割。如2U5D6T，表示2層上行呼叫、5層下行呼叫、6層目標(biāo)?？?。2/7/202311輸入文件格式定義：銀行輸入用銀行請(qǐng)求文件格式：文本文件，每一行表示一個(gè)時(shí)刻發(fā)生的客戶到達(dá)事件、窗口休息請(qǐng)求或下班指令。格式定義如下： T=<請(qǐng)求發(fā)生時(shí)間>,Req=<請(qǐng)求><\n> <請(qǐng)求>=C<客戶人數(shù)>|W<請(qǐng)求休息的窗口號(hào)> |Q<下班時(shí)間>例:T=1,Req=C5T=6,Req=W3T=200,Req=Q250時(shí)間：按程序運(yùn)行的系統(tǒng)時(shí)鐘時(shí)間，單位秒.2/7/202312輸出文件格式定義：銀行銀行運(yùn)行結(jié)果記錄文件格式：文本文件，每一行表示一個(gè)營業(yè)廳窗口的叫號(hào)、暫停休息、準(zhǔn)備下班、進(jìn)入空閑、下班等動(dòng)作，各窗口狀態(tài)和正在服務(wù)的客戶號(hào)碼，以及等待服務(wù)的客戶情況。格式定義如下： T=<當(dāng)前時(shí)間>,Event=<事件描述>,Now=<各窗口狀態(tài)>,Wait=<等待服務(wù)的客戶情況><\n>

<事件描述>=JH<空格><W窗口號(hào)><空格><C客戶號(hào)碼> ZT><空格><W窗口號(hào)><空格><R休息時(shí)長(zhǎng)> KX><空格><W窗口號(hào)>ZB><空格><下班時(shí)間>XB 2/7/202313輸出文件格式定義：銀行 <客戶號(hào)碼>=0001~9999<各窗口狀態(tài)>=<W窗口號(hào)><空格><S窗口狀態(tài)><空格><C當(dāng)前客戶號(hào)碼> <S窗口狀態(tài)>=S0表示空閑 S1表示服務(wù) S2表示暫停<等待服務(wù)的客戶情況>=

策略1：<Q隊(duì)列長(zhǎng)度>><空格><F隊(duì)首客戶號(hào)碼><空格><L隊(duì)尾客戶號(hào)碼>

策略2：<W窗口號(hào)>><空格><隊(duì)列中客戶號(hào)碼>例:T=3,Event=JHW2C0009,Now=W1S1

C0004W2S2C0000W3S0C0000,Wait=Q19F0010L002814用有限狀態(tài)自動(dòng)機(jī)模型實(shí)現(xiàn)復(fù)雜的過程控制策略15什么是有限狀態(tài)自動(dòng)機(jī)？FiniteStateMachine,又稱有限狀態(tài)機(jī)或簡(jiǎn)稱狀態(tài)機(jī)，是表示有限個(gè)狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型。狀態(tài)：存儲(chǔ)關(guān)于過去的信息，就是說,它反映從系統(tǒng)開始到現(xiàn)在時(shí)刻的輸入變化。轉(zhuǎn)移:指示狀態(tài)變更，并且用必須滿足來確使轉(zhuǎn)移發(fā)生的條件來描述它。動(dòng)作:是在給定時(shí)刻要進(jìn)行的活動(dòng)的描述。有多種類型的動(dòng)作：進(jìn)入動(dòng)作（Entryaction）-在進(jìn)入狀態(tài)時(shí)進(jìn)行退出動(dòng)作-在退出狀態(tài)時(shí)進(jìn)行輸入動(dòng)作-依賴于當(dāng)前狀態(tài)和輸入條件進(jìn)行轉(zhuǎn)移動(dòng)作-在進(jìn)行特定轉(zhuǎn)移時(shí)進(jìn)行16為了描述一個(gè)有限狀態(tài)機(jī)的工作狀況，可采用狀態(tài)轉(zhuǎn)換圖。狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖，圖中的每個(gè)節(jié)點(diǎn)表示一種狀態(tài)，一條邊（或弧）表示一個(gè)轉(zhuǎn)換關(guān)系。初始狀態(tài)通常用“沒有起點(diǎn)的箭頭”指向它來表示。終止?fàn)顟B(tài)是機(jī)器完成了它的程序之后的狀態(tài)，它通常表示為雙重圓圈。q0q1q3q2aabbb狀態(tài)轉(zhuǎn)換圖a17狀態(tài)表除了狀態(tài)轉(zhuǎn)換圖以外,還可以使用多種類型的狀態(tài)轉(zhuǎn)移表。最常見的表示如下：當(dāng)前狀態(tài)和條件的組合指示出下一個(gè)狀態(tài)。完整的動(dòng)作信息可以只使用腳注來增加。狀態(tài)轉(zhuǎn)移表當(dāng)前狀態(tài)→

條件↓狀態(tài)A狀態(tài)B狀態(tài)C條件X………條件Y…狀態(tài)C…條件Z………18FSM有兩個(gè)不同的類別：接受器／識(shí)別器和變換器。接受器產(chǎn)生一個(gè)二元輸出，說要么“是”要么“否”來回答輸入是否被機(jī)器接受。在所有輸入都被處理了的時(shí)候，如果當(dāng)前狀態(tài)是接受狀態(tài)，輸入被接受；否則被拒絕。作為規(guī)則，輸入是符號(hào)（字符）；動(dòng)作不使用。接受器狀態(tài)機(jī)q0q1q3q2aabbbErr非a或ba19變換器使用動(dòng)作基于給定輸入和／或狀態(tài)生成輸出。常分為兩種類型：Moore機(jī)和Mealy機(jī)。Moore機(jī)-只使用進(jìn)入動(dòng)作的FSM，就是說輸出只依賴于狀態(tài)。Moore模型的好處是行為的簡(jiǎn)單性。例：一個(gè)電梯門的MooreFSM。狀態(tài)“Opening”中的進(jìn)入動(dòng)作(E:)開啟電機(jī)開門，在狀態(tài)“Closing”中的進(jìn)入動(dòng)作以反方向開啟電機(jī)關(guān)門。狀態(tài)“Opened”和“Closed”不進(jìn)行任何動(dòng)作。變換器狀態(tài)機(jī)（1）q0openingcmd_opencmd_closecloseing開門關(guān)門openedclosed20Mealy機(jī)-只使用輸入動(dòng)作的FSM，就是說輸出依賴于輸入和狀態(tài)。MealyFSM的使用經(jīng)常導(dǎo)致狀態(tài)數(shù)目的簡(jiǎn)約。例：電梯門的MealyFSM有兩個(gè)輸入動(dòng)作：“開啟電機(jī)關(guān)門如果command_close下達(dá)”和“反向開啟電機(jī)開門如果

command_open下達(dá)”。變換器狀態(tài)機(jī)（2）q0openedcmd_open/開門cmd_close/關(guān)門closed21FSM的類型在實(shí)踐中經(jīng)常使用混合模型。進(jìn)一步可區(qū)分為確定型（DFA）和非確定型（NDFA、GNFA）自動(dòng)機(jī)。在確定型自動(dòng)機(jī)中，每個(gè)狀態(tài)對(duì)每個(gè)可能輸入只有精確的一個(gè)轉(zhuǎn)移。在非確定型自動(dòng)機(jī)中，給定狀態(tài)對(duì)給定可能輸入可以沒有或有多于一個(gè)轉(zhuǎn)移。這個(gè)區(qū)分在實(shí)踐而非理論中更有用，因?yàn)榇嬖谒惴ò讶魏蜰DFA轉(zhuǎn)換成等價(jià)的DFA，盡管這種轉(zhuǎn)換一般會(huì)增加自動(dòng)機(jī)的復(fù)雜性。22有限狀態(tài)自動(dòng)機(jī)的應(yīng)用有限狀態(tài)自動(dòng)機(jī)在很多不同領(lǐng)域中都是重要的，包括電子工程、語言學(xué)、計(jì)算機(jī)科學(xué)、哲學(xué)、生物學(xué)、數(shù)學(xué)和邏輯學(xué)。有限狀態(tài)機(jī)是在自動(dòng)機(jī)理論和計(jì)算理論中研究的一類自動(dòng)機(jī)。在計(jì)算機(jī)科學(xué)中，有限狀態(tài)機(jī)被廣泛用于建模應(yīng)用行為、硬件電路系統(tǒng)設(shè)計(jì)、軟件工程，編譯器、網(wǎng)絡(luò)協(xié)議、和計(jì)算與語言的研究。針對(duì)許多類型的編程問題，建立有限狀態(tài)自動(dòng)機(jī)模型，可以為分析、求解帶來很大的幫助。23例1：串口通信 兩臺(tái)微機(jī)通過串口通信,需在兩臺(tái)機(jī)器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動(dòng)機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開連接發(fā)出連接請(qǐng)求q0q1q2q0：空閑狀態(tài)q1:等待應(yīng)答狀態(tài)q2：通信狀態(tài)24例2：打電話(狀態(tài)機(jī)在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過程，話機(jī)的狀態(tài)及狀態(tài)遷移如下所示。q0q1q2q3q4摘機(jī)收到撥號(hào)音撥號(hào)收應(yīng)答信號(hào)掛機(jī)收齊號(hào)碼q0:空閑狀態(tài)q1:等待撥號(hào)音狀態(tài)q2:可以撥號(hào)狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)狀態(tài)遷移狀態(tài)25

接受器有限狀態(tài)機(jī)的形式化定義一個(gè)五元組其中：：有限的狀態(tài)集合；：有限的輸入字母表；：轉(zhuǎn)換函數(shù)，是到的映射；：初始狀態(tài)，；

：

終止?fàn)顟B(tài)集，

；接受器的形式化定義（初始狀態(tài)只有一個(gè)）26aq0q1q3q2aabbb狀態(tài)集合字母表初始狀態(tài)終止?fàn)顟B(tài)集轉(zhuǎn)換函數(shù)例3:用于識(shí)別輸入的字符串是否是或者形式的有限自動(dòng)機(jī)。27程序設(shè)計(jì)實(shí)例研究應(yīng)用有限狀態(tài)機(jī)模型求解問題，關(guān)鍵就是抽象出狀態(tài)，描述出狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移函數(shù)應(yīng)用有限狀態(tài)機(jī)解題步驟1、確定輸入集2、繪制狀態(tài)遷移圖（確定狀態(tài)，在每一個(gè)狀態(tài)下對(duì)輸入進(jìn)行分類，確定下一個(gè)狀態(tài)）3、確定狀態(tài)轉(zhuǎn)移函數(shù)（在某狀態(tài)下，接收到某一字符后，自動(dòng)機(jī)要執(zhí)行的操作，以及遷移到的下一狀態(tài)）28程序設(shè)計(jì)實(shí)例研究例4檢驗(yàn)輸入是否是合法的C語言注釋/*…*/導(dǎo)論教材P172,圖10.10,注意讀程序?qū)嵗齫1:等待*狀態(tài)q2：注釋開始狀態(tài)q3:等待/以結(jié)束注釋狀態(tài)q4：已接收注釋結(jié)束狀態(tài)29程序設(shè)計(jì)實(shí)例研究轉(zhuǎn)換函數(shù)分析start狀態(tài)下：輸入‘/’:state=q1輸出非‘/’:state=ERRORq1狀態(tài)下：輸入‘*’:state=q2輸出非‘*’:state=ERRORq2狀態(tài)下：輸入‘*’:state=q3輸入EOF：state=ERROR輸出其他:state=q2306.2程序設(shè)計(jì)實(shí)例研究轉(zhuǎn)換函數(shù)分析(續(xù)）q3狀態(tài)下：輸入‘*’:狀態(tài)不變輸入‘/’:state=q4輸入EOF：state=ERROR輸出其他:state=q2q4狀態(tài)下：輸入EOF：state=ACCEPT輸出其他:state=ERROR316.2程序設(shè)計(jì)實(shí)例研究例5去除C語言注釋32有限狀態(tài)機(jī)解題通用處理模式有限狀態(tài)機(jī)解題通用處理模式#defineSTART1...intstate=START;...while(state!=END){ ch=getch();switch(state){ caseSTART: if(ch==?)state=Q1;break;...}33為什么要用狀態(tài)機(jī)?有限狀態(tài)機(jī)到底有什么好處？怎樣才算應(yīng)用狀態(tài)機(jī)解題？1、狀態(tài)機(jī)用數(shù)學(xué)模型來設(shè)計(jì)解題思路，準(zhǔn)確可靠、簡(jiǎn)練，而程序員僅僅依靠自己的腦力和復(fù)雜的程序結(jié)構(gòu)。2、狀態(tài)機(jī)模型的思路和人解決問題的思路是一致的，都是把復(fù)雜的問題逐步分解為簡(jiǎn)單的步驟。所以狀態(tài)機(jī)模型是程序員的好助手，不是你的競(jìng)爭(zhēng)對(duì)手。3、狀態(tài)機(jī)解題的特征：在連續(xù)輸入的邏輯判斷過程中，有清楚的狀態(tài)分段，各狀態(tài)段之間的邏輯跳轉(zhuǎn)有嚴(yán)謹(jǐn)?shù)倪w移規(guī)則。4、應(yīng)用狀態(tài)機(jī)設(shè)計(jì)的程序最終表現(xiàn)出的清晰嚴(yán)謹(jǐn)?shù)倪壿嫿Y(jié)構(gòu)，而不是可讀性很差的“聰明”代碼。34例6:輸入一個(gè)字符串，以’#’結(jié)束，要求判斷其是否滿足anbncn形式。程序