c++課程設(shè)計(jì)——乘積最大

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　實(shí)驗(yàn)內(nèi)容： 課程設(shè)計(jì) </p><p>　　相關(guān)課程： 信息系統(tǒng)開(kāi)發(fā)語(yǔ)言（二） </p><p>　　學(xué) 期： 2011-2012學(xué)年第2學(xué)期 </p><p>　　學(xué)

2、時(shí)學(xué)分： 64 學(xué)時(shí) 4 學(xué)分 </p><p>　　專(zhuān)業(yè)班級(jí)： </p><p>　　學(xué)　　號(hào)： </p><p>　　姓　　名： </p&

3、gt;<p>　　指導(dǎo)老師： </p><p>　　提交日期： 2012年 6月23日 </p><p>　　信息系統(tǒng)開(kāi)發(fā)語(yǔ)言課程設(shè)計(jì)</p><p><b>　　一、課程設(shè)計(jì)目的</b></p><p>　　C++

4、是實(shí)踐性很強(qiáng)的課程。課程設(shè)計(jì)是加強(qiáng)我們實(shí)踐能力的一個(gè)強(qiáng)有力手段,要求我們?cè)谕瓿沙绦蛟O(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。通過(guò)課程設(shè)計(jì)要達(dá)到兩個(gè)目的，一是檢驗(yàn)和鞏固專(zhuān)業(yè)知識(shí)、二是提高綜合素質(zhì)和能力，對(duì)于我們基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。</p><p>　　課程設(shè)計(jì)主要是C++語(yǔ)言程序設(shè)計(jì)的實(shí)現(xiàn)。通過(guò)該課程設(shè)計(jì)，可以將學(xué)生課堂上掌握的理論知識(shí)與處理數(shù)據(jù)的業(yè)務(wù)相結(jié)合，以檢驗(yàn)我

5、們同學(xué)們掌握知識(shí)的寬度、深度及對(duì)知識(shí)的綜合運(yùn)用能力，同時(shí)提高和加強(qiáng)自己的計(jì)算機(jī)應(yīng)用與軟件開(kāi)發(fā)能力,培養(yǎng)自己獨(dú)立分析問(wèn)題、解決問(wèn)題、查閱資料以及自學(xué)能力，以適應(yīng)計(jì)算機(jī)產(chǎn)業(yè)日新月異發(fā)展的形勢(shì)。</p><p>　　學(xué)習(xí)和掌握 C++程序設(shè)計(jì)方法以及上機(jī)調(diào)試技巧，為今后學(xué)習(xí)其它專(zhuān)業(yè)課程打好堅(jiān)實(shí)的基礎(chǔ)，檢測(cè)自己在這一學(xué)期對(duì) C++的學(xué)習(xí)及掌握情況。知道自己的不足，及時(shí)的彌補(bǔ)。為以后的學(xué)習(xí)打下一定的基礎(chǔ),也為自己以后如何制

6、定學(xué)習(xí)計(jì)劃做一鋪墊。</p><p><b>　　二、問(wèn)題描述</b></p><p><b>　　題號(hào)8乘積最大</b></p><p>　　總體需求：編寫(xiě)一個(gè)實(shí)現(xiàn)將一個(gè)的數(shù)字串，分成K+1個(gè)部分，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲蟆?lt;/p><p>　　功能需求：設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要

7、求使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?。如：有一個(gè)數(shù)字串：312，當(dāng)N=3時(shí)，K=1時(shí)會(huì)有以下兩種分法：</p><p>　　1）3×12 = 36</p><p>　　2）31×2 = 62</p><p>　　此時(shí)，符合題意的結(jié)果是31×2 = 62</p><p&g

8、t;<b>　　用戶(hù)界面</b></p><p><b>　　輸入: </b></p><p>　　1）程序正常運(yùn)行后，提示用戶(hù)輸入一行共有2個(gè)自然數(shù)N，K（2≤N≤40，1≤K≤6）。</p><p>　　2）第二行是一個(gè)長(zhǎng)度為N的數(shù)字串。 </p><p><b>　　輸出:<

9、/b></p><p>　　相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。</p><p><b>　　提示與參考</b></p><p><b>　　輸入樣例：</b></p><p><b>　　4 2</b></p><p><b&

10、gt;　　1231</b></p><p><b>　　輸出樣例：</b></p><p><b>　　62</b></p><p><b>　　問(wèn)題分析</b></p><p>　　此程序要求實(shí)現(xiàn)將長(zhǎng)度為N的數(shù)字串，用K個(gè)乘號(hào)分成K+1個(gè)部分，使得這K+1個(gè)部分的

11、乘積能夠?yàn)樽畲蟆?lt;/p><p>　　由題，數(shù)字串的順序固定不變，乘號(hào)在不同的位置插入，使得數(shù)字乘積發(fā)生變化，并取其最大值輸出。設(shè)num=3456，n=4，k=3，這表示要將4 位的十進(jìn)制整數(shù)3456 分為3 段。劃分方法為：3×4×56=672，3×45×6=810，34×5×6=1020，而第3 種劃分才是最佳劃分。本問(wèn)題屬于求最優(yōu)值的一類(lèi)問(wèn)題。&l

