算法问题求解基础.pptx

1
算法设计与分析
DeSign and Analysis of Algorithm In C++
陈慧南编著
2
平时要求:
按时上下课、课堂不吵闹、手机调成非铃声状态
考试成绩:
平时表现(考勤、随堂提问、作业等):20%
期末考试:80%
3
课程简介
课程名称:算法设计与分析
Design and Analysis of Algorithms
先修课程:
面向对象程序设计语言C++,数据结构,离散结构
4
第1章算法问题求解基础
第1部分算法和算法分析
算法概述
问题求解方法
算法设计与分析
递归和归纳
5
什么是算法
算法是计算机学科的一个重要分支,它是计算机科学的基础,更是计算机程序的基石。算法是计算机求解问题的特殊方法。学****算法,一方面需要学****求解计算领域中典型问题的各种有效算法,还要学****设计新算法和分析算法性能的方法。
算法概述
算法(algorithm):一个算法是对特定问题求解步骤的一种描述,它是指令的有限序列。
中国的珠算口诀可视为典型的算法,它将复杂的计算描述为一系列的算珠拨动动作。
算法具有下列5个特征:
6
输入(input):算法有零个或多个输入量;
输出(output):算法至少产生一个输出量;
确定性(definiteness):算法的每一条指令都有确切的定义,没有二义性;
能行性(effectiveness):算法的每一条指令必须足够基本,它们可以通过已经实现的基本运算执行有限次来实现;
有穷性(finiteness):算法必须总能在执行有限步之后终止。
7
最早的算法是欧几里德的“求最大公因子算法”
辗转相除法
欧几里德算法(辗转相除法)
计算两个整数m和n(0≤m<n)的最大公约数,记为gcd(m, n)。其计算过程是重复应用下列等式,直到n mod m=0.
gcd(m,n)=gcd(n mod m,m),对于m>0 (1-1)
式中,n mod m表示n除以m之后的余数。
因为gcd(0,n)=n,n的最后取值也就是m和n最大公约数。
例如,gcd(24,60)=gcd(12,24)=gcd(0,12)=12
8
【程序1-1】欧几里德递归算法
void Swap(int&a,int&b)
{
int c=a;a=b;b=c;
}
int RGcd(int m,int n)
{
if(m==0) return n;
return RGcd(n%m,m);
}
int Gcd(int m,int n)
{
if (m>n) Swap(m,n);
return RGcd(m,n);
}
9
【程序1-2】欧几里德迭代算法
int Gcd(int m,int n)
{
if (m==0)return n;
if (n==0)return m;
if (m>n) Swap(m,n);
while(m>0){
int c=n%m;n=m;m=c;
}
return n;
}
10
迭代和递归的区别
迭代和递归各基于一种控制结构,都涉及到循环,都可无限进行。
迭代是循环求值,递归是调用本身;
迭代使用循环结构,递归使用选择结构;
迭代是当循环条件不满足时终止,递归是当满足基本条件时终止;
迭代是用计数器控制循环,不停地修改计数器的值,直到不满足条件为止;
递归是逐渐逼近基本条件而终止,不断的对问题进行简化直到可以直接计算基本问题为止。