# 编程题

1. 实现冒泡排序

   	class Solution:
   	# 定义一个名为 sortArray 的方法，接受一个整数列表 nums，返回一个排序后的整数列表
   	def sortArray(self, nums: List[int]) -> List[int]:
   	# 定义冒泡排序的函数
   	def bubbleSort(nums):
   	# 获取列表的长度
   	n = len(nums)
   	# 外层循环控制需要比较的轮数，每轮将当前最大的元素移动到末尾
   	for i in range(n - 1):
   	# 内层循环控制每轮比较的次数
   	for j in range(n - i - 1):
   	# 如果当前元素大于下一个元素，交换它们的位置
   	if nums[j] > nums[j + 1]:
   	nums[j], nums[j + 1] = nums[j + 1], nums[j]
   	# 返回排序后的列表
   	return nums
   	# 调用冒泡排序函数并返回结果
   	return bubbleSort(nums)

   https://leetcode.cn/problems/sort-an-array/description/

2. 二维数组中的查找

   题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

   	class Solution:
   	# 定义一个名为 searchMatrix 的方法，接受一个二维数组 matrix 和一个整数 target，返回一个布尔值
   	def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
   	# 获取二维数组的行数和列数
   	m, n = len(matrix), len(matrix[0])
   	# 初始化起始搜索位置为二维数组的左下角
   	row, col = m - 1, 0
   	# 使用循环进行搜索，直到搜索越界或找到目标值
   	while row >= 0 and col < n:
   	# 如果当前元素大于目标值，向上移动一行
   	if matrix[row][col] > target:
   	row -= 1
   	# 如果当前元素小于目标值，向右移动一列
   	elif matrix[row][col] < target:
   	col += 1
   	# 如果当前元素等于目标值，返回 True
   	else:
   	return True
   	# 如果循环结束仍未找到目标值，返回 False
   	return False

   https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
   https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/2361487/240-sou-suo-er-wei-ju-zhen-iitan-xin-qin-7mtf

3. 题目：输入两个正整数 m 和 n，求其最大公约数和最小公倍数。

   	# 定义计算最大公约数的函数
   	def gcd(a, b):
   	# 使用欧几里德算法，直到其中一个数为 0
   	while b != 0:
   	# 交换两个数的值，并取余数
   	a, b = b, a % b
   	# 返回最大公约数
   	return a
   	# 定义计算最小公倍数的函数
   	def lcm(a, b):
   	# 两个数的最小公倍数等于两个数的乘积除以它们的最大公约数
   	return a * b // gcd(a, b)
   	# 获取用户输入的两个正整数
   	m = int(input("请输入第一个正整数 m："))
   	n = int(input("请输入第二个正整数 n："))
   	# 调用函数计算最大公约数和最小公倍数，并打印结果
   	print("最大公约数是：", gcd(m, n))
   	print("最小公倍数是：", lcm(m, n))

# 数学基础

# 函数 (Function)

• 概念：函数就像一个 “机器”，你给它一个输入，它会根据一定的规则输出一个结果。
• 例子：比如一个简单的函数是 $f(x)=x+2$，意思是你给它一个数 $x$，它会把这个数加上 2，然后输出结果。如果你输入 3，它会输出 5。

# 导数 (Derivative)

• 概念：导数可以看作是一个函数的变化率，或者说是函数在某一点上的 “斜率”。
• 例子：比如，假设你有一个函数 $f(x)=x^2$，它的导数是 $f′(x)=2x$。这意味着在任意一点 $x$ 上，函数的变化率是 $2x$。如果 $x=3$，变化率就是 $2×3=6$。

导数的规则，也叫微分法则，是计算函数导数的基础。下面是一些基本的导数规则：

# 常数的导数

如果函数是一个常数 $c$，那么它的导数是 0，因为常数不会随着变量的变化而变化。

$$\frac{d}{dx}(c) = 0$$

# 恒等函数的导数