12、t;/p><p>　　假設(shè)第k個(gè)乘號(hào)插入的位置為p，取出由后n-q個(gè)數(shù)字組成的數(shù)字串，可能包含任意個(gè)（不多于k個(gè)）乘號(hào)。若能求出任意子串包含k-1個(gè)乘號(hào)的最大乘積，則只需窮舉第k個(gè)乘號(hào)的插入位置q，該乘號(hào)將數(shù)字串分成前后兩段，后半段包含k-1個(gè)乘號(hào)，其最大值根據(jù)假設(shè)已經(jīng)算出，將它與前半段的值相乘得到第k個(gè)乘號(hào)在位置q時(shí)的乘積。取所有的第k個(gè)乘號(hào)不同插入方案中的最大乘積即為問(wèn)題“后n-q個(gè)數(shù)字組成的數(shù)字串插入k-1個(gè)乘

13、號(hào)”的解。</p><p>　　假設(shè)數(shù)字字符串為aa…a（2<=n<=40），設(shè)f[i,j]表示在后i位數(shù)中插入j個(gè)乘號(hào)所得的最大值，p(1 , n , k )為從 l 到n加入 k 個(gè)乘號(hào)的最大乘積值。</p><p>　?。?）K=1時(shí)，一個(gè)乘號(hào)可以插在a1a2…a中的n-1個(gè)位置，這樣就得到n-1個(gè)子串的乘積：a*a…a ， aa* a…a ， …， aa…a* a<

14、;/p><p>　　此時(shí)的最大值p(1 , n , k )= max{ a*a…a ， aa* a…a ， …，aa…a* a}</p><p>　　（2）K=2時(shí)，二個(gè)乘號(hào)可以插在aa…a中n-1個(gè)位置的任兩個(gè)地方，這樣總共會(huì)產(chǎn)生 個(gè)乘積。把這些乘積分個(gè)類(lèi)，便于觀(guān)察規(guī)律。</p><p>　　Case1: a*a* a…a ， a*a

15、a*…a ， …， a*a…a* a</p><p>　　因后一個(gè)乘號(hào)位置不變，要使這些乘積最大，就要找出在前n-1個(gè)數(shù)中插入一個(gè)乘號(hào)的最大值。設(shè)符號(hào)f[n-1,1]為在后n-1個(gè)數(shù)中插入一個(gè)乘號(hào)的最大值，則 Case1的最大值為a*f[n-1,1]</p><p>　　Case2：aa* a*a…a ， aa*aa*…a ， …， aa*aa…a* a</p>&l

16、t;p>　　因后一個(gè)乘號(hào)位置不變，要使這些乘積最大，就要找出在前n-2個(gè)數(shù)中插入一個(gè)乘號(hào)的最大值。設(shè)符號(hào)f[n-2,1]為在后n-2個(gè)數(shù)中插入一個(gè)乘號(hào)的最大值，則</p><p>　　Case2的最大值為aa*f[n-2,1]</p><p>　　同理，Case3的最大值為aaa*f[n-3,1]</p><p><b>　　……</b>

17、</p><p>　　Case(n-2)的最大值為aa…a*f[2,1]</p><p>　　此時(shí)的最大值p(1 , n , k )= max{ Case1，Case2，…， Case(n-2) }</p><p>　　(3)由此得出K=i時(shí)，p(1 , n , k )= max{ a*f[n-1,i-1], aa*f[n-2,i-1], aa*f[n-3,i-1]

18、， …，aa…a*f[n-i,i-1] } </p><p>　　由上述可知，第k個(gè)乘號(hào)的插入位置q，p(1 , n , k )為從 l 到n加入 k 個(gè)乘號(hào)的最大乘積值。</p><p>　　又令d (1 ,q)= aa…a</p><p>　　則p( l,n,k )=max{ d (1 ,q)* p( n-q , n , k-1 ) } </p>

19、<p>　　四、算法分析、設(shè)計(jì)與描述</p><p><b>　　1．算法分析和設(shè)計(jì)</b></p><p><b>　　（1）算法分析</b></p><p>　　由于問(wèn)題的規(guī)模為2≤N≤40，1≤K≤6，且只有乘號(hào)插入的位置是變化的，要在長(zhǎng)為N的數(shù)字串中插入K個(gè)乘號(hào)使得乘積最大，自然數(shù)位數(shù)的上限為40，乘號(hào)數(shù)

20、的上限為6，最大乘積位數(shù)的上限接近42位,顯然將會(huì)超出長(zhǎng)整數(shù)的范圍，所以運(yùn)算要用高精度乘法。若用窮舉法，在長(zhǎng)為N的數(shù)字串中插入K個(gè)乘號(hào)的方案共有C（N-1,K）種，當(dāng)N=40，K=6時(shí)，C（N-1,K）=1344904種方案，而高精度乘法運(yùn)算也較費(fèi)時(shí)間。由此可知，窮舉法將不合適此題。</p><p>　　假設(shè)一個(gè)長(zhǎng)度為N 的數(shù)字串加入K個(gè)乘號(hào)的最大乘積記為f（n，k），前k段總共是q位，且1<=q<n

21、，則最后一段為n-q位，用d(q,n-q)表示從第q位開(kāi)始的最后長(zhǎng)度為n-q位的字符，則f(n，k)=f(q,k-1)*d(q,n-q)?，F(xiàn)在我們假設(shè)前面長(zhǎng)度為q位字符串加入K個(gè)乘號(hào)的最大乘積不是f(q,k-1)，而是e(q,k-1)，則有e(q,k-1)>f(q,k-1)左右兩邊同時(shí)乘以d(q,n-q)得 e(q,k-1)*d(q,n-q)>f(q,k-1)*d(q,n-q)=f(n,k)。即f(n,k)不是一個(gè)長(zhǎng)度為N

