main.tex

\documentclass[a4paper]{ctexbook}
\usepackage[dvipsnames]{xcolor}  % 扩展颜色支持
\usepackage{listings}  % 代码高亮宏包
\usepackage[hidelinks]{hyperref}
\usepackage{graphicx}
\usepackage{caption}   % 控制标题格式 (可选) 
\usepackage{float}     % 提供 [H] 固定位置选项 (可选) 

\usepackage[
    a4paper,       % 保持纸张类型不变
    left=2.5cm,       % 减小左边距
    right=2.5cm,      % 减小右边距
    top=2.5cm,      % 上边距
    bottom=2.5cm,   % 下边距
    includeheadfoot % 包含页眉页脚在边距内
]{geometry} % 引入页边距控制宏包

% 自定义C++高亮风格
\lstdefinestyle{MyCStyle}{
    % 基础样式
    language=C++,               % 使用C++语法规则(C语言兼容)
    basicstyle=\ttfamily\small, % 基础字体
    backgroundcolor=\color{gray!5}, % 背景色
    frame=single,                % 边框样式
    framesep=3pt,               % 边框内边距
    rulecolor=\color{black!30}, % 边框颜色
    % 行号设置
    numbers=left,               % 左侧行号
    numberstyle=\tiny\color{gray}, % 行号样式
    stepnumber=1,               % 每行显示行号
    numbersep=8pt,              % 行号与代码间距
    % 代码换行
    breaklines=true,            % 自动换行
    % breakatwhitespace=true,     % 只在空格处换行
    postbreak=\mbox{\textcolor{red}{$\hookrightarrow$}\space}, % 换行标记
    tabsize=4,                  % 制表符等效空格数
    showstringspaces=false,     % 字符串中不显示空格
    % 语法高亮颜色定义
    commentstyle=\color{ForestGreen}\itshape, % 注释样式
    keywordstyle=\color{blue}\bfseries,       % 关键字样式
    stringstyle=\color{red},                   % 字符串样式
    directivestyle=\color{purple}\bfseries,    % 预处理指令
    identifierstyle=\color{black},              % 标识符样式
    % 特殊字符高亮
    literate=*                  % 特殊字符处理
        {0}{{{\color{magenta}0}}}1
        {1}{{{\color{magenta}1}}}1
        {2}{{{\color{magenta}2}}}1
        {3}{{{\color{magenta}3}}}1
        {4}{{{\color{magenta}4}}}1
        {5}{{{\color{magenta}5}}}1
        {6}{{{\color{magenta}6}}}1
        {7}{{{\color{magenta}7}}}1
        {8}{{{\color{magenta}8}}}1
        {9}{{{\color{magenta}9}}}1
        {.0}{{{\color{magenta}.0}}}2
        {.1}{{{\color{magenta}.1}}}2
        {.2}{{{\color{magenta}.2}}}2
        {.3}{{{\color{magenta}.3}}}2
        {.4}{{{\color{magenta}.4}}}2
        {.5}{{{\color{magenta}.5}}}2
        {.6}{{{\color{magenta}.6}}}2
        {.7}{{{\color{magenta}.7}}}2
        {.8}{{{\color{magenta}.8}}}2
        {.9}{{{\color{magenta}.9}}}2
}

% C++关键字扩展 (包含C和C++常见关键字)
\lstset{style=MyCStyle,
    morekeywords={  % 添加额外关键字
        alignas, alignof, constexpr, decltype,
        noexcept, nullptr, static\_assert, thread\_local,
        override, final, using, dynamic\_cast,
        const\_cast, reinterpret\_cast, static\_cast,
        template, typename, namespace, explicit,
        inline, noexcept, constinit, consteval,
        concept, requires, co\_await, co\_return,
        co\_yield, char8\_t, char16\_t, char32\_t
    }
}

