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

1、學(xué)生學(xué)號(hào)0121510880508實(shí)驗(yàn)課成績學(xué)生實(shí)驗(yàn)報(bào)告書實(shí)驗(yàn)課程名稱算法設(shè)計(jì)與分桃實(shí)驗(yàn)開課學(xué)院一計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院指導(dǎo)教師姓名學(xué)生姓名丁小兵學(xué)生專業(yè)班級(jí)軟件學(xué)術(shù)】522015- 2016 學(xué)年 第 2 學(xué)期實(shí)驗(yàn)項(xiàng)目名稱分治法的應(yīng)用報(bào)告成績實(shí)驗(yàn)者丁小兵 專業(yè)班級(jí)軟件學(xué)術(shù)1502組別同組者完成日期2017年5月10日第一部分：實(shí)驗(yàn)分析與設(shè)計(jì)(可加頁)一、實(shí)驗(yàn)?zāi)康暮鸵竽康幕菊莆辗种嗡惴ǖ脑?。掌握遞歸算法及遞歸程序的設(shè)計(jì)。能用程序設(shè)計(jì)語言求解相關(guān)問題。2.要求用分治法求解問題；分析算法的時(shí)間性能，設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論。二、分析與設(shè)計(jì)了解用分治法求解的問題：當(dāng)要求解一個(gè)輸入規(guī)模為n,且n的

