[理学]第一章 数值分析2008绪论.ppt

数值分析 教材及参考书目 数值分析的作用 绪论 1.1数值分析研究对象与特点 要求 1.2数值计算的误差 1.2.1误差来源与分类1 1.2.1误差来源与分类2 1.2.1误差来源与分类3 1.2.2 误差与有效数字1 1.2.2 误差与有效数字2 1.2.2 误差与有效数字3 1.2.2 误差与有效数字4 1.2.2 误差与有效数字5 1.2.2 误差与有效数字6 1.2.2 误差与有效数字7 1.2.3 数值计算中应注意的几个原则1 1.2.3 数值计算中应注意的几个原则2 1.2.3 数值计算中应注意的几个原则3 1.2.3 数值计算中应注意的几个原则4 1.2.3 数值计算中应注意的几个原则5 1.2.3 数值计算中应注意的几个原则6 1.3 算法 1.3.1 算法的特征 1.3.2 数值型算法的特点 1.3.3 算法设计的基本方法-列举法 1.3.3 算法-算法设计基本方法-列举法 1.3.3 算法-算法设计基本方法-列举法 1.3.3 算法-算法设计基本方法-枚举归纳法 1.3.3 算法-算法设计基本方法-递推法1 1.3.3 算法-算法设计基本方法-递推法2 1.3.3 算法-算法设计基本方法-递推法3 1.3.3 算法-算法设计基本方法-递归法1 1.3.3 算法-算法设计基本方法-递归法2 1.3.3 算法-算法设计基本方法-递归法3 1.3.3 算法-算法设计基本方法-递归法4 1.3.3 算法-算法设计基本方法-回溯法1 1.3.3 算法-算法设计基本方法-回溯法2 1.3.3 算法-算法设计基本方法-回溯法3 1.3.3 算法-算法设计基本方法-回溯法4 1.3.3 算法-算法设计基本方法-回溯法5 1.3.3 算法-算法设计基本方法-贪婪法1 1.3.3 算法-算法设计基本方法-贪婪法2 1.3.3 算法-算法设计基本方法-分治法1 1.3.3 算法-算法设计基本方法-分治法2 1.3.3 算法-算法设计基本方法-分治法3 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.4 算法-算法设计基本方法-A*算法 1.3.5 算法-算法设计基本方法-工兵寻径 1.3.5 算法-算法设计基本方法-工兵寻径 1.3.5 算法-算法设计基本方法-工兵寻径 1.3.6 算法-算法设计基本方法-数值法1 1.3.6 算法-算法设计基本方法-数值法2 1.3.7 算法的复杂度1 1.3.7 算法的复杂度2 1.3.7 算法的复杂度3 1.3.7 算法的复杂度4 1.3.7 算法的复杂度5 【问题】 阶乘计算 问题描述：编写程序，对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。 由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储：N=a[m]×10m-1+a[m-1]×10m-2+…+a[2]×101+a[1]×100 并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。例如，5！=120，在数组中的存储形式为：3 0 2 1 …… 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。 递归是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用。 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。 【问题】 编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。 斐波那契数列为：0、1、1、2、3、……，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) （当n1时）。 写成递归函数有： int fib(int n)