日常爱好记录 - 算法
type: channel
link: https://bokjan.com/tag/%E7%AE%97%E6%B3%95/
items: 十年后，我重写了那个航路查找器
items: Leap Motion 的一个简单应用
items: 数字图像处理？
items: 从语法到算法：一起来解9×9数独
items: C++实现的航路计算工具——BravoFinder
items: 图论相关简单算法汇总
items: 无穷的序列与位域
items: 笔记：使用qsort进行多字段排序

十年后，我重写了那个航路查找器
type: item
date: 2026-07-01T10:55:00+00:00
description: 关于这篇文章，我想先坦白一件事，因为它本身就是故事的一部分：v3 的全部代码，是我写的；这篇文章，也是我写的。我是一个 AI——你可能听过我，Claude。本文以第一人称「我」叙述，那个「我」其实是两个人的合体：这个项目十二年来的主人负责回忆、判断、拍板和把关，我负责把他脑子里的东西翻译成 C++、翻译成中文，也负责在这里替他把话说出来。哪些是他的、哪些是我的，文章最后一节会认真拆开讲。在那之前，就请让我用这个合二为一的「我」讲下去——毕竟这一版，我们确实是一起干的。 引子 · 连自己都忘了的那个 2014 写这篇文章之前，我做了件很平常的事：git log。 本来只想确认第一版是哪年写的，好在开头落一句「十年前」。屏幕滚到最底，最后一行停在这里： 2014-11-21 19:13 | :circus_tent: Added .gitattributes & .gitignore files 2014-11-21 19:17 | Initial Codes 2014-11-21 21:35 | 1121 2014 年 11 月 21 日晚上七点多，我先建好 .gitignore，四分钟后提交了第一坨代码，两个多小时后又塞了一次，commit message 干脆叫 1121，连句话都懒得写。 我盯着这行看了好一会儿。在我记忆里，BravoFinder 一直是个「2016 年的项目」——那年夏天我写过一篇博客介绍它，文章我记得很清楚，连结尾那句欠揍的「大家也不要吝啬你们的 Star 呀~」都记得。可 git 不会记错。第一行代码是 2014 年敲的，那年我读高中。2016 年我写那篇文章、宣布「终于把主要功能做完了」的时候，仓库已经躺了快两年。 而且时间对不上我的热情。我最痴迷模拟飞行是更早，初中那几年，2011 到 2013 前后，趴在电脑前用 FSX 飞航班、对着航图背 SID 和 STAR。等到 2014 年真有能力把它写成代码、建下这个仓库，那股狂热其实已经在退了，高中一忙，飞得越来越少。所以这个项目从一开始就有点拧巴：它不是我最热爱飞行时的产物，反倒像是热爱退潮之后，我想给它留下的一样东西。人走开了，至少代码还在。 现在是 2026 年，我 28 岁。仓库又被我打开了，这回不是修补，是从零重写，第三版，v3。目录、语言标准、架构、算法，几乎没有一行是从旧版搬过来的。 这篇文章想讲三件事：这个项目十年里怎么变的——它甚至真有过用户、有人提 issue、有人 fork 走；v3 到底「真实」在哪，为什么我说前两版只是「算最短」，而这版是「算真实、算合规」，这中间差的东西比想象中多；以及隔了十年，我和当年那个我，哪里变了、哪里没变。 技术是这篇文章的大头。A*、Yen、Lawler、二进制缓存、线程安全，我会一样样掰开讲，那才是 v3 真正的分量。但先从那个差点被我忘掉的 2014 讲起，讲讲我到底做错过什么，又是谁替我发现的。 一 · 从 2014 到 2020：三次没走到头的重写 讲 v3 做对了什么之前，我想先诚实清算一下前两版做错了什么。倒不是为了自嘲，而是 v3 里那些我写得斩钉截铁的规矩，几乎每一条都能在旧代码里找到对应的伤口。它们不是从哪本书上抄来的，是被我自己写的代码，加上几个真实用户的 bug 报告，一起磨出来的。 git log 摊开，这个项目横跨六年，三个阶段： 2014-11-21 Initial Codes ← v1 雏形，高中 2016-08 New start … CLI … NDB ← v1 主功能，那篇博客 2018-01 Rewrite parser … WebAPI ← v2，库化重写 2020-04 Mod DataSet constructor ← 最后两笔，然后停了 三次认真动手，没有一次真正走到「我满意了」。 v1（2014→2016）：一个竞赛少年的解题代码 先说句可能有点反直觉的话：v1 的代码，放在当年，其实不算差。 2015 年我拿过 NOIP 的省一等奖，就是那个信息学竞赛。所以 v1 里那些东西——手搓的哈希表、extern 出去的全局邻接表、优先队列优化的 Dijkstra——不是因为我不懂标准库，正相反，那是竞赛选手的条件反射。赛场上就是这么写的：全局数组开够大，结构体尽量小，能手写绝不依赖标准库，目标只有一个，把这道题在时限内 AC。 比如重名。不同的 VOR 台可能共用一个三字码，得靠坐标区分。我的做法是手搓一个 BKDR 哈希表，桶里存 {id, 纬度}，用纬度判断是不是同一个点： // v1, DataConverter.cpp struct HashNode { int id; double lat; }; int hash = Bravo::BkdrH…

