計算機程序編程課程設(shè)計報告(馬爾可夫鏈算法生成隨機可讀文本)

1、計算機程序編程課程設(shè)計報告（馬爾可夫鏈算法生成隨機可讀文本）1、 引言：1、 馬爾可夫鏈的數(shù)學背景： 馬爾可夫鏈，因安德烈馬爾可夫（a.a.markov，18561922）得名 ，是數(shù)學隨機過程的一種。 在20實際的初期，由于物理學、通訊與控制、生物學、管理科學等領(lǐng)域的需要，隨機過程的理論逐步產(chǎn)生和發(fā)展起來。隨機過程理論為諸多領(lǐng)域的隨機現(xiàn)象提供了數(shù)學模型。 隨機過程的數(shù)學定義：設(shè)試驗e的樣本空間為，t是一個數(shù)集（t（-，+），如果對于每一個tt，都有一個定義在樣本空間上的隨機變量x（，t），則稱依賴于t的一族隨機變量x（，t），tt為隨機過程。 馬爾可夫鏈是一種特殊隨機過程。 馬爾可夫鏈的數(shù)學

2、定義：設(shè)隨機序列x（n），n=0,1,2,滿足如下條件： （1）對于每一個n（n=0,1,2,），x（n）取整數(shù)或它的子集（記為i）； （2）對于任意r+1個非負整數(shù)n1，n2 ，nr，m（0n1n2nrm）和任意正整數(shù)k ，以及狀態(tài)i1，i2，ir，i，ji，有px（n1）=i1，x（n2）=i2，x（nr）=ir，x（m）=i0，且 px(m+k)=jx(n1)=i1,x(n2)=i2,x(nr)=ir,x(m)=i =px(m+p)=jx(m)=i，則隨機序列x(n),n=0,1,2,為馬爾可夫鏈。條件概率px(m+k)=jx(m)=i稱為馬爾可夫鏈x(n),n=0,1,2,在時刻m從狀

3、態(tài)i出發(fā)，在時刻m+k轉(zhuǎn)移到狀態(tài)j的k步轉(zhuǎn)移概率，記作pij(m,m+k),即 pij(m,m+k)=px(m+k)=jx(m)=i.馬爾可夫鏈的性質(zhì)：對于齊次的馬爾可夫鏈有c-k方程成立，這一方程表明“從狀態(tài)i出發(fā)經(jīng)k+l步轉(zhuǎn)移到達狀態(tài)j”這一事件，可以分解為“從狀態(tài)i出發(fā)經(jīng)k步轉(zhuǎn)移到達中間狀態(tài)s（si），再從s出發(fā)經(jīng)l步轉(zhuǎn)移到達狀態(tài)j”這樣一些事件的并。對于不同的中間狀態(tài)s（si），這樣的事件是互不相容的。如果馬爾可夫鏈具有遍歷性，那么它的直觀意義是：不論質(zhì)點從哪一個狀態(tài)i出發(fā)，當轉(zhuǎn)移步數(shù)k充分大時，到達狀態(tài)j的概率近似于常數(shù)j 。如果已求出j 值，則當k充分大時j 可以作為pij（k）（

4、i,ji）的近似值。 如果馬爾可夫鏈具有平穩(wěn)分布，并取初試概率分布為平穩(wěn)分布，則它在任意時刻m的概率分布都相同，都等于初始概率分布。2、馬爾可夫鏈的典型應(yīng)用：物理馬爾可夫鏈通常用來建模排隊理論和統(tǒng)計學中的建模，還可作為信號模型用于熵編碼技術(shù)，如算術(shù)編碼（著名的lzma數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈與類似于算術(shù)編碼的區(qū)間編碼）。馬爾可夫鏈也有眾多的生物學應(yīng)用，特別是人口過程，可以幫助模擬生物人口過程的建模。隱蔽馬爾可夫模型還被用于生物信息學，用以編碼區(qū)域或基因預(yù)測。馬爾可夫鏈最近的應(yīng)用是在地理統(tǒng)計學（geostatistics）中。其中，馬爾可夫鏈用在基于觀察數(shù)據(jù)的二到三維離散變量的隨機模擬。這

5、一應(yīng)用類似于“克里金”地理統(tǒng)計學（kriging geostatistics），被稱為是“馬爾可夫鏈地理統(tǒng)計學”。3、 相關(guān)圖書介紹： 馬爾可夫決策過程引論（作者：胡奇英/劉建庸 ） 簡介:馬爾可夫決策過程是研究馬氏型序貫(動態(tài))決策問題的工具。本書提供了處理離散時間、連續(xù)時間、半馬氏等三類基本馬氏決策過程模型的一般化方法。在此基礎(chǔ)上，本書研究了狀態(tài)部分可觀察、多目標、帶約束條件等一般化馬氏決策過程以及處于隨機變化環(huán)境中的馬氏決策過程。 生滅過程與馬爾可夫鏈 （作者：王梓坤 ）簡介：本書敘述生滅過程與馬爾可夫鏈的基本理論并介紹近年來的一些研究進展第一章概述隨機過程的一般概念：第二章至第四章講述

