[coding]JustCengIt
实用小软件，恶搞无极限！:-P

gTerm 0.2也搞定了，支持自动发帖和快速连接POP3，字体也调了一下。现在支持退格和方向键了。
 
 

 

以后可以用自己的terminal啦。工作基本正常。可以连80端口取HTTP服务，可以连110POP3，可以连23Telnet，其他没试。Telnet还不支持NVT，只是简单的跳过了它的信息。

HTTP：

POP3：

Telnet：
”支持“NVT前：

”支持“NVT后：

诶~编程真是个好东西~ 

写了十几年的程序蓦然发现转了一圈又回来了……写的什么狗屁东西……

不过这也意味着我的gTerm有望啦啊哈哈哈哈哈~

大话“20 世纪10大算法”
（本文为转载，原文作者柯化成，发表于《程序员》2006年4月号）
本世纪初， 美国物理学会(American Institute of Physics)和IEEE计算机社团 (IEEE Computer Society)的一本联合刊物《科学与工程中的计算》发表了由田纳西大学的Jack Dongarra和橡树岭国家实验室的Francis Sullivan 联名撰写的“世纪十大算法”一文，该文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。作者苦于“任何选择都将是充满争议的，因为实在是没有最好的算法”，他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。有趣的是，该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章，实在是蔚为壮观。本文的目的，便是要带领读者走马观花，一同回顾当年这一算法界的盛举。
1946 蒙特卡洛方法
在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，呃，能帮我算算这个不规则图形的面积么？蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个:那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。别小看这个数黄豆的笨办法，大到国家的民意测验，小到中子的移动轨迹，从金融市场的风险分析，到军事演习的沙盘推演，蒙特卡洛方法无处不在背后发挥着它的神奇威力。
蒙特卡洛方法由美国拉斯阿莫斯国家实验室的三位科学家John von Neumann（看清楚了，这位可是冯诺伊曼同志！）,Stan Ulam 和 Nick Metropolis共同发明。就其本质而言，蒙特卡洛方法是用类似于物理实验的近似方法求解问题，它的魔力在于，对于那些规模极大的问题，求解难度随着问题的维数（自变量个数）的增加呈指数级别增长，出现所谓的“维数的灾难”（Course of Dimensionality）。对此，传统方法无能为力，而蒙特卡洛方法却可以独辟蹊径，基于随机仿真的过程给出近似的结果。
最后八卦一下，Monte Carlo这个名字是怎么来的？它是摩纳哥的一座以博彩业闻名的城市，赌博其实是门概率的高深学问，不是么？
1947 单纯形法
单纯形法是由大名鼎鼎的“预测未来”的兰德公司的Grorge Dantzig发明的，它成为线性规划学科的重要基石。所谓线性规划，简单的说，就是给定一组线性（所有变量都是一次幂）约束条件（例如a1*x1+ b1*x2+c1*x3>0)，求一个给定的目标函数的极值。这么说似乎也太太太抽象了，但在现实中能派上用场的例子可不罕见——比如对于一个公司而言，其能够投入生产的人力物力有限（“线性约束条件”），而公司的目标是利润最大化（“目标函数取最大值”），看，线性规划并不抽象吧！线性规划作为运筹学(operation research)的一部分，成为管理科学领域的一种重要工具。而Dantzig提出的单纯形法便是求解类似线性规划问题的一个极其有效的方法，说来惭愧，本科二年级的时候笔者也学过一学期的运筹学，现在脑子里能想起的居然只剩下单纯形法了——不过这不也正说明了该方法的简单和直观么？
顺便说句题外话，写过《万历十五年》的黄仁宇曾说中国的传统是“不能从数目字上管理”，我们习惯于“拍脑袋”，而不是基于严格的数据做决定，也许改变这一传统的方法之一就是全民动员学习线性规划喔。
1950 Krylov子空间迭代法
1951 矩阵计算的分解方法
50年代初的这两个算法都是关于线性代数中的矩阵计算的，看到数学就头大的读者恐怕看到算法的名字已经开始皱眉毛了。Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。
1951年由橡树岭国家实验室的AlstonHouseholder提出的矩阵计算的分解方法，则证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。
 1957 优化的Fortran编译器
