1、精選優(yōu)質(zhì)文檔-傾情為你奉上目錄實(shí)驗(yàn)A- ADFA的可判定性1、 問題描述Problem descriptionADFA=< B,w >|B是DFA，w是串，B接收w證明：ADFA是可判定的。 實(shí)驗(yàn)方法:編寫一個(gè)算法/程序，對(duì)于任意給定的輸入，可以判定ADFA。 Input有多個(gè)測(cè)試序列，測(cè)試結(jié)束于測(cè)試文件結(jié)束； 每個(gè)測(cè)試序列的第一行為幾個(gè)正整數(shù)n m t a分別表示有n個(gè)狀態(tài)，從a開始m個(gè)小寫字母組成的字符集，第一個(gè)狀態(tài)默認(rèn)為起始狀態(tài)。t個(gè)接受狀態(tài)和a個(gè)測(cè)試串,接下來為一個(gè)n行m列的矩陣S,其中Sij表示第i行第j列，意義為狀態(tài)i經(jīng)過字母j到達(dá)狀態(tài)Sij。接下來有t個(gè)數(shù)字,表示t個(gè)

2、接受狀態(tài)值，然后是a行，每行一個(gè)串表示待測(cè)試的串。Output對(duì)于每個(gè)字符串輸出YES表示該DFA接受該串，NO表示不接受。Sample Input3 3 1 22 3 23 3 33 3 32abSample OutputYESNO2、 算法設(shè)計(jì)思路A: 首先將輸入的狀態(tài)轉(zhuǎn)移矩陣保存在S數(shù)組中，其中其中Sij表示第i行第j列，意義為狀態(tài)i經(jīng)過字母j到達(dá)狀態(tài)Sij。B: 對(duì)每一個(gè)輸入的串W,從after（after表示每次轉(zhuǎn)換后的狀態(tài)，初始為起始狀態(tài)）開始，按照每一個(gè)字符，得到相應(yīng)的后繼狀態(tài)，保存在after中。C: 最后判斷acceptafter的值，即串在DFA上運(yùn)行之后最終狀態(tài)是否可接受

3、。3、 實(shí)驗(yàn)總結(jié)總的來說這一題比較容易（有點(diǎn)太水了），只要把輸入串的每一個(gè)字符按照前面的狀態(tài)得到后繼狀態(tài)，并不斷的走下去，直到串的最后一個(gè)字符，就可以得到最后的狀態(tài)，再根據(jù)其是否處在接受態(tài)，給出相應(yīng)的輸出4、 AC代碼#include <iostream>#include <cstring>using namespace std;long n,m,t,a;long s10001000; /存儲(chǔ)轉(zhuǎn)移矩陣long accept1000; /存儲(chǔ)接受狀態(tài)int main() while(cin>>n>>m>>t>>a) mems

4、et(s,0,sizeof(s); memset(accept,0,sizeof(accept); for(int i = 1;i<=n;i+) for(int j = 1;j<=m;j+) cin>>sij; for(int i = 0;i<t;i+) long temp; cin>>temp; accepttemp = 1; while(a-) string temps; cin>>temps; int after = 1; for(int i = 0;i<temps.length();i+) after = saftertemp

5、si-'a'+1; if(acceptafter=1) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0;實(shí)驗(yàn)B-CFG是P成員1、 問題描述Problem description上下文無關(guān)文法CFG G是否派生某個(gè)串W。采用動(dòng)態(tài)規(guī)劃（Dynamic Programming）設(shè)計(jì)一個(gè)一個(gè)多項(xiàng)式時(shí)間的驗(yàn)證算法。Input輸入第一行為一個(gè)正整數(shù)n，接下來n行為一個(gè)滿足喬姆斯基范式的文法描述。然后一個(gè)正整數(shù)m，接下來m行為m個(gè)小寫字母組成的字符串

6、(長(zhǎng)度小于100) 表示m個(gè)待測(cè)試的串。Output對(duì)于每一個(gè)測(cè)試串返回"yes"或者"no"，表示該串是否能被文法派生出來。Sample Input4S->ABA->AB|aB->BC|bC->CA|CC|c3abacbcSample Outputyesnono2、 算法設(shè)計(jì)思路A: 找出所有A->b型規(guī)則B: 找出所有A->BC型規(guī)則C: 考察每一個(gè)長(zhǎng)為1的子串D: 考察L長(zhǎng)度的子串E: 檢查起始變?cè)欠裨趖able0n中3、 實(shí)驗(yàn)總結(jié)（1）剛開始用棧和轉(zhuǎn)移矩陣來進(jìn)行狀態(tài)的切換，想要先把CFG轉(zhuǎn)換為一個(gè)PDA，在根

7、據(jù)PDA接受串的情況來判斷（因?yàn)轭}目要求線性時(shí)間復(fù)雜度），后來發(fā)現(xiàn)轉(zhuǎn)換成PDA的時(shí)候，每一個(gè)轉(zhuǎn)移矩陣?yán)飸?yīng)該是一個(gè)狀態(tài)的集合。（2）原本定義一個(gè)set<int> S來表示轉(zhuǎn)移矩陣，但是覺得這樣還不如直接用原來的CFG按照某種規(guī)則來進(jìn)行替換，讓他的復(fù)雜度為線性的。具體線性替換的順序在2中詳細(xì)介紹了4、 AC代碼#include<cstdlib>#include<iostream>#include<fstream>using namespace std;int main() int n,m;/n行滿足喬姆斯基范式的文法描述, m行待測(cè)字符串while(

