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

1、模型與算法四道題及“跳棋思考題1、找零錢思想：先找零25分的,然后再依次滿足10分、5、1.算法：符號說明：Sumi：消費(fèi)金額.Sleft2：找零金額.XI、X2、X3X4:需要找零25分、10分、5分和1分的數(shù)量.S1:請輸入小于100分的消費(fèi)金額：Sum10S2:需要找零白金額為：Sleft2=100-Sum1X3=(Sleft2-25*S3:計(jì)算與賦值：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>yoi

2、iimim(>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、帶有時間窗的任務(wù)分配算法?:還未被分配的任務(wù)集合.?:已經(jīng)被

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

4、#39;,'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+)/將任務(wù)按開始時間從小到大排序.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臺機(jī)器上的任務(wù)有：",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;/保證即將安排的任務(wù)是未被分配的.y2=y1;)if(y1)if(si>=fn)/保證即將安排的任務(wù)開始時間不得小于前一個任務(wù)的結(jié)束時間.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中物品和一個背包,假設(shè)物品i的重量wi,其價值為vi,背包容量為Co物品i有兩種狀態(tài),裝入背包或者不裝入背包.X=0時表示物品i不裝入背包,X=1時表示物品裝入背包,那么決策物品是否裝入背包的問題轉(zhuǎn)化為一個二叉樹搜索問題,根據(jù)約束條件進(jìn)行剪枝,然后結(jié)合回溯法求出解.所給物品根據(jù)單位價值量進(jìn)行非增排序,解空間表示為集合S=X,X2,./兇以./,i=1,2；n,如何選擇物品裝入背包,使得包內(nèi)物品的總價值最大的算法如下：Step1:從根節(jié)點(diǎn)開始,計(jì)算此時背包的剩余容量和背包中物品的價值；此時根節(jié)點(diǎn)為活結(jié)點(diǎn),也是當(dāng)前的擴(kuò)展結(jié)點(diǎn).Step2：以深度優(yōu)先方式搜索,從當(dāng)前的一個擴(kuò)展結(jié)

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

8、；Step3:計(jì)算新解Si時,背包中物品的價值Vi,假設(shè)Vi>Vo,那么S0=S,Vo=Vi;Step4：轉(zhuǎn)Stepi,直到算出最優(yōu)解或者滿意解為止；Step5:算法結(jié)束.例子：假設(shè)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:計(jì)算Vi=10,Vi>Vo,那么So=S,Vo=Vi;Step4：車專Stepi,直到算出最優(yōu)解或者滿意解為止；Step5:算法結(jié)束.4、寫出網(wǎng)絡(luò)

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

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

11、歸分治,跳了一次之后棋子數(shù)減一,并把跳過的棋子和編號最后的棋子交換,這樣就到達(dá)了把棋子去掉的目的,并把最優(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,

12、nx,ny,ndir,top;/ndir值代表方向,0向右,1向下,2向左,3向上intflag=1;/是否成功找到解的標(biāo)志/初始化棋盤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;stru

13、ctsteptemp;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、9;.')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

15、=x;temp.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;de

16、fault: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,

17、x,dir)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_

18、step.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<<,"