6、馬爾可夫鏈；第五、六章研究生滅過程的基本理論和構(gòu)造，主要是用概率方法；第七、八章研究生滅過程和雙邊生滅過程構(gòu)造論，主要是用分析的方法。同時還討論了用兩種方法所得結(jié)論之間的聯(lián)系。2、 數(shù)據(jù)結(jié)構(gòu)設(shè)計：本程序的數(shù)據(jù)結(jié)構(gòu)在用哈希表設(shè)計。1、 哈希表介紹：哈希表是一種散列結(jié)果，它只通過關(guān)鍵字的特征便可以查找出所需結(jié)果，是一種十分便捷的用于查找的數(shù)據(jù)結(jié)構(gòu)。在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系h，使每個關(guān)鍵字和結(jié)構(gòu)中唯一的一個存儲位置相對應(yīng)。因而在查找時，只要根據(jù)這個對應(yīng)關(guān)系h找到給定關(guān)鍵字值k的像h（k），即對應(yīng)的存儲位置。若結(jié)構(gòu)中存在關(guān)鍵字和k相等的記錄，則必定在h（k）的存儲位置上，

7、因此，不需要進行比較便可直接取得所查記錄。2、 哈希表的設(shè)計：前綴表設(shè)計：struct qianzhuib char *phrasen; struct houzhuib *houzhui;struct qianzhuib *next;struct qianzhuib *qianzhuitablehash;phrase2用于存儲前綴struct houzhuib *houzhui用于指向該前綴所跟隨的后綴struct qianzhuib *next用于指向具有相同關(guān)鍵字的同義詞前綴前綴表是一個很長（長度為hash）的結(jié)構(gòu)體數(shù)組后綴表設(shè)計：struct houzhuib char *word;st

8、ruct houzhuib *next; char *word用于指向后綴詞struct houzhuib *next用于指向同一前綴所跟隨的不同后綴對應(yīng)關(guān)系h的設(shè)計：對應(yīng)關(guān)系用于確定一個前綴具體存放在前綴表哪一個下標所對應(yīng)的空間中。我們將前綴詞組中每個字母的acsii值乘以37后作和當作對應(yīng)關(guān)系。之所以選擇37，是因為這可以將前綴較均勻的分布在散列表上。3、 程序架構(gòu)介紹：對算法的思考：這個程序運用了馬爾可夫鏈算法。因為文章的結(jié)尾兩個詞是沒有后綴的，所以當以這兩個詞為前綴時文章的輸出一定可以結(jié)束。如果把這兩個詞看作一個吸收壁，那么根據(jù)數(shù)學理論這個馬爾可夫鏈一定是具有遍歷性的，也就是說這個輸出

9、是可以結(jié)束的。這就是馬爾可夫鏈算法的可行性。int hash(char *cn) 該函數(shù)表示哈希表的對應(yīng)關(guān)系，它可以計算出前綴在哈希表中的對應(yīng)位置。調(diào)用它時需要輸入一個指針數(shù)組，這個數(shù)組分別指向前綴詞組的兩個詞；它返回的整數(shù)值就是前綴在哈希表中的位置。struct qianzhuib * lookout(char *phrasen,int create)該函數(shù)用于查找、添加一個前綴。調(diào)用它時第一個參數(shù)為指向需要添加前綴的指針數(shù)組，的二個參數(shù)為創(chuàng)建標識符（當create為0時之查找，當create為1時將前綴添加進前綴表）；它返回為一個指向所查找或創(chuàng)建的前綴結(jié)構(gòu)體的指針。void add(cha

10、r *phrasen,char *houzhui)該函數(shù)用于向指定前綴添加后綴。調(diào)用它時第一個參數(shù)為需添加后綴的前綴，第二個參數(shù)為指向需要添加的后綴的指針。該函數(shù)沒有返回值。void addhouzhui(struct qianzhuib *p,char *houzhui)該函數(shù)是上一函數(shù)內(nèi)部的函數(shù)，它用特定的方法添加后綴。int shuchu(char *phrasen)該函數(shù)用于輸出。調(diào)用該函數(shù)時參數(shù)為指向前綴的指針，函數(shù)隨機選擇一個對應(yīng)的后綴并將其輸出；函數(shù)返回一個整型變量，返回1表示繼續(xù)輸出，返回0表示輸出結(jié)束。在編寫c#語言時運用了許多模板庫：四、程序調(diào)試：1、編譯錯誤：由于本程序涉

11、及函數(shù)、變量很多，所以在編寫階段經(jīng)常把名字打錯，導(dǎo)致編譯過程中出現(xiàn)眾多錯誤。經(jīng)過多次修改后這些錯誤被排除。2、運行錯誤： （1）文章不能成功輸入：使用for(x=0;a!=13;x+)導(dǎo)致文章不能不能輸入，正確應(yīng)為for(x=0;a!=n;x+)。13不是換行符的ascii碼。 由于在裝入單詞時沒有在末尾添加0導(dǎo)致文章輸入不正確。添加語句wzzcxy=0;后輸入正確。 （2）查詢函數(shù)lookout中遇到問題：lookout函數(shù)中有一語句錯誤for(i=0;i=n;i+)它導(dǎo)致程序無法為同一個前綴建立不同的后綴，改為for(i=0;in;i+)后問題解決。 (3)關(guān)于函數(shù)中的return：在函數(shù)