8、cin>>n)string *cfg;/CFG文法描述cfg=new stringn;for(int i=0;i<n;i+)cin>>cfgi;/輸入CFG文法cin>>m;/輸入待測(cè)字符串?dāng)?shù)量string *str;/待測(cè)字符串str=new stringm;for(int i=0;i<m;i+)cin>>stri;/輸入待測(cè)字符串int *lstr;/待測(cè)字符串的長(zhǎng)度lstr=new intm;for(int i=0;i<m;i+)lstri=stri.length();string *table;/定義表格table=ne

9、w string*m;for(int i=0;i<m;i+)tablei=new string*lstri;for(int i=0;i<m;i+)for(int j=0;j<lstri;j+)tableij=new stringlstri;/找出所有A->b型規(guī)則string Ab100;int num=0;for(int i=0;i<n;i+)for(int k=3;k<cfgi.length();k+)if(cfgik>96 && cfgik<123)Abnum+=cfgi0;Abnum+=cfgik;num+;/找出所有A-

10、>BC型規(guī)則string ABC100;int num2=0;for(int i=0;i<n;i+)for(int k=3;k<cfgi.length();k+)if(cfgik<91)ABCnum2+=cfgi0;ABCnum2+=cfgik;ABCnum2+=cfgik+1;k+;num2+;/考察每一個(gè)長(zhǎng)為1的子串for(int i=0;i<m;i+)for(int j=0;j<lstri;j+)/考察每一個(gè)長(zhǎng)為1的子串for(int k=0;k<num;k+)if(strij=Abk1)/考察CFG文法的每一個(gè)字符tableijj=Abk0;/

11、考察l長(zhǎng)度的子串for(int i=0;i<m;i+)for(int l=2;l<=lstri;l+)/l是子串的長(zhǎng)度for(int p=0;p<lstri-l+1;p+)/p是子串的起始位置int j=p+l-1;/j是子串的結(jié)束位置for(int k=p;k<j;k+)/k是分裂的位置 k<=j-1 ->k<jfor(int q=0;q<num2;q+)if(tableipk.find(ABCq1,0)!=string:npos && tableik+1j.find(ABCq2,0)!=string:npos)tableipj

12、+=ABCq0;/檢查起始變?cè)欠裨趖able0n中for(int i=0;i<m;i+)int flag=0;if(tablei0lstri-1.find(cfg00,0)!=string:npos)flag=1;if(flag=1)cout<<"yes"<<endl;elsecout<<"no"<<endl;delete cfg;delete str;for(int i=0;i<m;i+)for(int j=0;j<lstri;j+)delete tableij;for(int i=0

13、;i<m;i+)delete tablei;delete table; return 0;實(shí)驗(yàn)C-NFA轉(zhuǎn)換為DFA1、 問題描述Problem description有限狀態(tài)自動(dòng)機(jī)（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限內(nèi)存的計(jì)算過程和某些語言類而抽象出的一種計(jì)算模型。有限狀態(tài)自動(dòng)機(jī)擁有有限數(shù)量的狀態(tài)，每個(gè)狀態(tài)可以遷移到零個(gè)或多個(gè)狀態(tài)，輸入字串決定執(zhí)行哪個(gè)狀態(tài)的遷移。有限狀態(tài)自動(dòng)機(jī)可以表示為一個(gè)有向圖。有限狀態(tài)自動(dòng)機(jī)是自動(dòng)機(jī)理論的研究對(duì)象。Input輸入第