22、的數(shù)字串加入K個(gè)乘號(hào)的最大乘積與最初的假設(shè)相矛盾。所以f(q,k-1)是前面q位字符串加入k-1乘號(hào)的最大乘積，即此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。</p><p>　　由于子問(wèn)題是在子串中插入k-1,k-2, … ,1,0個(gè)乘號(hào)，因此，把k作為階段變量。狀態(tài)變量是階段變量的函數(shù)，它會(huì)隨著階段變量的改變而變化。階段數(shù)J ，表示在子串中插入J個(gè)乘號(hào)。最少是長(zhǎng)度為J+1的子串才能剛好插入這J個(gè)乘號(hào)。這就是J階段的起始狀態(tài)：在

23、長(zhǎng)度為J+1的子串中插入J個(gè)乘號(hào)。再思考狀態(tài)數(shù)的上界，有k-J個(gè)乘號(hào)需要插入右子串中，右子串最短剛好容納K-J個(gè)乘號(hào)的長(zhǎng)度為K-J+1，而整個(gè)字串的長(zhǎng)度為n，故左子串最長(zhǎng)允許的長(zhǎng)度為n-(k-J+1) = n+J-k-1?？偨Y(jié)起來(lái)，狀態(tài)數(shù)I的取值范圍就是J+1 <= I <= n+J-k-1。階段、狀態(tài)確定了，要求解的當(dāng)前問(wèn)題也就確定了：在長(zhǎng)度為I的子串中插入J個(gè)乘號(hào)的最優(yōu)解是多少？用符號(hào)表示就是求F[I,J]的值。前面已經(jīng)

24、分析過(guò)，這一問(wèn)題可以理解為用第J個(gè)乘號(hào)把長(zhǎng)度為I的字串分左、右二個(gè)子串，右子串中插有J-1個(gè)乘號(hào)，求得它的最優(yōu)解，再乘以左子串的問(wèn)題。由于右子串要插入J-1個(gè)乘號(hào)，因此右子串的最短長(zhǎng)度為J-1+1 = J，這就是決策變量的起始值，也就是下界。又由于第J個(gè)乘號(hào)一定要分出左右子串來(lái)，左子串最短為1，此時(shí)右子串最長(zhǎng)為I-1</p><p><b>　?。?）算法設(shè)計(jì)</b></p>

25、<p>　　遞歸調(diào)用+回溯+向量容器</p><p>　　遞歸調(diào)用Maxproduct(num,n,k)，乘號(hào)插入第i個(gè)數(shù)后，截?cái)鄆個(gè)數(shù)，放到向量容器1里，如果得到一個(gè)最大乘積時(shí)置一個(gè)全局變量為真，則返回上一級(jí)遞歸調(diào)用后，將向量容器1存儲(chǔ)的數(shù)字回溯到前一狀。字符移到串的s+i位置，字符串個(gè)數(shù)為n-i，還可插入的乘號(hào)有k-1個(gè)，繼續(xù)調(diào)用Maxproduct(s+i,n-i,k-1)。直至k=0，算出pro

26、duct，與Maxproduct比較，如果大就重新賦值Maxproduct=product，清空容器2，并把字符串截?cái)嗟那闆r存儲(chǔ)容器2中。</p><p>　　2．算法描述（可插入流程圖）</p><p>　　輸入兩個(gè)自然數(shù)n、k和一個(gè)字符串num，判斷2≤n≤40&&1≤k≤6,如果2≤n≤40&&1≤k≤6，繼續(xù)判斷n=strlen(num)和n>

27、k，如果這兩個(gè)條件都滿(mǎn)足，則調(diào)用函數(shù)Maxproduct(s+i,n-i,k-1)，最后輸出最大值，結(jié)束算法。</p><p><b>　　五、程序設(shè)計(jì)</b></p><p><b>　　方法一：</b></p><p><b>　　1、程序代碼及說(shuō)明</b></p><p>

28、;　　#include <iostream> </p><p>　　#include <vector> </p><p>　　#include <string.h> </p><p>　　using namespace std; </p><p>　　#define BUFFERSIZE 40</p&

29、gt;<p>　　char num[BUFFERSIZE]={0};</p><p>　　vector<string> result; //將result聲明為一個(gè)元素類(lèi)型為string的向量容器對(duì)象</p><p>　　vector<string> temp; //將temp聲明為一個(gè)元素類(lèi)型為string的向量容器對(duì)象</p>&l

30、t;p>　　double maxProduct=0; </p><p>　　bool getAmaxproduct=false; </p><p>　　void maxproduct(char* s, int n,int k) </p><p><b>　　{ </b></p><p>　　vector<st

31、ring>::iterator p; //將p聲明為string 類(lèi)型的向量容器迭代器</p><p><b>　　if(k==0)</b></p><p><b>　　{ </b></p><p>　　getAmaxproduct=true; </p><p>　　temp.push_bac

32、k(s); //將字符串壓入vector</p><p>　　double product=1; </p><p>　　for (p=temp.begin(); p!=temp.end(); p++) </p><p>　　{ product *= atoi((*p).c_str()); } </p><p>　　if(product >

33、; maxProduct) </p><p><b>　　{ </b></p><p>　　maxProduct = product; </p><p>　　result.clear();//將容器result清空 </p><p>　　result=temp; </p><p><b>

34、;　　} </b></p><p><b>　　} </b></p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　for(int i=1; i<=n-k; i++) </p><p&

