1、皖西學院信息工程系實 驗 報 告姓名王禮 學號 20072077 院系信息工程系 專業 計算機科學與技術年級 2007級 班級 0702班 小組實驗任務分工 獨立完成 實驗時間 2010 年9月 20日實驗名稱 無優先級運算問題 指導老師及職稱 蘇守寶 教授 皖西學院信息工程系實驗課程：算法分析與設計 實驗名稱：無優先級運算問題 （綜設型實驗）第一部分 實驗內容1實驗目標對于給定的n個正整數，設計一個優先隊列式分支限界法用最少的無優先級運算次數產生整數m 。2. 實驗任務（1）從所給定的題目中選擇一題，使用分支限界法求解之。（2）用文字來描述你的算法思路，包括解空間、限界函數、算法主要步驟等。

2、（3）在Windows環境下使用C/C+語言編程實現算法。（4）記錄運行結果，包括輸入數據，問題解答及運行時間。（5）分析算法最壞情況下時間復雜度和空間復雜度。（6）談談實驗后的感想，包括關于該問題或類似問題的求解算法的建議。3. 實驗設備及環境PC；C/C+等編程語言。4. 實驗主要步驟(1) 根據實驗目標，明確實驗的具體任務；(2) 設計求解問題的算法，并編寫程序實現算法；(3) 設計實驗數據并運行程序、記錄運行的結果；(4) 分析算法時空性能；(5) 實驗后的心得體會。第二部分 問題及算法1. 問題描述：給定n個正整數和4個運算符+，-，*，/，且運算符無優先級，如2+35=25。對于任

3、意給定的整數m，試設計一個算法，用以上給出的n個數和4個運算符，產生整數m，且用的運算次數最少。給出的n個數中每個數最多只能用1次，但每種運算符可以任意使用 2. 算法設計：對于給定的n個正整數，設計一個算法，用最少的無優先級運算次數產生整數m。 3. 數據輸入由文件input.txt給出輸入數據。第一行有兩個正整數n和m。第二行是給定的用于運算的n個正整數。4. 結果輸出將計算出的產生整數的m的最少無優先級運算次數以及最優無先級運算表達式輸出到文件output.txt。 輸入文件示例 輸出文件示例 Input.txt output.txt 5 25 2 5 2 3 6 7 2 + 3 * 5

4、第三部分 實驗結果與分析1. 實驗數據及結果 2. 實驗分析及結論針對該實驗我做了仔細分析，剛看到這個題目，不知所云，后來分析后才知道，給定n個正整數和4個運算符+，-，*，/，且運算符無優先級，如2+35=25。對于任意給定的整數m，試設計一個算法，用以上給出的n個數和4個運算符，產生整數m，且用的運算次數最少。給出的n個數中每個數最多只能用1次，但每種運算符可以任意使用。第四部分 心得與展望1. 自我評價及心得體會分析無優先級算法問題時候一開始有點無從下手，經過我查資料以后，再加上自己的分析和見解，以及老師的幫助，最終得出了答案，讓我明白了只要自己 從分利用自己掌握的技術和周邊的壞境比如我

5、們學校的老師，網絡資源等，大多問題都可以解決的。2. 展望對算法產生了濃厚的興趣，打算以后可能會從事算法設計。第五部分 附錄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; /給定的用于運算n個正整數的存放位置int* num; /存放運算的產生整數mint* operate; int* flag; char* ptr; /存儲結果

6、中的運符;/用迭代加深的回溯法bool readin:search(int depth) /depth:遞歸深度if(depthk)if(found() return true; /判斷結點是否滿足件，即是否找到解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

7、=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);/讀入初始數據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=

8、n;X.m=m;X.a=a;X.operate=operate;X.flag=flag;X.num=num;X.ptr=ptr;cout給定的用于運算的n個正整數：endl;for(int i=0;iai;flagi=0;cout給定的運算結果 整數m：endl;for(k=0;kn;k+)if(X.search(0)cout計算的產生整數m的最少無優先級運算次數：endl; coutkendl; cout計算的產生整數m的最少無優先級運表達式：endl; for(i=0;i=k;i+)coutnumiptri;coutendl;return 0;coutNo Solution!endl;return 0;void mai