




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
《算法设计与分析》实验报告回溯法姓名:XXX专业班级:XXX学号:XXX指导教师:XXX完成日期:XXX一、试验名称:回溯法写出源程序,并编译运行详细记录程序调试及运行结果二、实验目的掌握回溯算法思想掌握回溯递归原理了解回溯法典型问题三、实验内容编写一个简单的程序,解决8皇后问题批处理作业调度数字全排列问题四、算法思想分析编写一个简单的程序,解决8皇后问题批处理作业调度[问题描述]给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理,然后再由机器2处理。作业Ji需要机器i的处理时间为tji,i=1,2,…,n;j=1,2。对于一个确定的作业调度,设Fji是作业i在机器i上完成处理的时间。则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业,制定一个最佳的作业调度方案,使其完成时间和达到最小。要求输入:1、作业数2、每个作业完成时间表:作业完成时间机器1机器2作业121作业231作业323要求输出:1、最佳完成时间2、最佳调度方案提示提示:算法复杂度为O(n!),建议在测试的时候n值不要太大,可以考虑不要超过12。(3)数字全排列问题:任意给出从1到N的N个连续的自然数,求出这N个自然数的各种全排列。如N=3时,共有以下6种排列方式:123,132,213,231,312,321。注意:数字不能重复,N由键盘输入(N<=9)。五、算法源代码及用户程序编写一个简单的程序,解决8皇后问题N皇后问题代码1:#include<stdio.h>#defineNUM8//定义数组大小inta[NUM+1];intmain(){ inta[100];intnumber;inti;intk;intflag;intnotfinish=1;intcount=0;i=1;//正在处理的元素下标,表示前i-1个元素已符合要求,正在处理第i个元素a[1]=1;//为数组的第一个元素赋初值printf("Result:\n");while(notfinish)//处理尚未结束{while(notfinish&&i<=NUM)//处理尚未结束且还没处理到第NUM个元素{for(flag=1,k=1;flag&&k<i;k++)//判断是否有多个皇后在同一行{if(a[k]==a[i])flag=0;}for(k=1;flag&&k<i;k++)//判断是否有多个皇后在同一对角线{if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))flag=0;}if(!flag)//若存在矛盾不满足要求,需要重新设置第i个元素{if(a[i]==a[i-1])//若a[i]的值已经经过一圈追上a[i-1]的值{i--;//退回一步,重新试探处理前的一个元素if(i>1&&a[i]==NUM){a[i]=1;//当a[i]的值为NUM时将a[i]的值置1}elseif(i==1&&a[i]==NUM){notfinish=0;//当第一位的值达到NUM时结束}else{a[i]++;//将a[i]的值取下一个值}}elseif(a[i]==NUM){a[i]=1;}else{a[i]++;//将a[i]的值取下一个值}}elseif(++i<=NUM)//第i位已经满足要求则处理第i+1位{if(a[i-1]==NUM)//若前一个元素的值为NUM则a[i]=1{a[i]=1;}else{a[i]=a[i-1]+1;//否则元素的值为前一个元素的下一个值}}}if(notfinish){++count;printf((count-1)%3?"[%2d]:":"\n[%2d]:",count);for(k=1;k<=NUM;k++)//输出结果{printf("%d",a[k]);}if(a[NUM-1]<NUM)//修改倒数第二位的值{a[NUM-1]++;}else{a[NUM-1]=1;}i=NUM-1;//开始寻找下一个满足条件的解}}//whileprintf("\n");return0;}批处理作业调度importjava.util.*;publicclassFlowShop{staticintn;//作业数staticintf1;//机器1完成处理时间staticintf;//完成时间和staticintbestf;//当前最优值staticint[][]m;//各作业所需要的处理时间staticint[]x;//当前作业调度staticint[]bestx;//当前最优作业调度staticint[]f2;//机器2完成处理时间publicstaticvoidtrackback(inti){if(i==n){for(intj=0;j<n;j++){bestx[j]=x[j];}bestf=f;}else{for(intj=i;j<n;j++){f1+=m[x[j]][0];if(i>0){f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][1];}else{f2[i]=f1+m[x[j]][1];}f+=f2[i];if(f<bestf){swap(x,i,j);trackback(i+1);swap(x,i,j);}f1-=m[x[j]][0];f-=f2[i];}}}privatestaticvoidswap(int[]x,inti,intj){inttemp=x[i];x[i]=x[j];x[j]=temp;}privatestaticvoidtest(){n=3;int[][]testm={{2,1},{3,1},{2,3}};m=testm;int[]testx={0,1,2};x=testx;bestx=newint[n];f2=newint[n];f1=0;f=0;bestf=Integer.MAX_VALUE;trackback(0);System.out.println(Arrays.toString(bestx));System.out.println(bestf);}publicstaticvoidmain(String[]args){test();System.out.println("HelloWorld!");}}数字全排列问题#include"stdio.h"#include"conio.h"intnum,cont=0;main(){inti,n,a[30];printf("enterN:");scanf("%d",&num);for(i=1;i<=num;i++)a[i]=i;perm(a,1);printf("\n%d",cont);getch();}intperm(intb[],inti){intk,j,temp;
if(i==num){for(k=1;k<=num;k++)printf("%d",b[k]);printf("\t");cont++;}
elsefor(j=i
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 水资源节约的宣传教育计划
- 2025年人造岗石树脂合作协议书
- 2025年冷光源:EL冷光片合作协议书
- 2025年涤纶短纤项目合作计划书
- 2025年铝合金精密模锻件项目合作计划书
- 客户关系层次化维护策略
- 数学王国里的奇妙旅程读后感
- 自动化科技设备公司项目投资合作协议
- Pinoxaden-Standard-生命科学试剂-MCE
- Mucic-acid-Standard-生命科学试剂-MCE
- 山东省春季高考技能考试-汽车专业必刷必练题库(600题)
- 膝关节前十字韧带扭伤查房
- 2024建设工程人工材料设备机械数据分类和编码规范
- 仓库高位货架管理制度培训课件
- 工会经费列支范围及工会经费支出范围
- 道教文化的映射:《三国演义》中的道教元素分析
- 成人高考课件
- 高中英语高考读后续写巧用动作链专项练习(附参考答案和解析)
- 哲学与人生全套课件146P
- 敬老院设备采购投标方案(技术方案)
- 充电桩采购安装售后服务方案
评论
0/150
提交评论