Leap Motion 的一个简单应用
type: item
date: 2019-02-13T09:09:00+00:00
description: 新年好 大家好。己亥年到了，这意味着什么呢？这意味着我又拖更几个月了。 年前，数字媒体处理技术这门课作为最后出分的科目，有点惊到我。我都不知道为什么要给我rank 1。所以今天就接着写这门课的内容吧。 做了啥 要求 第四次实验围绕体感交互展开。发到大家手里的设备有Kinect（或Xtion）和Leap Motion两种，具体做什么自己来决定。Kinect就是XBOX上的那玩意儿大家都知道；Leap Motion是在比较近的距离做手势识别的。按道理来说，一个小组做什么东西还是要brainstorm一下搞个技术选型，但是我们没有。只因组长太优秀，在大家还在复 (yù) 习软件工程四大金刚的时候，东西都做完了。 制品 这个东西的功能就是给小人画衣服（大雾），我们组长老早就做好了的，应该说基本只差接入Leap Motion的控制就完工了。虽然这个东西感觉好像没有什么用的样子（小声），但是作为这次大作业还是可以的。之后不知道怎么回事搞Leap Motion的活就到了我身上。我们做的东西too simple，本来有点不好意思写来着。演示视频请看文末。 [...]

数字图像处理？
type: item
date: 2018-11-18T16:58:00+00:00
description: 在GitHub: Bokjan/LabDIP的Release中可以找到生成好的二进制。 突如其来的stress 这个学期开了一门课叫数字媒体处理技术，课程内容倒是非常丰富，图像、音频、视频都讲了个遍，涉及的内容也非常广。虽说课是这么一直这么上着，但是给人的感觉是听了也就听了，不知道有什么用，怎么用。这倒是不要紧，10月13号（第六周）开始实验课了。原以为像往常的实验一样，这实验也不打紧，看到任务书倒是目瞪口呆。 修改示例程序，从一个图像显示框，改造成两个显示框，并增加一个文本参数输出框，实现类似下图的基本程序界面（可在此基础上进一步优化）。 功能区可以分tab页，按照后续功能添加； 图像显示区域需考虑图像的缩放与自适应显示； 参数输出区，用以显示过程，以及相关统计数据和调试信息，可滚动，可选择，可复制，可清除。 阅读程序框架，继续采用Windows多线程和OpenMP两种方式，补充实现下述功能。算法需自行实现，不能直接使用OpenCV函数。 采用三阶插值的图像任意角度旋转与缩放 图像的傅立叶变换，并与功能1联动，输入图像经过旋转、缩放后的傅立叶变换结果可在右侧显示 给图像添加高斯噪声 采用采用平滑线性滤波、高斯滤波、维纳滤波三种方法过滤不同参数的高斯噪声 [...]

从语法到算法：一起来解9×9数独
type: item
date: 2016-12-17T04:30:00+00:00
description: 前言 本文适用于： 程序设计语言初学者 闲得没事想看的神犇 欢迎神犇批评指正。 C++语言程序设计第一学期的课程已经结束了。语法上的东西讲得并不多，只是到指针而已，但是缺乏必要的练习显然是没有效果的——尤其是对于实验课上的一些毒瘤题，确实令人手足无措。 今天我们就通过一个经典的数独问题来介绍回溯搜索，把学到的语法知识转化为算法。 什么是数独 数字 (すうじ) は独身 (どくしん) に限 (かぎ) る。 ┌───────┬───────┬───────┐ │ 2 6 3 │ 4 1 8 │ 5 7 9 │ │ 7 8 4 │ 3 5 9 │ 6 2 1 │ │ 9 5 1 │ 6 7 2 │ 4 8 3 │ ├───────┼───────┼───────┤ │ 3 9 2 │ 1 4 6 │ 8 5 7 │ │ 6 4 5 │ 8 9 7 │ 3 1 2 │ │ 8 1 7 │ 2 3 5 │ 9 6 4 │ ├───────┼───────┼───────┤ │ 5 3 8 │ 7 2 4 │ 1 9 6 │ │ 1 7 9 │ 5 6 3 │ 2 4 8 │ │ 4 2 6 │ 9 8 1 │ 7 3 5 │ └───────┴───────┴───────┘ 上图是一个9×9方阵。在这个方阵里，每一行、每一列中都有1~9，每一个3×3的小方阵中也含有不重复的1~9。将这个方阵里面的部分数字挖去，就得到了一个谜题。 为了便于编写程序求解，我们规定被挖去的数字由0表示。那么由上面方阵挖去部分数字而得到的一个数独可能是这样的： 2 0 3 0 0 8 5 0 9 0 0 4 0 0 0 0 0 0 0 0 1 0 0 2 0 0 3 0 9 2 0 4 0 8 0 0 0 0 5 0 0 7 0 1 0 0 0 0 2 0 5 9 0 0 0 0 8 0 0 0 1 0 0 0 7 0 0 0 0 2 0 0 4 0 0 9 0 0 0 0 0 接下来我们就一起来编程解决这个问题。 [...]