14、一行只有一個(gè)正整數(shù)t，表示有t個(gè)測(cè)試數(shù)據(jù)（意味著t個(gè)NFA）t10;對(duì)于每組測(cè)試數(shù)據(jù)（每個(gè)NFA），首先是3個(gè)正整數(shù)n,Q0,f，分別表示狀態(tài)數(shù)、起始狀態(tài)集合和接受狀態(tài)集合的特征串對(duì)應(yīng)的整數(shù)。n10;Q0,f < 2n;接下來兩行是NFA的轉(zhuǎn)移函數(shù)矩陣，第一行是每個(gè)狀態(tài)在輸入為0的狀態(tài)轉(zhuǎn)移情況，用特征串對(duì)應(yīng)的整數(shù)表示；第二行是每個(gè)狀態(tài)在輸入為1的狀態(tài)轉(zhuǎn)移情況。Output對(duì)于每個(gè)NFA，輸出四行表示與之等價(jià)的DFA。輸出格式如下：第一行3個(gè)空格隔開的整數(shù)a b c，分別表示DFA的狀態(tài)數(shù)，接受狀態(tài)數(shù)，起始狀態(tài)的編號(hào)（從0開始對(duì)狀態(tài)編號(hào)）。要求 a < 65536。 b，c a 第二

15、行b個(gè)空格分隔的整數(shù)，表示每個(gè)接收狀態(tài)的編號(hào),每個(gè)編號(hào)的值一定在0,a)之間。第三行、第四行每行a個(gè)空格分隔的整數(shù)，表示DFA的轉(zhuǎn)移函數(shù)矩陣，第三行第i個(gè)值ui表示狀態(tài)轉(zhuǎn)移函數(shù)的一項(xiàng)（qi，0）ui，第四行第i個(gè)值vi表示狀態(tài)轉(zhuǎn)移函數(shù)的一項(xiàng)（qi，1）vi，,每個(gè)ui,vi的值一定在0,a)之間。 Sample Input14 1 81 4 0 87 8 8 8Sample Output16 8 18 9 10 11 12 13 14 150 1 4 5 0 1 4 5 8 9 12 13 8 9 12 130 7 8 15 8 15 8 15 8 15 8 15 8 15 8 1501q0q

16、0q0q1q2q1q2q3q2q3 q3q3q32、 算法設(shè)計(jì)思路01q017q148q208q388狀態(tài)集合的子集合，采用二進(jìn)制（特征）串的方式，一個(gè)子集中包含該狀態(tài)，對(duì)應(yīng)的特征串就為1，否則為0，比如上面狀態(tài)集合的子集q0q1q2，其特征串就是0111，而子集q0，其特征串就是0001。將對(duì)應(yīng)的特征串轉(zhuǎn)換為十進(jìn)制的數(shù)字，得到轉(zhuǎn)移函數(shù)。3、 實(shí)驗(yàn)總結(jié)在轉(zhuǎn)化的過程中經(jīng)NFA中狀態(tài)矩陣中的每一個(gè)狀態(tài)的集合映射到DFA中的一個(gè)狀態(tài)。即NFA中的狀態(tài)子集為一個(gè)DFA中的狀態(tài)；只要NFA狀態(tài)子集中有一個(gè)為接受態(tài)，相應(yīng)的映射的DFA中的狀態(tài)就為接受態(tài)4、 AC代碼#include<cstdio&g

17、t;#include<cstdlib>#include<iostream>#include<cstring>#include<cmath>#define M 99999using namespace std;int ansM;int oneM;int zeroM;int lftM;int rgtM;int changeM;bool visM;bool acM;int cnt, n, q, f;int index(int p) int x = 1; if(p = 1) return 0; int i = 0; while(+i) x <<

18、;= 1; if(p = x) return i; return 0;int mege(int a, int b) while(b) int x = b&(-b); if(!(a&x) a = x; b = x; return a;void dfs(int p) anscnt = p; int lsum = 0, rsum = 0; while(p) int x = p&(-p); int y = index(x); lsum = mege(lsum, zeroy); rsum = mege(rsum, oney); p = x; lftcnt = lsum; rgtc

19、nt = rsum; cnt+; if(!vislsum) vislsum = 1, dfs(lsum); if(!visrsum) visrsum = 1, dfs(rsum);int main() int t; scanf("%d", &t); while(t-) scanf("%d%d%d", &n, &q, &f); for(int i = 0; i < n; i+) scanf("%d", &zeroi); for(int i = 0; i < n; i+) scanf(&

20、quot;%d", &onei); cnt = 0; memset(vis, 0, sizeof(vis); memset(ac, 0, sizeof(ac); visq = 1; dfs(q); int sum = 0; for(int i = 0; i < cnt; i+) if(ansi&f) aci = 1, sum+; for(int i = 0; i < cnt; i+) changeansi = i; printf("%d %d %dn", cnt, sum, 0); for(int i = 0, j = 0; i <

21、; cnt; i+) if(aci) if(j) printf(" "); printf("%d", i); j+; printf("n"); for(int i = 0; i < cnt; i+) if(i) printf(" "); printf("%d", changelfti); printf("n"); for(int i = 0; i < cnt; i+) if(i) printf(" "); printf("%d&quo

22、t;, changergti); printf("n"); return 0;實(shí)驗(yàn)D-兩個(gè)數(shù)的互素判定1、問題描述Problem description稱兩個(gè)正整數(shù)是互素的，當(dāng)它們沒有大于1的公因子的時(shí)候。比如，4與9就是互素的，盡管4與9都不是素?cái)?shù)，但4與9只有一個(gè)公因子：1，所以它們互素。但4與22就不是互素的，因?yàn)樗鼈冇幸粋€(gè)大于1的公因子：2。你的任務(wù)，給你2個(gè)數(shù)，判斷它們是否互素。Input有多個(gè)測(cè)試序列，測(cè)試結(jié)束于測(cè)試文件結(jié)束； 每個(gè)測(cè)試序列占一行，每行2個(gè)用空格隔開的正整數(shù)a,b。a,b < 264. Output對(duì)于每對(duì)輸入的整數(shù)，輸出”YES”，如果它