说实话，在这份学术气息无比浓郁的榜单里突然冒出一个编译器(Compiler)如此工程化的东东实在让人有“关公战秦琼”的感觉。不过换个角度想想，Fortran这一门几乎为科学计算度身定制的编程语言对于科学家（尤其是数学家，物理学家）们实在是太重要了，简直是他们形影不离的一把瑞士军刀，这也难怪他们纷纷抢着要把票投给了它。要知道，Fortran是第一种能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。
话说回来，当年这帮开发Fortran的家伙真是天才——只用23500行汇编指令就完成了一个Fortran编译器，而且其效率之高令人叹为观止:当年在IBM 主持这一项目的负责人JohnBackus在数十年后，回首这段往事的时候也感慨，说它生成代码的效率“出乎了所有开发者的想象”。看来作为程序员，自己写的程序跑起来“出乎自己的想象”，有时候还真不一定是件坏事！
1959-61 计算矩阵特征值的QR算法
呼，又是一个和线性代数有关的算法，学过线性代数的应该还记得“矩阵的特征值”吧？计算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模大的时候十分困难。QR算法把矩阵分解成一个正交矩阵（什么是正交矩阵？！还是赶紧去翻书吧！）与一个上三角矩阵的积，和前面提到的 Krylov 方法类似，这又是一个迭代算法，它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。
1962 快速排序算法
不少读者恐怕和我一样,看到“快速排序算法”（Quick Sort）这个条目时,心里的感觉是——“这可总算找到组织了”。相比于其他一些对程序员而言高深莫测的数学物理公式,快速排序算法真是我们朝夕相处的好伙伴——老板让你写个排序算法,如果你写出来的不是快速排序,你都不好意思跟同事打招呼。其实根本不用自己动手实现, 不论是ANSI C,C++ STL,还是Java SDK,天下几乎所有的SDK里都能找到它的某种实现版本。
快速排序算法最早由Tony Hoare爵士设计，它的基本思想是将待排序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有序。说起这位Tony Hoare爵士，快速排序算法其实只是他不经意间的小小发现而已，他对于计算机贡献主要包括形式化方法理论，以及ALGOL60 编程语言的发明等，他也因这些成就获得1980 年图灵奖。
快速排序的平均时间复杂度仅仅为O(Nlog(N))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。
 1965 快速傅立叶变换
如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的总冠军——每天当拿起话筒，打开手机，听mp3，看DVD，用DC拍照 ——毫不夸张的说，哪里有数字信号处理，哪里就有快速傅立叶变换。快速傅立叶算法是离散傅立叶算法（这可是数字信号处理的基石）的一种快速算法，它有 IBM 华生研究院的James Cooley和普林斯顿大学的John Tukey共同提出，其时间复杂度仅为O(Nlog(N))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。
1977 整数关系探测算法
整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。具体的说:
给定—组实数X1,X2,...,Xn，是否存在不全为零的整数a1,a2,...an，使得:a 1 x 1 +a 2 x 2 + . . . + a n x n ＝ 0 这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。至于这个算法的意义嘛，呃，该算法应用于“简化量子场论中的Feynman图的计算”——太深奥的学问拉！
 1987 快速多极算法
日历翻到了1987 年，这一年的算法似乎更加玄奥了，耶鲁大学的Leslie Greengard和Vladimir Rokhlin提出的快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体，或者蛋白质中的原子间的相互作用”，天哪，不是我不明白，这世界真是变得快！
所谓浪花淘尽英雄，这些算法的发明者许多已经驾鹤西去。二十一世纪的头五年也已经在不知不觉中从我们指尖滑过，不知下一次十大算法评选的盛事何时再有，也许我们那时已经垂垂老去，也许我们早已不在人世，只是心中唯一的希望——里面该有个中国人的名字吧！
参考文献

本文基于下列材料编写:
[1] Dongarra and Sulliv an, Top Ten Algorithmsof the Century, Computing in Science andEngineering, January /February 2000.
[2] Barry Cipra,The Best of the 20th Century :Editors Name Top 10 Algorithms SIAM News,Volume 33, Number 4, May 2000, page 1.