恒等函数是指 $y$ 本身的函数，即 $f(y)=y$。这个函数的导数是 1，因为对于任何数 $y$，其导数表示的是函数值的变化率。

$$\frac{d}{dy}(y) = 1$$

# 幂函数的导数

如果函数是 $x$ 的 $n$ 次幂 $x^n$，那么它的导数是 $nx^{n-1}$。

$$\frac{d}{dx}(x^n) = nx^{n-1}$$

例如：

$$\frac{d}{dx}(x^3) = 3x^2$$

# 和的导数

如果函数是两个函数的和 $f(x) + g(x)$，那么它的导数是两个函数的导数之和。

$$\frac{d}{dx}[f(x) + g(x)] = \frac{d}{dx}[f(x)] + \frac{d}{dx}[g(x)]$$

# 差的导数

如果函数是两个函数的差 $f(x) - g(x)$，那么它的导数是两个函数的导数之差。

$$\frac{d}{dx}[f(x) - g(x)] = \frac{d}{dx}[f(x)] - \frac{d}{dx}[g(x)]$$

# 乘积的导数（乘积法则）

如果函数是两个函数的乘积 $f(x) \cdot g(x)$，那么它的导数是：

$$\frac{d}{dx}[f(x) \cdot g(x)] = f(x) \cdot \frac{d}{dx}[g(x)] + g(x) \cdot \frac{d}{dx}[f(x)]$$

# 商的导数（商法则）

如果函数是两个函数的商 $\frac{f(x)}{g(x)}$，那么它的导数是：

$$\frac{d}{dx}\left[\frac{f(x)}{g(x)}\right] = \frac{g(x) \cdot \frac{d}{dx}[f(x)] - f(x) \cdot \frac{d}{dx}[g(x)]}{[g(x)]^2}$$

# 积分 (Integral)

• 概念：积分可以看作是计算一个函数在某个区间内的 “总量” 或 “面积”。
• 例子：比如，假设你有一个函数 $f(x)=x$，你想知道从 $x=0$ 到 $x=3$ 这个区间内的总面积是多少。这个面积就是积分计算的结果。在这个例子中，积分结果是 4.5。

# 极限 (Limit)

• 概念：极限是描述一个函数在某一点附近的行为，而不一定是在那个点上的值。
• 例子：比如，函数 $f(x)=1/x​$ 当 $x$ 趋近于 0 时，函数值会越来越大，但在 $x=0$ 时函数是无定义的。我们说这个函数的极限在 $x$ 趋近于 0 时是无穷大。

# 坐标平面 (Coordinate Plane)

• 概念：坐标平面是一个二维空间，用来表示点的位置。它由两条互相垂直的轴组成：水平的 x 轴和垂直的 y 轴。
• 例子：如果我们在 x 轴上取 3，在 y 轴上取 2，那么点 (3, 2) 就表示在 $x=3$ 和 $y=2$ 的位置。

# 题目

