CUNY CSci335 软件设计与分析 3 讲义.pdfVIP

计算机科学335软件设计与分析III魏斯特教授

第1章先决条件主题回顾

第一章前提主题回顾

1.1数学基础知识

这是你在课程剩余部分需要了解的数学知识。非常重要的是，你要记住这些公式，并且知道如何

在实践中应用它们，因为它们在算法分析和计算机科学的研究中经常出现。

1.1.1级数求和

等差数列的求和公式是

n

∑k=n(n+1)(1.1)

2

k=0

方程式1.1可以通过数学归纳法轻松证明。通过这个公式，你可以解决更一般的等差数列求和问题

，形式如

n

∑(ak+b)(1.2)

k=0

通过直接写出并重新分配级数的项，可以得到：

nnn

∑(ak+b)=a∑k+∑b

k=0k=0k=0

an(n+1)

=+(n+1)b(1.3)

2

如果系列看起来不是从0开始，而是从c开始，那么观察到

n

∑(ak+b)=(a(c+0)+b)+(a(c+1)+b)+...+(a(c+n−c)+b)

k=c

n−c

=∑(a(c+k)+b)(1.4)

k=0

n−c

=∑(ac+ak+b)(1.5)

k=0

m

=∑(ak+d)(1.6)

k=0

换句话说，它总是可以看作从0开始。

1

计算机科学335软件设计与分析III魏斯特教授

第1章先决条件主题回顾

举个例子，假设你需要找到序列9,13,17,21,25,29,33,...,257的和。你会发现每个项之间的差是

常数a=4，从中你可以得出这是一个等差数列。第一个项是9，所以你可以取b=9。所以你知道

a=4和b=9。现在你需要知道n的值。最后一项是an+b=257；所以4n+9=257。解出n我

们得