算法问题求解基础.pptx

算法设计与分析DeSign and Analysis of Algorithm In C++陈慧南 编著 平时要求： 按时上下课、课堂不吵闹、手机调成非铃声状态考试成绩： 平时表现（考勤、随堂提问、作业等）：20%期末考试：80% 课程简介课程名称：算法设计与分析 Design and Analysis of Algorithms 先修课程： 面向对象程序设计语言C++，数据结构，离散结构? 第1部分 算法和算法分析第1章 算法问题求解基础1.1 算法概述 1.2 问题求解方法 1.3 算法设计与分析 1.4 递归和归纳 1.1 算法概述1.1.1 什么是算法算法是计算机学科的一个重要分支，它是计算机科学的基础，更是计算机程序的基石。算法是计算机求解问题的特殊方法。学习算法，一方面需要学习求解计算领域中典型问题的各种有效算法，还要学习设计新算法和分析算法性能的方法。算法（algorithm)：一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 中国的珠算口诀可视为典型的算法，它将复杂的计算描述为一系列的算珠拨动动作。 算法具有下列5个特征：输入（input）：算法有零个或多个输入量；输出（output）：算法至少产生一个输出量；确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性；能行性（effectiveness）：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；有穷性（finiteness）：算法必须总能在执行有限步之后终止。 最早的算法是欧几里德的“求最大公因子算法”辗转相除法 欧几里德算法(辗转相除法)计算两个整数m和n（0≤m＜n)的最大公约数，记为gcd(m, n)。其计算过程是重复应用下列等式，直到n mod m=0.gcd(m,n)=gcd(n mod m,m),对于m0 (1-1) 式中，n mod m表示n除以m之后的余数。因为gcd(0,n)=n,n的最后取值也就是m和n最大公约数。例如，gcd(24,60)=gcd(12,24)=gcd(0,12)=12 【程序1-1】 欧几里德递归算法void Swap(inta,intb){ 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 (mn) Swap(m,n); return RGcd(m,n);} 【程序1-2】 欧几里德迭代算法int Gcd(int m,int n){ if (m==0)return n; if (n==0)return m; if (mn) Swap(m,n); while(m0){ int c=n%m;n=m;m=c; } return n;} 迭代和递归的区别迭代和递归各基于一种控制结构，都涉及到循环，都可无限进行。迭代是循环求值，递归是调用本身；迭代使用循环结构，递归使用选择结构；迭代是当循环条件不满足时终止，递归是当满足基本条件时终止；迭代是用计数器控制循环，不停地修改计数器的值，直到不满足条件为止；递归是逐渐逼近基本条件而终止，不断的对问题进行简化直到可以直接计算基本问题为止。最大公约数问题还有其他算法。程序1-3的连续整数检测法的依据直接来自最大公约数的定义：m和n的最大公约数是能够同时整除它们的最大正整数。【程序1-3】 Gcd的连续整数检测算法int Gcd(int m,int n){ if (m==0)return n; if (n==0)return m; int t=mn?n:m; while (m%t || n%t) t--; return t;} 1.1.2 为什么学习算法 算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素的软件人才。对于计算机专业的学生来说，学习算法的理由是非常充分的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其效率。随着计算机应用的日益普及，各个应用领域的研究和技术人员都在使用计算机求解他们各自专业领域的问题，他们需要设计算法，编写程序，开发应用软件，所以学习算法对于越来越多的人来说变得十分必要。 Donald E. Knuth计算机科学大师、“算法分析之父”唐德纳（1938年1月10日-）现与其妻Jill生活于斯坦福校园内。1974年美国计算机协会图灵奖 (ACM Turing Award)1979年美国前总统卡特授予的科学金奖(Medal of Science)1996年11月由于发明先进技术荣获极受尊重的京都奖(Kyoto Prize)。1.2 问题求解方法1