1. 什么是极大似然估计？

   极大似然估计（Maximum Likelihood Estimation，简称 MLE）是一种统计方法，用于估计模型参数，使得在给定数据下，模型生成这些数据的概率最大。
   极大似然估计的核心思想是：在已知一组数据的情况下，希望找到一个参数值，使得在这个参数值下，观测到这组数据的概率（即似然函数）最大。

   假设你有一袋糖果，里面有红色和蓝色的糖果，但你不知道每种糖果的具体比例。你想要估计红色糖果的比例是多少。
   你可以通过以下步骤使用极大似然估计：

   1. 抽样：你从袋子里随机抽出一些糖果，比如抽出 10 个，发现有 7 个是红色的，3 个是蓝色的。
   2. 构建模型：假设你想知道的袋子里的红色糖果比例是 $p$，那么蓝色糖果的比例就是 $1−p$。
      使用极大似然估计的方法，会假设 $p$ 是未知的，需要估计。我们会根据抽样结果（7 颗红色，3 颗蓝色）来计算在不同 $p$ 值下，得到这个抽样结果的概率，然后选择使这个概率最大的 $p$ 值。你的任务是找到一个 $p$ ，使得在这个比例下，抽出 7 个红色糖果和 3 个蓝色糖果的概率最大。
   3. 写出似然函数，计算概率：似然函数 $L(p)$ 表示在给定 $p$ 下，观测到 7 个红色糖果和 3 个蓝色糖果的概率。对于每次抽取糖果来说，这个概率是 $p$ 和 $1−p$ 的乘积。
      根据概率论，你可以计算在某个比例 $p$ 下，抽出 7 个红色糖果和 3 个蓝色糖果的概率。这个概率可以用一个公式表示：

   $$L(p)=p^7×(1−p)^3$$

   4. 最大化似然函数，找到最大值：你需要找到一个 $p$ ，使得上述概率最大。这个 $p$ 就是你的极大似然估计。
      通过数学方法找到使 $L(p)$ 最大的 $p$ 值。通常，我们对似然函数取对数（称为对数似然函数），然后对参数求导，解出导数等于 0 的点。
      对数似然函数为：$\ln L(p)=7 \ln p+3 \ln (1-p)$
      对 $p$ 求导并解方程：$\frac{d}{d p} \ln L(p)=\frac{7}{p}-\frac{3}{1-p}=0$
      解这个方程得到 $p=\frac{7}{10}=0.7$

   在这个例子中，极大似然估计告诉我们，最有可能的红色糖果比例是 70%。换句话说，假设袋子里红色糖果的比例是 70%，那么抽到 7 颗红色和 3 颗绿色糖果的概率是最大的。
   通过这种方法，极大似然估计帮助我们在已知数据的基础上，找到最有可能的参数值。

2. 求偏导

   $$z=x^{2} y+y^{2}$$

   求

   $$\left.\frac{\partial z}{\partial y}\right|_{(1,2)} \frac{\partial^{2} z}{\partial y \partial x}$$

   偏导数是多元函数对其中一个变量的导数，其余变量保持不变。

   已知有一个公式：

   $$z = x^2 y + y^2$$

   要做的是两件事：

   1. 计算 $z$ 对 $y$ 的变化率（偏导数）在点 $(1, 2)$ 处的值。

   首先，对原公式里的 $y$ 进行变化，看公式会如何变化。
   $z$ 对 $y$ 的变化率可以理解为：当 $x$ 保持不变时，如果改变 $y$，那么 $z$ 会如何改变。

   对 $y$ 进行变化（求偏导数），按照导数的规则分别对两个项进行计算：

   • $x^2 y$ 对 $y$ 的偏导数是 $x^2$（因为 $x^2$ 被视为常数，恒等函数 $y$ 的导数是 1）。
   • $y^2$ 对 $y$ 的偏导数是 $2y$（根据幂函数求导法则，$y^2$ 的导数是 $2y$）。

   所以可以得到：

   $$\frac{\partial z}{\partial y} = x^2 + 2y$$

   这里的意思是， $z$ 对 $y$ 的变化率等于 $x^2$ 加上 $2y$。

   在点 $(1, 2)$ 处（就是 $x = 1$ 和 $y = 2$），把这些值代入公式：

   $$\left. \frac{\partial z}{\partial y} \right|_{(1, 2)} = 1^2 + 2 \times 2 = 1 + 4 = 5$$

   所以，$z$ 对 $y$ 的变化率在点 $(1, 2)$ 处是 5。

   2. 计算 $z$ 对 $y$ 和 $x$ 的混合变化率（二阶偏导数）在点 $(1, 2)$ 处的值。

   这是看 $z$ 同时对 $x$ 和 $y$ 变化的效果，计算的是二阶混合偏导数。

   首先，对 $x$ 进行变化，先对 $x$ 求偏导数：

   • $x^2 y$ 对 $x$ 的偏导数是 $2xy$（因为 $x^2$ 对 $x$ 的导数是 $2x$，而 $y$ 被视为常数）。
   • $y^2$ 对 $x$ 的偏导数是 0（因为它不含 $x$）。

   所以可以得到：

   $$\frac{\partial z}{\partial x} = 2xy$$

   这里的意思是， $z$ 对 $x$ 的变化率等于 $2xy$。

   然后，再对得到的这个结果 $2xy$，对 $y$ 进行变化，对 $y$ 再求偏导数：

   • $2xy$ 对 $y$ 的偏导数是 $2x$（因为 $y$ 的导数是 1，而 $2x$ 被视为常数）。

   所以可以得到：

   $$\frac{\partial^2 z}{\partial y \partial x} = 2x$$

   也就是$z$ 对 $y$ 和 $x$ 的二阶混合偏导数。
   在点 $(1, 2)$ 处，把 $x = 1$ 代入公式：

   $$\left. \frac{\partial^2 z}{\partial y \partial x} \right|_{(1, 2)} = 2 \times 1 = 2$$

   所以，$z$ 对 $y$ 和 $x$ 的混合变化率在点 $(1, 2)$ 处是 2。

