算法設(shè)計(jì)與分析報(bào)告1

1、學(xué)生學(xué)號(hào)0121510880508實(shí)驗(yàn)課成績(jī)學(xué)生實(shí)驗(yàn)報(bào)告書實(shí)驗(yàn)課程名稱開(kāi)課學(xué)院指導(dǎo)教師姓名學(xué)生姓名學(xué)生專業(yè)班級(jí)算法設(shè)計(jì)與分析限驗(yàn)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院丁小兵軟件學(xué)術(shù)15022021-2021學(xué)年第2學(xué)期實(shí)驗(yàn)工程名稱分治法的應(yīng)用報(bào)告成績(jī)1實(shí)驗(yàn)者丁小兵專業(yè)班級(jí)軟件學(xué)術(shù)1502組別1同組者完成日期2021年5月10日,1第一局部：實(shí)驗(yàn)分析與設(shè)計(jì)(可加頁(yè))一、實(shí)驗(yàn)?zāi)康暮鸵? .目的(1) 根本掌握分治算法的原理.(2) 掌握遞歸算法及遞歸程序的設(shè)計(jì).(3) 能用程序設(shè)計(jì)語(yǔ)言求解相關(guān)問(wèn)題.2 .要求(1) 用分治法求解問(wèn)題；(2) 分析算法的時(shí)間性能,設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論.二、分析與設(shè)計(jì)1 .了解用

2、分治法求解的問(wèn)題：當(dāng)要求解一個(gè)輸入規(guī)模為n,且n的取值相當(dāng)大的問(wèn)題時(shí),如果問(wèn)題可以分成k個(gè)不同子集合,得到k個(gè)不同的可獨(dú)立求解的子問(wèn)題,其中1<k<n,而且子問(wèn)題與原問(wèn)題性質(zhì)相同,原問(wèn)題的解可由這些子問(wèn)題的解合并得出.那末,對(duì)于這類問(wèn)題分治法是十分有效的.2 .掌握分治法的一般限制流程.DanC(p,q)globaln,A1:n;integerm,p,q;/1<pq<nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);/p_m<qreturnCombine(DanC(p,m),DanC(m+1,q);endifendDa

3、nC3 .實(shí)驗(yàn)內(nèi)容仔細(xì)閱讀備選實(shí)驗(yàn)的題目,設(shè)計(jì)序要的程滿足正確性,代碼中有關(guān)鍵的注釋,書寫格式清楚,簡(jiǎn)潔易懂,效率較高,利用C+的模板,設(shè)計(jì)的程序通用性好,適合各種合理輸入,并能對(duì)不合理輸入做出正確的提示.中位數(shù)問(wèn)題問(wèn)題描述設(shè)X0:n-1和丫0:n-1為兩個(gè)數(shù)組,每個(gè)數(shù)組中含有n個(gè)已排好序的數(shù).找出期口丫白2n個(gè)數(shù)的中位數(shù).編程任務(wù)利用分治策略試設(shè)計(jì)一個(gè)O(logn)時(shí)間的算法求出這2n個(gè)數(shù)的中位數(shù).數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù).文件的第1行中有1個(gè)正整數(shù)n(n<=200),表示每個(gè)數(shù)組有n個(gè)數(shù).接下來(lái)的兩行分別是X,丫數(shù)組的元素.結(jié)果輸出程序運(yùn)行結(jié)束時(shí),將計(jì)算出的中位數(shù)

4、輸出到文件output.txt中.輸入文件例如input.txt3輸出文件例如output.txt145151831421三、主要儀器設(shè)備及耗材1 .安裝了Windows10操作系統(tǒng)的PC機(jī)1臺(tái)2 .PC機(jī)系統(tǒng)上安裝了MicrosoftVisualStudio2021開(kāi)發(fā)環(huán)境第二局部：實(shí)驗(yàn)過(guò)程和結(jié)果可加頁(yè)四、代碼調(diào)試說(shuō)明調(diào)試手段、過(guò)程及結(jié)果分析調(diào)試主要內(nèi)容為編寫程序的語(yǔ)法正確性與否,程序邏輯的正確性與否.F5:啟動(dòng)調(diào)試；F11:逐語(yǔ)句調(diào)試；F12:逐過(guò)程調(diào)試；F9:切換斷點(diǎn);ctrl+B:新建斷點(diǎn)等.代碼：#include<iostream>#include<fstream&

