76《算法分析与设计》实验指导书

编著说明本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。本书共分8～10个实验，其具体要求和步骤如下：目录实验一、C/C++环境及递归算法......................................................................１实验二、递归与分治策略.................................................................................20实验三、动态规划算法（一）.........................................................................24实验四、动态规划算法（二）.........................................................................27实验五、贪心算法（一）.................................................................................30实验六、贪心算法（二）.................................................................................32实验七、回溯法（一）.....................................................................................35实验八、回溯算法（二）.................................................................................37实验九、分支限界法.........................................................................................39实验十：随机化算法（选学）.........................................................................44１实验一、C/C++环境及递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；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、编程实现题目要求；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;s1S;s1++){scenarios[s1].probability=0;scenarios[s1].times=0;for(i=0;istock_amount;i++)for(t=0;tT;t++){scenarios[s1].expect[i][t]=0;count[i][t][s1]=0;}}for(i=0;istock_amount;i++)for(j=0;jweek_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打开失败时进行错误处理;{cerrE:MultiStage_portfolioOptimize_data函数没有打开“USA_stock_data.txt”文件endl;exit(1);}while(f1.get(cha))//依次从文件中读取字符到ch并输出和统计行数(直到文件结束)；{if(isspace(cha))continue;//是空白字符不处理if(isalpha(cha))//是字母？{if(cha128)//如果是英文字母不保存{f1.putback(cha);f1s;//从f1中读入一个字符串到s中；但不保存到任何文件中；}}elseif(isdigit(cha)||cha=='.')//发现是数值数据{f1.putback(cha);//向流中压回刚读过的数字或小数点；f1data[SUM++];//从f1中读入一个浮点数到data[2*stock_amount*week_amount]中；３}else//发现其他字符跳过{f1.putback(cha);f1s;//从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];elsestock[a[0]].Close_price[a[1]-week_amount]=data[i];}for(i=0;istock_amount;i++)for(j=0;jweek_amount;j++)stock[i].return_percentage[j]=(stock[i].Close_price[j]-stock[i].Open_price[j])/stock[i].Open_price[j];/*以下是求S种情况发生的概率及各个阶段所有资产的收益率均值*/SUM=0;ifstreamf2(E:S&P100Index.txt,ios::in|ios::nocreate);/*定义一个输入文件流:f2，并用输入文件流f2打开文件文本：S&P100Index.txt，若打开失败则!f1为true.*/if(!f2)//当f2打开失败时进行错误处理;{cerrE:MultiStage_portfolioOptimize_data函数没有打开“S&P100Index.txt”文件endl;exit(1);}while(f2.get(cha))//依次从文件中读取字符到ch并输出和统计行数(直到文件结束)；{if(isspace(cha))continue;//是空白字符不处理if(isalpha(cha))//是字母？{if(cha128)//如果是英文字母不保存{f2.putback(cha);f2s;//从f1中读入一个字符串到s中；但不保存到任何文件中；}}elseif(isdigit(cha)||cha=='.')//发现是数值数据{f2.putback(cha);//向流中压回刚读过的数字或小数点；４f2Index[SUM++];//从f2中读入一个浮点数到Index[4*week_amount]中；}else//发现其他字符跳过{f2.putback(cha);f2s;//从f1中读入一个字符串到s中；但不保存到任何文件中；}}f2.close();for(i=0;iweek_amount;i++)Index_Open[i]=Index[i];for(i=0;iweek_amount;i++)Index_Close[i]=Index[i+week_amount];for(i=0;iweek_amount;i++)Index_High[i]=Index[i+2*week_amount];for(i=0;iweek_amount;i++)Index_Low[i]=Index[i+3*week_amount];//判断每周的市场指数是上升还是下降for(j=0;jweek_amount-1;j++){if(Index_Close[j]Index_Close[j+1])Scenarios[j]=1;elseScenarios[j]=0;}Scenarios[week_amount-1]=1;//计算S种情况发生的概率及各个阶段所有资产的收益率均值if(T==4){for(j=0;jweek_amount-2;j=j+T){s1=0;for(t=0;tT;t++){a[t]=Scenarios[j+t];s1+=a[t]*((int)pow(2,t));}scenarios[s1].times++;for(i=0;istock_amount;i++)for(t=0;tT;t++){scenarios[s1].expect[i][t]+=stock[i].return_percentage[j+t];count[i][t][s1]++;}}５for(i=0;istock_amount;i++)for(s1=0;s1S;s1++)for(t=0;tT;t++)scenarios[s1].expect[i][t]/=(double)count[i][t][s1];}elseif(T==3){for(j=0;jweek_amount-1;j=j+T){s1=0;for(t=0;tT;t++){a[t]=Scenarios[j+t];s1+=a[t]*((int)pow(2,t));}scenarios[s1].times++;for(i=0;istock_amount;i++){for(t=0;tT;t++){scenarios[s1].expect[i][t]+=stock[i].return_percentage[j+t];count[i][t][s1]++;}}}for(i=0;istock_amount;i++)for(s1=0;s1S;s1++)f