[Coding]GPopup
写了一个根据IP地址进行消息和文件发送/接收的小程序。用了MFC、多线程编程、Socket编程，总结经验教训如下：
根据自己的实践经验和网络上的搜索结果，MFC静态版本的CSocket似乎有Bug，运行报Assertion failed。换成动态版本问题解决。但这样有利有弊，一方面动态版本有利于程序的维护和升级，一方面程序分发的难度加大，必须要加入一个MFC动态链接库才可以。
传文件和传消息的差异在于两个方面，第一是大小不同。消息一般是1024字节以下，但文件则上不封顶，因此就涉及到CSocket::Receive()的用法。需要注意，这一函数并不是你让它Receive多少就Receive多少，而是用返回值来告诉调用函数它收到了多少字节。处理的时候应当重视这一点。
传文件和传消息的第二个不同就是模式不同。传消息是不需要征得接收方允许的，因此实现起来很方便。但是传文件需要发送方先发送请求，同时还要发送一些基本信息，比如文件名、大小等等，然后等待接收方同意。接收方收到请求和文件的基本信息后询问用户，再给发送方发送反馈。如果同意才开始正式的文件传输。不管代码实现是困难还是简单，算法是事先要搞清楚的。不过值得庆幸的是这一次我没有成为代码民工。看来前一段时间的反思是有效果的。
开发文档的维护相当重要。从前一段开始很多程序就已经进入多线程的阶段了。虽然面向对象程序设计大大减少了开发者要维护的内容，但要处理的东西还是很繁杂的。类之间的关系，线程之间的配合，时间一长就容易忘掉。所以一份详尽完整的开发文档的维护是相当必要的。它不仅可以理清开发的过程，而且可以使后续开发可以在短时间内运作起来。
架构！最重要的东西往往留在最后压轴。一个程序，或者说一个工程，最重要的东西就是架构。一方面因为架构从根本上决定/体现了程序的效率、算法，一方面因为一旦开发进入了编码阶段，架构的更改就非常困难，骑虎难下也许是最生动的比喻。所以对于架构一定要慎重慎重再慎重，思考思考再思考，理清楚各个部件的关系，谁包含谁，谁和谁通信。三思而后行。
一件事往往看上去简单，但真正做起来的时候却不得不处理很多细节方面的问题。还是那句老话，纸上得来终觉浅，绝知此事要躬行啊！

