第一篇：《计算机算法》实验报告范文(例文)
1.实验名称 本次实验的名称。
2.问题描述 对本次实验要解决的问题的描述。
例子：处理汉诺塔问题时，描述什么是汉诺塔问题。
3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21 页图 2-6 下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种 L 型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图 2-6 的 b），则三个小棋盘都各有 1 个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。
4.算法设计与分析 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。
例子：快速排序 伪算法描述 QuickSort(int a[], int p, int r){ 如果待排序数组 a[]中只有一个元素则直接返回； 如果待排序数组 a[]中不止一个元素，则进行如下处理 {
对数组 a[p:r]进行 Partition 划分，使得 a[p:r]以 a[p]为标准，划分为三个部分，即：
左半部分 a[p:q-1]；划分基准 a[q]=a[p]；右半部分 a[q+1:r]；
对左半部分快速排序 QuickSort(a, p, q-1);
对右半部分快速排序 QuickSort(a, q+1, r)； } }
例子：0-1 背包问题 递归关系或者递归方程。
给出 P72 页“2.递归关系”中的递归表达式，并给出文字说明。
注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。
5.程序实现 依据第 4 部分，给出 C 语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。
程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。
例子：快速排序的 partition 函数 int Partition(Type a[], int p, int r){
int i=p, j= r+1;
int x = a[p];
//x=a[p]是对数组 a 进行划分的标准；
/* 以下循环将数组 a[p:r]以 a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组 a[p:r]的中间位置 q，有 a[q]=a[p]；q 左边所有的* 元素均小于 a[p]，即 a[p:q-1]中的任意元素都小于 a[p]；q 右边
* 所有的元素均大于 a[p]，即 a[q+1:r]中的元素都大于 a[p]。
* /
while(true){ /* i 用来从数组 a[p:r]的左边向右边扫描，如果 a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的 a[++i]（即 a[++i]>=i）
* 出现，或者整个数组 a[p:r]扫描完毕（即 i */ while(a[++i] …… 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 1.实验名称 本次实验的名称。 2.问题描述 对本次实验要解决的问题的描述。 例子：处理汉诺塔问题时，描述什么是汉诺塔问题。 3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21页图2-6下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图2-6的b），则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。 4.算法设计与分析 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。例子：快速排序 伪算法描述 QuickSort(int a[], int p, int r){ 如果待排序数组a[]中只有一个元素则直接返回； 如果待排序数组a[]中不止一个元素，则进行如下处理 { 对数组a[p:r]进行Partition划分，使得a[p:r]以a[p]为标准，划分为三个部分，即： 左半部分a[p:q-1]；划分基准a[q]=a[p]；右半部分a[q+1:r]； 对左半部分快速排序QuickSort(a, p, q-1); 对右半部分快速排序QuickSort(a, q+1, r)； } } 例子：0-1背包问题 递归关系或者递归方程。 给出P72页“2.递归关系”中的递归表达式，并给出文字说明。注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。 5.程序实现 依据第4部分，给出C语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。 程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。 例子：快速排序的partition函数 int Partition(Type a[], int p, int r){ int i=p, j= r+1; int x = a[p];//x=a[p]是对数组a进行划分的标准； /* 以下循环将数组a[p:r]以a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组a[p:r]的中间位置q，有a[q]=a[p]；q左边所有的* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p]；q右边 * 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。 * / while(true){ /* i用来从数组a[p:r]的左边向右边扫描，如果a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的a[++i]（即a[++i]>=i）* 出现，或者整个数组a[p:r]扫描完毕（即i while(a[++i] „„ 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 《算法设计与分析》 实验报告 班级 姓名 学号 ****年**月**日 目录 实验一 二分查找程序实现…………………………………………………………………03页 实验二 棋盘覆盖问题（分治法）.…………………………………………………………08页 实验三 0-1背包问题的动态规划算法设计……………………………………………….11页 实验四 背包问题的贪心算法………………………………………………………………14页 实验五 最小重量机器设计问题（回溯法）………………………………………………17页 实验六 最小重量机器设计问题（分支限界法）…………………………………………20页 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验一：二分查找程序实现 一、实验时间：2013年10月8日，星期二，第一、二节地点：J13#328 二、实验目的及要求 目的： 建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。要求： 1、用c/c++语言实现二分搜索算法。 2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。 三、实验环境 平台：Win7 32位操作系统 开发工具：Codeblocks10.05 四、实验内容 对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。 五、算法描述及实验步骤 算法描述： 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x 1、首先设定问题规模n； 2、随即产生递增数列； 3、在n个有序数中随机取一个作为待查找量，搜索之； 4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次； 5、改变问题规模n重复上述步骤2~4，n取100、200……1000； 6、依实验数据作图，并与理论图作比较； 7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn)+ 1/2 // Int()函数为向下取整 即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。 实验步骤： 1.初始化生成递增随机数列： for(int j=100;j <=1000;j+=100){ array[0]=10+rand()%15; for(int i=1;i array[i]=array[i-1]+1+rand()%3+rand()%10; } } 2.定义二分查找算法： int BinarySearch(const int b[], int searchKey, int low, int high);其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。该算法实现过程为： 将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止；如果searchKey 3.实现主函数并完成所有代码。4.算法复杂性分析： 容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。 六、调试过程及实验结果 输出结果为： Every array repeat search times: 10 Number of Elements 理论平均查找次数 实际平均查找次数 6.5 6.1 200 7.5 7.3 300 8.5 7.4 400 8.5 7.4 500 8.5 7.5 600 9.5 8.2 700 9.5 8.8 800 9.5 8.7 900 9.5 8.8 1000 9.5 9.4 七、总结 二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验二：分治法解决棋盘问题 一、实验时间：2013年10月22日，星期二，第一、二节地点：J13#328 二、实验目的及要求 1、用c/c++语言实现分治法解决棋盘问题算法。 2、实现棋盘化以及棋盘覆盖 三、实验环境 Windows 2007 操作系统 以及code blocks软件 四、实验内容 在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。 五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是： 左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。 六、调试过程及实验结果 七、总结 由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在渐近意义下最优的算法。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验三：0-1背包问题的动态规划算法设计 一、实验目的及要求 1.了解并掌握动态规划算法的设计思想。 2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。 二、实验环境 使用C++语言； 在windows环境下使用CodeBlocks调试并运行。 三、实验内容 1.了解并掌握动态规划的设计思想。 2.利用动态规划算法的思想解决0-1背包问题。 四、算法描述及实验步骤 每种物品一件，可以选择放1或不放0。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 五、调试过程及实验结果 六、总结 0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验四：背包问题的贪心算法 一、实验目的： 运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。 二、实验要求 1.用c++语言实现背包问题的贪心算法。 2.掌握贪心思想的应用。 三、实验原理 在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策（在一定的标准下），决策一旦做出就不可更改。 四、实验过程(步骤)1.定义背包结构体： struct stone { int name;int weight;//物品的剩余重量 int weight_t;//物品的重量 float benefit;//物品的价值 //float b;};2.定义函数void sort(stone *data,int num)//计算物品的单位重量的价值，并进行排序 3.定义主函数并完成贪心选择。4.分析算法复杂性分析： 该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（n*logn）。 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 五、运行结果 六、实验分析与讨论 贪心法的基本思路： ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题： 1.不能保证求得的最后解是最佳的； 2.不能用来求最大或最小解问题； 3.只能求满足某些约束条件的可行解的范围。实现该算法的过程： 1.Begin 从问题的某一初始解出发； 2．while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素； 4.由所有解元素组合成问题的一个可行解 七、实验心得 贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验五：最小重量机器设计问题（回溯法） 一、实验目的 建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 二、实验要求 1、用c++语言实现最小重量机器设计的回溯算法。 2、分析算法的计算复杂性 三、实验原理 首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动（回溯）至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。 四、实验过程(步骤)由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。 数据说明： N：零件数量 m：不同的零件商 W[][]:是从供应商j处购得的部件i的重量 c[][]：相应的价值 算法设计： a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。 b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 ① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。 ② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。 ③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行； ④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。 c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。 五、运行结果 六、实验心得 通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验六：最小重量机器设计问题（分支限界法） 一、实验时间：2013年11月12日，星期二，第一、二节地点：J13#328 二、实验目的及要求 1、了解分支限界法的基本思想。 2、运用分支限界法解决最小重量机器设计问题。 三、实验环境 平台：win7操作系统 开发工具：codeblocks10.05 四、实验内容 最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计 五、算法描述及实验步骤 算法描述： 解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer 实验步骤： 1.定义一个优先队列LinkQueue： void InitQueue(LinkQueue &Q);//创建一个队列-----首尾结点 void DestroyQueue(LinkQueue &Q);//销毁一个队列 void ClearQueue(LinkQueue &Q);//清空队列 int QueueEmpty(LinkQueue &Q);//判断队列是否为空，空则返回TURE，否则返回FLASE int QueueLength(LinkQueue &Q);//求队列的长度 void EnQueue(LinkQueue &Q,QElemType &e);//拆入e为新的队尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回队列的对头元素 bool IsEmpty(LinkQueue &Q)//判断队列是否为空 2.定义类MinWeight，实现函数有： void Add(int wt,int ct,int i);//往队列插入节点 int FindBest();//实现最小重量机器的查找 void setMW();//函数初始化 void printMW();//打印输出结果 3 实现主函数并完成所有代码。 六、调试过程及实验结果 七、总结 利用分支限界法解决最小重量机器问题，就是构造一个优先队列，按照规定的优先级按最大效益优先的方式查找解空间树，找出满足要求的最优解。通过利用分支限界法解决最小重量机器问题，熟练了对分支限界法的使用。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 篇一：prim算法实验报告 算法实验报告 学院：xxx 班级：xxx 学号：xxx 姓名：xxx prim 篇二：prim最小生成树算法实验报告 算法分析与设计之prim 学院：软件学院 学号：201421031059 姓名：吕吕 一、问题描述 1.prim的定义 prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。2.实验目的 选择一门编程语言，根据prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.prim算法的实现过程 基本思想：假设g＝(v，e)是连通的，te是g上最小生成树中边的集合。算法从u＝{u0}（u0∈v）、te＝{}开始。重复执行下列操作： 在所有u∈u，v∈v－u的边(u，v)∈e中找一条权值最小的边(u0,v0)并入集合te中，同时v0并入u，直到v＝u为止。 此时，te中必有n-1条边，t=(v，te)为g的最小生成树。prim算法的核心:始终保持te中的边集构成一棵生成树。2.时间复杂度 prim算法适合稠密图，其时间复杂度为o(n^2)，其时间复杂度与边得数目无关，n为顶点数，而看ruskal算法的时间复杂度为o(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class graph { private: int *verticeslist;int **edge;int numvertices;int numedges;int maxvertices;graph();~graph();bool insertvertex(const int vertex);bool insertedge(int v1,int v2,int cost);int getvertexpos(int vertex);int getvalue(int i);int getweight(int v1,int v2);int numberofvertices();1 public: } void prim();其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。 四、代码与运行结果 代码运行结果： 源码： //普雷姆算法 #include int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入结点 bool graph::insertvertex(const int vertex){ };//插入边，v1和v2为结点在数组的下标 bool graph::insertedge(int v1,int v2,int cost){ if(v1>-1&&v1 istream& operator>>(istream &in ,graph &g){ };//输出图对象 ostream& operator<<(ostream &out,graph &g){ int i,j,vertices,edges;int start,end,weight;vertices=g.numberofvertices();edges=g.numberofedges();out< in>>vertices>>edges;for(i=1;i<=vertices;i++){ } i=0;while(i 黄冈师范学院 提高型实验报告 实验课题 最小生成树的prim算法 （实验类型：□综合性 ■设计性 □应用性） 实验课程 算法程序设计 实验时间2010年12月24日 学生姓名 周 媛鑫 专业班级 计科 0801 学 号 200826140110 一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法;（2）掌握最小生成树的prim算法;（3）熟练掌握贪心算法的设计方法;二．实验条件 （1）硬件环境：实验室电脑一台（2）软件环境：wintc 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为mst的性质：假设n=(v,{e})是一个连通网，u是顶点集v的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈u，v∈v-u，则必存在一棵包含边(u.v)的最小生成树。（3）普里姆（prim）算法即是利用mst性质构造最小生成树的算法。算法思想如下： 假设n=(v,{e})和是连通网，te是n上最小生成树中边的集合。算法从u={u0}(u0∈v)，te={}开始，重复执行下述操作：在所有u∈u，v∈v-u的边(u, v)∈e中找一条代价最小的边(u0, v0)并入集合te，同时v0并入u，直到u=v为止。此时te中必有n-1条边，则t=(v,{te})为n的最小生成树。四．实验步骤 （1）数据结构的设计 ： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #defineinfinityint_max //最大值 #define max_ertex_num20 //最大顶点数 typedef enum {dg,dn,udg,udn}graphkind;//{有向图,有向网，无向网，无向图} typedef struct arc cell{ vrtype adj;// vrtype 是顶点关系的类型。对无权图用1和0表示相邻否； infotype * info;//该弧相关信息的指针 }arccell，adjmatrix [ max_vertex_num][max_vertex_num]； typedef struct { vertextype vexs [ max_vertex_num];//顶点向量adjmatrixarcs;// 邻接矩阵 intvexnum , arcnum;//图的当前顶点数和弧数 graphkindkind;// 图的种类标志 }mgraph;（2）函数设计 函数名称 函数原型 功能描述 main()int main(void)系统调用主函数 huiru()void huitu()绘制无向图 graphicver()void graphicver(graph *g)输出邻接矩阵 prim()void prim(graph *g)prim算法演示（3）实验源代码 #include 课程设计报告 课程设计名称 共享资源分配与银行家算法 系（部） 专业班级 姓 名 学 号 指导教师 年 月 日 、目 录 一、课程设计目的和意义...................................................................................3 二、方案设计及开发过程..............................................................................................3 1.课题设计背景.................................................................................................................3 2.算法描述 ............................................................................................................................3 3.数据结构 ............................................................................................................................4 4.主要函数说明.................................................................................................................4 5.算法流程图......................................................................................................................5 三、调试记录与分析 四、运行结果及说明 ..............................................................................................6 1．执行结果.........................................................................................................................6 2．结果分析.........................................................................................................................7 五、课程设计总结...................................................................................................8 、一、程设计目的和意义 计算机科学与技术专业学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，其目的在于加深催操作系统基础理论和基本知识的理解，加强学生的动手能力.银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法 二、方案设计及开发过程 1.课题设计背景 银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待 2.算法描述 1）如果Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti[j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 2）如果Requesti[j]<=Available[j],便转向步骤3，否则，表示尚无足够资源，进程Pi须等待。 3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j]; 、4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程pi等待。 3.数据结构 1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组，其中的每一个元素代表一类可利用的资源数目，其3初始值是系统中所配置的该类全部可哦那个资源的数目，其数值随该类资源的分配和回收而动态的改变。 2.最大需求矩阵MAX。这是一个M*N的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。 3.分配矩阵ALLOCATION。这也是一个M*N的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。 4.需求矩阵NEED。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类资源数。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W] 4.主要函数说明 主要的常量变量 #define W 10 //最大进程数W=10 #define R 20 //最大资源总数R=20 int AVAILABLE[R];//可利用资源向量 int MAX[W][R];//最大需求矩阵 int ALLOCATION[W][R];//分配矩阵 int NEED[W][R];//需求矩阵 int Request[R];//进程请求向量 void changdata(int k);//进程请求资源数据改变 int chksec(int s);//系统安全性的检测 主要模块 void inputdata()void showdata()void changdata(int k)void restoredata(int k)int chksec(int s)int chkmax(int s) 、5.算法流程图 三、调试记录与分析 调试通过,程序未出错 、四、运行结果及说明 1.执行结果 、2.结果分析 银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁，若发生死锁则让进程等待。 、五、课程设计总结 通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。实验中遇到点问题，通过查阅资料、询问老师顺利解决。通过这次的实践，使我的理论知识更加的牢固。 附录 程序源码: #include void changdata(int k);//进程请求资源数据改变 void restoredata(int k);//数据恢复 int chksec(int s);//系统安全性的检测 int chkmax(int s);//检测最大需求 void bank();//检测分配的资源是否合理 int main(){ int i,j;inputdata();//安全性算法 for(i=0;i 、cout<<“错误提示：经安全性检查发现，系统的初始状态不安全！！n”< { int i=0,j=0,p;cout<<“请输入总进程数:”< 、for(j=0;j do{ cin>>ALLOCATION[i][j]; if(ALLOCATION[i][j]>MAX[i][j]) cout< }while(ALLOCATION[i][j]>MAX[i][j]);} } cout< NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];for(j=0;j AVAILABLE[j]=0;} } } void showdata()//银行家算法 { int i,j;cout<<“各种资源的总数量，即向量all_resource为:”< cout< 、cout< cout< void changdata(int k)//进程请求资源数据改变 { int j;for(j=0;j AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];} } void restoredata(int k)//数据恢复 { int j;for(j=0;j ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j];} } int chksec(int s)//系统安全性的检测 { int WORK,FINISH[W];int i,j,k=0;for(i=0;i FINISH[i]=FALSE;for(j=0;j WORK=AVAILABLE[j]; 、i=s;do { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; }else { i++; } }while(i if(FINISH[i]==FALSE) { return 1; } } return 0;} int chkmax(int s)//检测最大需求 { int j,flag=0;for(j=0;j if(MAX[s][j]==ALLOCATION[s][j]) { flag=1; AVAILABLE[j]=AVAILABLE[j]+MAX[s][j]; MAX[s][j]=0; } } return flag;} void bank(){ int i=0,j=0;char flag='Y';while(flag=='Y'||flag=='y'){ i=-1;while(i<0||i>=M){ cout<<“请输入需申请资源的进程号（从P0到P”< cin>>i;if(i<0||i>=M) 、cout<<“输入的进程号不存在，重新输入!”< cin>>Request[j];if(Request[j]>NEED[i][j]) { cout<<“进程P”< cout<<“申请不合理，出错!请重新选择!”< flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) { cout<<“进程P”< cout<<“申请不合理，出错!请重新选择!”< flag='N'; break; } } } if(flag=='Y'||flag=='y'){ changdata(i); if(chksec(i)) { cout< cout<<“该分配会导致系统不安全！!本次资源申请不成功，不予分配！!”< cout< restoredata(i); } else { cout< cout<<“经安全性检查，系统安全，本次分配成功，且资源分配状况如下所示：”< cout< showdata(); if(chkmax(i)) {cout<<“在资源分配成功之后，由于该进程所需的某些资源的最大需求量已经满足，”< cout<<“因此在进程结束后系统将回收这些资源！”< showdata(); 、} } } cout<第二篇：《计算机算法》实验报告
第三篇：算法实验报告
第四篇：PRIM算法实验报告
第五篇：银行家算法_实验报告
点击咨询 