無優(yōu)先級(jí)問題

皖西學(xué)院信息工程系實(shí) 驗(yàn) 報(bào) 告姓名王禮 學(xué)號(hào) 院系信息工程系 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)年級(jí) 2007級(jí) 班級(jí) 0702班 小組實(shí)驗(yàn)任務(wù)分工 獨(dú)立完成 實(shí)驗(yàn)時(shí)間 2010 年9月 20日實(shí)驗(yàn)名稱 無優(yōu)先級(jí)運(yùn)算問題 指導(dǎo)老師及職稱 蘇守寶 教授 皖西學(xué)院信息工程系實(shí)驗(yàn)課程：算法分析與設(shè)計(jì) 實(shí)驗(yàn)名稱：無優(yōu)先級(jí)運(yùn)算問題 （綜設(shè)型實(shí)驗(yàn)）第一部分 實(shí)驗(yàn)內(nèi)容1實(shí)驗(yàn)?zāi)繕?biāo)對(duì)于給定的n個(gè)正整數(shù)，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法用最少的無優(yōu)先級(jí)運(yùn)算次數(shù)產(chǎn)生整數(shù)m 。2. 實(shí)驗(yàn)任務(wù)（1）從所給定的題目中選擇一題，使用分支限界法求解之。（2）用文字來描述你的算法思路，包括解空間、限界函數(shù)、算法主要步驟等。（3）在Windows環(huán)境下使用C/C+語言編程實(shí)現(xiàn)算法。（4）記錄運(yùn)行結(jié)果，包括輸入數(shù)據(jù)，問題解答及運(yùn)行時(shí)間。（5）分析算法最壞情況下時(shí)間復(fù)雜度和空間復(fù)雜度。（6）談?wù)剬?shí)驗(yàn)后的感想，包括關(guān)于該問題或類似問題的求解算法的建議。3. 實(shí)驗(yàn)設(shè)備及環(huán)境PC；C/C+等編程語言。4. 實(shí)驗(yàn)主要步驟(1) 根據(jù)實(shí)驗(yàn)?zāi)繕?biāo)，明確實(shí)驗(yàn)的具體任務(wù)；(2) 設(shè)計(jì)求解問題的算法，并編寫程序?qū)崿F(xiàn)算法；(3) 設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)并運(yùn)行程序、記錄運(yùn)行的結(jié)果；(4) 分析算法時(shí)空性能；(5) 實(shí)驗(yàn)后的心得體會(huì)。第二部分 問題及算法1. 問題描述：給定n個(gè)正整數(shù)和4個(gè)運(yùn)算符+，-，*，/，且運(yùn)算符無優(yōu)先級(jí)，如2+35=25。對(duì)于任意給定的整數(shù)m，試設(shè)計(jì)一個(gè)算法，用以上給出的n個(gè)數(shù)和4個(gè)運(yùn)算符，產(chǎn)生整數(shù)m，且用的運(yùn)算次數(shù)最少。給出的n個(gè)數(shù)中每個(gè)數(shù)最多只能用1次，但每種運(yùn)算符可以任意使用 2. 算法設(shè)計(jì)：對(duì)于給定的n個(gè)正整數(shù)，設(shè)計(jì)一個(gè)算法，用最少的無優(yōu)先級(jí)運(yùn)算次數(shù)產(chǎn)生整數(shù)m。 3. 數(shù)據(jù)輸入由文件input.txt給出輸入數(shù)據(jù)。第一行有兩個(gè)正整數(shù)n和m。第二行是給定的用于運(yùn)算的n個(gè)正整數(shù)。4. 結(jié)果輸出將計(jì)算出的產(chǎn)生整數(shù)的m的最少無優(yōu)先級(jí)運(yùn)算次數(shù)以及最優(yōu)無先級(jí)運(yùn)算表達(dá)式輸出到文件output.txt。 輸入文件示例 輸出文件示例 Input.txt output.txt 5 25 2 5 2 3 6 7 2 + 3 * 5第三部分 實(shí)驗(yàn)結(jié)果與分析1. 實(shí)驗(yàn)數(shù)據(jù)及結(jié)果 2. 實(shí)驗(yàn)分析及結(jié)論針對(duì)該實(shí)驗(yàn)我做了仔細(xì)分析，剛看到這個(gè)題目，不知所云，后來分析后才知道，給定n個(gè)正整數(shù)和4個(gè)運(yùn)算符+，-，*，/，且運(yùn)算符無優(yōu)先級(jí)，如2+35=25。對(duì)于任意給定的整數(shù)m，試設(shè)計(jì)一個(gè)算法，用以上給出的n個(gè)數(shù)和4個(gè)運(yùn)算符，產(chǎn)生整數(shù)m，且用的運(yùn)算次數(shù)最少。給出的n個(gè)數(shù)中每個(gè)數(shù)最多只能用1次，但每種運(yùn)算符可以任意使用。第四部分 心得與展望1. 自我評(píng)價(jià)及心得體會(huì)分析無優(yōu)先級(jí)算法問題時(shí)候一開始有點(diǎn)無從下手，經(jīng)過我查資料以后，再加上自己的分析和見解，以及老師的幫助，最終得出了答案，讓我明白了只要自己 從分利用自己掌握的技術(shù)和周邊的壞境比如我們學(xué)校的老師，網(wǎng)絡(luò)資源等，大多問題都可以解決的。2. 展望對(duì)算法產(chǎn)生了濃厚的興趣，打算以后可能會(huì)從事算法設(shè)計(jì)。第五部分 附錄1. 源程序#includeusing namespace std;int k;class readinfriend int nreadin(int n,int m);private:bool found(); /found判斷是否找到解bool search(int t);int n,m,x; int * a; /給定的用于運(yùn)算n個(gè)正整數(shù)的存放位置int* num; /存放運(yùn)算的產(chǎn)生整數(shù)mint* operate; int* flag; char* ptr; /存儲(chǔ)結(jié)果中的運(yùn)符;/用迭代加深的回溯法bool readin:search(int depth) /depth:遞歸深度if(depthk)if(found() return true; /判斷結(jié)點(diǎn)是否滿足件，即是否找到解elsereturn false;elsefor(int i=0;in;i+)if(flagi=0)numdepth=ai;flagi=1;for(int j=0;j4;j+)operatedepth=j;if(search(depth+1)return true;flagi=0;return false;bool readin:found()int x=num0;for(int i=0;ik;i+)switch (operatei)case 0:x+=numi+1;ptri=+;break;case 1:x-=numi+1;ptri=-;break;case 2:x*=numi+1;ptri=*;break;case 3:x/=numi+1;ptri=/;break;return(x=m);/讀入初始數(shù)據(jù)int nreadin(int n,int m)readin X;int* a=new intn; int* num=new intn; int* operate=new intn; int* flag=new intn;char* ptr=new charn;X.n=n;X.m=m;X.a=a;X.operate=operate;X.flag=flag;X.num=num;X.ptr=ptr;cout給定的用于運(yùn)算的n個(gè)正整數(shù)：endl;for(int i=0;iai;flagi=0;cout給定的運(yùn)算結(jié)果 整數(shù)m：endl;for(k=0;kn;k+)if(X.search(0)cout計(jì)算的產(chǎn)生整數(shù)m的最少無優(yōu)先級(jí)運(yùn)算次數(shù)：endl; coutkendl; cout計(jì)算的產(chǎn)生整數(shù)m的最少無優(yōu)先級(jí)運(yùn)表達(dá)式：endl; for(i=0;i=k;i+)coutnumiptri;coutendl;return 0;coutNo Solution!endl;return 0;void main()int n; int m;cout輸入給定的用于運(yùn)算的n個(gè)正整數(shù)和給定的運(yùn)算結(jié)果整數(shù)m：nm; nreadin(n,m); system(pause