分治算法，贪心算法，动态规划，回溯法.doc

实 验 报 告 实验一 实验名称： 分治和动态规划算法实现 实验学时：4 实验内容和目的： 希望通过本次试验，加深对分治算法原理及实现过程的理解 (1) 二分法求方程近似解：求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解，精确度为0.01。 (2) 给定一个顺序表，编写一个求出其最大值和最小值的分治算法 由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。 实验原理： 分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并到原问题的解。 在递归算法中，原问题和子问题的区别关键在于尺寸的不同，实际上解决的是同样的问题，对于分解了的子问题分别求解，也可以在此分割，如此递归下去。最后，自底向上逐步求出原问题的解。 实验器材（设备、元器件） 硬件环境：i5-2450M双核处理器，2.5GHz，NVIDIA GT630M独立显卡芯片，1GB独立显存，2GB DDR3内存，500GB硬盘空间 软件环境：Windows 7操作系统及以上，Microsoft Visual Studio 2010 实验步骤： 给定一个顺序表，编写一个求出其最大值和最小值的分治算法 /* 给定一个顺序表编写一个求出其最大值和最小值的分治算法 */ #include "stdafx.h" #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define Len 1000000 #define MIN(a,b)((a)>(b)?(b):(a)) #define MAX(a,b)((a)>(b)?(a):(b)) int a[Len] , n ; int GetMin(int l,int r){ if (l==r) return a[l] ; int mid = (l+r)>>1 ; return MIN(GetMin(l,mid) , GetMin(mid+1,r)) ; } int GetMax(int l,int r){ if (l==r) return a[l] ; int mid = (l+r)>>1 ; return MAX(GetMax(l,mid) , GetMax(mid+1,r)) ; } int main() { int i ; printf("请输入您顺序表中元素的个数："); scanf("%d",&n);printf("请依次输入您顺序表中的元素："); for (i = 0 ; i < n ; i++) scanf("%d",&a[i]); printf("MinValue = %d\n",GetMin(0,n-1)) ; printf("MaxValue = %d\n",GetMax(0,n-1)) ; system("pause"); } 二分法求方程近似解：求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解，精确度为0.01。 实验源程序如下： /* 二分法求方程近¨似解求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解精确度为0.01。 */ #include "stdafx.h" #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> double function(double x){ return x*x*x + x*x - 1 ; } int main() { double l = 0 , r = 1.0 , mid ; while (r-l>0.01){ mid = (r+l)/2 ; if (function(mid)>=0) r = mid ; else l = mid ; }