\begin{document}
\begin{titlepage}
	\centering
	\vspace*{2cm}

	% 封面主图占位符, 可替换为实际图片文件
	% \includegraphics[width=0.5\textwidth]{./blacksimithing.png}\\[1.5cm]

	% 书名与副标题, 中间使用 en-dash
	{\Huge\bfseries 基础算法示例 -- C++实现\par}
	\vspace{2cm}
	% 作者、机构等信息 (可修改) 
	{\Large 作者: Haoming Bai\par}
	\vfill

	% 两个小图占位符
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.6\textwidth]{./ccpc_logo.png}
		% \hspace{1cm}
		% \includegraphics[width=0.2\textwidth]{cover_image3_placeholder}
	\end{figure}
	\vfill

	% 出版日期
	{\large \today\par}
\end{titlepage}

% 目录页
\clearpage
\addcontentsline{toc}{chapter}{目录}
\tableofcontents
\clearpage

% 正文开始
\mainmatter

\chapter{概念}

Concept (概念) 是本 C++ 模板的一项核心概念. "概念"引进于 C++20, 是通过一些限定的组合, 进而约束模板的适用范围, 同时也给代码补全器提供便利. 模板还可以简化报错信息, 将抽象的重载决议简化为条件不满足. 例如在 "Addable" 这个概念出现后, 用户可以知道自己传入的参数类型不满足加法性质, 而不是奇怪地在层层编译器的堆栈展开之后, 发现自己的类型不能满足标准库中的一个奇怪函数. 本章节仅覆盖了最常用的一些基础概念, 一些不够常用的概念会分布在各个章节之中. 在本模板中, 除去AVL树部分由于一些特殊原因, 并未使用概念以外, 所有代码都使用概念进行约束.

\lstinputlisting[language=C++, caption=concepts.cpp, style=MyCStyle]{./concepts.cpp}

\chapter{图论}

图是计算机数据结构中最复杂的结构之一. 图论 (Graph theory) 是数学的一个分支, 图是图论的主要研究对象. 图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形, 这种图形通常用来描述某些事物之间的某种特定关系. 顶点用于代表事物, 连接两顶点的边则用于表示两个事物间具有这种关系.

图分为有向图和无向图, 有向图意味着在一个图中, 所有的边是有方向的. 有向图就像漂流一样, 游客只能顺着水流或者水车, 从水位高的地方去往水位低的地方, 或者从水车从山脚到山顶. 也可以回忆一下高中学到的洋流图, 我至今仍然记得当年学到的, 在南极洲附近的那个西风漂流. 西风漂流应该是只能从西到东, 从东到西就要出事情. 当然, 就像漂流的游客可以从山顶漂到山脚, 也可以从山脚坐水车来到山顶, 在有向图中, 如果存在 A->B, 并不意味着不能存在 B->A. 当然无向图就要简单得多, 就像大多数的城市路网规划一样. 如果你走错了路, 本应该在顾戴路下高架却一路开到了漕宝路, 你也可以原路返回.

这份算法示例中的图全部是有向图, 一些强制需要无向图的算法都是用有向图去模拟的无向图. 因为起草的时间很早, 所以没有使用概念约束, 同时很多算法因为较为常见, 也没来得及编写注释, 还请读者谅解. 不过想到使用这份模板的人算法水平应该远高于我, 所以应该也不需要很详细的解释了.

\lstinputlisting[language=C++, caption=graph.cpp, style=MyCStyle]{./graph.cpp}

\chapter{数据结构}

数据结构是大学计算机专业的第一门专业课, 也是ICPC共同主席, 西北工业大学计算机基础教学中心的副主任姜学锋教授眼中对于算法能力帮助最大的一门课. 常见的在课上会提及的数据结构在 C++ 的标准库中通常都有, 或者存在更好的平替, 那么只要记住 ADT, 然后在编程中使用标准的实现就足够了. 这里关注的是那些不常见的数据结构.

\section{线段树}

