Gauss-Legendre 和 Gauss-Lobatto 积分表计算
在数值计算的编程实践中经常需要获取 Gauss-Legendre 和 Gauss-Lobatto 积分点和权重， 除了直接打表，还可以利用 Legendre 多项式自身的特点和牛顿迭代法通过高效的数值计算获得相应的积分点和权重，这也是本文关注的内容。 本文的主要动机是对下面两份 MATLAB 代码的学习和解释： Legendre-Gauss Quadrature Weights and Nodes Legende-Gauss-Lobatto nodes and weights 基本概念 Gauss 型数值积分 首先需要介绍一些关于 Gauss 型数值积分的基本内容。 对于标准积分区间 \([-1,1]\) 的如下形式的数值积分公式： \[ I(f) = \int_{-1}^1 f(x)\,dx \approx I_n(f) = \sum_{i=1}^n w_i f(x_i) \] 其中节点 \(x_i \in [-1,1]\)。这些节点和权重的选取有一共 \(2n\) 个自由度，至多可以达到 \(2n-1\) 阶的代数精度。如果加上某些额外的约束条件，则可达到的最优代数精度也...
LeetCode 42. 接雨水
刷到一个笑话：字节跳动员工是不是个个都会接雨水。顺便记录一下这道题吧。 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 1234输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 显然需要算出接满水之后的状态数组，即每一个位置的水面高度，然后减掉原本的柱子高度，对数组求和即可。 如何计算水面高度： 如果当前位置的高度大于左右两侧的高度，那么该位置的水面高度就是当前位置的高度，其实就是没有接水； 如果当前位置的高度小于左右两侧的高度，那么该位置的水面高度就是左右两侧的高度中的最小值。 所以问题归结于计算当前位置左侧的最高高度和右侧的最高高度，两次遍历即可。 12345678910111213141516171819202122232425262728class Solution {public: int trap(vector<...
密码学笔记——RSA算法
整理一下RSA算法的内容，主要参考维基百科。 对称加密与非对称加密 首先从对称加密开始，Alice和Bob需要进行加密的通信，Alice传递信息 \(m\) 给Bob。 为了信息安全，Alice首先用字母表替换的方式 \(A\) 将明文m变成密文 \(m'=f_A(m)\)，然后通过公开方式传递给Bob，Bob使用同样约定好的字母表替换方式 \(A\) ，将收到的密文 \(m'\) 变成明文 \(f_A^{−1}(m')=f_A^{−1}(fA(m))=m\) 。 这里我们对信息都视作字符串，从而字母表替换规则 \(A\) 实际上定义了字符串到字符串的加密函数 \(f_A\) 和解密函数 \(f_A^{−1}\) ，这里加密函数和解密函数都是通过 \(A\) 决定的，并且极容易从其中一个推出另一个，因此双方都必须保管好密码本 \(A\) 。 例如，使用替换的字母表 \(A\) 为 11->3， 2->4， 3->2， 4->1 用轮换的记号就是\((1324)\)，此时的加密函数 \(f_A\) ，明文\(1234\)，密文 \(f...
C 语言练习——实现终端进度条
记录一下通过C语言实现在终端中展示进度条的动画效果，代码同时支持 Linux 和 Windows。 头文件 pbar.h 内容如下 12345678910111213141516#ifndef PBAR_H#define PBAR_H#ifdef __cplusplusextern "C" {#endifstruct pbar *pbar_create(int style); // style: 0,1,2,3void pbar_update(struct pbar *pb, double pct);double pbar_time_cost(struct pbar *pb);#ifdef __cplusplus}#endif#endif // PBAR_H 这里导出的接口同时支持 C 和 Cpp。 具体实现的源文件 pbar.c 内容如下 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
Docsify 搭建记录
需要一个小型的在线文档系统，Docsify可以满足需求，记录一下搭建记录，主要 Docsify官方的中文文档。 本地搭建 前提：本地需要安装 nodejs 并完成相应配置。 新建DocBase/文件夹，在其中本地安装 docsify-cli 1npm i docsify-cli -g 由于 docsify-cli 不是全局安装的，存在找不到 hexo 命令的问题，对于 Windows 可以通过临时添加路径到 PATH 解决，在 DocBase 目录下执行 1$env:Path += ";$((Get-Item -Path .\node_modules\.bin -Force).FullName)" 初始化项目 1docsify init ./docs 初始化过程会自动新建./docs子文件夹，并生成如下文件： index.html：项目入口 README.md：内容会被渲染成项目主页 .nojekyll：防止Github忽视下划线开头文件 使用下面的命令可以在本地预览 123cd ./docsdocsify serve# or docsify s ...
Cpp 基础笔记整理
一些零散的不同主题的 Cpp 基础笔记，单独拆开显得内容太少，干脆整理到一起。 类型别名 typedef typedef是用于为类型定义别名的关键字，在C和C++中都可以使用。 最简单的用法是对基本类型起别名，例如 1typedef int Length; 下面的是MSVC的stdint.h中的部分源码，对基本数据类型起了意义更明确的别名 12345678typedef signed char int8_t;typedef short int16_t;typedef int int32_t;typedef long long int64_t;typedef unsigned char uint8_t;typedef unsigned short uint16_t;typedef unsigned int uint32_t;typedef unsigned long long uint64_t; 数组类型和指针类型可以通过typedef起别名达到简化语法和提升可读性...
Linux 学习笔记：控制台，终端，tty
整理一下关于下面这些概念的学习： 终端（terminal） 控制台（console） 电传打字机 tty（teletype） 这些概念在早期是有明确的定义的，但是随着计算机的发展，它们的物理实体逐渐消失，各种概念主要靠计算机软件模拟，它们之间的区别变得模糊难以理解，因此学习整理一下，以Linux系统为主。 TODO shell 控制台与终端 早期的计算机是一套巨大的机器，就像工厂的大型机器一样，如此的庞然大物必然需要一个专门的操作台， 用于陈列各种仪表盘、指示灯、按钮、电线，专业操作人员通过这个操作台控制计算机的启动、运行、停止，结果也会实时反馈到操作台，这个操作台就叫“控制台”（console）。 控制台是附着在机器上的设备，可以实现对计算机的完全操控，但是主要是用来管理计算机的。 对于多用户操作系统（特别是UNIX），控制台并不方便给用户提供计算服务。 因此自然产生了终端（terminal）的硬件概念：每个用户通过终端设备与主机远程连接（还不是现代意义上的基于互联网的远程连接），管理员给每个用户分配一个账户，用户“登录”到系统获得计算机使用权。在这个阶段，计算机通常只...
Cpp 并行计算学习笔记
基本概念 首先学习几组基本概念： 并发（Concurrency）/并行（Parallelism） 同步（Synchronous）/异步（Asynchronous） 进程（Process）/线程（Thread） 并发 / 并行 并发指的是多个任务在同一时间段内被同时推进，可能是同时执行不同的任务，也可能是频繁交替执行每一个任务的一小部分 并行指的是多个任务在同一时间段内真正同时执行 举个例子： 学生在课后可以并发地完成每一个科目的作业：一会写语文作业，一会又切换回写数学作业，切换可以非常频繁，但是不可能同时写两科作业，也就是不能并行 人体的消化系统的任务和循环系统的任务在并行地执行：在同一时间内，肠道蠕动和血液循环在同时进行，不可能说心脏跳动时就让肠道蠕动暂停 同步 / 异步 同步是指任务按照顺序依次执行，每个任务在前一个任务完成后开始执行。在同步模式中，任务之间需要等待其他任务完成才能继续执行。 异步是指任务可以独立于其他任务进行执行，它们的执行过程不会产生堵塞。在异步模式中，任务可以在后台执行，执行结果可能需要等待一段时间才能获得，但这不会影响其他任务的执行。 ...
GCC 源码编译安装（离线，普通用户）
gcc 的非 root 用户离线编译安装比其他的软件的源码安装都要复杂：因为它有依赖，在服务器上无法通过联网下载，要提前下载依赖的压缩包，而且gcc的编译时间很长。 安装过程主要参考CentOS7 离线升级安装gcc到6.3.0 和Linux 非root安装GCC9.1.0 下载依赖 在官网或者镜像网站下载 gcc-11.4.0.tar.gz，传到服务器上解压为~/tmp/gcc-11.4.0 进入~/tmp/gcc-11.4.0子目录，需要解决下载依赖的问题。在可以联网的情况下，直接执行自带的下载依赖的脚本 ./contrib/download_prerequisites。如果服务器无法联网，则需要手动下载处理 查看上述脚本，找到四个必要的依赖 gmp,mpfr,mpc,isl 以及对应的具体版本，例如 gcc-11.4.0 需要的四个依赖版本及其下载地址如下（不同版本的gcc对应的依赖版本也不一样） 123456gmp='gmp-6.1.0.tar.bz2'mpfr='mpfr-3.1.6.tar.bz2'mpc='mpc-...
Cpp 面向对象——成员函数中的 this
整理一下关于C++类的成员函数所拥有的特殊的this指针的知识，并且学习C++23中的新内容：显式推导this。 隐式this 基础 this指针是C++面向对象编程中的重要机制，在自定义类型的非静态成员函数中，都存在这一个自动传递的this指针指向当前对象自身，例如 12345678910111213#include <iostream>struct Test { int data = 0; void call() { std::cout << "call: " << data << "\n"; }};int main() { Test test{1}; test.call(); return 0;} 对于编译器来说，这里的定义和调用过程等效于下面的形式（因为this是关键词，在代码中使用this_来代表） 1234567891011121314#include <iostre...