文档介绍：1、算法与程序
答案:对于计算机科学来说,算法的概念是至关重要的。例如,在一个大型软件系统的开发中,设计出有效的算法将起决定性的作用,通俗的讲,算法是指解决问题的一种方法或一个过程,更严格的讲,算法是由若干条指令组成的有穷序列,且满足下述4条性质。(1)输入:有零个或多个由外部提供的量作为算法的输入。(2)输出:算法产生至少一个量作为输出。(3)确定性:组成算法的每条指令是清晰的,无歧义的。(4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有线的。
程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统,它是一个在无限循环中执行的程序,因而不是一个算法。然后可把操作系统的各种任务看成是一些单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
2、递归的概念(举例)
答案:直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。例:i数列
无穷数列1,1,2,3,5,8,13,21,34,55,……,i数列。它可以递归的定义为
1 n = 0
F (n) 1 n = 1
F(n – 1)+ F(n – 2) n > 1
这是一个递归关系式,它说明当n > 1时,这个数列的第n项的值是它前面两项之和。它用两个较小的自变量的函数值来定义一个较大自变量的函数值,所以需要两个初始值F(0)和F(1)。
3、快速排序
答案:快速排序算法是基于分治策略的另一个排序算法。其基本思想是,对于输入的子数组a [p : r] ,按一下三个步骤进行排序。(1)分解:以a [p] 划分成3段a [p : q - 1],a[q]和a[q + 1 : r],使a[p : q - 1]中任何一个元素小于等于a[q],而a[q + 1 : r]中任何一个元素大于等于a [q]。下标q在划分过程中确定。(2)递归求解:通过递归调用快速排序算法分别对a[p : q - 1]和a[q + 1 : r]进行排序。(3)合并:由于对a [p : q - 1]和a[q + 1 : r]都已拍好的序后,不需要执行任何计算,a[p : r]就已排好序。
4、矩阵连乘问题
答案:(1)分析最优解的结构(2)建立递归关系(3)计算最优值
void MatrixChain(int * p , int n,int * * m , int * * s)
{
for( int i = 1 ; i < = n ; i + +)m[i][i]=0;
for( int r = 2 ; r < = n ; r + +)
for(int i = 1 ; i < = n – r + 1 ; i + +) {
int j = i + r – 1 ;
m[i][j] = m[i + 1][j] + p[ i - 1] * p[i]*p[j] ;
s[i][j] = i ;
for( int k = i + 1 ; k < j ; k + +) {
int t = m[i][k] + m[k + 1][j] + p[ i - 1] * p[k] * p[j]
if ( t < m[i][j]) {m[i][j] = t ; s[i]