线段树是算法竞赛中常用的用来维护区间信息的数据结构. 线段树可以在 $O(\log(N))$ 的时间复杂度内实现单点修改, 区间修改, 区间查询 (区间求和, 求区间最大值, 求区间最小值) 等操作. 线段树存在两种常见的存储方案. 一种是朴素地使用数组存储数据, 然后通过一系列的计算, 维护节点在树中的位置和下标的关系, 这种方法常数小, 但是写起来很复杂, 也不够灵活. 另外一种是使用 "动态开点" 的算法, 使用链式结构的二叉树, 同时使用线性的方法开辟内存空间, 这样就可以简化代码, 同时保证速度. 后一种方案可以把线段树写的很大, 同时可以支持持久化等高阶操作.

\subsection*{朴素线段树}

朴素线段树基于分治思想构建二叉树: 根节点覆盖整个区间, 每个非叶节点递归二分其区间 (左子树 $[l, mid]$, 右子树 $[mid+1, r]$) , 叶节点对应单元素区间. 节点存储区间聚合信息 (如和/最值) , 更新时自底向上回溯修正受影响的节点值, 查询时合并目标区间的分解子区间结果. 其优势在于:
\begin{itemize}
	\item \textbf{高效查询/更新}: 单点更新与区间查询时间复杂度均为 $O(\log n)$
	\item \textbf{结构清晰}: 标准二叉树实现, 逻辑简单易理解
\end{itemize}
主要缺陷包括:
\begin{itemize}
	\item \textbf{区间更新效率低}: 直接更新每个元素需 $O(n \log n)$ 时间
	\item \textbf{空间冗余}: 需 $4N$ 数组存储树结构, 空间复杂度 $O(n)$
\end{itemize}

尽管在正式文件中通常避免附着测试代码, 但为直观展示线段树通过运算符重载实现字符串加法、乘法及最值等聚合功能的灵活性, 此处特别提供了由AI编写的测试类作为补充示例.

\lstinputlisting[language=C++, caption=segment\_tree/simple\_segtree.cpp, style=MyCStyle]{./segment_tree/simple_segtree.cpp}

\section*{可持久化线段树}

与之前介绍的普通线段树不同, 可持久化线段树 (persistent segment tree) 并非在原地修改节点, 而是通过“路径复制”创建一个新的版本, 旧版本仍可保存历史记录. 这意味着每次更新操作仅复制涉及的那条从根到叶的路径节点, 其他未改动的节点被共享使用, 因此可以高效维护多个历史状态, 而普通线段树更新会破坏原结构, 不支持版本回溯.

可持久化线段树常被应用于 "区间第 $K$ 小" 问题: 先对原数组进行离散化, 并为每个前缀 $A[1\dots i]$ 构建一个版本的值域线段树, 每个节点保存该值段在当前前缀下出现的次数. 查询$[l,r]$区间第 $K$ 小, 可视作 $CT[r]–CT[l–1]$ (两版本的减法) 后, 从根节点下行, 查找 $K$ 所在子区间, 从而在 $O(log(n))$ 内得出答案.

至于“主席树” (Chair/Chairman Tree) 这一称呼, 据说其名字源于一位昵称带 "主席" 二字的选手推广此结构, 故后人暂借此称；也有人说是因为其推广者拼音缩写与中国某前国家主席相同, 因此得名. 无论来源如何, 这个名称在中文竞赛圈内被广泛接受, 几乎成了可持久化值域线段树的代名词.

第 $K$ 小数的查询之所以能够高效实现, 关键在于版本树间共享大量节点, 仅针对一个插入或查询路径创建 $O(log n)$ 个新节点, 版本之间的差异小, 既保持了线段树查询的效率, 也支持历史版本的任意访问, 是处理静态区间 $K_{th}$ 问题的经典方案.

\lstinputlisting[language=C++, caption=segment\_tree/persistent\_segtree.cpp, style=MyCStyle]{./segment_tree/persistent_segtree.cpp}

\section{并查集}

