數(shù)據(jù)結(jié)構(gòu)專業(yè)課程設(shè)計(jì)方案報(bào)告在表達(dá)式中左邊的適當(dāng)位置插入運(yùn)算符或以使等式成立

課程設(shè)計(jì)匯報(bào)設(shè)計(jì)題：在表示式“=100”中左邊合適位置插入運(yùn)算符“+”或“-”，以使等式成立。比如123+45-67+8-9=100.問題分析：輸出表示式時(shí)應(yīng)作為字符串輸出，方便得到結(jié)果，所以應(yīng)該定義一個(gè)函數(shù)實(shí)現(xiàn)把int變量轉(zhuǎn)化為string型。（用string類是為了便于表示，即可直接用cout，+等。中間有8個(gè)“空”，每個(gè)“空”有“+”“-”“空格”三種選擇，故一共有3^8種可能。又需要所得到表示式滿足結(jié)果為100，即類似于有約束條件進(jìn)行深度優(yōu)先遍歷。設(shè)計(jì)所用軟件及運(yùn)行環(huán)境：VisualC++6.0Windows7操作系統(tǒng)算法設(shè)計(jì)概要：要利用遞歸。遞歸出口即滿足表示式運(yùn)算結(jié)果為100而且完成了一遍從1到9過程，滿足條件則輸出結(jié)果，而且統(tǒng)計(jì)滿足統(tǒng)計(jì)個(gè)數(shù)。不然，對(duì)三種可能情況寫對(duì)應(yīng)三個(gè)遞歸函數(shù)，一直到滿足條件為止。輸出函數(shù)要注意消除字符串?dāng)?shù)組中無用字符。程序運(yùn)行結(jié)果：運(yùn)行結(jié)果一共171個(gè)。（因屏幕有限故截取前后兩部分圖片）程序調(diào)試：最開始出來程序是這個(gè)樣子。即表示式前邊出現(xiàn)了部分無用字符。而依據(jù)我自己分析應(yīng)該是使用遞歸函數(shù)時(shí)可能往字符串?dāng)?shù)組里存入了部分無用字符。所以應(yīng)該在每次輸出表示式時(shí)候全部要?jiǎng)h掉那些無用字符。相關(guān)三個(gè)遞歸函數(shù)次序。調(diào)整三個(gè)函數(shù)次序總結(jié)果不會(huì)改變，不過表示式出現(xiàn)位置會(huì)發(fā)生改變。這個(gè)源于遞歸尤其是嵌套遞歸實(shí)現(xiàn)內(nèi)部過程是一個(gè)折線型。遞歸能夠避免大量反復(fù)運(yùn)算，不過也要注意其次序問題。幸而這道題里面不用考慮表示式次序。觀察前面25個(gè)統(tǒng)計(jì)。合并、減法、加法加法、合并、減法減法、加法、合并設(shè)計(jì)總結(jié)和體會(huì)：在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課時(shí)候一直不知道學(xué)東西應(yīng)該怎么使用，比如鏈表、樹、圖等存放結(jié)構(gòu)，不過經(jīng)過這次課程設(shè)計(jì)，我最終對(duì)它們有所體會(huì)了。收獲最深一是相關(guān)遞歸使用，二是C++程序設(shè)計(jì)相關(guān)string類使用。剛拿到題目標(biāo)時(shí)候認(rèn)為跟做24點(diǎn)很相同，分析了一下又有不一樣。除開24點(diǎn)規(guī)則跟這道題規(guī)則不一樣外，比較關(guān)鍵一點(diǎn)就是24點(diǎn)四個(gè)數(shù)位置能夠變換，而這道題里9個(gè)數(shù)則不能夠。之前看過部分24點(diǎn)相關(guān)算法，有暴力窮舉這么最直接卻也最簡單算法。所以我也自然而然地想采取這種算法。況且跟24點(diǎn)四種運(yùn)算比起來，3^8=6561種可能并不算太多。不過事實(shí)證實(shí)這并不是個(gè)好點(diǎn)子，最少對(duì)我腦子來說，光考慮設(shè)置怎樣函數(shù)將這些可能全部包含進(jìn)來就夠令我頭疼，還莫談它們還有次序。碰到瓶頸時(shí)候在網(wǎng)上查資料看到有用遞歸思想做算法，立即有種豁然開朗感覺。照這么想法做下來，程序也相當(dāng)簡單。在程序編譯運(yùn)行過程中也碰到部分問題，尤其是相關(guān)string類相關(guān)利用，比如string屬于C++標(biāo)準(zhǔn)庫，不能使用.hC頭文件，而必需使用命名空間std來申明。總來說經(jīng)過這次課程設(shè)計(jì)填補(bǔ)了之前數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)中缺點(diǎn)，讓我受益良多。附錄：源程序#include<iostream>#include<string>usingnamespacestd;inttotal=1;voidprint(stringstr){ cout<<total++<<":"; inti=0,length=str.length(); while(i<length&&str[i]!='1')i++;//去掉前面無用字符for(;i<length;i++)cout<<str[i]; cout<<"=100"<<endl;}stringatos(intn)//數(shù)字轉(zhuǎn)換成字符函數(shù){ if(n==0)return"0"; stringstr="";intN=;//1~9能組成最大數(shù)數(shù)量級(jí) while(n/N==0)N=N/10;//確定n數(shù)量級(jí) while(n>0){ str+=char('0'+n/N);//將n按位取出，轉(zhuǎn)化為字符型 n=n%N; N=N/10; } returnstr;}voidfunction(intcur,intpre,stringstr,intresult){ if(result==100&&cur>10)//搜索到最終一個(gè)數(shù)9 print(str);//輸出符合條件表示式 elseif(cur>10)return; else{ function(cur+1,pre*10+cur,str,result);//和前一個(gè)數(shù)合并 function(cur+1,cur,str+"+"+atos(pre),result+pre);//和前一個(gè)數(shù)做加法,str+"+"+atos(pre)表示表示式。 funct