35、gt;<b>　　{ </b></p><p><b>　　//釋放空間</b></p><p>　　if(getAmaxproduct) </p><p><b>　　{ </b></p><p>　　int poplength=0; </p><p>

36、;　　for(p=temp.end()-1; poplength!=n;temp.pop_back(),p=temp.end()-1) </p><p>　　{poplength += (*p).size();} </p><p>　　getAmaxproduct=false; </p><p><b>　　} </b></p>

37、<p>　　//聲明一個(gè)指針，對(duì)其進(jìn)行分配空間，并初始化</p><p>　　char *tmp=new char[BUFFERSIZE]; //新建一個(gè)等長(zhǎng)度BUFFERSIZE的字符數(shù)組</p><p>　　memset(tmp,0,BUFFERSIZE); //為結(jié)構(gòu)體tmp分配BUFFERSIZE大小內(nèi)存空間</p><p>　　for(int j

38、=0; j<i; j++) </p><p><b>　　{ </b></p><p>　　if (tmp[0]==0) </p><p>　　tmp[0]=*(s+j); </p><p><b>　　else </b></p><p>　　tmp[strlen(tm

39、p)] = *(s+j); </p><p><b>　　} </b></p><p>　　temp.push_back(tmp); //將tmp里的字符串放到temp尾部</p><p>　　maxproduct(s+i,n-i,k-1); //遞歸調(diào)用</p><p><b>　　} </b>&

40、lt;/p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void main() </p><p><b>　　{ </b></p><p><b>　　int k,n; </b><

41、;/p><p>　　cout<<"Please input n and k (2≤N≤40，1≤K≤6):\n"; </p><p>　　cin>>n>>k;</p><p>　　cout<<"Please input num:\n";</p><p><

42、;b>　　cin>>num;</b></p><p>　　if(n>=2&&n<=40&&k>=1&&k<=6)</p><p><b>　　{</b></p><p>　　if(n !=strlen(num))</p><

43、p><b>　　{ </b></p><p>　　cout<<"請(qǐng)確保輸入的字符串的長(zhǎng)度=n\n"; </p><p><b>　　return; </b></p><p><b>　　} </b></p><p>　　if (n<=

44、k) </p><p><b>　　{ </b></p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)不能分成 "<<k<<"+1部分\n"; </p><p><b>　　return

45、; </b></p><p><b>　　} </b></p><p>　　maxproduct(num,n,k); </p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)分成"<<k<<"+1

46、部分的最大乘積= "; </p><p>　　for(vector<string>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p><p>　　cout<<(*p).c_str(); </p>

47、<p>　　if (p==result.end()-1) </p><p>　　{cout<<" = "; }</p><p><b>　　else </b></p><p>　　cout<<"*"; </p><p><b>　　} &

48、lt;/b></p><p>　　cout<< maxProduct<<endl; </p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　cout<<"請(qǐng)重新輸入n和k(2≤N≤40，1≤K≤6

49、)"<<endl; </p><p><b>　　}</b></p><p><b>　　方法二：</b></p><p>　　1、程序設(shè)計(jì)的基本思路</p><p>　　class BigDecimal // 高精度整數(shù)</p><p><b&g

50、t;　　{</b></p><p>　　unsigned char num[100]; // 從低位到高位存放每一位數(shù)字，最高支持100位，修改此數(shù)字可以提高支持精度</p><p>　　int len; // 數(shù)字的位數(shù)</p><p><b>　　public:</b></p><p>　　BigDeci

51、mal() // default constructor, 初始化數(shù)字為0</p><p>　　BigDecimal(string s) // 由s初始化整數(shù)</p><p>　　BigDecimal operator*(const BigDecimal& a) // 高精度乘法</p><p>　　bool operator<(const BigDe

52、cimal& a) const // 比較兩個(gè)高精度整數(shù)</p><p>　　bool operator>(const BigDecimal& a) const</p><p>　　bool operator==(const BigDecimal& a) const</p><p>　　void print() const // 從高位

53、開(kāi)始打印</p><p><b>　　};</b></p><p><b>　　2．程序代碼及說(shuō)明</b></p><p>　　#include <iostream></p><p>　　#include <string></p><p>　　#inc

54、lude <cstring></p><p>　　using namespace std;</p><p>　　class BigDecimal // 高精度整數(shù)</p><p><b>　　{</b></p><p>　　unsigned char num[100]; // 從低位到高位存放每一位數(shù)字，最高

55、支持100位，修改此數(shù)字可以提高支持精度</p><p>　　int len; // 數(shù)字的位數(shù)</p><p><b>　　public:</b></p><p>　　BigDecimal() // default constructor, 初始化數(shù)字為0</p><p><b>　　{</b>&

56、lt;/p><p><b>　　len = 1;</b></p><p>　　num[0] = 0;</p><p><b>　　}</b></p><p>　　BigDecimal(string s) // 由s初始化整數(shù)</p><p><b>　　{</b&

57、gt;</p><p>　　len = s.size(); // 讀取長(zhǎng)度</p><p>　　for(int i=s.size()-1;i>=0;i--) // 從低位開(kāi)始讀取</p><p><b>　　{</b></p><p>　　num[len-i-1] = s[i]-'0';</p

58、><p><b>　　}</b></p><p>　　while(len>0&&num[len-1]==0) len--; // 去除高位0</p><p>　　if(len==0) len = 1;</p><p><b>　　}</b></p><p>