并查集 (Disjoint Set Union, DSU) 是一种高效处理集合合并与查询的数据结构, 常用于解决元素分组, 连通性判断等问题. 在算法竞赛中, 它被广泛应用于图论相关题目, 尤其是在处理无向图的连通分量, 最小生成树 (如 Kruskal 算法) 以及等价关系建模中. 例如, 给定若干合并操作与查询操作, 并查集可以在接近常数时间内判断两个元素是否属于同一集合, 极大提升算法效率. 此外, 在图像识别, 网络社群划分, 物理模拟等实际问题中, 并查集也同样展现了其强大的应用价值.

\lstinputlisting[language=C++, caption=dsu.cpp, style=MyCStyle]{./dsu.cpp}

\section{ST表}

ST表是一种很简单的数据结构, 在特定的题目里面比线段树的解法常数小, 因此还是应该掌握. ST表适用于这样一种场景: 可重复贡献的场景下的反复查询. ST表的查询非常快, 可以达到最坏 $O(1)$ 的量级, 但是ST表只能用于那种 $x*x=x$ 的特殊运算, 且不能进行修改.

\lstinputlisting[language=C++, caption=sparce\_table.cpp, style=MyCStyle]{./sparce_table.cpp}

\section{平衡搜索树}

\subsection*{手工实现的B+树}

B+树是一种专为磁盘存储系统优化的多路平衡搜索树, 在现代数据库和文件系统中占据核心地位. 与传统的二叉搜索树不同, B+树通过高度的多路分叉和严格的结构约束, 在维持高效查询性能的同时, 极大地减少了磁盘I/O操作.

B+树的独特设计体现在以下几个关键特性上:

\textbf{多路平衡结构}: 每个节点可以包含多个键值 (通常为数百个) , 形成宽而矮的树形结构. 这种高扇出特性使得即使存储海量数据, 树的高度也维持在很低的水平, 从而保证了稳定的查询效率.

\textbf{数据与索引分离}: 内部节点仅存储键值作为导航索引, 所有实际数据记录都集中在叶子节点层. 这种清晰的职责分离使得索引结构更加紧凑, 能够在内存中缓存更多的索引节点.

\textbf{叶子节点顺序链接}: 所有叶子节点通过双向链表连接成有序序列, 这使得范围查询和全表扫描变得极其高效. 与传统的树结构相比, B+树无需回溯到父节点即可完成顺序访问.

\textbf{稳定的平衡维护}: B+树通过节点分裂与合并来维持平衡, 本实现采用了\textbf{预分裂策略}, 在插入过程中提前检测并处理可能出现的节点溢出, 避免了级联分裂带来的性能波动, 确保了写入操作的稳定性.

在应用层面, B+树凭借其卓越的I/O优化特性, 成为关系型数据库 (如MySQL InnoDB, Oracle) 的标准索引结构, 现代文件系统 (如NTFS, ext4) 也依赖其管理磁盘空间. 此外, 在分布式存储系统和大数据组件中, B+树同样发挥着关键作用.

\lstinputlisting[language=C++, caption=bplus\_tree.cpp, style=MyCStyle]{./bplus_tree.cpp}

\subsection*{AI辅助完成的自平衡二叉搜索树}

AVL树是一种严格自平衡的二叉搜索树. 它通过在普通二叉搜索树的基础上增加额外的平衡信息 (节点高度) 和遵循一组严格的平衡规则 (AVL规则: 任意节点的左右子树高度差绝对值不超过1) , 确保树在动态插入和删除操作后能通过旋转操作自动恢复完美平衡. 这种近乎苛刻的平衡性是其提供最坏情况下高效查询性能的关键保障.

这里提供了一份由我和AI共同完成的AVL树, 可靠性基本有保障, 仅供参考.

\lstinputlisting[language=C++, caption=avl.cpp, style=MyCStyle]{./avl.cpp}

\section{单调队列}
单调队列是一种基于队列的数据结构, 主要的作用是求解固定滑动窗口的最大值/最小值问题. 这种数据结构满足:
\begin{itemize}
	\item 队列内满足单调性
	\item 插入新元素时通过从队尾弹出元素保持单调性
