具体数学-2-1第二章求和问题.pptxVIP

具体数学Concrete Mathematics 04 十月 2023 2023/10/42Chapter 2 求和问题Sums 2023/10/43Chapter 2 求和问题Sums 各种求和问题是最基本的数学内容之一，在数学的各个分支中都无处不在（离散求和：级数，连续求和：积分）。在计算机科学中，求和是算法设计和分析工作中的重要运算。因此，需要一些基本而巧妙的工具和方法来处理求和问题。本章讲解与求和相关的符号、方法和技巧。 2023/10/442.1 和的表示法Notions 2023/10/452.1 表示法? 2023/10/462.1 表示法准确理解一般∑形式： 是所有满足p(k)的下标k对应的项ak的和p(k)可以是任意的谓词对不限于连续整数的指标求和还可以写成 ，用于减少行高 2023/10/472.1 表示法∑表示法是由法国数学家J. Fourier引入的。定界形式与一般形式的比较：一般形式更容易操作可以方便地将下标变量k改为k + 1：下标变量的变换过程比较简明易懂定界形式比较简洁优美在表达同一个和的时候，所用符号往往较少缺点是下标变换不太直观好理解： 2023/10/482.1 表示法根据一般形式和定界形式的特点，常用定界形式表示最终结果，用一般形式进行计算和推导 2023/10/492.1 表示法? 2023/10/4102.1 表示法更激进的表示方法：Iverson约定Kenneth Iverson在程序设计语言APL中提出，将谓词p(k)放到被加项中，而不是用来限制下标变量。求和式可写成：有时项ak不是对所有k都有定义。如果p(k)=0，则ak可以是无定义的，因为不影响结果。 2023/10/4112.2 和与递归Sums and Recurrences 2023/10/4122.2 和与递归求和问题归结为递归问题如何求和？先试试运用已学知识，归结为递归问题，再求解递归问题假设我们要求的和是 ，那么就有递归出现了……施展Guess-Prove法或成套法 2023/10/4132.2 和与递归? 2023/10/4142.2 和与递归递归问题归结为求和问题很多递归问题可归结为求和问题，后面的各种求和方法都可以用来计算较难的递归问题例：Hanoi Tower问题归结为求和问题T0 = 0Tn = 2Tn-1 + 1下面我们尝试用求和方法来计算Tn首先，两端除以2n，得到T0 / 20 = 0Tn / 2n = Tn-1 / 2n-1 + 1 / 2n 2023/10/415递归简化为和设Sn= Tn/ 2n，于是得到S0 = 0Sn = Sn-1 + 2-n容易看出，计算Sn是一个求和问题：假如可以很容易地解决求和问题，就可以得到递归方程的封闭解Tn = Sn * 2n 。事实上，上面的Sn是常见的等比级数，因此Tn = (1 – 2-n) 2n = 2n - 1 2023/10/416一般递归方程的化和技巧形如 的递归方程归结为等比级数求和问题方法类似两边乘以求和因子sn可得巧妙地选择此因子sn使得接下来，记Sn = snanTn，则可得到递归式因此原递归式的解即为：?????? 2023/10/417一般递归方程的化和技巧如何找到正确的sn ，使下式成立？sn bn =sn-1 an-1sn-1 bn-1 =sn-2 an-2…s2b2=s1a1将以上等式连续相乘，可得s1、s0的值仅受到s1b1=s0a0的约束，因此可以为任意非零值。上面等式可略去s1，sn可以取下值或其任意倍数避免被零除：所有a和b非零时，求和因子法才能用。对河内塔问题，an=1，bn=2， 可取sn=2-n，无需灵感 2023/10/418小试牛刀—快速排序快速排序方法是Hoare在1962年发明的。在实际应用中，快排是效率最高的简单排序算法。假定待排序的n项记录的初始次序随机排列的，则快速排序所需的平均比较次数Cn满足递归式在递归式两边同乘以n，可得然后用(n-1)代替n ，可得 2023/10/419小试牛刀—快速排序上下两个方程相减，可得因此，递归式可化简为：令an=n，bn=n +1和cn=2n，则求和因子Sn为 2023/10/420小试牛刀—快速排序可得解为我们记调和数Hn为此时得到了Cn的封闭形式解。也就是说，这里将“调和数”Hn视为“常见”的运算。字母H代表“调和”(Harmonic)。Hn被称为调和数，其来历是：小提琴的琴弦产生的第k个泛音是由其1/k长（手指搭在弦上）的弦产生的基音。 2023/10/421小试牛刀—快速排序在定义完Hn之后，对Cn中的求和部分做些变换，以便使用Hn来表