3. 矩阵运算

   给定矩阵，$A=\left[\begin{array}{ccc}1 & -1 & -1 \\2 & -1 & -3 \\-3 & 4 & 4\end{array}\right]$，$B=\left[\begin{array}{lll}1 & 2 & 3 \\2 & 2 & 1 \\3 & 4 & 3\end{array}\right]$，求 $B^{T} A$ 和 $A^{-1}$ 。

   1. 计算 $B^T A$

   首先，计算 $B$ 的转置矩阵 $B^T$：

   $$B^T = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 2 & 4 \\ 3 & 1 & 3 \end{pmatrix}$$

   转置矩阵（Transpose Matrix）是通过将矩阵的行与列互换得到的矩阵。

   然后，计算矩阵乘法 $B^T A$。
   矩阵乘法的规则是：第一个矩阵的行与第二个矩阵的列对应元素相乘并相加。

   $$B^T A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 2 & 4 \\ 3 & 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & -1 & -1 \\ 2 & -1 & -3 \\ -3 & 4 & 4 \end{pmatrix}$$

   计算步骤如下：

   • 第 1 行第 1 列：$1 \cdot 1 + 2 \cdot 2 + 3 \cdot -3 = 1 + 4 - 9 = -4$
   • 第 1 行第 2 列：$1 \cdot -1 + 2 \cdot -1 + 3 \cdot 4 = -1 - 2 + 12 = 9$
   • 第 1 行第 3 列：$1 \cdot -1 + 2 \cdot -3 + 3 \cdot 4 = -1 - 6 + 12 = 5$
   • 第 2 行第 1 列：$2 \cdot 1 + 2 \cdot 2 + 4 \cdot -3 = 2 + 4 - 12 = -6$
   • 第 2 行第 2 列：$2 \cdot -1 + 2 \cdot -1 + 4 \cdot 4 = -2 - 2 + 16 = 12$
   • 第 2 行第 3 列：$2 \cdot -1 + 2 \cdot -3 + 4 \cdot 4 = -2 - 6 + 16 = 8$
   • 第 3 行第 1 列：$3 \cdot 1 + 1 \cdot 2 + 3 \cdot -3 = 3 + 2 - 9 = -4$
   • 第 3 行第 2 列：$3 \cdot -1 + 1 \cdot -1 + 3 \cdot 4 = -3 - 1 + 12 = 8$
   • 第 3 行第 3 列：$3 \cdot -1 + 1 \cdot -3 + 3 \cdot 4 = -3 - 3 + 12 = 6$

   所以，

   $$B^T A = \begin{pmatrix} -4 & 9 & 5 \\ -6 & 12 & 8 \\ -4 & 8 & 6 \end{pmatrix}$$

   2. 计算 A^

   计算矩阵 $A$ 的逆矩阵 $A^{-1}$，将使用初等行变换法。

   逆矩阵（Inverse Matrix）是一个方阵（即行数和列数相同的矩阵）的一个特殊矩阵。设 $A$ 是一个 $n \times n$ 的方阵，如果存在一个矩阵 $A^{-1}$，使得 $A$ 与 $A^{-1}$ 的乘积是单位矩阵 $I$，即：

   $$A A^{-1} = A^{-1} A = I$$

   其中，单位矩阵 $I$ 是一个对角线上全是 1，其余元素全是 0 的矩阵。例如，3x3 的单位矩阵是：

   $$I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

   求逆矩阵的方法有几种，常见的方法包括：

   • 高斯 - 约当消去法：通过一系列初等行变换将矩阵 $A$ 化为单位矩阵，同时将单位矩阵化为 $A$ 的逆矩阵。具体步骤：
     1. 将矩阵 $A$ 和单位矩阵 $I$ 拼接成一个增广矩阵 $[A|I]$。
     2. 通过一系列初等行变换将矩阵 $A$ 化为单位矩阵，同时对单位矩阵进行相同的行变换。
        初等行变换包括以下三种操作：
        • 交换两行：用于调整行的顺序，以便进行进一步的操作。例如将第 i 行和第 j 行交换。改变矩阵的行顺序，这不会影响行列式的值（如果行列式为零，则矩阵不可逆）。
        • 将某一行乘以一个非零常数：用于将某个行元素变为 1，从而简化后续操作。例如将第 i 行乘以一个非零常数 k。这改变了矩阵的行的大小，但不会改变其可逆性。
        • 将某一行加上另一行的倍数：用于将其他行中的相应元素变为 0，从而使矩阵逐渐逼近单位矩阵。例如将第 i 行加上第 j 行的 k 倍。这相当于对矩阵进行线性变换，使其逐渐逼近单位矩阵。
     3. 当矩阵 $A$ 被化为单位矩阵时，单位矩阵被化为 $A$ 的逆矩阵 $A^{-1}$。
   • 伴随矩阵法：利用矩阵的行列式和伴随矩阵求逆矩阵。
   • 分块矩阵法：适用于一些特殊结构的矩阵。

   回到原题
   首先，写下 $A$ 和单位矩阵 $I$：

   $$[A|I] = \left[ \begin{array}{ccc|ccc} 1 & -1 & -1 & 1 & 0 & 0 \\ 2 & -1 & -3 & 0 & 1 & 0 \\ -3 & 4 & 4 & 0 & 0 & 1 \end{array} \right]$$

   其次，通过初等行变换将 $A$ 变成单位矩阵，同时将 $I$ 变成 $A^{-1}$。

   • 将第二行减去第一行的两倍，将第二行的第一个元素变为 0 $R2 = R2 - 2R1$
   • 将第三行加上第一行的三倍，将第三行的第一个元素变为 0 $R3 = R3 + 3R1$

   $$\left[ \begin{array}{ccc|ccc} 1 & -1 & -1 & 1 & 0 & 0 \\ 0 & 1 & -1 & -2 & 1 & 0 \\ 0 & 1 & 1 & 3 & 0 & 1 \end{array} \right]$$

   • 将第三行减去第二行，将第三行的第二个元素变为 0 $R3 = R3 - R2$

   $$\left[ \begin{array}{ccc|ccc} 1 & -1 & -1 & 1 & 0 & 0 \\ 0 & 1 & -1 & -2 & 1 & 0 \\ 0 & 0 & 2 & 5 & -1 & 1 \end{array} \right]$$

   • 将第三行乘以 1/2，将第三行的第三个元素变为 1 $R3 = \frac{1}{2}R3$

   $$\left[ \begin{array}{ccc|ccc} 1 & -1 & -1 & 1 & 0 & 0 \\ 0 & 1 & -1 & -2 & 1 & 0 \\ 0 & 0 & 1 & \frac{5}{2} & -\frac{1}{2} & \frac{1}{2} \end{array} \right]$$

   • 将第二行加上第三行，将第二行的第三个元素变为 0 $R2 = R2 + R3$
   • 将第一行加上第三行，将第一行的第三个元素变为 0 $R1 = R1 + R3$

   $$\left[ \begin{array}{ccc|ccc} 1 & -1 & 0 & \frac{7}{2} & -\frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 & \frac{5}{2} & -\frac{1}{2} & \frac{1}{2} \end{array} \right]$$

   • 将第一行加上第二行，将第一行的第二个元素变为 0，使第一行最终成为单位矩阵的一部分 $R1 = R1 + R2$

   $$\left[ \begin{array}{ccc|ccc} 1 & 0 & 0 & 4 & 0 & 1 \\ 0 & 1 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 & \frac{5}{2} & -\frac{1}{2} & \frac{1}{2} \end{array} \right]$$

   此时，左边的 $A$ 已经变成单位矩阵，右边的单位矩阵被变成了 $A^{-1}$。

   通过初等行变换逐步消去非对角线元素，使对角线元素变为 1，从而最终将 $A$ 化为单位矩阵。这些行变换同时应用于右边的单位矩阵 $I$，最终右边的矩阵变成了 $A$ 的逆矩阵 $A^{-1}$。

   所以，逆矩阵 $A^{-1}$ 是：

   $$A^{-1} = \begin{pmatrix} 4 & 0 & 1 \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{5}{2} & -\frac{1}{2} & \frac{1}{2} \end{pmatrix}$$