\end{itemize}

本实现还附带了一个滑动窗口最大值的简单实现 (队列单调递减).

\lstinputlisting[language=C++, caption=mono\_queue.cpp, style=MyCStyle]{./mono_queue.cpp}

\section{单调栈}

单调栈和单调队列是同样的原理, 只是和单调队列不同, 它从栈顶弹出元素.

\lstinputlisting[language=C++, caption=mono\_stack.cpp, style=MyCStyle]{./mono_stack.cpp}

\section{二叉堆}

二叉堆是一种基于完全二叉树的数据结构, 它满足堆序性质: 每个节点的值都大于等于或小于等于其子节点的值. 前者称为最大堆 (根节点最大), 后者称为最小堆 (根节点最小). 由于其完全二叉树的特性, 二叉堆通常使用数组实现, 可以高效地支持插入, 删除最大值/最小值等操作, 常用于实现优先队列或堆排序算法. 常见操作的时间复杂度为 $O(log n)$.

\lstinputlisting[language=C++, caption=heap.cpp, style=MyCStyle]{./heap.cpp}

\chapter{散列方法}

如果数据的范围过大, 就需要一些快速方法缩小这个范围. 例如对于1000个自然数-字符串对, 完全可以使用数组存储, 使用下标代表key, 但是如果简单地使用数组, 一旦数据中出现一个1000000000000-"xyz", 那么内存占用就会过大. 这时候, 合适的散列方法就相当重要.

\lstinputlisting[language=C++, caption=hash\_methods.cpp, style=MyCStyle]{./hash_methods.cpp}

\chapter{计算几何}

图形学是计算机的一个重要分支. 在计算机图形学中, 我们常常需要处理图形的构造, 变换与交互, 例如判断两个物体是否相交, 生成可视化模型的边界, 或进行光线追踪渲染. 这些看似图形学的问题, 其背后往往依赖于严密的几何计算逻辑. 计算几何正是处理这类问题的基础学科, 它研究如何通过算法和数据结构来解决几何对象之间的关系与操作, 如求交, 最近点对, 凸包, 半平面交等问题.

计算几何不仅服务于图形学本身, 在机器人路径规划, 地图导航系统, CAD设计, 物理引擎甚至算法竞赛中也发挥着重要作用. 它为图形学提供了强有力的理论与算法支持, 使得我们能以更高效, 更精确的方式处理二维或三维空间中的复杂几何问题.

\section{计算机和的基本方法}

\lstinputlisting[language=C++, caption=geometry.cpp, style=MyCStyle]{./geometry.cpp}

\section{最近点对}

在平面中, 我们经常需要找到两个最近的点. 相比最传统的暴力方法, 即找到所有点对, 并计算出任意两者之间的距离, 一些方法可以大幅度简化计算, 进而有效降低我们的程序的时间复杂度. 本题中, 我们采用了一种分治与合并的方法, 从概率上, 让算法的复杂度降低到 $O(nlog(n))$.

\lstinputlisting[language=C++, caption=nearest\_point\_pair.cpp, style=MyCStyle]{./geometry/nearest_point_pair.cpp}

\section{凸包}
在平面中, 对于一组点, 我们可以找到一个凸多边形, 使得这些点全部在凸多边形的内部或者在凸多边形上, 这样的凸多边形, 就是凸包. 凸包在很多领域都有应用, 包括旋转卡壳等.

\lstinputlisting[language=C++, caption=convex\_hull.cpp, style=MyCStyle]{./geometry/convex_hull.cpp}

\section{旋转卡壳}

旋转卡壳是计算几何中的一个重要部分. 这里笔者提供了一份凸包的直径代码供参考.

\lstinputlisting[language=C++, caption=convex\_diameter\_square.cpp, style=MyCStyle]{./geometry/convex_diameter_square.cpp}

\chapter{字符串}