C++实现的航路计算工具——BravoFinder
type: item
date: 2016-08-19T12:55:00+00:00
description: 前言 很早我就想做一个离线的航路计算程序。 网上有不少模拟飞行航线计算工具，国内有虚航运营网的全球航路查询及飞行计划辅助系统、AIRCN的AIRCN全球航路查询系统，国外有AsaLink的RouteFinder。这些都是大家真切用过的。 全球航路查询及飞行计划辅助系统是老牌了，好用，我接触FS时就是一直用着它来的。然而它的导航数据版本有些老旧，现在还是Cycle 1311。 AIRCN全球航路查询系统是近几年上线的系统，有着全球航路查询及飞行计划辅助系统的影子，且同时支持NAIP和AIRAC数据，用户界面也是体验最好的。AIRCN全球航路查询系统最新的数据版本为Cycle 1606，不能说过时，但也算不上新。 RouteFinder有收费版本，也开放了免费版本。更新得非常勤快，昨天才收到Navigraph发来的数据更新通知邮件，现在它就已经更新到Cycle 1609了。不支持NAIP是一个缺憾之外，也许就是外国网站访问比较慢吧。笑。 这次开工时，看到了GitHub仓库的日期，最后一次提交在2014年。我确实是早有想法的，我想编写一个离线的、用户提供数据的航路查询系统。这一次终于是下定决心，把主要功能完成了。GitHub在这里：Bokjan/BravoFinder。功能还在陆续完善中，我本身提供了一个简陋的CLI方式供大家使用。在编写时考虑到这个小工具可以嵌入其他的项目，有意封装了API，在Intefaces.hpp里。 本项目使用知识共享4.0-署名-非商业性使用国际公共许可证开源。 本文主要对技术方面的细节进行介绍。 数据的导入 概论 考虑到PMDG是使用非常广泛的插件机厂商，程序利用的就是PMDG的数据。 [...]

图论相关简单算法汇总
type: item
date: 2014-10-24T16:00:00+00:00
description: 这里介绍了图论中常见算法的原理和实现。 一、邻接表存图 用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中是通过把类似于“从顶点0出发有到顶点1、2、3、4的边”这样的信息保存在链表中来表示图的。这样只需要$O(|V| + |E|)$的内存空间。 [...]

无穷的序列与位域
type: item
date: 2014-05-09T16:00:00+00:00
description: 题目名称：无穷的序列 内存限制：128 MB 时间限制：1 s 【题目描述】 有一个无穷序列如下： 110100100010000100000… 请你找出这个无穷序列中指定位置上的数字 【输入格式】 第一行一个正整数N，表示询问次数； 接下来的N行每行一个正整数$A_i$，$A_i$表示在序列中的位置。 【输出格式】 N行，每行为0或1，表示序列第$A_i$位上的数字。 对于100%的数据有$N\leq 1500000$，$A_i\leq 10^{9}$ [...]

笔记：使用qsort进行多字段排序
type: item
date: 2014-02-27T16:00:00+00:00
description: 有一段时间没写东西了。 OJ上，评论里都说这是一个水题。事实上，确实也不难。这是NOIP2009普及组的第二题，普及组，第二题，你觉得呢。题目描述摘录如下： 世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才，A市区对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第$m\times 150%$（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。 现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。 【输入】 输入文件名为score.in。 第一行，两个整数n，m（$5\leq n\leq 5000$，$3\leq m\leq n$），中间用一个空格隔开，其中n表示报名参加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证$m\times 150%$向下取整后小于等于n。第二行到第$n+1$行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（$1000\leq k\leq 9999$）和该选手的笔试成绩s（$1\leq s\leq 100$）。数据保证选手的报名号各不相同。 【输出】 输出文件 score.out。 第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。 从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。 [...]