59、　　BigDecimal operator*(const BigDecimal& a) // 高精度乘法</p><p><b>　　{</b></p><p>　　BigDecimal c; // 結(jié)果存放變量</p><p>　　memset(c.num,0,sizeof(c.num)); // 初始化為0</p>&

60、lt;p>　　for(int i=0;i<len;i++) // 模擬豎式乘法</p><p><b>　　{</b></p><p>　　for(int j=0;j<a.len;j++)</p><p><b>　　{</b></p><p>　　c.num[i+j]+=num[

61、i]*a.num[j]; // 對(duì)本數(shù)字的第i位和a的第j位相乘， 存放在結(jié)果的i+j位</p><p>　　c.num[i+j+1] += c.num[i+j]/10; // 模擬進(jìn)位</p><p>　　c.num[i+j]%=10;</p><p><b>　　}</b></p><p><b>

62、　　}</b></p><p>　　c.len = a.len+len;</p><p>　　while(c.len>0&&c.num[c.len-1]==0) c.len--; // 去掉高位0</p><p>　　if(c.len==0) c.len = 1;</p><p><b>　　ret

63、urn c;</b></p><p><b>　　}</b></p><p>　　bool operator<(const BigDecimal& a) const // 比較兩個(gè)高精度整數(shù)</p><p><b>　　{</b></p><p>　　if(len <

64、 a.len)</p><p>　　return true;</p><p>　　else if(len > a.len)</p><p>　　return false;</p><p>　　for(int i=len-1;i>=0;i--)</p><p><b>　　{</b>&l

65、t;/p><p>　　if(num[i]<a.num[i])</p><p>　　return true;</p><p>　　else if(num[i]>a.num[i])</p><p>　　return false;</p><p><b>　　}</b></p>&

66、lt;p>　　return false;</p><p><b>　　}</b></p><p>　　bool operator>(const BigDecimal& a) const</p><p><b>　　{</b></p><p>　　return a<(*thi

67、s);</p><p><b>　　}</b></p><p>　　bool operator==(const BigDecimal& a) const</p><p><b>　　{</b></p><p>　　return !((*this)<a||a<(*this));&l

68、t;/p><p><b>　　}</b></p><p>　　void print() const // 從高位開(kāi)始打印</p><p><b>　　{</b></p><p>　　for(int i=len-1;i>=0;i--)</p><p>　　cout <&

69、lt; ((int)num[i]);</p><p>　　cout << endl;</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　string str;</p><p>　　bool cal[41][41]

70、[7]; // DP標(biāo)記, true表示dp[i][j][k]已算過(guò), false表示沒(méi)有算過(guò)</p><p>　　BigDecimal dp[41][41][7]; // 存放DP(i,j,k)的結(jié)果</p><p>　　int mark[41][41][7]; // 回溯標(biāo)記</p><p>　　BigDecimal DP(int i, int j, int k

71、) // 函數(shù)計(jì)算輸入從i到j(luò)-1中間插入k個(gè)乘號(hào)的最大值</p><p><b>　　{</b></p><p>　　if(cal[i][j][k]) // 如果DP(i,j,k)已經(jīng)算過(guò)</p><p>　　return dp[i][j][k]; // 返回之前記錄的數(shù)據(jù)</p><p>　　cal[i][j][k]

72、 = true; // 標(biāo)記cal[i][j][k]為true，避免以后重復(fù)計(jì)算</p><p>　　if(j-i<=k) // 如果長(zhǎng)度不夠k+1，就塞不下k個(gè)乘號(hào)，返回0</p><p><b>　　{</b></p><p>　　dp[i][j][k] = BigDecimal();</p><p>　　re

73、turn dp[i][j][k];</p><p><b>　　}</b></p><p>　　if(k==0) // 如果不需要插入任何乘號(hào)</p><p><b>　　{</b></p><p>　　dp[i][j][k] = BigDecimal(str.substr(i,j-i)); //

74、返回 i到j(luò)-1這個(gè)數(shù)</p><p>　　return dp[i][j][k];</p><p><b>　　}</b></p><p>　　BigDecimal temp; // 最后結(jié)果初始化為0</p><p>　　mark[i][j][k] = i+1; // 回溯標(biāo)記, 記錄乘號(hào)在哪個(gè)位置之前</p&g

75、t;<p>　　for(int t=i+1;t<j;t++) // 枚舉下一個(gè)乘號(hào)所有的位置，從i+1到j(luò)-1</p><p><b>　　{</b></p><p>　　BigDecimal temp2 = DP(i,t,0)*DP(t,j,k-1); // dp遞推式，算式值等于i到t-1的值 * t到j(luò)中間插入k-1個(gè)乘號(hào)的最大值</p

76、><p>　　if(temp < temp2) // 更新temp為較大值</p><p><b>　　{</b></p><p>　　mark[i][j][k] = t; // 更新回溯標(biāo)記</p><p>　　temp = temp2;</p><p><b>　　}</b&

77、gt;</p><p><b>　　}</b></p><p>　　dp[i][j][k] = temp; // 記錄到dp數(shù)組，以后可以直接返回</p><p>　　return temp;</p><p><b>　　}</b></p><p>　　int main()&

