《算法分析與設(shè)計(jì)方案》實(shí)驗(yàn)指導(dǎo)書

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

｛

if（size==1)return;

intt=tile++,

//L型骨牌號(hào)

s=size/2;

//分割棋盤

//覆蓋左上角子棋盤

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

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

else{//此棋盤中無(wú)特殊方格

board［tr+s-1］［tc+s-1]=t;//用t號(hào)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｛//此棋盤中無(wú)特殊方格

board[tr+s—1］[tc+s]=t；//用t號(hào)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號(hào)L型骨牌覆蓋右上角

//覆蓋其余方格

chessBoard(tr+s，t