下载文档原格式
算法分析与设计课程教案课程编号：50c24037-01总学时：51 周学时：4适用年级专业（学科类）：2007级计科专业开课时间：2010－2011 学年第1 学期使用教材：王晓东编著计算机算法设计与分析第3版章节第1章1.1~ 1.2 第2 章2.1 课时 2教学目的理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；理解递归的概念。
教学重点及突出方法重点：程序与算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。
通过讲解、举例方法。
教学难点及突破方法难点：算法复杂性与递归通过讲解、举例、提问与引导方法。
相关内容此部分内容基础知识可参考清华大学出版社出版严蔚敏编著的《数据结构》教学过程（教师授课思路、设问及讲解要点）回顾数据结构课程中的算法概念、排序算法等知识，从而引出本课程内容。
提问算法与程序的区别、联系以及算法具有的特性。
讲解算法的复杂性，主要包括时间复杂性与空间复杂性。
讲解最坏情况、最好情况与平均情况的时间复杂性。
讲解算法复杂性在渐近意义下的阶，主要包括O、Ω、θ与o，并通过具体例子说明。
通过具体例子说明递归技术。
主要包括阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题等。
第页章节第2 章2.2~2.5 课时 2 教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，掌握计算算法复杂性方法。
教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。
通过讲解、举例方法。
教学难点及突破方法难点：计算算法复杂性。
通过讲解、举例、提问与引导方法。
相关内容素材教（教师授课思路、设问及讲解要点）学过程通过生活中解决复杂问题的分解方法，引出分治方法。
讲解分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。
通过具体例子采用分治思想来设计有效算法。
1. )(n T 给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法）a 、 算法思想用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。
b 、复杂度分析：把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算：有递推公式为：T(n)=1 n=1T(n)= 2T(n/2)+1 n>1所以，分治算法的时间复杂度是n+[logn]-2，当n 为奇数时，logn 取上线，当n 为偶数时，logn 取下线。
//不知道为什么会-2！C 、代码实现：#include <stdio.h>int a[100]; void maxcmax(int i,int j,int &max,int &cmax){int lmax,lcmax,rmax,rcmax;int mid;if (i==j){ max=a[i];cmax=a[i];}else if (i==j-1)if (a[i]<a[j]){max=a[j];cmax=a[i];}else{max=a[i];cmax=a[j];}else{mid=(i+j)/2;maxcmax(i,mid,lmax,lcmax);maxcmax(mid+1,j,rmax,rcmax);if(lmax>rmax)if(lcmax>rmax){max=lmax;。
cmax=lcmax;}else{max=lmax;cmax=rmax;}elseif(rcmax>lmax){if(rmax==rcmax){max=rmax;cmax=lmax;}else{max=rmax;cmax=rcmax;}}。
实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的1．掌握能用分治法求解的问题应满足的条件；2．加深对分治法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二、实验内容1、找最大和最小元素输入n 个数，找出最大和最小数的问题。
2、归并分类将一个含有n个元素的集合，按非降的次序分类（排序）。
三、实验要求（1）用分治法求解问题（2）上机实现所设计的算法；四、实验过程设计（算法设计过程）1、找最大和最小元素采用分治法，将数组不断划分，进行递归。
递归结束的条件为划分到最后若为一个元素则max和min都是这个元素，若为两个取大值赋给max，小值给min。
否则就继续进行划分，找到两个子问题的最大和最小值后，比较这两个最大值和最小值找到解。
2、归并分类使用分治的策略来将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序，最后将排序好的子数组合并成一个有序的数组。
在合并过程中，比较两个子数组的首个元素，将较小的元素放入辅助数组，并指针向后移动，直到将所有元素都合并到辅助数组中。
五、源代码1、找最大和最小元素#include<iostream>using namespace std;void MAXMIN(int num[], int left, int right, int& fmax, int& fmin); int main() {int n;int left=0, right;int fmax, fmin;int num[100];cout<<"请输入数字个数：";cin >> n;right = n-1;cout << "输入数字:";for (int i = 0; i < n; i++) {cin >> num[i];}MAXMIN(num, left, right, fmax, fmin);cout << "最大值为：";cout << fmax << endl;cout << "最小值为：";cout << fmin << endl;return 0;}void MAXMIN(int num[], int left, int right, int& fmax, int& fmin) { int mid;int lmax, lmin;int rmax, rmin;if (left == right) {fmax = num[left];fmin = num[left];}else if (right - left == 1) {if (num[right] > num[left]) {fmax = num[right];fmin = num[left];}else {fmax = num[left];fmin = num[right];}}else {mid = left + (right - left) / 2;MAXMIN(num, left, mid, lmax, lmin);MAXMIN(num, mid+1, right, rmax, rmin);fmax = max(lmax, rmax);fmin = min(lmin, rmin);}}2、归并分类#include<iostream>using namespace std;int num[100];int n;void merge(int left, int mid, int right) { int a[100];int i, j,k,m;i = left;j = mid+1;k = left;while (i <= mid && j <= right) {if (num[i] < num[j]) {a[k] = num[i++];}else {a[k] = num[j++];}k++;}if (i <= mid) {for (m = i; m <= mid; m++) {a[k++] = num[i++];}}else {for (m = j; m <= right; m++) {a[k++] = num[j++];}}for (i = left; i <= right; i++) { num[i] = a[i];}}void mergesort(int left, int right) { int mid;if (left < right) {mid = left + (right - left) / 2;mergesort(left, mid);mergesort(mid + 1, right);merge(left, mid, right);}}int main() {int left=0,right;int i;cout << "请输入数字个数：";cin >> n;right = n - 1;cout << "输入数字:";for (i = 0; i < n; i++) {cin >> num[i];}mergesort(left,right);for (i = 0; i < n; i++) {cout<< num[i];}return 0;}六、运行结果和算法复杂度分析1、找最大和最小元素图1-1 找最大和最小元素结果算法复杂度为O(logn）2、归并分类图1-2 归并分类结果算法复杂度为O(nlogn）实验二背包问题和最小生成树算法实现（用贪心法）一、实验目的1．掌握能用贪心法求解的问题应满足的条件；2．加深对贪心法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
《计算机算法设计与分析》课程设计用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题一、课程设计目的：《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。
通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。
二、课程设计内容：1、分治法：（2）快速排序；2、动态规划：（4）最优二叉搜索树；3、回溯法：（2）图的着色。
三、概要设计：分治法—快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
分治法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；动态规划—最优二叉搜索树：动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。
设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。
●回溯法—图的着色回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始节点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的或节点，并成为当前扩展结点。
算法实验报告一分治法实验一、实验目的及要求利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。
要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用c语言（或者c++语言）实现算法，给出程序的正确运行结果。
（必须完成）设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘法（利用数组实现），给出程序的正确运行结果。
（任选）二、算法描述1、输入两个相同位数的大整数u，v 输出uv的值判断大整数的位数i；w=u/10^(i/2);y=v/10^(i/2);x=u-w*10^(i/2);z= v-y*10^(i/2);然后将w,x,y,z代入公式求得最后结果uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz三、调试过程及运行结果在实验中我遇到的问题：原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少次方时，写的是10^(i/2),10^(i)，结果不对，我就将它改成了for循环语句四、实验总结在本次实验中，我知道了分治算法，以及分治算法的基本思想。
我还掌握了编写大整数乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。
五、附录（源程序代码清单）1、#include<iostream.h> int weishu(int x){int i;while(x!=0){ x=x/10;i++;}return i;}void main(){int u,v;cout<<输入两个位数相同的大整数:<<endl; cin>>u;cin>>v;int i,j,m,n;int p,x,y,z,w;int a=1;int b=1;i=weishu(u);for(int k=1;k<=i;k++){a=a*10;}for(int q=1;q<=i/2;q++) {b=b*10;}w=u/b;y=v/b;x=u-w*b;z=v-y*b;p=w*y*a+((w+x)*(y+z)-w*y-x*z)*b+x*z; cout<<u<<*<<v<<=<<p; }教师评语：成绩：√优良中及格不及格算法实验报告二动态规划法实验一、实验目的及要求利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。
【关键字】分析《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。
2.程序：程序是算法用某种程序设计语言的具体实现。
2、简答题：1.算法需要满足哪些性质？简述之。
算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。
2）输出：算法产生至少一个量作为输出。
3）确定性：组成算法的每条指令清晰、无歧义。
4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。
将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。
该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
2）用递推来实现递归函数。
3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
三、算法编写及算法应用分析题：1.冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。
解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。
1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。
算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)（1)分治法核心思想 (3)（2）MaxMin算法分析 (3)2、动态规划 (4)（1）动态规划核心思想 (4)（2）矩阵连乘算法分析 (5)3、贪心法 (5)(1）贪心法核心思想 (5)（2）背包问题算法分析 (6)（3）装载问题算法分析 (7)4、回溯法 (7)（1）回溯法核心思想 (7)（2)N皇后问题非递归算法分析 (7)(3）N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (10)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归） (11)6、N皇后问题(递归) (11)四、心得体会 (12)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (15)4、装载问题 (17)5、N皇后问题(非递归） (19)6、N皇后问题(递归） (20)一、课程内容1、分治法,求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。
二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。
如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。
那末，这类问题可以用分治法求解。
分治法的核心技术1)子问题的划分技术.2）递归技术。
反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。
3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。
