具体数学 第2章 和式(2.1节-2.3节).pptx

第2章 和式（SUMS）;参考教材与书目;参考教材与书目;课程教学内容;课程教学内容;课程教学内容;本章教学内容;8;9;10;11;12;13;14;15;16;17;本章教学内容;19;20;2015/3/21;2015/3/21;令Rn=1，可得α=1，β=0，γ=0，从而A(n)=1； 令Rn=n，可得α=0，β=1，γ=0，从而B(n)=n； 令Rn=n2，可得α=0，β=-1，γ=2，从而2C(n)-B(n)=n2，即：C(n)=(B(n)+n2)/2 最终可得：;2015/3/21;2015/3/21;对于一般形式的递归方程 ，可采用类似方法，将其化成等比级数求和问题： 两边乘以求和因子sn可得 巧妙地选择此因子sn使得 接下来，记Sn = snanTn，则可得到递归式 因此 原递归式的解即为：;尚有未决问题：sn 到底是怎样的，才能使下式成立？ sn bn = sn-1 an-1 sn-1 bn-1 = sn-2 an-2 … s2 b2 = s1a1 将以上等式连续相乘，可得 s1、s0的值仅受到s1b1=s0a0的约束，可为任意非零值。因此可略去s1，因而sn可取如下值或其任意倍数 避免被零除。当所有a和b非零时，求和因子法才能用。;快速排序方法是Hoare在1962年发明的。在实际应用中，快排是效率最高的简单排序算法。 假定待排序的n项记录的初始次序随机排列的，则快速排序所需的平均比较次数Cn满足递归式 消掉除法：两边同乘n。 消掉∑：用(n-1)代替n 。 ;上下两个方程相减，可得 因此，递归式可化简为： 令an=n，bn=n +1和cn=2n，则求和因子sn为;可得解为 我们记调和数Hn为 此时得到了Cn的封闭形式解。也就是说，这里将“调和数”Hn视为“常见”的运算。 字母H代表“调和”(Harmonic)。Hn被称为调和数，其来历是：小提琴的琴弦产生的第k个泛音是由其1/k长（手指搭在弦上）的弦产生的基音。;在定义完Hn之后，对Cn中的求和部分做些变换，以便使用Hn来表达Cn ： 因此Cn可以写成 对小数值n = 0, 1, 2，可检查其正确性。;本章教学内容;33;34;示例：对算术级数 求和 运用交换律，用n – k替代k，可得 运用结合律，将两个等式相加，得到 运用分配率，提取常数(2a + bn)，可得 最终得到 ;2015/3/21;2015/3/21;2015/3/21;2015/3/21;2015/3/21;2015/3/21;2015/3/21;2015/3/21;本章教学内容;45;46