12、中如果執(zhí)行了return語句，那么函數(shù)便就此結(jié)束，不會再執(zhí)行下面的語句。在lookout函數(shù)的編寫中曾經(jīng)出現(xiàn)了這種錯誤，即函數(shù)執(zhí)行了return后不再向下執(zhí)行。 五、程序測試：輸入文本：a b c a b d a b e a b f a b g a b h.輸入前綴：a b輸出文本：a b e a b g a b c a b e a b e a b h.輸入文本：show your flowchars and conceal your tables and i will be mystified. show your tables and your flowcharts will be obv

13、ious. 輸入前綴：show your輸出文本：show your tables and your flowcharts will be my stified. show your flowchars and conceal your tables and i will be obvious. 六、語言對比：從代碼結(jié)構(gòu)來看，c語言代碼長度大結(jié)構(gòu)較為復(fù)雜，需要編寫者考慮每一個細節(jié)。由于長度大結(jié)構(gòu)復(fù)雜，c語言程序在編譯期和運行期都出現(xiàn)了很多錯誤，花費了大量時間調(diào)試修改。而c#語言采用面向?qū)ο笤O(shè)計的方法，編寫中運用了大量的類和模板，因此代碼緊湊、數(shù)據(jù)結(jié)構(gòu)清晰，算法使人一目了然。即使發(fā)生錯誤，調(diào)試修

14、改也比較容易。從運行時間來看，運用c語言編寫的程序效率較高，運行時間較短；c#程序效率沒有c語言程序高。7、 程序代碼： c語言代碼：#define n 2 /*前綴長度*/#define hash 4093 /*散列長度*/#define long 30 /*單詞長度*/#define null 0#define lenq sizeof(struct qianzhuib)#define lenh sizeof(struct houzhuib)#include #include #include #include /*后綴表結(jié)構(gòu)*/struct houzhuib char *word;stru

15、ct houzhuib *next; /*前綴散列表*/struct qianzhuib char *phrasen; /*裝前綴單詞*/struct houzhuib *houzhui;struct qianzhuib *next;struct qianzhuib *qianzhuitablehash;/*計算哈希值*/int hash(char *cn) int h;int i;char *p;h=0;for(i=0;inext)for(i=0;iphrasei)!=0) break;if(n=i) return (p);if(1=create)p=(struct qianzhuib*)

16、malloc(lenq);for(i=0;iphrasei=phrasei;p-houzhui=null;p-next=qianzhuitableh;/*往前插入*/qianzhuitableh=p;return (p); /*添加后綴*/void addhouzhui(struct qianzhuib *p,char *houzhui)struct houzhuib *pp; pp=(struct houzhuib*) malloc(lenh);pp-word=houzhui;pp-next=p-houzhui;p-houzhui=pp; /*添加后綴*/ void add(char *ph

17、rasen,char *houzhui)struct qianzhuib *p;p=lookout(phrase,1);/*創(chuàng)建前綴*/addhouzhui(p,houzhui);/*加入后綴*/memmove(phrase,phrase+1,(n-1)*sizeof(phrase0);/*庫函數(shù)*/phrasen-1=houzhui; /*輸出函數(shù)*/int shuchu(char *phrasen)struct qianzhuib *p;struct houzhuib *sp;int match,i;char *w;p=lookout(phrase,0);if(p-houzhui=null

18、) i=0;return (i);else match=0;for(sp=p-houzhui;sp!=null;sp=sp-next)if(rand()%+match=0)w=sp-word;printf(%s40,w);memmove(phrase,phrase+1,(n-1)*sizeof(phrase0);phrasen-1=w;i=1;return (i);void main()char wzzc20030;/*二維數(shù)組用于暫存文章*/char w120,w220; char *ppn,*pppn; int x,y,j;int h; char a;/*前綴表初始化為空*/for(h=0

19、;hhash;h+)qianzhuitableh=null; /*輸入文章*/printf(請輸入一段文章:); a=0;for(x=0;a!=n;x+)/*回車*/for(y=0;(a=getchar()!=32)&(a!=n);y+)/*空格*/wzzcxy=a;wzzcxy=0;/*如此之后x的值便是文章單詞長度*/ /*建立前綴表和后綴表*/ppp0=wzzc0;ppp1=wzzc1;for(j=2;jx;j+)add(ppp,wzzcj); /*隨機輸出*/ printf(請輸入一個前綴n); scanf(%s%s,w1,w2); pp0=w1; pp1=w2; while(shuc

20、hu(pp)=1);c#代碼：using system;using system.collections.generic;using system.linq;using system.text;namespace mtest class program random random = new random(); static void main(string args) string words = string.empty; program p = new program(); while (1 = 1) /words = console.readline(); words = show your flowchars and conceal your tables and i will be my stified. show your tables and your flowcharts will be obvious.(end); console.readline(); if (words.tolower() = exit) break; console.writeline(p.getstr(words); public string getstr(string words) list templist = new list(); li