在计算机系统中, 字符串作为信息的基本载体, 承载着从数据存储到逻辑控制的核心功能. 尤其在类Unix生态中, 诸如\texttt{grep}的文本搜索、\texttt{sed}的流编辑及\texttt{awk}的模式处理等工具, 均构建于高效字符串操作之上, 印证了Knuth「字符串处理是程序设计技术的试金石」的论断.

本章将实现字符串处理中的部分基础算法模板, 涵盖:
\begin{itemize}
	\item 字符串匹配 (单模式/多模式)
	\item 字典树与自动机
\end{itemize}

后续代码模板均以工业级效率为标准设计, 可直接应用于竞赛及工程场景.

\section{模式匹配}

文本模式匹配是信息检索与文本处理的基石, 其效率直接影响搜索引擎响应速度、基因序列分析等关键场景的性能. 以Unix工具链为例, 当\texttt{grep}在GB级日志中检索模式时, 朴素匹配$O(nm)$的时间复杂度将导致灾难性延迟.

本节实现Knuth-Morris-Pratt(KMP)算法模板, 其核心在于:
\begin{itemize}
	\item 通过\textbf{失配函数}预处理模式串($O(m)$)
	\item 实现$O(n)$时间复杂度匹配
	\item 避免回溯的\textbf{状态机跳转}机制
\end{itemize}
代码设计支持动态模式更新与流式数据匹配, 可直接集成至文本处理系统.

\lstinputlisting[language=C++, caption=kmp.cpp, style=MyCStyle]{./str/kmp.cpp}

\section{字典树}

字典树 (Trie) 作为高效处理字符串集合的树形数据结构, 在搜索引擎自动补全、拼写检查及路由协议中具有不可替代性. 其核心优势在于:
\begin{itemize}
	\item \textbf{前缀共享}: 具有公共前缀的字符串共享存储路径
	\item \textbf{检索加速}: $O(L)$时间完成键查询 ($L$为键长)
	\item \textbf{字典序遍历}: 天然支持按字典序访问所有键
\end{itemize}

本节实现基于数组的双版本Trie模板, 部分支持字符串的删除.

\lstinputlisting[language=C++, caption=trie.cpp, style=MyCStyle]{./str/trie.cpp}

\section{AC自动机}

AC自动机 (Aho-Corasick automaton) 是一种高效的多模式匹配算法, 用于在文本中同时查找多个关键词的出现位置. 其核心结构基于\textbf{Trie树}, 并通过添加\textbf{失败指针} (failure links) 实现快速状态转移.
当匹配失败时, 算法沿失败指针回溯, 避免重复比较, 保证$O(n+m+z)$的时间复杂度 ($n$为文本长度, $m$为模式串总长, $z$为匹配次数). 该算法广泛应用于敏感词过滤, 生物序列分析等领域.

\lstinputlisting[language=C++, caption=aho\_corasick.cpp, style=MyCStyle]{./str/aho_corasick.cpp}

\section{后缀数组}

后缀数组(\textit{Suffix Array, SA})是一种存储字符串所有后缀按字典序排列索引的数据结构. 给定长度为$n$的字符串$S$, 其对应的后缀数组$SA[i]$表示字典序第$i$小的后缀起始下标. 该结构在生物信息学中用于DNA序列快速比对 (如BLAST工具), 在数据压缩中支撑Burrows-Wheeler变换 (BZIP2核心), 并在全文搜索引擎中实现高效的子串匹配 (如Lucene库).

SA-IS算法是一种线性时间构建后缀数组的诱导排序算法. 其核心思想是:
\begin{enumerate}
	\item \textbf{分类}: 将字符分为\textbf{L型} (字典序大于后继) 和\textbf{S型} (小于或等于后继), 标记特殊\textbf{SMS型}子串.
	\item \textbf{递归}: 提取SMS型子串并递归生成子串后缀数组.
	\item \textbf{诱导}: 通过子串SA诱导排序L型后缀,再进一步诱导排序S型后缀.
