《算法分析與設計方案》實驗指導書

PAGE編著說明本書是為配合《算法分析與設計實驗教學大綱》而編寫的上機指導，其目的是使學生消化理論知識,加深對講授內容的理解，尤其是一些算法的實現(xiàn)及其應用,培養(yǎng)學生獨立編程和調試程序的能力，使學生對算法的分析與設計有更深刻的認識。上機實驗一般應包括以下幾個步驟：（1）、準備好上機所需的程序。手編程序應書寫整齊,并經人工檢查無誤后才能上機。(2）、上機輸入和調試自己所編的程序。一人一組，獨立上機調試，上機時出現(xiàn)的問題，最好獨立解決。（3）、上機結束后，整理出實驗報告。實驗報告應包括:題目、程序清單、運行結果、對運行情況所作的分析。本書共分8～10個實驗，其具體要求和步驟如下：目錄TOC\o”1-3”\h\z\u_Toc241173487”實驗二、遞歸與分治策略 20HYPERLINK\l”_Toc241173488"實驗三、動態(tài)規(guī)劃算法（一） 24實驗四、動態(tài)規(guī)劃算法（二） 27實驗五、貪心算法（一） 30_Toc241173492"實驗七、回溯法（一） 35HYPERLINK\l”_Toc241173493”實驗八、回溯算法（二） 37HYPERLINK\l”_Toc241173494"實驗九、分支限界法 39HYPERLINK\l”_Toc241173495”實驗十：隨機化算法(選學） 44PAGE１實驗一、C/C++環(huán)境及遞歸算法一、實驗目的與要求1、熟悉C/C++語言的集成開發(fā)環(huán)境；2、通過本實驗加深對遞歸過程的理解并了解分治策略；二、實驗內容：1、掌握遞歸算法的概念和基本思想，分析并掌握“數字計數”問題的遞歸算法; 2、掌握C/C++語言的基本庫函數；三、實驗題數字計數問題：一本書的頁碼從自然數1開始順序編碼到N。頁碼按照通常的習慣編排，即每個頁碼不能含多余的前倒數0,例如，、第6頁的頁碼為6，不能是06、006等。數字計數問題要求從鍵盤輸入頁數N，輸出全書頁碼中分別用到0、1、2、3、4、5、6、7、8、9的次數;四、實驗步驟1、理解算法思想和問題要求；2、編程實現(xiàn)題目要求；3、上機輸入和調試自己所編的程序；4、驗證分析實驗結果；5、整理出實驗報告；五、C++示例程序/＊下列讀文本文件中數據并處理的頭文件Data_arrange.h中的內容：*///***＊*＊***＊**整理金融數據的函數MultiStage_portfolioOptimize_data（)*＊*＊*＊＊＊**＊＊*＊*＊*＊＊＊*//voidMultiStage_portfolioOptimize_data（）{ inti,j，s1,t，a［T］,SUM； intcount［stock_amount]［T］[S],Scenarios[week_amount］; chars［10000]; charcha=0； doubledata[2＊stock_amount＊week_amount］，Index［4*week_amount]; for（s1=0；s1〈S;s1++) { scenarios[s1］.probability=0; scenarios［s1］。times=0； for(i=0;i<stock_amount;i++) for(t=0；t〈T；t++） ｛ scenarios［s1］.expect[i]［t]=0； count[i]［t］［s1]=0; } } for(i=0；i<stock_amount;i++） for（j=0;j<week_amount;j++） { stock[i］.name［j］=0; stock[i].Open_price[j]=0。0； stock［i]。Close_price［j]=0。0； stock［i].return_percentage［j]=0.0; ｝//以下是把E：USA_stock_data。txt中數據讀入數組data[N]中并計算各階段各種情況下所有股票的歷史收益率// SUM=0; ifstreamf1(”E:USA_stock_data.txt”,ios：:in｜ios:：nocreate）;/*定義一個輸入文件流：f1，并用輸入文件流f1打開文件文本:USA_stock_data.txt，若打開失敗則！f2為true。＊/ if(!f1)//當f1打開失敗時進行錯誤處理; ｛ cerr<〈”E:MultiStage_portfolioOptimize_data函數沒有打開“USA_stock_data。txt”文件”<〈endl； exit（1）; ｝while(f1.get（cha））//依次從文件中讀取字符到ch并輸出和統(tǒng)計行數（直到文件結束）； ｛ if（isspace(cha))continue;//是空白字符不處理 if(isalpha（cha)）//是字母？ { if（cha<128）//如果是英文字母不保存 { f1。putback(cha）; f1>>s；//從f1中讀入一個字符串到s中；但不保存到任何文件中； } } elseif(isdigit(cha）｜｜cha==’.')//發(fā)現(xiàn)是數值數據 {f1。putback(cha）；//向流中壓回剛讀過的數字或小數點;f1>〉data［SUM++]；//從f1中讀入一個浮點數到data［2＊stock_amount*week_amount]中； ｝ else//發(fā)現(xiàn)其他字符跳過 { f1。putback（cha）； f1>〉s；//從f1中讀入一個字符串到s中；但不保存到任何文件中； ｝ ｝ f1.close(）； for(i=0;i〈（2＊stock_amount＊week_amount)；i++) { a［0]=i/（2*week_amount）； a［1]=i％(2*week_amount）; if(a[1］〈week_amount) stock[a［0］].Open_price[a［1］］=data[i］; else stock［a［0]］。Close_price［a[1]-week_amount］=data[i］; ｝ for（i=0；i<stock_amount；i++） for(j=0;j<week_amount;j++) stock[i］.return_percentage［j]=(stock［i].Close_price［j]-stock［i].Open_price［j］）/stock［i］。Open_price［j］; /＊以下是求S種情況發(fā)生的概率及各個階段所有資產的收益率均值*/ SUM=0; ifstreamf2(”E:S&P100Index。txt",ios：：in｜ios：:nocreate）;/＊定義一個輸入文件流：f2，并用輸入文件流f2打開文件文本：S＆P100Index.txt，若打開失敗則!f1為true。＊/ if（!f2）//當f2打開失敗時進行錯誤處理； ｛ cerr<〈"E：MultiStage_portfolioOptimize_data函數沒有打開“S＆P100Index.txt”文件”<<endl； exit（1); }while（f2.get（cha))//依次從文件中讀取字符到ch并輸出和統(tǒng)計行數（直到文件結束）； { if（isspace(cha)）continue;//是空白字符不處理 if(isalpha(cha）)//是字母？ ｛ if(cha<128）//如果是英文字母不保存 ｛ f2。putback(cha）； f2>〉s;//從f1中讀入一個字符串到s中;但不保存到任何文件中； ｝ ｝ elseif(isdigit（cha)｜|cha=='?！?/發(fā)現(xiàn)是數值數據 {f2.putback(cha)；//向流中壓回剛讀過的數字或小數點；f2>〉Index[SUM++］;//從f2中讀入一個浮點數到Index［4＊week_amount]中； } else//發(fā)現(xiàn)其他字符跳過 ｛ f2。putback(cha）; f2>〉s;//從f1中讀入一個字符串到s中；但不保存到任何文件中； ｝ } f2。close（）; for（i=0;i〈week_amount;i++） Index_Open［i］=Index［i］; for（i=0;i〈week_amount；i++） Index_Close[i］=Index［i+week_amount］； for（i=0；i〈week_amount；i++) Index_High［i]=Index［i+2＊week_amount]; for（i=0；i〈week_amount；i++) Index_Low[i]=Index[i+3＊week_amount］； //判斷每周的市場指數是上升還是下降 for（j=0；j〈week_amount—1；j++) { if(Index_Close［j］>Index_Close[j+1］) Scenarios［j］=1; else Scenarios[j］=0; } Scenarios[week_amount—1］=1; //計算S種情況發(fā)生的概率及各個階段所有資產的收益率均值 if(T==4） ｛ for(j=0;j<week_amount—2;j=j+T) { s1=0； for(t=0；t<T；t++) { a[t］=Scenarios[j+t］; s1+=a［t]*((int）pow(2,t)）； } scenarios［s1]。times++; for(i=0；i〈stock_amount;i++） for（t=0；t〈T;t++） ｛ scenarios[s1］.expect［i]［t]+=stock[i]。return_percentage[j+t］; count[i］[t］[s1]++; } ｝ for(i=0;i〈stock_amount;i++） for(s1=0；s1〈S；s1++） for(t=0；t<T；t++) scenarios［s1］。expect［i][t］/=（double）count［i]［t]［s1]； } elseif（T==3) { for(j=0；j<week_amount—1；j=j+T） ｛ s1=0； for（t=0;t<T；t++） ｛ a［t]=Scenarios[j+t］; s1+=a[t]＊(（int)pow(2，t）); } scenarios[s1].times++； for（i=0;i<stock_amount；i++) ｛ for（t=0;t〈T;t++) { scenarios［s1］。expect[i］[t］+=stock［i]。return_percentage[j+t］； count［i]［t］［s1]++; } } ｝ for（i=0；i〈stock_amount；i++) for(s1=0；s1<S;s1++) for(t=0；t〈T；t++） scenarios［s1].expect［i］[t］/=(double）count[i］[t］［s1]； } else cout〈<”階段數T設置錯誤,T只能為“或”，請重新設置階段數T的值"<〈endl； SUM=0; for（s1=0;s1<S;s1++) SUM+=scenarios［s1］。times； for(s1=0；s1〈S;s1++) scenarios[s1］.probability=scenarios[s1］.times/（(double）SUM)； //提取各種情況下各個階段所選股票的歷史收益率 for（s1=0；s1〈S;s1++)//提取所選股票的歷史收益率 for（t=0；t〈T;t++） ｛ Scenarios_probability［s1］=scenarios[s1]。probability； if（Section［0]==0） ｛ Scenarios_expect［0][t］［s1]=0.005468；//設置銀行存款利率 for（j=1;j<N;j++） Scenarios_expect[j][t][s1］=scenarios[s1］.expect[Section[j]］[t]； } else ｛ for（j=0；j〈N;j++） Scenarios_expect［j]［t][s1]=scenarios[s1］.expect［Section［j]][t]； } }//記錄各個階段各種情況下所選資產的歷史收益率SUM=0； ifstreamf3（"E:QPSO_data.txt”，ios：:in|ios：:nocreate）；/*定義一個輸入文件流：f3，并用輸入文件流f3打開文件文本：QPSO_data，若打開失敗則！f3為true。*/ if（!f3)//當f2打開失敗時進行錯誤處理； { cerr〈〈"E:MultiStage_portfolioOptimize_data函數沒有打開“QPSO_data.txt"文件"〈<endl; exit（1）; ｝while(f3。get（cha)) SUM++; f3。close（）； ofstreamf4（”E：QPSO_data。txt”,ios：:in|ios:：nocreate）;/*定義一個輸入文件流：f4，并用輸入文件流f4打開文件文本:QPSO_result，若打開失敗則!f3為true.＊/ if（！f4)//當f1打開失敗時進行錯誤處理； ｛ cerr<<"E：MultiStage_portfolioOptimize_data函數沒有打開“QPSO_data.txt”文件”<〈endl; exit(1）; ｝ for（i=0；i<=SUM;i++） f4〈<”"; f4。close(）; ofstreamf5("E：QPSO_data.txt”,ios：:in|ios：：nocreate);/＊定義一個輸入文件流:f5，并用輸入文件流f5打開文件文本：QPSO_result，若打開失敗則!f4為true.*/ if（！f5）//當f3打開失敗時進行錯誤處理； ｛ cerr<〈”E：MultiStage_portfolioOptimize_data函數沒有打開“QPSO_data.txt”文件"〈<endl; exit（1)； } f5<<"＊*＊*＊*＊＊＊*＊*＊＊＊*＊**＊＊**＊*＊**＊＊”〈〈”所選的資產號分別為:*＊＊*****＊***＊**＊*＊＊**＊****＊”〈<endl;f5<〈”"； for（i=0；i<N；i++） f5<〈Section［i］<〈”；”； f5<〈endl; f5〈〈”%％％％%％％％%%%％％%％%％％%%％％%”〈<"所選資產的歷史回報率分別為：%％％％%％%％％％%％%％%%％％％％％％%”〈〈endl； f5〈〈endl； for（s1=0;s1〈S;s1++） ｛ f5<<”＊***＊*＊*＊＊**＊＊*＊＊第"<〈s1+1<〈”種情況下各個階段的歷史回報率：＊**＊＊＊*＊＊＊＊＊＊＊＊*＊＊*＊”<<endl； for（t=0；t<T;t++) ｛ f5〈<"第”<<t+1〈<”階段的歷史回報率："<〈endl； for（j=0;j<N；j++) f5〈<Scenarios_expect［j］[t］[s1］〈<"；"; f5〈〈endl; } f5<<endl〈〈endl； } f5〈<endl； f5〈〈"％％％％％％％%％％%%%％％%%%%%％%％％%%”<<"各種情況的發(fā)生概率分別為:％％%％%％％％％%%％%%%%％%％％％%％％%%”<<endl； for(s1=0；s1〈S；s1++) { f5〈〈Scenarios_probability［s1］〈<”；”； if（（s1+1)%8==0) f5〈<endl； }f5〈<endl;f5.close(）；｝//////////以下是全局變量頭文件Overall_variation.h#include〈iostream。h>＃include<fstream.h〉#include〈ctype。h〉＃include”string.h”#include"stdlib。h”＃include”time。h”#include"math.h”＃definestock_amount20//資產總數；＃defineweek_amount310//數據個數(周數)；＃definerdft(）rand(）/（32767.0+1。0)structStage_Scenarios｛ doubleexpect［stock_amount]［T]; inttimes; doubleprobability；｝scenarios［S］;doubleIndex_Open[week_amount］;doubleIndex_Close［week_amount];doubleIndex_High［week_amount］；doubleIndex_Low［week_amount];structdata｛ charname［10］； doubleOpen_price[week_amount]；doubleClose_price[week_amount］; doublereturn_percentage［week_amount］;}stock[stock_amount];doubleScenarios_expect[N][T]［S］；//各個階段S情節(jié)下各個資產的期望回報率；doubleScenarios_probability[S］；//各情節(jié)的發(fā)生概率；doublembest[N］[T]［S］；doubleAvg_Adaptation［R］；//目標函數值平均值;doubleVariation_Adaptation［R］；//目標函數值方差;doubleMax_Adaptation［R］;//目標函數值最大值；doubleMin_Adaptation［R];//目標函數值最小值;doubleAvg_expect［R］；//期望回報平均值;doubleVariation_expect［R];//期望回報方差；doubleMax_expect[R]；//期望回報最大值；doubleMin_expect［R］；//期望回報最小值;doubleAvg_Expect［R][S];//各種情況下的期望回報平均值；doubleVariation_Expect［R］[S];//各種情況下的期望回報方差；doubleMax_Expect[R]［S];//各種情況下的期望回報最大值；doubleMin_Expect[R］［S]；//各種情況下的期望回報最小值；structGBEST｛ doubleAdaptation［R］[RUN］；//全局最佳目標函數值; doubletsw[N］[T］[S]； doublets_before[R][RUN］[N][T]［S]； doublets_after[R][RUN］[N］［T]［S]； doublets_buy［R］［RUN][N］[T][S]; doublets_sale［R]［RUN］[N］[T］[S]; doublets_expect［R][RUN]［N］［T］［S］; doublet_buy［R]［RUN］［N］［T］;//函數運行RUN次的各個資產各個階段購買量； doublet_sale［R］［RUN]［N］[T];//函數運行RUN次的各個資產各個階段賣出量； doublet_expect［R］[RUN][N］[T］;//函數運行RUN次的各個資產各個階段結束時期望資產量； doublet_before[R]［RUN］［N][T］;//函數運行RUN次的各個資產各個階段開始時（平衡前)資產量； doublet_after［R][RUN］［N]［T］；//函數運行RUN次的各個資產各個階段開始時(平衡后)資產量}Gbest;structpartical｛doubleAdaptation；doubletsw［N］［T][S］； doublets_buy[N][T］［S］; doublets_sale［N］[T］[S］； doublets_expect[N]［T][S］； doublets_after[N］［T］[S］； doublets_before［N］［T］[S］； doublepbest_Adaptation； doubletsw_pbest[N][T][S]； doublets_pbest_buy[N］[T]［S]； doublets_pbest_sale［N］[T][S］; doublets_pbest_expect［N］[T］[S］； doublets_pbest_before[N］[T］[S]; doublets_pbest_after[N］[T］［S]; doublet_before[N］［T］; doublet_after[N]［T］； doublet_buy［N］［T]； doublet_sale[N][T]; doublet_expect[N］[T］； doublet_pbest_before［N][T]; doublet_pbest_after［N]［T]； doublet_pbest_buy［N]［T］; doublet_pbest_sale［N]［T]; doublet_pbest_expect［N]［T];}p[NP];///以下是QPSO算法函數的頭文件QPSO_MultiStage_portfolioOptimize。h//＊***＊****＊**＊＊＊*＊*＊QPSO算法的函數MultiStage_portfolioOptimize_QPSO(）＊＊＊＊**＊***＊*＊＊*＊****＊＊＊＊＊*＊*//voidMultiStage_portfolioOptimize_QPSO(intrun,doubletoleration，intr）{doublea,b,CR,min,max,Q，U,w,SUM［S］,rebalance[N]，pp0[N]，pp1［N],pw[N];intmm=0,i,j,m,n,s,t,k0，k1,times,nn1[N],nn0［N］；//以下為初始化過程:for（i=0;i<NP;i++）//初始化權重for（s=0；s<S；s++） for（t=0；t〈T；t++) for（j=0；j<N;j++) ｛ do{ p[i］。tsw［j］[t][s］=rdft（); ｝while(p［i］.tsw[j］［t］[s］<=0｜|p[i].tsw［j][t][s]>=1）； p［i］.tsw_pbest[j］[t]［s]=p［i］.tsw［j][t］[s］； }for（s=0；s<S；s++) for(t=0；t<T；t++） for（j=0；j<N;j++) Gbest.tsw[j］［t］［s]=p[0].tsw［j］[t］［s］； //以下是主循環(huán)a=0。9；b=0。1;for（times=0;times<=Circletimes；times++）{ w=a—(a-b)*times/Circletimes;//參數w從a線形地遞減到b； for（i=0；i<NP；i++)//權重標準化 for(s=0；s〈S;s++) for（t=0;t〈T;t++） { SUM[0]=0； for（j=0;j〈N;j++） SUM[0]+=p[i].tsw[j］[t]［s]; for（j=0;j〈N;j++) p［i].tsw［j]［t][s]/=SUM[0］； } for(i=0;i〈NP；i++)//以下計算求各個粒子目標函數值的相關變量值； ｛ for(s=0；s<S；s++） { for（t=0；t〈T；t++） ｛ if(t==0） ｛ p[i].ts_before[0][t][s]=WEALTH； for(j=1;j〈N;j++) p[i].ts_before[j］[t］[s]=0； } else { for（j=0；j<N;j++) p[i].ts_before［j］［t］[s］=p[i］.ts_expect[j]［t—1]［s］; } SUM[s]=0； for(j=0；j〈N；j++) SUM[s]+=p［i］。ts_before[j］[t]［s]; for(j=0;j〈N;j++） { p[i]。ts_after［j］［t］［s]=SUM［s]＊p[i]。tsw[j][t][s]; p[i］。ts_expect［j］［t]［s]=p［i］.ts_after[j］[t][s］＊（1+Scenarios_expect[j][t]［s］)； } ｝ ｝ for（t=0；t〈T；t++) for（j=0；j〈N;j++） ｛ p[i]。t_before[j］[t]=0； p［i]。t_after［j][t］=0; p［i］。t_expect[j］[t］=0; } for(s=0；s〈S；s++) for(t=0;t<T；t++) ｛ if（t==0） ｛ p［i].t_before［0]［t］=WEALTH; for(j=1;j<N;j++) p［i］。t_before[j]［t]=0； for(j=0；j<N；j++） { p[i]。t_after[j］[t］+=Scenarios_probability［s]*p［i].ts_after［j］［t］［s]; p［i］。t_expect［j]［t]+=Scenarios_probability［s］*p[i］。ts_expect[j]［t］［s］; ｝ ｝ else { for（j=0;j〈N；j++） ｛ p［i］。t_before[j］[t］+=Scenarios_probability［s］＊p[i]。ts_expect［j］[t-1］[s]； p[i]。t_after［j]［t]+=Scenarios_probability[s］＊p［i］。ts_after［j]［t］[s]; p[i].t_expect[j]［t]+=Scenarios_probability［s]＊p［i］.ts_expect［j]［t］[s］； ｝ ｝ ｝ } for(i=0；i<NP；i++）//以下求各個粒子目標函數值； ｛ p[i].Adaptation=0; for（s=0;s〈S;s++) ｛ SUM[s］=0； for(j=0;j<N；j++） SUM[s］+=p[i］。ts_expect[j］[T—1]［s]; ｝ if（toleration!=0) for(s=0;s〈S;s++) p［i］.Adaptation+=Scenarios_probability［s］＊pow（SUM[s]，toleration)/toleration； else for(s=0；s<S；s++） p［i］.Adaptation+=Scenarios_probability[s]*log（SUM[s]); ｝ //以下是修改局部最優(yōu)點和全局最優(yōu)點 if（times==0） ｛ for（i=0;i〈NP;i++) ｛ p［i]。pbest_Adaptation=p[i］。Adaptation; for(t=0;t<T;t++) for（j=0;j〈N;j++) ｛ for（s=0；s<S;s++） { p［i]。tsw_pbest[j][t］［s]=p［i].tsw［j］［t][s］； p［i]。ts_pbest_before［j］［t］[s]=p[i］.ts_before[j］[t］[s］; p[i］。ts_pbest_after［j]［t]［s］=p[i］。ts_after[j][t][s]； p[i].ts_pbest_expect[j］［t］[s］=p[i］。ts_expect［j］[t］[s]； ｝ p［i］。t_pbest_before［j］［t]=p［i]。t_before[j］[t]; p［i]。t_pbest_after［j]［t］=p［i］.t_after[j][t］; p［i].t_pbest_expect[j］［t］=p［i］。t_expect［j］［t］; } } Gbest.Adaptation［r］[run]=p[0]。pbest_Adaptation； for(t=0；t〈T;t++) for(j=0；j<N；j++) { for（s=0;s<S；s++) { Gbest。tsw［j］［t］［s］=p［0]。tsw［j］[t]［s]; Gbest。ts_before［r][run］［j］[t]［s］=p［0］.ts_before［j］［t]［s］； Gbest。ts_after［r]［run][j］［t］[s］=p[0］。ts_after［j][t］[s］; Gbest。ts_expect[r］[run］［j］[t］[s]=p［0].ts_expect［j]［t][s]; } Gbest.t_before[r][run］［j］[t]=p［0].t_before[j］[t]; Gbest。t_after[r]［run］[j][t]=p［0］.t_after[j][t]； Gbest。t_expect[r］［run］[j]［t]=p[0］.t_expect[j][t]； ｝ } for（i=0；i<NP;i++)//以下修改各個粒子局部最優(yōu)點； if(p[i]。pbest_Adaptation〈p[i］.Adaptation) { p［i].pbest_Adaptation=p［i].Adaptation； for（t=0；t〈T;t++） for（j=0;j〈N;j++) { for（s=0;s<S；s++) { p［i］.tsw_pbest[j]［t][s]=p［i]。tsw[j][t]［s］; p[i].ts_pbest_before[j]［t]［s］=p［i］.ts_before［j]［t]［s]; p[i]。ts_pbest_after［j］［t]［s]=p[i].ts_after[j］［t]［s]; p[i]。ts_pbest_expect[j］[t]［s]=p[i］.ts_expect［j][t］[s］; ｝ p［i］。t_pbest_before［j］［t]=p［i］。t_before[j][t]；p[i］.t_pbest_after［j］［t］=p［i]。t_after[j][t］；p［i].t_pbest_expect[j]［t]=p［i]。t_expect[j][t］; ｝ } for(i=0；i〈NP；i++）//以下修改全局最優(yōu)點； if(Gbest.Adaptation［r］［run］〈p［i].pbest_Adaptation) { Gbest。Adaptation[r][run]=p［i］。pbest_Adaptation; for（t=0；t〈T；t++) for（j=0；j〈N;j++） { for（s=0；s<S;s++） ｛ Gbest.tsw［j]［t］［s]=p［i］.tsw_pbest［j]［t］[s]; Gbest。ts_before[r]［run］［j]［t］[s]=p[i]。ts_pbest_before[j］［t][s]； Gbest。ts_after［r］［run］［j］［t][s］=p［i］.ts_pbest_after［j][t］[s］; Gbest。ts_expect[r］[run]［j］[t］[s］=p[i]。ts_pbest_expect［j］［t][s]; } Gbest.t_before［r][run]［j]［t］=p［i］。t_pbest_before［j］［t]; Gbest.t_after[r][run］［j][t］=p[i］.t_pbest_after［j］［t］； Gbest.t_expect[r］[run]［j][t］=p［i］。t_pbest_expect［j]［t］； } } //以下是QPSO進化過程 for(t=0；t〈T；t++） for(s=0;s〈S;s++) for（j=0；j<N；j++） mbest[j］［t][s]=0； for(t=0;t〈T;t++) for（s=0;s〈S;s++) for(j=0;j<N;j++） for(i=0；i<NP;i++）mbest[j］［t]［s］+=p［i].tsw_pbest[j][t］［s];//進化公式a for(t=0；t<T;t++） for(s=0;s〈S;s++) for(j=0；j<N；j++) mbest［j]［t][s］/=(NP+0.0）； for（i=0；i〈NP；i++） for（t=0;t〈T；t++) for（s=0;s〈S；s++) ｛for（j=0;j〈N;j++） ｛Q=rdft(）; U=rdft();rebalance[j］=Q*p［i]。tsw_pbest［j][t]［s]+(1-Q）*Gbest。tsw［j][t］[s]；//進化公式bif（rdft(）〈=0。5)p［i].tsw[j]［t］［s]=rebalance[j］+w＊(fabs（mbest[j]［t]［s］-p[i]。tsw[j］［t][s]）)*log(1/U)；//進化公式celsep［i].tsw［j]［t][s］=rebalance[j］-w＊(fabs(mbest[j]［t］［s］-p[i］.tsw［j]［t]［s]））＊log（1/U)；//進化公式c } ｝ for(i=0；i〈NP;i++） for（t=0；t<T；t++) for(s=0;s<S;s++) ｛ k0=0; for(j=0;j〈N;j++) if（p[i］。tsw［j］［t]［s］<0) ｛p[i］。tsw［j］［t]［s］=0;++k0; ｝ if（k0==N) p[i].tsw［0][t][s］=1; }}｝//以下是統(tǒng)計分析程序運行結果的頭文件Statistics_QPSO-result.h//voidstatistics_QPSO_result（){ intrun，r； doubleexpect［R]［RUN］； doubleExpect［R］［RUN]［S]； for（r=0;r〈R;r++） ｛ Avg_Adaptation［r］=0。0; Max_Adaptation[r]=Gbest。Adaptation[r][0］； Min_Adaptation［r］=Gbest。Adaptation［r］[0]； for（run=0；run〈RUN;run++）//統(tǒng)計目標函數值 ｛ if（Max_Adaptation[r］<Gbest。Adaptation［r]［run］） Max_Adaptation［r］=Gbest。Adaptation［r］［run］; if（Min_Adaptation[r］〉Gbest.Adaptation［r]［run]) Min_Adaptation[r]=Gbest.Adaptation［r]［run］; Avg_Adaptation［r]+=Gbest。Adaptation［r][run]； } Avg_Adaptation[r］=Avg_Adaptation[r]/(RUN+0。0)； Variation_Adaptation[r]=0.0； for（run=0;run<RUN；run++）Variation_Adaptation［r]+=(Gbest.Adaptation［r］［run］-Avg_Adaptation[r］)*(Gbest.Adaptation[r］［run］-Avg_Adaptation［r])； Variation_Adaptation[r］/=（RUN+0.0); //以下是統(tǒng)計總體的期望回報率 for(run=0；run〈RUN;run++) ｛ expect[r]［run］=0.0； for（intj=0；j〈N；j++） expect［r]［run]+=Gbest.t_expect［r］［run］[j］[T—1］; expect［r]［run］=（expect［r］[run]-WEALTH）/（WEALTH+0。0); expect［r]［run］=expect[r］［run］/（T+0。0)； } Avg_expect［r]=0。0; Max_expect［r］=expect[r］［0］； Min_expect[r]=expect[r］[0］； for(run=0；run<RUN;run++) ｛ if(Max_expect［r］<expect[r]［run]） Max_expect［r］=expect［r］[run]； if(Min_expect[r]>expect［r］［run］） Min_expect［r］=expect[r］［run］; Avg_expect[r]+=expect［r]［run]; } Avg_expect[r］=Avg_expect[r]/(RUN+0.0）； Variation_expect［r］=0。0； for(run=0；run〈RUN;run++) Variation_expect[r]+=（expect［r][run]-Avg_expect［r]）＊(expect[r]［run］-Avg_expect[r］）； Variation_expect［r］/=（RUN+0.0)； //統(tǒng)計各個情況下的期望回報率 for(ints=0;s<S；s++) { for（run=0;run〈RUN；run++) { Expect[r]［run］［s］=0.0； for（intj=0;j〈N;j++） Expect［r］[run］［s］+=Gbest.ts_expect[r]［run][j]［T—1］［s］; Expect[r］[run］［s］=(Expect［r]［run][s］—WEALTH）/（WEALTH+0.0); Expect[r][run]［s]=Expect[r］[run][s］/(T+0。0）； } Avg_Expect［r］［s］=0。0； Max_Expect［r］［s]=Expect［r］［0][s］; Min_Expect［r］[s]=Expect［r]［0］[s]; for（run=0;run〈RUN；run++) ｛ if(Max_Expect[r][s]<Expect［r][run］[s]） Max_Expect[r］[s]=Expect[r][run][s]； if(Min_Expect［r］[s］〉Expect［r］[run］[s］） Min_Expect[r］［s]=Expect［r］[run][s］； Avg_Expect[r]［s]+=Expect［r］[run][s］； ｝ Avg_Expect[r][s]=Avg_Expect[r]［s］/（RUN+0.0); Variation_Expect[r]［s]=0。0； for(run=0；run〈RUN;run++）Variation_Expect[r］［s]+=（Expect[r]［run］[s］-Avg_Expect［r］［s］)＊(Expect[r］［run]［s］–Avg_Expect[r][s］）; Variation_Expect［r］[s］/=(RUN+0.0）; } }}//以下是把結果寫入文本文件QPSO_result.txt的頭文件write_QPSO_result.hvoidrecord_QPSO_result(）｛ inti，r，s，number=0，run； charcha；ofstreamw3(”E：QPSO_result.txt”,ios：：in｜ios::ate）；/＊定義一個輸入文件流：w3，并用輸入文件流w3打開文件文本:微分進化結果.txt,若打開失敗則！w3為true。＊/ if（!w3）//當w3打開失敗時進行錯誤處理； { cerr〈〈”E:QPSO_result。txtfilenotopen”〈<endl； exit（1)； ｝w3〈<"”〈〈”階段數設置為“”〈〈T<<””，粒子數設置為“"〈<NP〈〈””個,主循環(huán)次數設置為“"〈〈Circletimes<<”"次，選擇"<〈N<<"個資產的資產號分別為："<<endl; w3<〈"”; for（i=0；i<N;i++） w3<<Section[i]〈〈",”； w3<<endl； w3〈<”&＆&&＆＆&&＆&＆&＆&&＆&＆&&&＆&&＆&&&&&&＆&&&＆&＆&&&&＆&＆&＆＆＆＆＆&＆＆&&&＆&&&＆&＆&＆＆＆＆＆＆&"〈〈endl； for(r=0；r<R;r++) ｛ w3<<”r="<<Toleration［r］<〈”函數“MultiStage_portfolioOptimize_QPSO(）"運行”<<RUN<〈"次時各個變量的均值如下:"〈〈endl； w3<〈"目標函數值均值為："〈<Avg_Adaptation[r］〈〈"；"<〈endl; w3<<”最終總體期望回報均值為："<〈Avg_expect[r］<〈”；”<<endl; for（s=0；s<S；s++） w3〈<”在s=“"<<s〈〈””情況下，最終期望回報均值為："<〈Avg_Expect［r］[s］<〈”；”<〈endl； w3<〈endl； ｝ w3〈<"＊＊＊*＊**＊*＊***＊***＊＊*＊＊*＊＊**＊＊******＊＊＊***＊****＊＊***＊***＊＊*＊*＊＊＊＊＊＊＊****＊＊＊＊＊*＊*＊*"〈<endl; for（r=0；r〈R;r++） ｛ w3<〈”r="<〈Toleration[r]〈〈”函數“MultiStage_portfolioOptimize_QPSO（)”運行”<<RUN<<”次時各個變量的方差如下:”〈〈endl; w3<〈"目標函數值方差為："〈〈Variation_Adaptation[r]<<”；”<〈endl； w3〈〈"最終總體期望回報方差為:"<<Variation_expect［r]〈〈"；”〈〈endl； for(s=0;s〈S；s++) w3〈〈”在s=“”<〈s〈<””情況下,最終期望回報方差為:”〈〈Variation_Expect[r］[s]<〈";”<〈endl； w3<〈endl； } w3〈<”*＊＊****＊＊*＊＊**＊**＊**＊＊＊＊*＊*＊*＊＊***＊＊**＊＊＊*＊*＊**＊＊*＊*＊****＊＊**＊＊***＊＊*****＊**＊******”<〈endl； for(r=0;r〈R；r++) { w3<<"r=”〈<Toleration[r]〈<”函數“MultiStage_portfolioOptimize_QPSO(）”運行”〈<RUN〈<"次時各個變量的最大值如下:"<〈endl; w3<<”目標函數值最大值為:"<〈Max_Adaptation［r］〈〈";”〈<endl; w3〈<"最終總體期望回報最大值為:"〈〈Max_expect［r］<〈"；”〈<endl; for(s=0;s〈S;s++) w3<〈”在s=“”〈<s〈<””情況下,最終期望回報最大值為:"<<Max_Expect[r][s］〈〈”;"〈〈endl; w3〈〈endl； } w3<<"*＊＊**＊*****＊*＊**＊**＊*＊**＊＊*＊**＊*****＊＊＊＊＊＊＊＊＊＊*＊*＊＊*＊＊**＊＊＊＊**＊******＊＊****＊**＊**”<〈endl； for(r=0;r<R；r++) ｛ w3〈<”r="〈<Toleration［r]<〈”函數“MultiStage_portfolioOptimize_QPSO()”運行”〈〈RUN〈〈"次時各個變量的最小值如下:”<〈endl; w3〈<”目標函數值最小值為:”〈<Min_Adaptation[r］〈〈"；”<〈endl； w3<<"最終總體期望回報最小值為：”〈〈Min_expect［r]<〈"；”〈<endl； for(s=0；s〈S；s++) w3〈〈"在s=“”<〈s<〈”"情況下，最終期望回報最小值為:”<〈Min_Expect[r]［s］〈<"；”〈<endl； w3<〈endl; ｝ w3〈〈endl; w3<<"&&＆&＆＆＆＆&&＆＆＆＆＆&&&＆&＆&&&＆&&＆＆＆&&&&＆＆＆&&＆&＆&&&＆&&&＆＆&＆＆&&&＆＆＆&＆&&＆＆＆＆&&＆&&&&&＆＆＆＆＆&＆”〈<endl; for（r=0；r<R；r++） { w3〈<">〉〉〉>>〉〉“資產固定不變，"<<”主循環(huán)跌代”〈〈Circletimes<〈”次，投資者設定的風險容忍參數r=”〈〈Toleration[r]<〈"”時運行結果如下：<<〈〈<〈〈<"<<endl； w3<<"函數“MultiStage_portfolioOptimize_QPSO()"運行"〈〈RUN<〈”次時各次目標函數值分別為："<〈endl;for（run=0；run〈RUN;run++） ｛ w3〈<”";w3<〈Gbest.Adaptation[r][run］〈<";”; if（r==0&&（run+1)％6==0) w3<<endl; if（r!=0&＆（run+1）%10==0) w3<〈endl； } w3<〈endl； w3〈<endl； ｝ w3<<endl； w3〈〈endl； w3。close();｝//以下是主函數所在的文件main（）。cpp#definerdft(）rand（）/(32767.0+1。0）/*rand()產生0～32767之間的均勻分布的隨機整數，rdft（）產生0～1之間的均勻分布的隨機小數*/＃defineNP30//粒子總數＃defineN10//選擇的資產數＃defineRUN100//函數運行次數#defineR3//風險參數個數＃defineCircletimes5000//函數主循環(huán)跌代次數＃define T4//階段數＃define S16//特定情節(jié)數＃include”overall_variation。h”intSection［N]=｛0，3,5，7,9，12，14,16，18,19｝;//零號資產為現(xiàn)金，對應的收益率為儲蓄利率doubleToleration［R］=｛—1,0，1}；//投資者設定的風險容忍參數r；doubleWEALTH=10000.0；//第一階段開始時價值總量;＃include"Data_arrange。h”＃include"QPSO_MultiStage_portfolioOptimize.h”＃include"write_QPSO_result。h"＃include”Statistics_QPSO-result。h”//%％%％％％％%％%％％%％%%％％％％%％%％%%％％％％%%%％％%%運行主函數%%%％％%%%％％％％%％%％%％%％%％%%%％%％％％%%%％%%%％%%％//voidmain（)｛inti=0,j=0,r=0，s，t=0,run=0; srand（(unsigned）time（NULL)）；//產生隨機數種子;MultiStage_portfolioOptimize_data（);//整理金融數據； for（r=0；r〈R；r++） ｛ for（run=0;run〈RUN;run++)//調用QPSO函數； ｛MultiStage_portfolioOptimize_QPSO(run,Toleration［r]，r）； cout<〈"r=”〈〈Toleration［r]<〈”時，MultiStage_portfolioOptimize_QPSO()第”〈〈run+1〈<”次運行結束”〈<endl; } } statistics_QPSO_result（）; record_QPSO_result（)； cout〈〈”&＆&＆&&&&&＆&&＆＆&＆＆&＆&&＆＆＆&&&&&＆&&＆＆&&＆＆&&＆＆＆&&＆&＆＆＆＆＆&&&&&＆＆＆＆&&&＆&＆＆&&＆＆＆＆&＆&&”<<endl； cout<〈endl； for（r=0;r〈R；r++） ｛ cout<<”參數r="<<Toleration[r］〈<”時運行”<〈RUN〈<"次的各次目標函數值分別為："〈〈endl； for（run=0；run<RUN;run++) {cout〈<Gbest。Adaptation［r]［run］〈〈”；”； if（r==0＆&（(run+1）%5==0)） cout<<endl； if（r!=0＆＆(（run+1）％8==0）） cout<<endl; ｝ cout〈〈endl； }cout〈<"＆&＆&＆＆＆＆&＆&&＆&＆＆＆＆＆&＆&＆&&＆&＆＆＆＆&&＆＆&＆＆&＆＆＆＆＆＆＆＆&&&＆&＆＆&&&＆&＆＆&＆＆＆＆&&＆＆&&&&＆＆＆&”〈<endl； for（r=0；r<R；r++） {cout<<"r=”〈<Toleration[r]<<”函數“QPSO(）"運行”〈<RUN<<"次時目標函數值均值為：”〈〈Avg_Adaptation[r］〈〈";"<〈endl； cout〈<”r=”<<Toleration[r]<<”函數“QPSO（）”運行”<〈RUN〈<"次時最終總體期望回報均值為："<〈Avg_expect［r]<〈”;”<〈endl； for(s=0;s<S；s++）cout〈<”r="〈〈Toleration［r]〈〈"函數“QPSO（)"運行”〈<RUN<〈"次時在s=“"<〈s<<""下的期望回報均值為:"〈<Avg_Expect[r][s］〈〈";"〈<endl； cout<<endl; cout<〈"r="〈〈Toleration[r］〈〈”函數“QPSO（）"運行"〈〈RUN<〈"次時目標函數值方差為："<<Variation_Adaptation[r]〈<"；"〈〈endl; cout<<"r="<〈Toleration［r］〈<”函數“QPSO(）”運行”<〈RUN〈〈"次時最終總體期望回報方差為:”<〈Variation_expect［r]<<";”<〈endl； for(s=0;s<S；s++)cout<〈”r="〈<Toleration［r］<<”函數“QPSO()”運行"<〈RUN<<”次時在s=“"〈<s<〈"”下的期望回報方差為:"<〈Variation_Expect［r］［s］〈〈”；"〈〈endl； cout<<”＊＊***＊＊*＊＊＊*＊＊*＊*＊＊***＊*＊＊*＊**＊＊***＊*＊＊＊*＊＊＊＊＊**＊＊＊＊*＊*＊＊＊＊*＊*＊*＊＊****＊***＊＊*"〈<endl; ｝｝實驗二、遞歸與分治策略一、實驗目的與要求1、進一步熟悉C/C++語言的集成開發(fā)環(huán)境；2、通過本實驗加深對遞歸與分治策略的理解和運用；二、實驗內容：1、分析并掌握“棋盤覆蓋問題”的遞歸與分治算法示例；2、分析并掌握“二分搜索問題”的遞歸與分治算法示例； 3、練習使用遞歸與分治策略求解眾數問題或集合劃分問題;三、實驗題眾數問題：給定含有N個元素的多重集合S，每個元素在S中出現(xiàn)的次數稱為該元素的重數,多重集合S中重數最大的元素稱為多重集合S的眾數,眾數的重數稱為多重集合S的重數，試求一個給定多重結合的重數和眾數;例如:S={a，b,b,b,f,f，4，5｝的重數是3,眾數是b集合劃分問題：N個元素的集合{1，2，…，N｝可以劃分為若干個非空集合的子集,例如，當N=4時，集合｛1,2，3，4｝可劃分為15個不同的非空子集如下：｛｛1}，｛2｝,｛3}，{4}}；｛{1，2}，{3｝,｛4｝}；｛{1，3｝，｛2｝，｛4｝}；{｛1,4｝，｛2},{3}｝；｛{2，3}，{1},{4}｝；｛{2，4}，{1｝，{3｝};｛｛3,4}，｛1}，{2｝}；｛｛1，2},｛3，4｝｝；{｛1,3},{2，4}｝；{｛1，4｝，{3，2｝｝;{{2,3，4}，｛1}}；｛{1，3，4｝，{2｝};｛{1，2，4｝，{3}｝；｛{1,2，3｝，{4｝｝；｛｛1,2，3，4｝}；給定正整數N，計算出N個元素的集合{1，2,…，N}可以劃分多少個非空集合的子集；四、實驗步驟1．理解遞歸和分治策略的基本思想和算法示例；2．上機輸入和調試算法示例程序；3．理解實驗題的問題要求；4．上機輸入和調試自己所編的實驗題程序;5．驗證并分析實驗題的實驗結果;6．整理出實驗報告；五、遞歸與分治算法示例程序1、棋盤覆蓋問題：在一個2k×2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中,要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋；voidchessBoard（inttr,inttc,intdr,intdc，intsize）

｛

if（size==1)return;

intt=tile++,

//L型骨牌號

s=size/2;

//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&＆dc<tc+s)//特殊方格在此棋盤中

chessBoard（tr，tc，dr，dc,s);

else{//此棋盤中無特殊方格

board［tr+s-1］［tc+s-1]=t;//用t號L型骨牌覆蓋右下角

chessBoard(tr,tc,tr+s—1，tc+s—1,s)；//覆蓋其余方格}

//覆蓋右上角子棋盤

if(dr〈tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc+s,dr，dc,s)；

else｛//此棋盤中無特殊方格

board[tr+s—1］[tc+s]=t；//用t號L型骨牌覆蓋左下角

//覆蓋其余方格

chessBoard（tr，tc+s，tr+s-1,tc+s，s);}

//覆蓋左下角子棋盤

if（dr〉=tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr+s，tc，dr,dc，s）；

else｛

board[tr+s][tc+s—1]=t；//用t號L型骨牌覆蓋右上角

//覆蓋其余方格

chessBoard(tr+s，t