78、lt;/p><p><b>　　{</b></p><p><b>　　int N,K;</b></p><p>　　cout << "Please input N and K (2≤N≤40，1≤K≤6):" << endl;</p><p>　　cin

79、>> N >> K;</p><p>　　cout << "請(qǐng)輸入一個(gè)長(zhǎng)度為" << N << "的數(shù)字串str:" << endl;</p><p>　　cin >> str;</p><p>　　if(N>=2&&N&

80、lt;=40&&K>=1&&K<=6)</p><p><b>　　{</b></p><p>　　if(N!=str.size())</p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)確保輸入的數(shù)符串的長(zhǎng)

81、度=N\n"; </p><p>　　return 0; </p><p><b>　　} </b></p><p>　　if (N<=K) </p><p><b>　　{ </b></p><p>　　cout<<str<<&quo

82、t;中輸入"<<K<<"個(gè)乘號(hào)不能分成 "<<K<<"+1部分\n"; </p><p>　　return 0; </p><p><b>　　} </b></p><p>　　memset(cal,0,sizeof(cal));</p>

83、;<p>　　cout << "所求得的最大乘積:" ;</p><p>　　BigDecimal ans = DP(0,str.size(),K);</p><p>　　int temp = K;</p><p>　　int tempstart = 0;</p><p>　　while(temp

84、)</p><p><b>　　{</b></p><p>　　cout << str.substr(tempstart,mark[tempstart][str.size()][temp]-tempstart) << " * ";</p><p>　　tempstart = mark[tempstar

85、t][str.size()][temp];</p><p><b>　　temp--;</b></p><p><b>　　}</b></p><p>　　cout << str.substr(tempstart,str.size()-tempstart) << " = ";&l

86、t;/p><p>　　ans.print();</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　cout<<"請(qǐng)重新輸入N

87、和K(2≤N≤40，1≤K≤6)"<<endl; </p><p><b>　　}</b></p><p>　　六、程序運(yùn)行、調(diào)試和結(jié)果分析</p><p>　　1．程序運(yùn)行中出現(xiàn)的問(wèn)題及調(diào)試手段（包括異常處理）</p><p>　　本次程序設(shè)計(jì)以方法一為主，程序的開(kāi)始的輸入運(yùn)行過(guò)程，會(huì)有很多的錯(cuò)誤

88、，像大小寫(xiě)輸入錯(cuò)誤，”{}”忘記輸入等，還有一些語(yǔ)句上的錯(cuò)誤導(dǎo)致程序運(yùn)行不出結(jié)果，經(jīng)過(guò)多次的調(diào)試，本程序基本上可以實(shí)現(xiàn)計(jì)算要求。以下列舉出程序調(diào)試過(guò)程中出現(xiàn)的部分錯(cuò)誤：</p><p><b>　　(1)</b></p><p><b>　　程序報(bào)錯(cuò)：</b></p><p><b>　　{</b>&

89、lt;/p><p>　　maxproduct(num,n,k); </p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)分成"<<k<<"+1部分的最大乘積= \n"; </p><p>　　for(vector<s

90、tring>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p><p>　　cout<<(*p).c_str(); </p><p>　　if (p==result.end()-1) </p><p>

91、　　{cout<<" = "; </p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　cout<<"*"; </p><p><b>　　} </b><

92、/p><p>　　cout<< maxProduct<<endl; </p><p><b>　　}</b></p><p>　　程序修改：刪除第一行maxproduct前面的“{”；</p><p><b>　　(2)</b></p><p>　　沒(méi)有n

93、的輸入語(yǔ)句，直接要求輸入數(shù)字，不符合題目要求。程序修改如下：</p><p>　　void main() </p><p><b>　　{ </b></p><p><b>　　int k,n; </b></p><p>　　cout<<"Please input num an

94、d k:\n"; </p><p>　　cin>>num>>k; </p><p>　　if (num[0]=='0') </p><p><b>　　{ </b></p><p>　　cout<<"Be sure a number should b

95、egin with non 0\n"; </p><p><b>　　return; </b></p><p><b>　　} </b></p><p>　　n = strlen(num); </p><p>　　if (n < k) </p><p><

96、;b>　　{ </b></p><p>　　cout<<num<<" does not have a "<<k<<" product!"; </p><p><b>　　return; </b></p><p><b>　　} &

97、lt;/b></p><p>　　if(n > BUFFERSIZE) </p><p><b>　　{ </b></p><p>　　cout<<"Buffer overload,size="<<BUFFERSIZE<<endl; </p><p>&

98、lt;b>　　return; </b></p><p><b>　　} </b></p><p>　　kproduct(num,n,k); </p><p>　　cout<<num<<"'s max K product is "; </p><p>　

99、　for(vector<string>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p><p>　　cout<<(*p).c_str(); </p><p>　　if (p==result.end()-1) </

100、p><p>　　cout<<" = "; </p><p><b>　　else </b></p><p>　　cout<<"*"; </p><p><b>　　} </b></p><p>　　cout<&

101、lt;KProduct<<endl; </p><p><b>　　}</b></p><p><b>　　修改為：</b></p><p>　　void main() </p><p><b>　　{ </b></p><p><b&

102、gt;　　int k,n; </b></p><p>　　cout<<"Please input n and k (2≤N≤40，1≤K≤6):\n"; </p><p>　　cin>>n>>k;</p><p>　　cout<<"Please input num:\n&quo

103、t;;</p><p><b>　　cin>>num;</b></p><p>　　if(n>=2&&n<=40&&k>=1&&k<=6)</p><p><b>　　{</b></p><p>　　if(n !=s

104、trlen(num))</p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)確保輸入的字符串的長(zhǎng)度=n\n"; </p><p><b>　　return; </b></p><p><b>　　} </b></p

105、><p>　　if (n<=k) </p><p><b>　　{ </b></p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)不能分成 "<<k<<"+1部分\n"; </p>

106、<p><b>　　return; </b></p><p><b>　　} </b></p><p>　　maxproduct(num,n,k); </p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)分成&quo