23、們互素；否則，輸出”NO”。 Sample Input22 44 9Sample OutputNOYES2、 算法設(shè)計(jì)思路A：我們先來比較總結(jié)一下GUN中整形的范圍：int - + (4 Bytes)unsigned int 0 (4 Bytes)long = intlong long - + (8 Bytes)double 1.7 * 10308 (8 Bytes)unsigned int 0_int64的最大值：_int64的最小值：-unsigned _int64的最大值：B：從上面的結(jié)果可以看到，unsigned _int64可以符合題目的數(shù)據(jù)要求C:用輾轉(zhuǎn)相除的方法來計(jì)算最大公約數(shù)，

24、這里使用輾轉(zhuǎn)相除的遞歸法3、 實(shí)驗(yàn)總結(jié)（這題也好水）實(shí)驗(yàn)時(shí)要注意題目所給數(shù)據(jù)的取值范圍；對(duì)于輾轉(zhuǎn)相除求最大公約數(shù)，可以用非遞歸的或者遞歸的形式，兩者的復(fù)雜度相差無幾，鑒于遞歸形式的思路比較明確，而且方便編寫（幾行代碼就可以搞定），所以使用遞歸形式的輾轉(zhuǎn)相除。4、 AC代碼#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;unsigned _int64 gcd(unsigned _int64 a, unsigned _int64 b) if (b > 0) r

25、eturn gcd(b, a % b); return a;int main()unsigned _int64 a,b; while(cin>>a>>b)if(gcd(a,b)=1) printf("YESn");elseprintf("NOn");return 0;實(shí)驗(yàn)E-可判定的DFA的空問題1、 問題描述Problem descriptionEDFA=< B >|B是DFA，且L（A）= 證明：EDFA是可判定的語言。 實(shí)驗(yàn)方法:編寫一個(gè)算法/程序，對(duì)于任意給定的輸入（/確定性有限狀態(tài)自動(dòng)機(jī)DFA），可以判定ED

26、FA。Input有多個(gè)測(cè)試序列，測(cè)試結(jié)束于測(cè)試文件結(jié)束；每個(gè)測(cè)試序列相對(duì)應(yīng)一個(gè)DFA，其第一行為2個(gè)正整數(shù)n，m，表示有n個(gè)狀態(tài)，狀態(tài)集Q=q0,q1,qn-1。默認(rèn)起始狀態(tài)為q0，字符集有m個(gè)字符。0 < n,m 100。隨后n行，每行m個(gè)空格隔開的整數(shù)ij，（ 0 i < n , 0 j < m ）表示DFA的狀態(tài)轉(zhuǎn)移函數(shù)。ij表示第i個(gè)狀態(tài)在輸入j（字母表第j個(gè)字符）時(shí)，變?yōu)榈趇j個(gè)狀態(tài)。每個(gè)DFA的最后一行，首先一個(gè)整數(shù)f，表示接受狀態(tài)數(shù)，然后f個(gè)空格隔開的整數(shù)fk（0 k < f），是所有接受狀態(tài)的編號(hào)。其中 0 ij，fk < n。Output對(duì)于每個(gè)輸入的DFA，輸出”YES”，如果該DFA確實(shí)不接受任何串；否則，輸出”NO”。 Sample Input1 20 01 01 20 00Sample OutputNOYES2、 算法設(shè)計(jì)思路A：<DFA B>是否接受w的問題。ADFA是可判定的。ANFA是可判定的。ARES是可判定的。EDFA是可判定的。EQDFA是可判定的。P100。核心思想：圖靈機(jī)跟蹤DFA的狀態(tài)和當(dāng)前位置，狀態(tài)和位置的變化由轉(zhuǎn)移