数学模型经典题目及答案.docx

模型与算法四道题及“跳棋”思考题1、找零钱思想：先找零25分的，然后再依次满足10分、5、1.算法：符号说明：Sum1：消费金额。Sleft2：找零金额。X1、X2、X3、X4：需要找零25分、10分、5分和1分的数量。S1：请输入小于100分的消费金额：Sum1。S2：需要找零的金额为：Sleft2=100- Sum1。S3：计算与赋值：X1= Sleft2/25、X2= (Sleft2-25* X1)/10、X3=(Sleft2-25* X1-10*X2)/5、X4=Sleft2-25* X1-10*X2-5*X3.S4:输出X1、X2、X3、X4。2、带有时间窗的任务分配算法S未：还未被分配的任务集合。S已：已经被分配的任务集合。A：临时集合。S1:赋值k=1。S2：从S未中找出一个开始时间最小的任务i，并输出：“任务i分配到第k个机器“，并且 S已=S已 i ，S未=S未- i 。S3：判断A=iS未|sifj jS已是否为空集，若A为空集，则此机器已经满了，k=k+1， S已=，进入S4；否则从A中选出一个开始时间最小的任务i，并输出：“任务i分配到第k个机器“，并S已=S已 i ，S未=S未- i ，进入S3。S4：判断S未是否为空集，若是，程序结束；否则进入S3。#includevoid main()char a7=a,b,c,d,e,f,g;char b;char x7;int s7=0,3,4,9,7,1,6; int f8=2,7,7,11,10,5,8,0;int i,j,k,n,m,c,d,x1,x2,x3,x4;bool y1,y2;k=0;m=1;for(i=0;i7;i+) / 将任务按开始时间从小到大排序。for(j=i;jsj)c=si;si=sj;sj=c;d=fi;fi=fj;fj=d;b=ai;ai=aj;aj=b;x0=0;n=0;doprintf(安排在第%d台机器上的任务有：,m);if(m=1) printf( %c,a0);for(i=1;i7;i+)y2=1;for(j=0;j=fn) / 保证即将安排的任务开始时间不得小于前一个任务的结束时间。k=k+1;xk=i;n=xk;printf( %c,ai);if(i=6) n=8;printf(n);+m;while(kV0，则S0=S1，V0=V1； Step4：转Step1，直到算出最优解或者满意解为止； Step5：算法结束。 例子：假设n=6，i=1,2.6，W=9,7,5,13,8,6，V=4,3,2,5,3,2，C=24;利用邻域搜索算算法求解时：Step1：首先给出初始可行解S0=1,1,1,0,0,0，此时V0=9;Step2：通过邻域搜索用S1=1,1,0,0,1,0替换S0。Step3：计算V1=10，V1V0，则S0=S1，V0=V1；Step4：转Step1，直到算出最优解或者满意解为止；Step5：算法结束。4、写出网络图中寻找V1至Vn的路径的算法Step1：用Wij表示图中两点Vi与Vj之间的距离，若Vi与Vj之间没有连线，Wij=+。显然可令图中每个顶点Wii=0。Step2：给起点Vi标上固定的标号Pv1=0,并打上*号。给其它各点标上临时标号，如起点到该点有边直接相连，就标Tvj=w1j，否则Tvj=+。Step3：在所有T标号中选取最小的，将其改为P标号，并重新计算有T标号的其它各点的T标号。Step4：转step3，直至所有的顶点得到P标号为止。Step5：算法结束。5、独立砖石跳棋问题题目：图中33个顶点摆着32枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。 解：回溯法的基本思想是：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解，如果肯定不包含，跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。简而言之就是从某一可行解开始进行，能进则进，不进则退至上一步，换一可行路径再试。本题中用回溯的思想，如果两个子之间能跳，那么跳了之后记录其新的位置，因为跳的前后都是一个问题，所以我们能用递归分治，跳了一次之后棋子数减一，并把跳过的棋子和编号最后的棋子交换，这样就达到了把棋子去掉的目的，并把最优解保存。把棋盘上的位置规定成一个二维数组，如图所示： #include #include using namespace std;struct step /记录移动棋子的信息 int sx, sy; / 记录移动棋子前棋子的位置 int tx, ty; / 记录移动棋子后棋子的位置 int dir; / dir值代表移动棋子的方向struct step mystack100, last_step;char diamond77;int Left_diamond = 32;int x, y, nx, ny, ndir, top; /ndir值代表方向, 0向右, 1向下, 2向左, 3向上int flag=1; / 是否成功找到解的标志/初始化棋盘void Init_diamond() for(int i=0; i7; i+) for(int j=0; j7; j+) if(i4) & (j4); else diamondij = *; diamond33 = .;/移动棋子int Move_diamond(int y, int x, int dir) if(diamondyx != *) return 0; struct step temp; switch(dir) case 0: if(x+26 | diamondyx+1!=* | diamondyx+2!=.) return 0; diamondyx = diamondyx+1 = .; diamondyx+2 = *; temp.sx = x; temp.sy = y; temp.tx = x+2; temp.ty = y; temp.dir = dir; mystacktop+ = temp; return 1; break; case 1: if(y+26 | diamondy+1x!=* | diamondy+2x!=.) return 0; diamondyx = diamondy+1x = .; diamondy+2x = *; temp.sx = x; temp.sy = y; temp.tx = x; temp.ty = y+2; temp.dir = dir; mystacktop+ = temp; return 1; break; case 2: if(x-20 | diamondyx-1!=* | diamondyx-2!=.) return 0; diamondyx = diamondyx-1 = .; diamondyx-2 = *; temp.sx = x; temp.sy = y; temp.tx = x-2; temp.ty = y; temp.dir = dir; mystacktop+ = temp; return 1; break; case 3: if(y-20 | diamondy-1x!=* | diamondy-2x!=.) return 0; diamondyx = diamondy-1x = .; diamondy-2x = *; temp.sx = x; temp.sy = y; temp.tx = x; temp.ty = y-2; temp.dir = dir; mystacktop+ = temp; return 1; break; default: break; return 0;/主函数void main() answer.txt / 输出一个解到文本文件 ofstream answer(answer.txt); Init_diamond(); top = nx = ny = ndir = 0;while(1) / 回溯遍历，直到找到一个解 if(Left_diamond = 1 & diamond33 = *) break; for(y=ny; y7; y+,nx=0) for(x=nx; x7; x+,ndir=0) for(int dir=ndir; dir= 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.sy; ndir = last_step.dir + 1; Left_diamond+; else answerCant find any answer, I am sorry.endl; coutCant find any answer, I am sorry.endl; flag=0; break; Init_diamond(); answerThe initialization diamond states:endl; for(int i=0; i7; i+) for(int j=0; j7; j+) answerdiamondij ; answerendl; answerendlendl; for(int n=0; ntop; n+) / 输出解 answerstep n+1: Move diamond (mystackn.sy+1, mystackn.sx+1(mystackn.ty+1,mystackn.tx+1)endl; diamondmystackn.symystackn.sx = .; diamond(mystackn.sy+mystackn.ty)/2(mystackn.sx+mystackn.tx)/2 = .; diamondmystackn.tymystackn.tx =