此外，stephen同学从跨平台兼容性的角度提出了很好的建议。可是我所知道的跨平台的方法就是在每个平台下都写一份代码，然而目前主流的操作系统Windows和Linux在创建线程/进程、界面构造等方面差异实在太大，除了傻傻的把这个程序再写一遍，我个人实在不晓得怎么搞 :-( 然后stephen同学说到了标准的问题，只要在写代码的时候支持POSIX标准就好了~另外，他提到了Linux和Windows在设计理念上的不同。觉得很好，引用如下：(已征得作者允许)
======================quote begin=========================
我觉得跨平台不是这么理解的。
正真讲到跨平台，应该是同一份代码能够直接或者只需很少的改动就能在多个平台上运行。
比如Java程序就是跨平台的，同一份代码，完全不用修改就能在Windows、Linux、Mac等系统上运行，甚至能直接在手机上运行。但是，注意，我说的是Java程序，而不是Java虚拟机。Java虚拟机不是跨平台的，每个平台上的代码都不一样，但用Java开发的程序却是跨平台的。再说我刚才提到的Qt、GTK等，就开发工具而言并不是跨平台的，但开发出来的程序却是跨平台的，用Qt或GTK开发的程序，在界面部分的代码可以完全不用修改，就能直接在Win下运行。当然，涉及到其他一些东西，比如网络通信等，两个系统的接口不一样的，可能需要改一些代码，但这部份不属于Qt或GTK，当然也有解决方法，那就是Qt或GTK也考虑到了这一点，它们像MFC一样，对多线程、网络等都有自己的封装，直接用它们封装好的类就行了，就完全没有兼容性问题了。如果我用Qt写程序，我肯定会尽量不用fork这类函数，毕竟它们太底层了，而Qt已经封装的很高层了，掺和在一起写，程序就会很别扭。我向来坚持，要么写纯C，要么写纯C++，至少在一个源文件中是这样，不然程序很丑，就像现在班里很多人写算法实验，用的是C语言，但用cpp的后缀，而程序中唯一用到的C++的特性就是随地声明变量。这样的程序真的很难看。Qt有多线程的类，我学习一下~
说实话，涉及到网络的东西，Linux/Unix有着先天性的长处。毕竟Win的设计初衷就是桌面系统，而Linux/Unix从最早的版本就设计成网络模式。所以现在服务器市场Linux/Unix占的份额还是比Win多。我们现在用电脑都是Single User(意思就是自己的电脑自己用，很少使用公共电脑)，但其实*nix从最初就设计成终端模式，不推荐用户直接物理接触试用机器，而是像那个freeshell一样，大家共用一台机器，每个人都有自己的终端，互不干扰。所以*nix的在网络方面相当成熟。至于桌面系统，其实我个人觉得Linux本身并不想争桌面系统的地位，只是一些发行版在那里热闹而已。Linux因为其设计的初衷（多终端系统），它更多的是用于科研计算，就像集群机一样，提供很强的机器与机器/人与机器的交互行，合作完成高性能的计算。*nix下的X只是为了提高某些工作的效率，因为图形界面很多时候能比字符界面提供更多的信息。但很多事情还是命令行更高效。（如果用习惯的话）
如果撇开界面，就核心部分而言，其实跨平台也不难，只要尽可能试用兼容POSIX标准的东西就行了。随便哪个系统，其进程管理/通信等各方面的接口肯定都是差不多的，可能只是函数名不大一样，头文件位子不一样，只要简单的写几个define就能解决问题的。
======================quote end==========================

[coding]补码的设计思路
目的：通过设计一种新的编码来让减法转换成加法来做。
如1011 - 0010能够利用加法器的电路来完成而不用专门设计减法器的电路。当然，运算数和结果全部用这种新的编码来表示。
稍微思考一下可以发现，由于计算机的字长是有限的，我们有可能利用溢出这种现象来完成任务。比如1011 - 0010 = 1001，但是我们可以让1011 + 某个数，让它们的和等于11001，这样最高位被迫舍弃，得到的结果恰为1001。我们记减数为-A，计算得到的“某个数”为B。若A和B之间有某种确定的映射关系，则我们可以认为找到了一种新的编码。由于这种编码是针对于优化减法的，因此我们可以认为正数的编码为它本身，而负数的编码需要通过新找到（如果存在）的映射关系来计算。这样不论加法或是减法都可以用B0 + B来表示，B0，B以及结果都用这个新的编码来表示。
下面从1011 - 0010这个特例出发，讨论是否存在这样的映射关系。
由我们利用溢出进行计算的原理可知1011 + B = 11001 = 10000 + 1011 - A = 1111 + 1011 + 1 - A
两边的1011消去，有B = 1111 - A + 1
由于结果和被减数1011无关，所以不论被减数是什么，以上结论都成立，所以B与A有确定的映射关系。
如果进一步从这个特力拓展，假设计算机的字长为n位，则很容易得到结论：
B = 111...1(n个1) - A + 1
从形象的角度来说，B就是A按位取反后加1得到。注意这里A指的是那个负数的绝对值。
这样我们就得到了一种新的编码，由于负数-A在编码过程中需要计算111...1(n个1) - A，这是一个求补的操作，因此它的一个看起来比较适当的名称可以是：“补码”。正数的补码就是它本身，负数的补码根据机器字长按位取反再加1即可得到。但是由于一位被符号位占据，所以正数的合法范围是00...0 ~ 011...1，而负数是100...0 ~ 111...1。在补码下，加法和减法可以按照同一种逻辑进行计算。

P.S.探讨既知知识的发明历程是一件很有意思的事情~假装他们还没有被发现，照着一般的思路来思考~发现~发明~~~
P.S.2.从特例出发，探讨一般情况是一种很有启发性的思路~

[coding]请喊我代码民工头，谢谢
接到HY短信，问在C语言中怎么用printf把一个double型变量小数点后12位打出来。稍微试了一下%12f不行，然后代码民工本性开始发作了……觉得似乎可以通过写代码解决这个问题，于是从2030开始写代码，写写写，写到2330。搞定。
然后HY无比迷惑发个短信过来：C语言库函数不能实现吗……
一想是啊，废话，C语言有那么傻么，且不说这是一个基本功能，你都把打印6位小数给实现了，怎么会不提供打印12位小数。一翻书，我靠，类似%.12f的语句是可以实现改变有效数字位数的。
代码民工了吧，写代码完全不想它的意义，完全不晓得它在整个程序架构中的地位，就知道写！写！写！真是……搞得跟一民办电脑培训学校C语言速成班毕业的一样。还本科生，还计算机系，买块豆腐撞死算了！
最后小安慰一下，这次好歹知道关注一下算法，没有超级SB自己去写高精度乘法和加法来转二进制，用了滑动窗口转二进制的方法，也知道IEEE 754浮点数标准。想想看一般代码民工还写不出来这样底层的东西。所以……
请喊我代码民工头，谢谢。

P.S.以后除了注意算法以外，在写代码之前更要注意它的意义和整个程序中的地位。也许写代码之前先写用户文档是个不错的主意。

原来做成gif的，Live Space显示不了，鄙视一下