计算机组织与体系结构——实验报告
{
thissum+=a[j]; if(thissum>sum) {
sum=thissum; besti=i; bestj=j; } } }
return sum; } int main() {
int *a=new int[50]; int x,n,besti,bestj;
cout<<\请输入字符串的个数：\cin>>n;
cout<<\请输入字符串中的每个数字：\for(int i=0;i cin>>a[i]; } x=MaxSum(n,a,besti,bestj); cout<<\最大子段和为：\起始位置：\至\结果为： \ return 0; } 四、运行结果 实验小结 第一个求公共子序列感觉和递归查询差不多，然后再查询第二列进行对比！最大子段和感觉就像求整列的和！ 实验三 贪心算法（2学时） 一：多机调度问题 一、实验目的与要求 1、熟悉多机调度问题的算法； 8 计算机组织与体系结构——实验报告 2、初步掌握贪心算法； 二、实验题 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 三、实验程序 #include typedef struct Job { int ID;//作业号 int time;//作业所花费的时间 }Job; Job J[10]; typedef struct JobNode //作业链表的节点 { int ID; int time; JobNode *next; }JobNode,*pJobNode; typedef struct Header //链表的表头,不同的机器？？ { int s; //表示其最大的容量 pJobNode next; }Header,*pHeader; // int l=1; int main() { //Job J[10]; Header M[10]; int m,n; //机器的个数 cout<<\请输入数据作业的个数与机器的个数\ cin>>n>>m; cout<<\请输入所有的任务的相关数据\ for(int i=1;i<=m;i++) M[i].s=0; //表示其最大容量 for( l=1;l<=n;l++)//所有的任务作业 cin>>J[l].ID>>J[l].time; int SelectMin(Header* M,int m);//SelectMin(M,m); for(l=1;l<=n;l++) cout<<\第\个任务在第\ <<\台机器上完成\ return 0; } 9 计算机组织与体系结构——实验报告 int SelectMin(Header* M,int m) //有几台机器，就创建几个链表 { int k=1; for(int i=1;i<=m;i++) { if(M[i].s<=M[1].s) //最小的加入,s标识时间的和值 k=i; } M[k].s+=J[l].time; return k; //k是标识第几台机器加入作业 } 五、实验结果 二： 用贪心算法求解最小生成树 一、实验要求与目的 1、 熟悉贪心算法的基本原理与适用范围。 2、 使用贪心算法编程，求解最小生成树问题。 二、实验内容 1、 任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。 编程实现，并给出测试实例 三、实验程序 #include int n=6; cout<<\所给图的最小生成树一次选定的边是表示为：\int c[7][7]= { {inf,inf,inf,inf,inf,inf,inf}, {inf,inf,6,1,5,inf,inf}, {inf,inf,inf,5,inf,3,inf}, {inf,1 , 5,inf,5,6,4}, {inf,5,inf,5,inf,inf,2}, {inf,inf,3,6,inf,inf,6}, 10 计算机组织与体系结构——实验报告 {inf,inf,inf,4,2,6,inf} }; //c[1][2]=6;c[1][4]=5;c[1][3]=1;c[2][3]=5;c[3][4]=5;c[2][5]=3;c[2][6]=2; //c[3][5]=6;c[3][6]=4;c[5][6]=6; c[2][1]=6;c[4][1]=5;c[3][1]=1;c[3][2]=5;c[4][3]=5;c[5][2]=3;c[6][2]=2; //c[5][3]=6;c[6][3]=4;c[6][5]=6; void prim(int n,int c[7][7]); prim(n,c); return 0; } void prim(int n,int c[7][7]) { int lowcost[7]; int closet[7]; bool s[10]; s[1]=true; for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closet[i]=1; s[i]=false; } int j=1; for(i=1;i int j=1; for(int k=2;k<=n;k++) if((lowcost[k] } cout< for(k=2;k<=n;k++) if((c[j][k] } } 11 计算机组织与体系结构——实验报告 } 四、实验结果 五、实验小结 贪心算法上课老师讲的时候也能听懂，讲的例子也能明白，但是在实际调度时遇到了不小的麻烦！最后在老师和同学的帮助下完成了！尽管自己没有做出来，但是对贪心算法的实际操作有了更一步的把握！ 实验四 回溯算法和分支限界法（2学时） 一：符号三角形问题 一、实验目的与要求 1、掌握符号三角形问题的算法； 2、初步掌握回溯算法； 二、实验题图 下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相 三、实验程序 #include using namespace std; typedef unsigned char uchar; int sum; uchar** p; //符号存储空间；//表示满足要求的三角形个数 char ch[2]={'+','-'}; int n; //第一行符号总数 int half; int count; //用来计算‘-’的个数 void BackTrace(int t) { if (t>n) { sum++; cout<<\第\个三角形：\for (int i=1;i<=n;i++) { for (int j=1;j for (j=1;j<=n-i+1;j++) cout< 12
计算机算法与设计分析实验报告