107、t;<<k<<"+1部分的最大乘積= \n"; </p><p>　　for(vector<string>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p><p>　　cout<&

108、lt;(*p).c_str(); </p><p>　　if (p==result.end()-1) </p><p>　　{cout<<" = "; </p><p><b>　　}</b></p><p><b>　　else </b></p>&l

109、t;p>　　cout<<"*"; </p><p><b>　　} </b></p><p>　　cout<< maxProduct<<endl; </p><p><b>　　}</b></p><p><b>　　else&

110、lt;/b></p><p>　　cout<<"請(qǐng)重新輸入n和k(2≤N≤40，1≤K≤6)"; </p><p><b>　　}</b></p><p><b>　　(3)</b></p><p>　　未考慮到n和k的取值范圍：</p><

111、p><b>　　程序修改如下： </b></p><p>　　void main() </p><p><b>　　{ </b></p><p><b>　　int k,n; </b></p><p>　　cout<<"Please input n

112、and k:\n"; </p><p>　　cin>>n>>k;</p><p>　　cout<<"Please input num:\n";</p><p><b>　　cin>>num;</b></p><p>　　if(n !=strle

113、n(num))</p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)確保輸入的字符串的長(zhǎng)度=n\n"; </p><p><b>　　return; </b></p><p><b>　　} </b></p>

114、<p>　　if (n ==k) </p><p><b>　　{ </b></p><p>　　cout<<num<<" 不能分成 "<<k<<"+1部分"; </p><p><b>　　return; </b><

115、;/p><p><b>　　} </b></p><p>　　Maxproduct(num,n,k); </p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)分成"<<k<<"+1的最大乘積= ";

116、</p><p>　　for(vector<string>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p><p>　　cout<<(*p).c_str(); </p><p>　　if (p=

117、=result.end()-1) </p><p>　　cout<<" = "; </p><p><b>　　else </b></p><p>　　cout<<"*"; </p><p><b>　　} </b></p>

118、<p>　　cout<<MaxProduct<<endl; </p><p><b>　　}</b></p><p><b>　　修改為：</b></p><p>　　void main() </p><p><b>　　{ </b><

119、;/p><p><b>　　int k,n; </b></p><p>　　cout<"Please input n and k (2≤N≤40，1≤K≤6):\n"; </p><p>　　cin>>n>>k;</p><p>　　cout<<"Ple

120、ase input num:\n";</p><p><b>　　cin>>num;</b></p><p>　　if(n>=2&&n<=40&&k>=1&&k<=6)</p><p><b>　　{</b></p>

121、<p>　　if(n !=strlen(num))</p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)確保輸入的字符串的長(zhǎng)度=n\n"; </p><p><b>　　return; </b></p><p><b>

122、　　} </b></p><p>　　if (n<=k) </p><p><b>　　{ </b></p><p>　　cout<<num<<"中輸入"<<k<<"個(gè)乘號(hào)不能分成 "<<k<<"+1部分\

123、n"; </p><p><b>　　return; </b></p><p><b>　　} </b></p><p>　　maxproduct(num,n,k); </p><p>　　cout<<num<<"中輸入"<<k<

124、;<"個(gè)乘號(hào)分成"<<k<<"+1部分的最大乘積= \n"; </p><p>　　for(vector<string>::iterator p=result.begin(); p!=result.end(); p++) </p><p><b>　　{ </b></p>

125、<p>　　cout<<(*p).c_str(); </p><p>　　if (p==result.end()-1) </p><p>　　{cout<<" = "; </p><p><b>　　}</b></p><p><b>　　else <

126、/b></p><p>　　cout<<"*"; </p><p><b>　　} </b></p><p>　　cout<< maxProduct<<endl; </p><p><b>　　}</b></p><p

127、><b>　　else</b></p><p>　　cout<<"請(qǐng)重新輸入n和k(2≤N≤40，1≤K≤6)"; </p><p><b>　　}</b></p><p>　　2．程序運(yùn)行結(jié)果分析（多組數(shù)據(jù)測(cè)試）</p><p>　　本次程序設(shè)計(jì)以方法一為主，

128、一下測(cè)試數(shù)據(jù)與結(jié)果分析均為方法一測(cè)試結(jié)果。</p><p>　?。?）輸入一串字符串和兩個(gè)自然數(shù)n、k（2≤n≤40，1≤k≤6）時(shí)的運(yùn)行結(jié)果如下：</p><p>　　分別輸入n和k，使n和k在限定范圍內(nèi)，程序正常運(yùn)行，輸入三個(gè)數(shù)1、2、3，插入一個(gè)乘號(hào)，一共有兩種插入方法：1*23=23</p><p><b>　　12*3=36</b>&

129、lt;/p><p>　　由題目要求，輸出結(jié)果應(yīng)為12*3=36，與實(shí)際輸出結(jié)果相同，程序運(yùn)行結(jié)果正確，運(yùn)行正常。</p><p>　?。?）輸入一串字符串和兩個(gè)自然數(shù)n、k,且（n<2‖n>40‖k>6）時(shí)的運(yùn)行結(jié)果如下：</p><p>　　分別輸入n和k，使 n=k，輸入不符合題目要求，按照程序設(shè)定，應(yīng)當(dāng)輸出“請(qǐng)重新輸入n和k（2≤N≤40,1≤k

