数学基础知识

集合

• 由一个或多个确定的元素所构成的整体
• 特性
  1. 确定性
  2. 互异性
  3. 无序性
• Java 中的 Set 用于描述集合 => HashSet

空集

子集

交集

并集

幂集

• 所有自己组成的集合
• 一个有限集的幂集元素个数 => 2^{<有限集元素个数>}

函数

• 在一个变化过程中有两个变量x、y，对于任意一个x都有唯一确定的一个y和它对应，那么称x为自变量，y是x的函数。x的取值范围为函数的定义域，y的取值范围为函数的值域
• 设A，B是非空的数集，如果按照某种确定的对应关系f，使对于集合A中的任意一个数x，在集合B中都有唯一确定的数y与之对应，那么就称映射f：A->B为集合A到集合B的一个函数
• y = f(x) && x A
• 三要素
  1. 定义域
  2. 值域
  3. 对应关系
• 特性
  1. 有界性
  2. 单调性
  3. 奇偶性
  4. 周期性

常见函数

• 常函数 => y = a
• 幂函数 => y = ax^b
• 指数函数 => y = a^x(a>0且a≠1)
• 对数函数 => y = log_ax(a>0且a≠1) =>
  1. 换底公式
  2. lgx
  3. lnx

排列和组合

排列

从n个不同元素中，任取m(m n，m与n均为自然数)个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列

排列计算方法

组合

• 从n个不同元素中，任取m(m n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合
• 从n个不同元素中取出m(m n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数

组合计算方法

数学归纳法

• 一种数学证明方法，通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立

步骤

1. 基础步骤 => 证明当 n = 1 时命题成立
2. 归纳步骤 => 假设 n = k 时命题成立，推导出在 n = k + 1 时命题也成立

例子

求证：1 + 2 + 3 + ... + n = n(n + 1)/2

1. 基础步骤：当 n = 1 时，1 = 1*(1 + 1)/2 = 1
2. 归纳步骤
   1. 假设 n = k 时命题成立 => 1 + 2 + 3 + ... + k = k(k + 1)/2
   2. 当 n = k + 1 时，1 + 2 + 3 + ... + k + k + 1 = k(k + 1)/2 + k + 1 = (k + 1)(k + 2)/2

数列

• 一组按顺序排列的数，记为{a_n}(n N^*)(n属于正整数)
• 通项公式 => 数列的第N项a_n与项的序数n之间的关系可以用一个公式a_n=f(n)来表示，这个公式就叫做这个数列的通项公式
• 递推公式 => 如果数列{a_n}的第n项与它前一项或几项的关系可以用一个式子来表示，那么这个公式叫做这个数列的递推公式
• 前n项和

斐波那契数列 Fibonacci

• F₀ = 0
• F₁ = 1
• 递推公式 => F_n = F_{n - 1} + F_{n - 2}(n 2)

等差数列

• 从第二项起，每一项与它的前一项的差等于同一个常数
• 通项公式 => a_n = a₁ + (n - 1) * d
• 递推公式 => a_n = a_{n - 1} + d
• 前n项和 => S_n = n * (a₁ + a_n) / 2 = n * a₁ + n * (n - 1) * d / 2
• a_n = S_n - S_{n - 1}

等比数列

• 从第二项起，每一项与它的前一项的比等于一个常数
• 通项公式 => a_n = a₁ * q^{n - 1}
• 递推公式 => a_n = a_{n - 1} * q
• 前n项和 =>
  • q 1 => S_n = a₁ * (1 - qⁿ) / (1 - q)
  • q = 1 => S_n = n * a₁