2、取值相當(dāng)大的問題時(shí)， 如果問題可以分成k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問題，其中1kWn, 而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對(duì) 于這類問題分治法是十分有效的。掌握分治法的一般控制流程。DanC(p,q)global n， A1:n; integer m,p,q; / 1pqnif Small(p,q) then return G(p,q);else m=Divide(p,q); / pmqreturn Combine(DanC(p,m),DanC(m+1,q);endifend DanC實(shí)驗(yàn)內(nèi)容仔細(xì)閱讀備選實(shí)驗(yàn)的題目，設(shè)計(jì)序要的程滿足正確性，

3、代碼中有關(guān)鍵的注釋，書寫格 式清晰，簡潔易懂，效率較高，利用C+ +的模板，設(shè)計(jì)的程序通用性好，適合各種合 理輸入，并能對(duì)不合理輸入做出正確的提示。中位數(shù)問題問題描述設(shè)X0：n - 1和Y 0 : n- 1 為兩個(gè)數(shù)組，每個(gè)數(shù)組中含有n個(gè)已排好序的 數(shù)。找出X和Y的2n個(gè)數(shù)的中位數(shù)。編程任務(wù)利用分治策略試設(shè)計(jì)一個(gè)O (log n)時(shí)間的算法求出這2n個(gè)數(shù)的中位數(shù)。數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個(gè)正整數(shù)n(n=200)，表示每個(gè)數(shù)組有n個(gè)數(shù)。接下來的兩行分別是X，Y數(shù)組的元素。結(jié)果輸出程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的中位數(shù)輸出到文件output.txt中。輸入文件示例

4、輸出文件示例input.txtoutput.txt3145 15 183 14 21三、主要儀器設(shè)備及耗材安裝了Windows10操作系統(tǒng)的PC機(jī)1臺(tái)PC機(jī)系統(tǒng)上安裝TMicrosoftVisualStudio2013開發(fā)環(huán)境第二部分：實(shí)驗(yàn)過程和結(jié)果(可加頁)四、代碼調(diào)試說明(調(diào)試手段、過程及結(jié)果分析)調(diào)試主要內(nèi)容為編寫程序的語法正確性與否，程序邏輯的正確性與否。F5：啟動(dòng)調(diào)試；F11 :逐語句調(diào)試；F12：逐過程調(diào)試；F9：切換斷點(diǎn)； ctrl+B新建斷點(diǎn)等。代碼：#include#include usingnamespace std;int midNum(inta, intn) ( if

5、(n % 2 = 0) (return (an / 2 + an / 2 - 1) / 2;else returnan / 2;int max(inta, intb) ( if (a= b) ( returna;else (returnb;int min(inta, intb) ( if (a= b) ( returna;else (returnb;int getmidNum(inta口，intb , intn) ( int ml, m2;if (n= 0) return -1;if (n = 1) return (a0 + b0) / 2;if (n = 2) return (max(a0,

6、 b0) + min(a1, b1) / 2;ml = midNum(a, n);m2 = midNum(b, n);if (m1 = m2) ( return m1;if (m1m2) (if (n % 2 = 0) (return getmidNum(a + n / 2 - 1, b, n / 2 + 1);else (return getmidNum(a + n / 2, b, n / 2 + 1);else (if (n % 2 = 0) (return getmidNum(b + n / 2 - 1, a, n / 2 + 1);else (return getmidNum(b +

7、n / 2, a, n / 2 + 1);int main()/*ofstream oo(file1.txt”, ios:out);if (!oo)cout Error;system(pause);return 1;oo 11;oo.close();*/ifstream ii(file1.txt”, ios:in);if (!ii)cout i;/cout i;int a10;int b10;int s = 0;for (s = 0; s as;for (s = 0; s bs;ii.close();/cout b2;int result = getmidNum(a, b, i);cout r

8、esultendl;ofstream oo(file2.txt”, ios:out); if (!oo)cout Error”;system(pause);return 1;oo result;oo.close();system(pause);return 0;運(yùn)行截圖:輸入截圖:輸出截圖：J! He2 -1用*SD 日匚msiEi第三部分：實(shí)驗(yàn)小結(jié)、收獲與體會(huì)這次實(shí)驗(yàn)主要是利用分治法來尋求中位數(shù)。通過這次的實(shí)驗(yàn)，讓我充分學(xué)習(xí)了分治法以及其相關(guān)知識(shí)點(diǎn)，給我提供了一個(gè)動(dòng) 手操作的機(jī)會(huì)，并且為了能夠?qū)崿F(xiàn)這個(gè)目的而努力。當(dāng)然，不否認(rèn)這次的實(shí)驗(yàn)也是相 當(dāng)有難度的，畢竟感覺工作量挺大的，而且也確實(shí)有不少

9、自己不明白的地方。對(duì)于這次的實(shí)驗(yàn)來說，我通過努力了解了什么是分治法，而且，也懂得了如何利 用代碼實(shí)現(xiàn)分治法?？偠灾?，這次我收獲確實(shí)很大。實(shí)驗(yàn)項(xiàng)目名稱動(dòng)態(tài)規(guī)劃算法報(bào)告成績實(shí)驗(yàn)者丁小兵 專業(yè)班級(jí)軟件學(xué)術(shù)1502組別同組者完成日期2017年5月10日實(shí)驗(yàn)?zāi)康暮鸵髮?shí)驗(yàn)?zāi)康模?）能用程序設(shè)計(jì)語言實(shí)現(xiàn)求解相關(guān)問題的算法；（2）深刻掌握動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想并能熟練運(yùn)用；（3）理解這樣一個(gè)觀點(diǎn)：同樣的問題可以用不同的方法解決，一個(gè)好的算法 是反復(fù)努力和重新修正的結(jié)果。實(shí)驗(yàn)要求（1）用動(dòng)態(tài)規(guī)劃法求解問題；分析算法的時(shí)間性能，設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論實(shí)驗(yàn)內(nèi)容（1）仔細(xì)閱讀備選實(shí)驗(yàn)的題目，選擇一個(gè)（可選多個(gè)）作

10、為此次實(shí)驗(yàn)題目，設(shè)計(jì)的 程序要滿足正確性，代碼中有關(guān)鍵的注釋，書寫格式清晰，簡潔易懂，效率較 高，利用C+ +的模板，設(shè)計(jì)的程序通用性好，適合各種合理輸入，并能對(duì)不合 理輸入做出正確的提示。（2）從以下題目中任選其一完成。最大K乘積問題問題描述設(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)制整數(shù)1234劃分為3段可有如下情形：1 X 2 X 34 = 681 X 23 X 4 = 9212 X 3 X 4 = 144編程任務(wù)對(duì)于給定的I和k，編程計(jì)算I的最大k乘積。數(shù)據(jù)輸入輸

11、入的第1行中有2個(gè)正整數(shù)n和k。正整數(shù)n是序列的長度；正整數(shù)k是 分割的段數(shù)。接下來的一行中是一個(gè)血位十進(jìn)制整數(shù)。（n=10）結(jié)果輸出計(jì)算出的最大k乘積。輸入文件示例輸出文件示例input.txtoutput.txt3 262312分析設(shè)計(jì)理解最優(yōu)子結(jié)構(gòu)的問題。有一類問題的活動(dòng)過程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該 階段的狀態(tài)，與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。這類問題的解決是 多階段的決策過程。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題 的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計(jì)方法一動(dòng)態(tài)規(guī)劃。對(duì)于一個(gè)多階段過程問題，

12、是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問題是否有最 優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動(dòng)態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多 次。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。（1）理解分段決策Bellman方程。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長度。即當(dāng)前最優(yōu)只與上一步有關(guān)。s = 0,u = minu + w .j詳j i可us初始值，*第j段的最優(yōu)值。（2）一般方法1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2）遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程

13、）；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中記錄的信息也較少；若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。三、主要儀器設(shè)備及耗材1.安裝了Windows10操作系統(tǒng)的PC機(jī)1臺(tái)PC機(jī)系統(tǒng)上安裝TMicrosoftVisualStudio2013開發(fā)環(huán)境第二部分：實(shí)驗(yàn)過程和結(jié)果（可加頁）四、代碼調(diào)試說明（調(diào)試手段、過程及結(jié)果分析）調(diào)試主要內(nèi)容為編寫程序的語法正確性與否，程序邏輯的正確性與否。F5：啟動(dòng)調(diào)試；F11 :逐語句調(diào)

14、試；F12：逐過程調(diào)試；F9：切換斷點(diǎn)；ctrl+B新建斷點(diǎn)等。代碼：#include#include#include usingnamespace std;int a101;/給定的n個(gè)數(shù)字int m101101; /目標(biāo)數(shù)組，儲(chǔ)存最優(yōu)解 int w101101;int n, k;int max(int a, int b);void maxdp()int temp, _max;/*動(dòng)態(tài)轉(zhuǎn)移方程的求解過程 if(j=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)

15、*m(d+1,i)其中：1=d i (即從1開始一直到i-1中找最大值)else if(i j) m(i,j) = 0 ;、*/如果分成1段for (int i = 1; i = n; i+) mi1 = w1i;for (int i = 1; i = n; i+)for (int j = 2; j = k; j+)_max = 0;for (int d = 1; d _max)_max = mdj - 1 * wd + 1i;/cout mdj - 1 * wd + 1i = _max b)returna;elsereturnb;int main()system(pause);ifstrea

16、m i1(input.txt”, ios:in);if (!i1)cout nknum;int y = n;for (int x = 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 (int i = 1; i = n; i+)wii = ai;for (int j = i + 1; j = n; j+)wij = wij - 1 * 10 + aj;/每次乘以10再加上個(gè)位數(shù) maxdp();ofstream o1(output.txt”, ios :out);if (!o1)cout ERROR”;system(pause);return 1;o1 mnk;o1.close();cout mnk endl;/fprintf(fp2, %I64d”, mnk);/ coutmnkendl ;10system(pause);return 0;運(yùn)行截圖：輸入截圖:營