130、≤6）”,程序?qū)嶋H運(yùn)行結(jié)果正確，運(yùn)行正常。</p><p>　?。?）輸入一串字符串和兩個(gè)自然數(shù)n、k（2≤kn≤40，1≤k≤6），當(dāng)字符串的長(zhǎng)度不等于n時(shí)的運(yùn)行結(jié)果：</p><p>　　分別輸入n和k，使n不等于字符串的長(zhǎng)度，輸入不符合題目要求，按照程序設(shè)定，應(yīng)當(dāng)輸出“請(qǐng)確保輸入的字符串長(zhǎng)度=n”,程序?qū)嶋H運(yùn)行結(jié)果正確，運(yùn)行正常。</p><p>　　（4）輸

131、入一串字符串和兩個(gè)自然數(shù)n、k（2≤n≤40，1≤k≤6），當(dāng)n≤k時(shí)的運(yùn)行結(jié)果：</p><p>　　分別輸入n和k，使n≤k，輸入不符合題目要求，按照程序設(shè)定，應(yīng)當(dāng)輸出“***（num）中輸入*（k）個(gè)乘號(hào)不能分成**（k+1）個(gè)部分”,程序?qū)嶋H運(yùn)行結(jié)果正確，運(yùn)行正常。</p><p><b>　　七、總結(jié)與體會(huì)</b></p><p>　

132、　本次C++程序設(shè)計(jì)為編寫(xiě)一個(gè)程序，實(shí)現(xiàn)將一個(gè)的數(shù)字串，分成K+1個(gè)部分，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?，主要運(yùn)用的思想是遞歸調(diào)用+回溯+向量容器。</p><p>　　第一次使用C++進(jìn)行程序設(shè)計(jì)，從重新了解熟悉面向?qū)ο蟮幕靖拍?，研究面向?qū)ο蟮能浖ちP的流程，從問(wèn)題分析到程序設(shè)計(jì)，編寫(xiě)程序段，最后調(diào)試程序，編寫(xiě)文檔，歷時(shí)約半個(gè)月。從實(shí)踐中學(xué)習(xí)從來(lái)都是最好的學(xué)習(xí)方式，從本次程序編寫(xiě)過(guò)程中，我們才發(fā)現(xiàn)了日常學(xué)

133、習(xí)中，我們所存在的大量問(wèn)題，比如知識(shí)掌握不牢靠，能看不能寫(xiě)，眼高手低，不能很好的運(yùn)用面向?qū)ο蟮乃枷?，很容易受面向過(guò)程的思想左右，編程缺少面向?qū)ο笏枷胍蛴械膸状笠?。通過(guò)此次課程設(shè)計(jì)，我們對(duì)面向?qū)ο笏枷胗辛诉M(jìn)一步的了解，明白了面向?qū)ο笾蓄?lèi)、對(duì)象、封裝、繼承、多態(tài)性等特點(diǎn)，并將這些必要環(huán)節(jié)應(yīng)用于我們的程序編寫(xiě)當(dāng)中。同時(shí)我發(fā)現(xiàn)，我的分析問(wèn)題解決問(wèn)題的能力亟待提高。</p><p>　　程序設(shè)計(jì)的過(guò)程中，我通過(guò)查閱書(shū)籍，

134、網(wǎng)絡(luò)資源檢索，與朱珍珍同學(xué)積極的討論，相互交流思想，來(lái)解本次設(shè)計(jì)中所面臨的問(wèn)題，合作完成本次課程設(shè)計(jì)。在課程設(shè)計(jì)完成之際，我依舊感覺(jué)到這次課程設(shè)計(jì)的困難，感覺(jué)力不從心，但通過(guò)老師的悉心教導(dǎo)、書(shū)籍查閱、跟同學(xué)們之間的溝通與交流后，確實(shí)學(xué)會(huì)了很多東西。從頭文件、變量設(shè)計(jì)、表達(dá)式、算法、語(yǔ)句、函數(shù)到繁星程序設(shè)計(jì)與C++標(biāo)準(zhǔn)模板庫(kù)，雖然說(shuō)了解都不很深入，應(yīng)用也不熟練，考慮問(wèn)題也不夠成熟，但是有不足才會(huì)有進(jìn)步，有不懂才會(huì)去有求知的欲望，當(dāng)問(wèn)題擺在

135、我們面前的時(shí)候，我們不得不逼自己去面對(duì)，在面對(duì)之后，自我強(qiáng)迫之后，才發(fā)現(xiàn)其實(shí)并沒(méi)有自己想象的那么困難。 </p><p>　　在網(wǎng)上搜索了很多相似的語(yǔ)句，但是都不符合題意，同時(shí)也存在大量的問(wèn)題和錯(cuò)誤，為了解決這些問(wèn)題，完善程序，我花了大量的時(shí)間去搞懂每一個(gè)語(yǔ)句的意思，主函數(shù)和調(diào)用函數(shù)的編寫(xiě)，這不僅僅是在課程上、知識(shí)上對(duì)自己的強(qiáng)化和鍛煉，更是一種心理上的考驗(yàn)，充分的鍛煉了我的耐心、細(xì)心。</p>&l