數(shù)學模型經(jīng)典題目及答案

1、模型與算法四道題及“跳棋”思考題1、找零錢思想：先找零25分的，然后再依次滿足10分、5、1.算法：符號說明：Sumi：消費金額。Sleft2：找零金額。XI、X2、X3X4:需要找零25分、10分、5分和1分的數(shù)量。S1:請輸入小于100分的消費金額：Sum10S2:需要找零白金額為：Sleft2=100-Sum1X3=(Sleft2-25*S3:計算與賦值：X1=Sleft2/25、X2=(Sleft2-25*X1)/10、X1-10*X2)/5、X4=Sleft2-25*X1-10*X2-5*X3.S4輸出X1、X2、X3、X4的CpplcppVinQliiidCnath.h>yo

2、iiimim(>41nitsall9dati；Int匕1葉42人工心；pHntK糙小人小于1吩的滿獸金郵FThEMF("ti"v&5al)；£i*ft«3-|D«-Eail;叫叫-a響m：0/25);slelt1-5left|0J-2S*kL(sJ；x1-i»b5<5left11/18);l1-1ft»x1;xl3-51e(t2JPinE'需要找零招小1叨J分一工史越重分別徹,由prints，'覲個，1；巧、5”尸【叫戶”h?戶打心2、帶有時間窗的任務分配算法?:還未被分配的任務集合。?:

3、已經(jīng)被分配的任務集合。A:臨時集合。S1賦值k=1oS2：從?余中找出一個開始時間最小的任務i,并輸出：“任務i分配到第k個機器“，并且？?=?比i,?余=?-i。S3:判斷A=i?|?i?>?j?a是否為空集，若A為空集，則此機器已經(jīng)滿了，k=k+1,?=?，進入S4;否則從A中選出一個開始時間最小的任務i,并輸出：“任務i分配到第k個機器“，并？Z=?aUi,?集=?-i,進入S3S4:乎U斷？條是否為空集，若是，程序結束；否則進入S3D:O43rlDrbugCpp2#include<stdio.h>voidmain()(chara7='a','b

4、','c','d','e','f,'g'charb;charx7;ints7=0,3,4,9,7,1,6;intf8=2,7,7,11,10,5,8,0;inti,j,k,n,m,c,d,x1,x2,x3,x4;booly1,y2;k=0;m=1;for(i=0;i<7;i+)/將任務按開始時間從小到大排序。for(j=i;j<7;j+)if(si>sj)c=si;si=sj;sj=c;d=fi;fi=fj;fj=d;b=ai;ai=aj;aj=b;)x0=0;n=0;doprintf("

5、;安排在第%d臺機器上的任務有：",m);if(m=1)printf("%c",a0);for(i=1;i<7;i+)y2=1;for(j=0;j<k;j+)y1=(i!=xj)&&y2;/保證即將安排的任務是未被分配的。y2=y1;)if(y1)if(si>=fn)/保證即將安排的任務開始時間不得小于前一個任務的結束時間。k=k+1;xk=i;n=xk;printf("%c",ai);)if(i=6)n=8;)printf("n");+m;while(k<6);)3、01背包問題啟發(fā)

6、式算法(回溯法)：給定n中物品和一個背包，假設物品i的重量wi,其價值為vi,背包容量為Co物品i有兩種狀態(tài)，裝入背包或者不裝入背包。X=0時表示物品i不裝入背包，X=1時表示物品裝入背包，則決策物品是否裝入背包的問題轉化為一個二叉樹搜索問題，根據(jù)約束條件進行剪枝，然后結合回溯法求出解。所給物品按照單位價值量進行非增排序，解空間表示為集合S=X,X2,./兇以。/,i=1,2；n,如何選擇物品裝入背包，使得包內物品的總價值最大的算法如下：Step1:從根節(jié)點開始，計算此時背包的剩余容量和背包中物品的價值；此時根節(jié)點為活結點，也是當前的擴展結點。Step2：以深度優(yōu)先方式搜索，從當前的一個擴展結

7、點向縱深方向移至一個新的結點，此時這根結點成為活結點并成為當前擴展結點。計算此時背包的剩余容量，并計算背包中物品的價值；Step3:根據(jù)約束條件判斷當前的擴展結點是否可以再向縱深方向移動；Step4：如果滿足約束條件則向縱深方向移至新節(jié)點,否則回溯至最近的活結點,使其成為當前擴展結點；Step5:"專step2,直到找出最優(yōu)解或者解空間中沒有活結點；Step6:算法結束。0-1背包問題的鄰域搜索算法：Stepl：根據(jù)約束條件給出一個可行解Sd,并計算初始可行解時裝入背包中物品的價值Vo；Step2：利用貪心算法構造領域函數(shù)，將單位價值量大的物品替換初始可行解中的單位價值量小的物品；S

8、tep3:計算新解Si時，背包中物品的價值Vi,若Vi>Vo,則S0=S,Vo=Vi;Step4：轉Stepi,直到算出最優(yōu)解或者滿意解為止；Step5:算法結束。例子：假設n=6,i=1,2.r6W=9,7,5,13,8,6,V=4,3,2,5,3,21,C=24;利用鄰域搜索算算法求解時：Stepi:首先給出初始可行解?=1,1,1,0,0,0,此時？=9;Step2：通過鄰域搜索用？=1,1,0,0,1,0替換SdoStep3:計算Vi=10,Vi>Vo,則So=S,Vo=Vi;Step4：車專Stepi,直到算出最優(yōu)解或者滿意解為止；Step5:算法結束。4、寫出網(wǎng)絡圖中尋

9、找V1至Vn的路徑的算法Stepi:用Wij表示圖中兩點Vi與Vj之間的距離，若V與M之間沒有連線，？%?+°°顯然可令圖中每個頂點？?？00Step2:給起點Vi標上固定的標號P(?)=0,并打上*號。給其它各點標上臨時標號，如起點到該點有邊直接相連，就標T(?)=?否則T(?=+oo0Step3:在所有T標號中選取最小的，將其改為P標號，并重新計算有T標號的其它各點的T標號。Step4："Sstep3,直至所有的頂點得到P標號為止。Step5:算法結束。5、獨立磚石跳棋問題題目：圖中33個頂點擺著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規(guī)則是任一棋子可以

10、沿水平或垂直方向跳過與其相鄰的棋子，進入空著的頂點并吃掉被跳過的棋子。試設計一個算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。解：回溯法的基本思想是：在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹，算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解，如果肯定不包含，跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。簡而言之就是從某一可行解開始進行，能進則進，不進則退至上一步，換一可行路徑再試。本題中用回溯的思想，如果兩個子之間能跳，那么跳了之后記錄其新的位置，因為跳的前后都是一個問題，所以我們能用遞歸分治，跳了

11、一次之后棋子數(shù)減一，并把跳過的棋子和編號最后的棋子交換，這樣就達到了把棋子去掉的目的，并把最優(yōu)解保存。把棋盤上的位置規(guī)定成一個二維數(shù)組，如圖所示：#include<iostream>#include<fstream>usingnamespacestd;structstep/記錄移動棋子的信息(intsx,sy;/記錄移動棋子前棋子的位置inttx,ty;/記錄移動棋子后棋子的位置intdir;/dir值代表移動棋子的方向structstepmystack100,last_step;chardiamond77;intLeft_diamond=32;intx,y,nx,ny

12、,ndir,top;/ndir值代表方向，0向右，1向下，2向左，3向上intflag=1;/是否成功找到解的標志/初始化棋盤voidInit_diamond()(for(inti=0;i<7;i+)(for(intj=0;j<7;j+)(if(i<2|i>4)&&(j<2|j>4);else(diamondij='*')diamond33='.')/移動棋子intMove_diamond(inty,intx,intdir)(if(diamondyx!='*')return0;structste

13、ptemp;switch(dir)case0:if(x+2>6|diamondyx+1!='*'|diamondyx+2!='.')return0;diamondyx=diamondyx+1='.'diamondyx+2='*'temp.sx=x;temp.sy=y;temp.tx=x+2;temp.ty=y;temp.dir=dir;mystacktop+=temp;return1;break;case 1:if(y+2>6|diamondy+1x!='*'|diamondy+2x!='.&#

14、39;)return0;diamondyx=diamondy+1x='.'diamondy+2x='*'temp.sx=x;temp.sy=y;temp.tx=x;temp.ty=y+2;temp.dir=dir;mystacktop+=temp;return1;break;case 2:(if(x-2<0|diamondyx-1!='*'|diamondyx-2!='.')return0;diamondyx=diamondyx-1='.'diamondyx-2='*'temp.sx=x;te

15、mp.sy=y;temp.tx=x-2;temp.ty=y;temp.dir=dir;mystacktop+=temp;return1;break;case 3:if(y-2<0|diamondy-1x!='*'|diamondy-2x!='.')return0;diamondyx=diamondy-1x='.'diamondy-2x='*'temp.sx=x;temp.sy=y;temp.tx=x;temp.ty=y-2;temp.dir=dir;mystacktop+=temp;return1;break;default

16、:break;return0;/主函數(shù)voidmain()answer.txt/輸出一個解到文本文件ofstreamanswer("answer.txt");Init_diamond();top=nx=ny=ndir=0;while(1)/回溯遍歷，直到找到一個解if(Left_diamond=1&&diamond33='*')break;for(y=ny;y<7;y+,nx=0)for(x=nx;x<7;x+,ndir=0)for(intdir=ndir;dir<4;dir+)if(Move_diamond(y,x,dir

17、)Left_diamond-;nx=ny=ndir=0;gotonextstep;nextstep:if(y=7)top-;if(top>=0)/回到上一步，并改變方向last_step=mystacktop;diamond(last_step.sy+last_step.ty)/2(last_step.sx+last_step.tx)/2='*'diamondlast_step.sylast_step.sx='*'diamondlast_step.tylast_step.tx='.'nx=last_step.sx;ny=last_step.

18、sy;ndir=last_step.dir+1;Left_diamond+;elseanswer<<"Can'tfindanyanswer,Iamsorry."<<endl;cout<<"Can'tfindanyanswer,Iamsorry."<<endl;flag=0;break;)Init_diamond();answer<<"Theinitializationdiamondstates:"<<endl;for(inti=0;i<7;i+)for(intj=0;j<7;j+)answer<<diamondij<<''answer<<endl;answer<<endl<<endl;for(intn=0;n<top;n+)/輸出解answer<<"step"<<n+1<<":Movediamond("<<mystackn.sy+1<<”,"