4. 不定积分

   1. 若 $f(x) = \int_x^2 e^{-t^2} \, dt$，则 $f'(x) =$ ？
   2. 若 $f(x) = \int_0^x tf(t) \, dt$，求 $f'(x) =$ ？

   1. 若 $f(x) = \int_x^2 e^{-t^2} \, dt$，则 $f'(x) =$ ？

   这题涉及到微积分基本定理中的一个重要公式。如果我们有一个函数 $F(x) = \int_a^x g(t) \, dt$，那么它的导数 $F'(x)$ 就是被积函数 $g(x)$。具体的公式是：

   $$\frac{d}{dx} \left( \int_a^x g(t) \, dt \right) = g(x)$$

   但是，这题稍微复杂一些，积分的上限是一个常数（2），而下限是变量 $x$。我们可以用微积分基本定理中的一个变式来解决这个问题。如果我们有：

   $$F(x) = \int_{u(x)}^{v(x)} g(t) \, dt$$

   其中 $u(x)$ 和 $v(x)$ 是两个关于 $x$ 的函数，那么 $F(x)$ 的导数是：

   $$F'(x) = g(v(x)) \cdot v'(x) - g(u(x)) \cdot u'(x)$$

   对于这题，$u(x) = x$ 而 $v(x) = 2$，所以 $u'(x) = 1$，而 $v'(x) = 0$（因为 2 是常数，对 2 求导数是 0）。

   我们将函数 $f(x)$ 写成：

   $$f(x) = \int_x^2 e^{-t^2} \, dt$$

   那么，根据上述变式公式，我们得到：

   $$f'(x) = e^{-2^2} \cdot 0 - e^{-x^2} \cdot 1 = -e^{-x^2}$$

   所以，

   $$f'(x) = -e^{-x^2}$$

   2. 若 $f(x) = \int_0^x tf(t) \, dt$，求 $f'(x) =$ ？

   这题也涉及到微积分基本定理。我们有：

   $$f(x) = \int_0^x t f(t) \, dt$$

   根据微积分基本定理，假设 $F(x) = \int_a^x g(t) \, dt$，那么 $F(x)$ 的导数是 $g(x)$，即：

   $$\frac{d}{dx} \left( \int_a^x g(t) \, dt \right) = g(x)$$

   对于这题，$g(t) = t f(t)$，所以 $f(x)$ 的导数是：

   $$f'(x) = x f(x)$$

   总结：

   • 对于第一个问题，$f(x) = \int_x^2 e^{-t^2} \, dt$，则 $f'(x) = -e^{-x^2}$。
   • 对于第二个问题，$f(x) = \int_0^x t f(t) \, dt$，则 $f'(x) = x f(x)$。