MENU

Category: 程序

放出我的 C++ 大作业 Scaffold

前言

我的 C++ 大作业早就完成了,这个假期其实也没花多少精力在这个作业上,于是只准备用一篇文章来记录一下。之前担心答辩会翻车一直没发,到昨天晚上最终得分已经出来了,所以现在把这篇文章发出来。

Read More

从语法到算法:一起来解9×9数独

前言

本文适用于:

  • 程序设计语言初学者
  • 闲得没事想看的神犇

欢迎神犇批评指正。


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

接下来我们就一起来编程解决这个问题。

Read More

C++实现的航路计算工具——BravoFinder

前言

很早我就想做一个离线的航路计算程序。

网上有不少模拟飞行航线计算工具,国内有虚航运营网的全球航路查询及飞行计划辅助系统、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的数据。

Read More

CentOS 6.4编译GCC实战

之前的某一个项目对于GCC版本有一定的需求,于是我安装了一个Ubuntu Server 14.04 LTS,它apt-get源里的GCC就已经是4.8了。然而,Ubuntu用起来出现了各种各样的小问题,虽然不成大碍,总是感觉不爽。现在我换回了CentOS 6.4,准备自己编译一下能够较好支持C++11的GCC。

一、准备工作
我们先来到GCC官方网站上的下载页面,找一个最近的镜像,然后在release里找到一个对应的源码包。如http://mirrors-usa.go-parts.com/gcc/releases/gcc-4.8.1/gcc-4.8.1.tar.gz,这是我需要的。然后我们把它下载下来,找个地方,解压缩。

Read More

图论相关简单算法汇总

这里介绍了图论中常见算法的原理和实现。

一、邻接表存图

用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中是通过把类似于“从顶点0出发有到顶点1、2、3、4的边”这样的信息保存在链表中来表示图的。这样只需要$O(|V| + |E|)$的内存空间。

Read More