5、gt;usingnamespacestd;intmidNum(inta口,intn)if(n%2=0)return(an/2+an/2-1)/2;)elsereturnan/2;)intmax(inta,intb)if(a>=b)intmin(inta,intb)intgetmidNum(inta口,intb口,intn)intm1,m2;if(n<=0)return-1;if(n=1)return(a0+b0)/2;if(n=2)return(max(a0,b0)+min(a1,b1)/2;m1=midNum(a,n);m2=midNum(b,n);if(m1=m2)|_retu

6、rnm1;)if(m1<m2)if(n%2=0)returngetmidNum(a+n/2-1,b,n/2+1);else(returngetmidNum(a+n/2,b,n/2+1);)else(if(n%2=0)returngetmidNum(b+n/2-1,a,n/2+1);)elsereturngetmidNum(b+n/2,a,n/2+1);intmain()/*ofstreamoo("file1.txt",ios:out);if(!oo)cout<<"Error"system("pause");retur

7、n1;)oo<<11;oo.close();*/ifstreamii("file1.txt",ios:in);if(!ii)cout<<"wrong"system("pause");return1;inti;ii>>i;/cout<<i;inta10;intb10;ints=0;for(s=0;s<i;s+)ii>>as;一|)for(s=0;s<i;s+)ii>>bs;|)ii.close();/cout<<b2;intresult=ge

8、tmidNum(a,b,i);cout<<result<<endl;ofstreamoo("file2.txt",ios:out);if(!oo)(cout<<"Error"system("pause");return1;oo<<result;oo.close();system("pause");return0;運(yùn)行截圖:輸入截圖:輸出截圖：.Ad的.trtumfifrCm第三局部：實(shí)驗(yàn)小結(jié)、收獲與體會(huì)這次實(shí)驗(yàn)主要是利用分治法來(lái)尋求中位數(shù).通過(guò)這次的實(shí)驗(yàn),讓我充分學(xué)習(xí)

9、了分治法以及其相關(guān)知識(shí)點(diǎn),給我提供了一個(gè)動(dòng)手操作的時(shí)機(jī),并且為了能夠?qū)崿F(xiàn)這個(gè)目的而努力.當(dāng)然,不否認(rèn)這次的實(shí)驗(yàn)也是相當(dāng)有難度的,畢竟感覺(jué)工作量挺大的,而且也確實(shí)有不少自己不明白的地方.對(duì)于這次的實(shí)驗(yàn)來(lái)說(shuō),我通過(guò)努力了解了什么是分治法,而且,也懂得了如何利用代碼實(shí)現(xiàn)分治法.總而言之,這次我收獲確實(shí)很大.實(shí)驗(yàn)工程名稱動(dòng)態(tài)規(guī)劃算法報(bào)告成績(jī)11實(shí)驗(yàn)者丁小兵專業(yè)班級(jí)軟件學(xué)術(shù)1502組別1同組者完成日期2021年5月10日,1實(shí)驗(yàn)?zāi)康暮鸵? .實(shí)驗(yàn)?zāi)康?1) 能用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)求解相關(guān)問(wèn)題的算法；(2) 深刻掌握動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想并能熟練運(yùn)用；(3) 理解這樣一個(gè)觀點(diǎn)：同樣的問(wèn)題可以用不同的方法解決

10、,一個(gè)好的算法是反復(fù)努力和重新修正的結(jié)果.2 .實(shí)驗(yàn)要求(1) 用動(dòng)態(tài)規(guī)劃法求解問(wèn)題；分析算法的時(shí)間性能,設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論3 .實(shí)驗(yàn)內(nèi)容(1)仔細(xì)閱讀備選實(shí)驗(yàn)的題目,選擇一個(gè)(可選多個(gè))作為此次實(shí)驗(yàn)題目,設(shè)計(jì)的程序要滿足正確性,代碼中有關(guān)鍵的注釋,書寫格式清楚,簡(jiǎn)潔易懂,效率較高,利用C+的模板,設(shè)計(jì)的程序通用性好,適合各種合理輸入,并能對(duì)不合理輸入做出正確的提示.(2) 從以下題目中任選其一完成.1. 最大踩積問(wèn)題問(wèn)題描述設(shè)I是一個(gè)n位十進(jìn)制整數(shù).如果將I劃分為k段,那么可得到k個(gè)整數(shù).這k個(gè)整數(shù)的乘積稱為I的一個(gè)k乘積.試設(shè)計(jì)一個(gè)算法,對(duì)于給定的I和k,求出I的最大k乘積.例如十進(jìn)

11、制整數(shù)1234劃分為3段可有如下情形：1 X2X34=682 X23X4=9212 X3X4=144編程任務(wù)對(duì)于給定的I和k,編程計(jì)算I的最大k乘積.數(shù)據(jù)輸入輸入的第1行中有2個(gè)正整數(shù)n和k.正整數(shù)n是序列的長(zhǎng)度；正整數(shù)k是分割的段數(shù).接下來(lái)的一行中是一個(gè)n位十進(jìn)制整數(shù).(n<=10)結(jié)果輸出計(jì)算出的最大k乘積.輸入文件例如輸出文件例如input.txt32output.txt623124.分析設(shè)計(jì)理解最優(yōu)子結(jié)構(gòu)的問(wèn)題.有一類問(wèn)題的活動(dòng)過(guò)程可以分成假設(shè)干個(gè)階段,而且在任一階段后的行為依賴于該階段的狀態(tài),與該階段之前的過(guò)程如何到達(dá)這種狀態(tài)的方式無(wú)關(guān).這類問(wèn)題的解決是多階段的決策過(guò)程.在50