\end{enumerate}
该算法时间复杂度为$O(n)$, 空间效率优于后缀树, 适用于大规模文本处理 (如基因组序列分析).

\lstinputlisting[language=C++, caption=suffix\_array.cpp, style=MyCStyle]{./str/suffix_array.cpp}

\section{最长回文子串}

最长回文子串问题是指: 在一个字符串中寻找其中最长的对称子串. 换句话说, 这个子串正着读和反着读完全相同.

对于最长回文子串问题, 一种朴素的解法是枚举中心并向两边扩展, 或者使用其它动态规划的方法, 但是这些方式在字符串较长时往往会遇到效率瓶颈.

Manacher算法是一种在线性时间内解决最长回文子串的算法. 它通过在原始字符串中插入分隔符并利用回文的对称性, 避免了重复计算, 将复杂度降低到$O(n)$. 这种高效性使得它不仅是理论研究的成果, 也在一些实际场景中得到了应用. 例如, 在DNA序列分析中寻找对称片段, 在自然语言处理里发现对称的语言结构, 以及在数据压缩中利用回文模式进行优化等.

\lstinputlisting[language=C++, caption=manacher.cpp, style=MyCStyle]{./str/manacher.cpp}

\chapter{数值方法}

在生产实践中, 尤其是大型工业软件的开发过程中, 数值计算的速度和精度通常和软件的运行效率息息相关. 在数学建模, 仿真, 有限元分析等领域, 使用精度高, 效率高的算法通常可以使程序的性能, 比使用低效算法的相同程序提升十倍甚至百倍. 而在生产环境, 微不足道的浮点误差可以造成惨重的人员和财产损失. 由此观之, 在建设中国式现代化的过程中, 为了解决工业软件领域的 "卡脖子" 难题, 提升数值计算的效率是非常重要的一环. 而掌握正确的计算方法, 则是每一位立志成为 "总师型人才" 的计算机专业学生的必修课. 下面笔者将提供一些简单常用的数值计算方法的实现以供参考, 所有代码都配备详尽注释, 力求通俗易懂, 方便移植改造.

\section{辛普森法}

辛普森法是一种常用的数值积分方法, 它的原理是利用二次插值多项式在小区间上近似被积函数, 从而得到定积分的近似值.

然而, 当积分区间较大或被积函数变化复杂时, 单一的辛普森公式往往难以保证精度. 为此, 可以采用复化辛普森法: 将积分区间划分为若干个小区间, 在每个小区间分别应用辛普森公式, 然后将结果加总.这样虽然提高了精度, 但由于分块数目固定, 可能会在函数比较平滑的区间上产生不必要的计算.

自适应辛普森法则通过递归的方式在尽可能少分块的前提下保证精度. 它先在整个区间上应用一次辛普森公式, 再将区间一分为二分别应用辛普森公式, 并比较两者结果.如果二者差异超过误差容许范围, 就继续对子区间递归分裂; 否则接受结果.这样, 自适应辛普森法能够在函数平滑的区域少分块, 在函数变化剧烈的区域多分块, 从而兼顾效率和精度.

在现实应用中, 辛普森法和自适应辛普森法被广泛用于工程与科学计算. 例如, 在航天工程中进行复杂气动力模型的积分估算, 在医学成像中计算复杂函数的积分, 或在金融工程中估算涉及不规则函数的积分问题.

\lstinputlisting[language=C++, caption=asr.cpp, style=MyCStyle]{./numeric/asr.cpp}

\section{快速傅里叶变换}

快速傅里叶变换 (FFT) 是一种高效计算离散傅里叶变换 (DFT) 的算法. 它的主要作用是将信号从时域转换到频域, 从而便于分析信号的频率成分. FFT显著降低了计算复杂度, 从$O(n^2)$降至$O(n \log n)$, 因此在信号处理, 图像处理, 音频分析和数据压缩等领域得到广泛应用.

\lstinputlisting[language=C++, caption=asr.cpp, style=MyCStyle]{./numeric/fft.cpp}

\end{document}