12、年代,貝爾曼RichardBellman等人提出了解決這類問(wèn)題的“最優(yōu)化原理,從而創(chuàng)立了最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法-動(dòng)態(tài)規(guī)劃.對(duì)于一個(gè)多階段過(guò)程問(wèn)題,是否可以分段實(shí)現(xiàn)最優(yōu)決策,依賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì),能否采用動(dòng)態(tài)規(guī)劃的方法,還要看該問(wèn)題的子問(wèn)題是否具有重疊性質(zhì).最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解.子問(wèn)題重疊性質(zhì)：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題,有些子問(wèn)題被反復(fù)計(jì)算屢次.問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)根本要素.（1） 理解分段決策Bellman方程.每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長(zhǎng)度.即當(dāng)前最優(yōu)只與上一步有關(guān).Us=0,Uj丁平打

13、WiBUs初始值,Uj第J段的最優(yōu)值.（2） 一般方法1找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征；2遞歸地定義最優(yōu)值寫出動(dòng)態(tài)規(guī)劃方程；3以自底向上的方式計(jì)算出最優(yōu)值；4根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造一個(gè)最優(yōu)解.步驟1-3是動(dòng)態(tài)規(guī)劃算法的根本步驟.在只需要求出最優(yōu)值的情形,步驟4可以省略,步驟3中記錄的信息也較少；假設(shè)需要求出問(wèn)題的一個(gè)最優(yōu)解,那么必須執(zhí)行步驟4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解.三、主要儀器設(shè)備及耗材1 .安裝了Windows10操作系統(tǒng)的PC機(jī)1臺(tái)2 .PC機(jī)系統(tǒng)上安裝了MicrosoftVisualStudio2021開(kāi)發(fā)環(huán)境第二局部：實(shí)驗(yàn)過(guò)程和結(jié)果可加頁(yè)四、代碼調(diào)試

14、說(shuō)明調(diào)試手段、過(guò)程及結(jié)果分析調(diào)試主要內(nèi)容為編寫程序的語(yǔ)法正確性與否,程序邏輯的正確性與否.F5:啟動(dòng)調(diào)試；F11:逐語(yǔ)句調(diào)試；F12:逐過(guò)程調(diào)試；F9:切換斷點(diǎn)；ctrl+B:新建斷點(diǎn)等.代碼：#include<iostream>#include<fstream>#include<math.h>usingnamespacestd;inta101;/給定的n個(gè)數(shù)字intm101101;/目標(biāo)數(shù)組,儲(chǔ)存最優(yōu)解intw101101;intn,k;intmax(inta,intb);voidmaxdp()inttemp,_max;/*動(dòng)態(tài)轉(zhuǎn)移方程的求解過(guò)程|if(j

15、=1)m(i,j)=w(1,i);前i位(1:i)數(shù)字分j組乘積的最大值等于分為j-1組的結(jié)果再乘以一個(gè)因子if(j>=1&&j<=i)m(i,j)=maxm(d,j-1)*m(d+1,i)|其中：1<=d<i(即從1開(kāi)始一直到i-1中找最大值)elseif(i<j)m(i,j)=0;、*/如果分成1段|for(inti=1;i<=n;i+)mi1=w1i;for(inti=1;i<=n;i+)for(intj=2;j<=k;j+)_max=0;for(intd=1;d<i;d+)mij=max(mdj-1*wd+1i,mi

16、j);if(mdj-1*wd+1i)>_max)_max=mdj-1*wd+1i;/cout<<mdj-1<<"*"<<wd+1i<<"="<<_max<<endl;mij=_max;intmax(inta,intb)if(a>b)returna;)elsereturnb;intmain()(system("pause");ifstreami1("input.txt",ios:in);if(!i1)(cout<<&quo

17、t;Error"Isystem("pause");return1;)intnum;i1>>n>>k>>num;inty=n;for(intx=1;x<=n;x+)(y=y-1;ax=num/(pow(10,y);num=num-ax*(pow(10,y);)/wij表示從第i位到第j位所組成的十進(jìn)制數(shù)for(inti=1;i<=n;i+)(wii=ai;for(intj=i+1;j<=n;j+)wij=wij-1*10+aj;/每次乘以10再加上個(gè)位數(shù))maxdp();ofstreamo1("output.txt",ios:out);if(!o1)(cout<<"ERRORsystem("pause");return1;)o1<<mnk;o1.close();cout<<mnk<<endl;/fprintf(fp2,"%I64d",mnk);/cout<<mnk<<endl;system("pause");return0;運(yùn)行截圖：*飛嶗一網(wǎng)鶯磔訃£刖*0*治|)1聃觸1g/IEft爺講庶內(nèi).輸入截圖：