2009-08-29

关于批量重命名文件

关于批量重命名文件

redraiment, 2009-08-29





  不久前,我们软件工程系举行了全系大会。我在大会上做了简短的报告,主题是“学以致用、动手实践”。报告期间我说了一个亲身经历:以前校园内U盘病毒肆虐,病毒会把U盘里所有的文本文件加上系统属性和隐藏属性,并添加“.tmp”扩展名(例如原文件名为“a.txt”,病毒修改为“a.txt.tmp”),然后生成一个和原文件同名的病毒文件。我不幸中招,于是用我所学的知识写了一个小程序,几秒钟就解决了。
  原以为它就像插播广告一样随听随忘,不料言者无心听者有意。几个学弟回去后也都竭尽所能玩了一把:有用 Java 的,也有用 C# 的……功能也五花八门,不仅能批量修改扩展名,还能按 1→N 的顺序批量重命名文件等等。看他们玩得不亦乐乎,想来那次报告还有点作用嘛^_^。
  今天又被问起我那时候的程序是怎么写的。其实在我们大一那会儿,要用计算机只能到图书馆的电子阅览室。那儿的系统“干干净净”,不会有 VC++ 等编译器,而且那种打开网页需要半分钟的速度也不会让你考虑去下载(估计其他高校情况也差不多),所以我是用批处理解决的。我用了下面三条命令:
::a.bat
@echo off
::删除所有病毒文件
del /F /S /Q *
::递归地去掉文件的隐藏属性
attrib -s -h -r * /S /D
::遍历目录,去掉 tmp 扩展名
for /R . %%f in (*.tmp) do ren %%f %%~nf

  上面的程序中是为了去掉“.tmp”这个扩展名,所以用 for 命令来遍历。但如果仅仅是修改扩展名则更简单,只要运行 ren *.bat *.txt 即可。另附一段好玩的批处理:将下面的代码保存成 bat 文件,双击运行就能将当前目录下的 jpg 图片文件按 1-N 的顺序重新命名(用来批量处理从网上下载下来的图片非常有效)。大家可以修改蓝色部分来改变扩展名。
::b.bat
@echo off
::开启延迟的变量扩充
setlocal enabledelayedexpansion
::计数器
set /a i=1
for /R . %%f in (*.jpg) do (
  ren %%f !i!.jpg
  set /a i=!i!+1
)
  只要大家悉心观察,生活中还有很多好玩的问题可以去解决,祝大家玩得开心^_^。

版权声明
请尊重原创作品。转载请保持文章完整性,并以超链接形式注明原始作者“redraiment”和主站点上的本文原始地址,方便其他朋友提问和指正。

2009-08-23

Shell中同时读多个文件

Shell中同时读多个文件

redraiment, 2009-08-23

一个文件分割成多个文件





  有时需要提取文件中的一个或多个列元素生成新的文件,这一操作在 Shell 里很容易实现。比如有一个数据文件 data,有三列信息:姓名、学号、班级。
redraiment 0612800134 0601
christine 0612800136 0601
zb 0612800229 0602

  现在需要这个文件的第一列和第二列信息分别存到文件 f1 和 f2 中,可以用 awk 提取,也可以用下面这个简单 shell 程序:
#!/bin/sh

while read f1 f2 f3
do
    echo $f1 >> f1
    echo $f2 >> f2
done

多个文件合并成一个文件

  如果想把多个文件重新合并成一个多列文件,而不是追加到文件尾处。例如把上列中生成的 f1 和 f2 重新组成 join.txt 。这时需要同时操作多个文件,就像 C 语言中用 fopen 同时打开多个文件,在 shell 里也是类似的。只是在 shell 里叫做“文件描述符”,用“0-9”十个数字表示。其中 0、1、2 分别是系统的标准输入、输出、错误。“3-9”则由用户只有使用。我们就可以任选两个来重定向输入。脚本如下:
#!/bin/sh

exec 3<f1
exec 4<f2
while read f1 <&3 && read f2 <&4
do
    echo $f1 $f2 >> join.txt
done



2009-08-18

JavaScript中的字符串乘法

JavaScript中的字符串乘法

redraiment, Date

原文

原作者:David Flanagan





In Ruby, the "*" operator used with a string on the left and a number on the right does string repetition. "Ruby"*2 evaluates to "RubyRuby", for example. This is only occasionally useful (when creating lines of hyphens for ASCII tables, for example) but it seems kind of neat. And it sure beats having to write a loop and concatenate n copies of a string one at a time--that just seems really inefficient.

I just realized that there is a clever way to implement string multiplication in JavaScript:

String.prototype.times = function(n) {
    return Array.prototype.join.call({length:n+1}, this);
};

"js".times(5) // => "jsjsjsjsjs"

This method takes advantage of the behavior of the Array.join() method for arrays that have undefined elements. But it doesn't even bother creating an array with n+1 undefined elements. It fakes it out using and object with a length property and relies on the fact that Array.prototype.join() is defined generically. Because this object isn't an array, we can't invoke join() directly, but have to go through the prototype and use call(). Here's a simpler version that might be just as efficient:

String.prototype.times = function(n) { return (new Array(n+1)).join(this);};

When you call the Array() constructor with a single numeric argument, it just sets the length of the returned array, and doesn't actually create any elements for the array.

I've only tested these in Firefox. I'm assuming that either is more efficient than anything that involves an actual loop, but I haven't run any benchmarks.

解释

我的英语非常烂,没办法为大家逐字逐句地翻译,只能为大家解释一下大概的意思。

  在Ruby中,“*”操作符用一个字符串作为左边参数,一个数字作为右边参数,来实现字符串重复。例如,"Ruby" * 2 的值为 "RubyRuby"。这仅在少数地方有用(例如,生成一张由连字符等ASCII 码字符构成的表格),但是非常简洁。而且好过写一个循环来连接n次字符串——这样显得很没效率。
  我刚刚发现在JavaScript中有个聪明的技巧来实现字符串的乘法:
String.prototype.times = function(n) {
    return Array.prototype.join.call({length:n+1}, this);
};

"js".times(5)   // => "jsjsjsjsjs"
  这个方法是调用一个由元素全为“undefined”的数组的Array.join()行为。但是它并没有真正创建一个包含 n+1 个“undefined”元素的数组。它利用一个包含length属性的匿名对象,依靠Array对象的原型函数join()。因为“Object”不是数组,不能直接调用join(),因此不得不通过原型的call()来实现。下面给出一个同样效果的简单版本:
String.prototype.times = function(n) { return (new Array(n+1)).join(this);};
  当我们调用 Array 的带一个参数的构造器时,仅仅是设置了数组的长度,实际上并没有创建数组的元素。
  我仅在Firefox 下对其做了测试,我估计它会比普通的循环更加有效,但我并没有进行基准测试。

作者简介

  David Flanagan 是一个醉心于Java写作的计算机程序员,他的大部分时间都致力于编写Java相关图书。David 在麻省理工学院获得了计算机科学于工程学位。他生活在地处西雅图和温哥华之间的美国太平洋西北海岸。他在O'Reilly出版的畅销书有《Java in a Nutshell》、《Java Foundation Classes in a Nutshell》、《Java Enterprise in a Nutshell》、《JavaScript: The Definitive Guide》、《JavaScript Pocket Reference》以及《The Ruby Programming Language》等。

我的评论

  如果要考虑效率的话,对循环迭代稍作优化可能效率更高。比如下面这段递归调用,算法复杂度是O(log2n)。在Google Chrome下测试结果是比David的方法执行更快,但不得不承认他的方法很优雅!
String.prototype.times = function(n) {
    if ( n == 1 ) {
        return this;
    }

    var midRes = this.times(Math.floor(n/2));
    midRes += midRes;
    if ( n % 2 ) {
        midRes += this;
    }

    return midRes;
}

2009-08-17

难得糊涂

难得糊涂

redraiment, 2009-08-17

前记

  以前戏称自己写的是“自醒文”,世道轮回,我终究还是来写“自省文”了。

悲剧

  曾经我自视遵循老庄的教诲、奉行道家的指导,但现在看来我完全是在背其道而行。
  《庄子·天地》有云:“有机械者,必有机事;有机事者,必有机心。”大致意思就是说:“有省劲的工具,就一定有省劲的事;有那个省劲的事,就说明我起了省劲的心。”而所谓省劲的心就是投机取巧。这虽然是道家反对智慧、反对科技文明的极端思想,但也不无道理。易中天老师就总结得非常好:“我们现在买一包方便面一撕开,开水一泡就吃了;我们买一个快餐食品,微波炉里转两分钟就出来了。这个食品里还有妈妈的味道吗?”科技越发达,个人的能力也得到越大的发挥,人与人之间就越独立,也越来越不知人情冷暖。
  易老师的分析给我触动很大,诸多事情依然历历在目:某人能将谷歌金山词霸里的生词本导出去打印,我就花了几天写了一个程序让她自动转换,从此不再听她和我提起这件事;某人喜欢我陪她玩小游戏,结果我写了个外挂24小时刷分,于是游戏失去了娱乐意义,她也不再邀请我一起玩;某人希望我帮她去学校内网图书馆下载论文,我在内网的机子上开后门、中木马、启用VPN,打那以后下载论文不再需要我这个“代理”……
  那时还洋洋得意,自以为做了一件一劳永逸的事情,甚至自视思想简单得和计算机一样只知道01,不知深浅地认为已经达到梁肇新老师说的“我就是程序,程序就是我”的境界。却不料总是无情地将人家一颗挚热的心抛给不知冷暖的程序。
  希望此文能和大家共勉:不要因为长时间面对冷冰冰的计算机而被同化,该糊涂时则糊涂,因为现在能对她说“我来帮你”的已经不再是我了。

2009-08-16

永生轮回之术

永生轮回之术

redraiment, 2009-08-15





  前段时间看了一个视频——《科学家证明轮回的事实》。视频中疑点甚多,姑且就当科幻片看好了很多宗教里都有生命轮回的概念,但真伪难证。我相信生命还是公平的,每个人要完成的任务份额是一样的。我的身体属于早熟型,不晓得早熟会不会意味着早衰,所以在十多岁就开始感叹人生苦短,一直渴望能有永生之法。今撰此文来扯扯“永生轮回”的淡,本文是在一本正经地讲一段屁话,仅供消遣切莫认真。

从物理学的波开始

  “波”蕴含能量:在真空中没有任何阻碍,因此能力可以毫无损失地传播到任意远处;在空气或其他介质中传播,能量不断地被其他物质吸收直至耗尽。
  “波”储存信息:不同的频率、不同的振幅、不同的波长能组合出成千上万种信息。不要小看它,DNA只有4种含氮碱基、计算机更是寥寥的二进制,但都能存储这大千世界。
  量子物理学认为万物皆有波粒二象性,所有物质都有波,即物质波(相关概念请看这里)。人体就随时随地的往四周扩散着波,比如广为人知的“脑电波”。目前已经研究出一些运动“脑电波”的产品,比如用“脑电波”控制的轮椅、用意念玩游戏的头盔等等。这至少说明了“脑电波”在离开人体后不仅能继续存在,而且还存储着本体思维意识等的信息。因此我大胆提出一个假设——灵魂也是一种电磁波。

灵魂也是一种电磁波

  神秘的人体蕴含了肉身和精神。从上面的观点来看,我更愿意将“肉身”视作给精神之力(灵魂)提供能量的制造机;而灵魂获得了能量后可以指挥肉身工作,还会将自己复制传播出去,来影响周边。发散出去的“波”携带的能量越多意识就越强,其他一些相对意识较弱的人可能就很容易受到影响,导致自己的意识波慢慢地与它同步、产生共鸣,最终完全接受了其他人的思想观点(今天的话叫“洗脑成功”)。
  不同的环境里聚集着不同的波,因而你在不同的地方能感受到不同的气氛、产生不同的想法,所以艺术家们需要踏遍万水千山到处寻找灵感。上述的影片中也提到,出现轮回现象的大多是宗教盛行之地。
  生活中有很多诸如此类的现象,比如一下几个荒唐的说法。
  1. 电影中的幽灵:当我们很专注地看完一部电影,接下来的两三天大脑几乎像不受自己控制似的回味着电影里情节、对话,在大型的电影院里看效果尤佳。因为全神贯注的状态就是主动地去同步自己的意识波,所以很容易引起共鸣,致使人们身临其境沉浸于其中不能自拔。大型电影院中人群密集,而且每个人都向往发散相同的意思波(电影情节等),聚集的能量自然比其他环境下更强大,大部分人都无法避免受其影响(犹如鬼上身一般)。
  2. 传说中的投胎:按照本文的说法,肉身是用来容纳灵魂的容器,并为意识提供生物能(写到这里突然让我联想到《黑客帝国》,故事里的Matrix也具备了自我意识,因此它生成出很多“人类”,插上管子为自己提供生物能)。人从一个受精卵开始逐渐成形,这个过程相当于我们计算机中硬件从生产线上生产出来,但其没有意识(软件),终究只是一台裸机。在胎儿大脑成型后,飘荡在周围的“波”就会对它产生影响,如果某段“波”有幸能保存到这个“ROM”里,那就恭喜它投胎成功重新做人了。难怪说孕妇要远离电脑、微波炉等高辐射电器,家里贴漂亮小孩的照片生的小Baby也比较可爱。科学家们果然英明!
  3. 未死亡的死亡:人的死亡应该伴随着肉身和精神的共同消亡。科学界对肉身的死亡定义为脑死亡,但对于精神这种虚幻的东西没有定论。按照本文观点,人平时也不停地向外界散播自己的“意思波”,回光返照时更是集齐肉身所有剩余能量。加上日后亲朋好友等人的追悼和思念,又为这股强大的“波”添加能量。如果在这股能量消耗殆尽之前,再找到一个婴儿投胎(见上段),那就可以周而复始的延续。所以,我们平时定义的死亡并非真正的死亡,它将一直延续到被全世界所有人遗忘为止——不再悼念、不再回忆、不再睹物思人……一个不被人们记得的人,即使活着也只是个隐形人。
  4. 网瘾电击疗法从本文的观点来看,通过外部强大的外力也许可以踏平沉浸于网络的意识。但电流多少安培、电压几伏特都没有科学依据就这样胡乱电击,反而有可能导致病人变成“无意识”,这就得不偿失了。
  5. 西藏活佛转世:西藏活佛转世时,原有的肉身已死,却将一生的智慧、领悟与经验传于转世灵童,才得以生命在某种意义上的延续与永生。

思想上的传承

  传统的观念中,有了后代(尤其是男孩子)就可以传宗接代,但如果大脑只是别人思想的跑马场,则仅仅从基因上继承了肉体上的特征,而我们的思想也将无人问津,不久就被世人淡忘。这一点林肯很有体会,他消灭敌人的方法就是将他变成朋友。如果全世界的人思想都和林肯一致,那一件事无论换了谁来处理结果都会一样,因为全世界都是林肯!
  寻寻觅觅追求永生,发现追求的永生有很多误区:最初追求的是形式上的永生,即奢望拥有金刚不坏之身,肉身永久具有生命力。只是有形之物必会劳损,何况按照本文的腔调肉身只是一副臭皮囊而已;后来我改变想法,觉得肉身是一种形式,可以不一样。但至少应该有前世的记忆片断,知道我前世是什么人(玄幻小说里经常这样描写)。现在我发现这点也是不必要:我记性很差,这辈子的事情都已经忘得差不多了,又何必苛求人家记住上辈子的事情?好记性不如烂笔头,真的想记住事情还是得乖乖地记日记。
  话说回来,知道以前发生了事情就是转生轮回了?我们读历史,知道秦始皇统一六国,那我们就是秦始皇投胎的?何况按照量子物理学的理论,我此刻出现在此处只是概率问题,这一刻的我是不是下一刻的我,记忆中以前的我还是不是现在的我?事迹可以人人传颂,文章可以大家转载,故此以前的事对现在的我并不重要。
  拨开一层一层无关紧要的外包装,最终剩下的就是属于我个人的意识,独立的思想。因此,为求永生:
  1. 酝酿自己的思想
  2. 传播自己的思想
  拿电脑来做比喻(人毕竟不是商品,所以你姑且抛开物品所属等观念),就像我的电脑之所以称为“我的”电脑,并不是因为硬件(肉身)是我花钱买的,也不是因为里面存放着我的图片、视频等数据(旧时的回忆),而是因为这里软件是按我的需求进行个性化设置的(独特的思想)。比如全世界的计算机都按我的想法组织目录结构、按照我的喜欢调整字体大小等对系统和软件进行个性化配置,那我无论用其中那一台都一样自如,那全世界的电脑都是“我的电脑”。

2009-08-13

VB和Dev-C++合作

VB和Dev-C++合作——手把手教你写GUI程序

redraiment, 2009-08-13

声明





  此文的读者定为C语言初学者。此文介绍的技巧适用于开发迷你型项目或自娱自乐的玩具程序,正规的项目中可能不会采用。读者可以抱着茶余饭后休闲娱乐的心态来围观,至于CLI、GUI等名词解释请参看百度百科。转载请保留此声明和原作者redraiment,谢谢!

诱人的GUI程序

  程序的作用就是化繁为简,让计算机高效地帮我们完成枯燥的工作。写程序最大的动力就是你精心设计的程序能获得大家的认可、大众的好评,这其中伴随着发布程序给大家使用。
  在C语言编写的操作系统(比如UNIX、Windows等)上,C语言可以说是“无所不能”。但很多初学者发现,即便自己把C语言教材从头啃到尾,依然只能写出命令行下的程序。程序是CLI还是GUI本无可厚非,对我们程序员来说更重要的是程序本身提供的功能嘛,而且CLI相对于GUI还更灵活一些。也许你可以尝试一下把程序发送给一个非计算机科班出身的朋友,估计得大费唇舌来解释程序如何运行,可能最后还落得一个“不方便”的抱怨。撇开这些不说,至少一个活泼的桌面图标也比死气沉沉的终端图标更吸引人。
  但编写GUI程序从来不是一件容易的事情,MFC也好、Swing也罢,都是一堆烦人的接口。用VB可以屏蔽这些细节,界面设计是所见即所得的,拖拖拽拽就能堆出一个像样的界面。本文的原理就是用VB来设计前台界面,C做后台逻辑处理。实现方法就是将C程序打包成DLL文件,由VB程序来调用。

所需软件

  Dev-C++ 4.9.9.2或以上版本,VB 6.0精简版。这两款软件在华军软件园都能下载到,合起来大小也就15MB左右。如果你有完整版的VB当然更好,不过有精简版的也够用了。

Dev-C++生成DLL的方法

  1. 打开Dev-C++;
  2. 点击“文件”-“新建”-“工程”,工程类型选择“DLL”;
  3. 语言必须选择“C”,不能选择“C++”;
  4. 为工程取一个名字,比如“hello”。确定后会自动生成“dllmain.c”和“dll.h”两个文件;
  5. “dllmain.c”里自带了一个函数“DLLIMPORT void HelloWord ()”,但为了能在VB里调用,需要在DLLIMPORT后面添加一个“__stdcall”,即“DLLIMPORT __stdcall void HelloWord ()”,“dll.h”文件中也做同样的修改。没有写“__stdcall”的话会弹出“DLL调用约定错误,错误号:49”,所以请务必小心。
  6. 保存文件后,按Ctrl+F9编译。就会在工程的目录下生成一个hello.dll。

用VB设计程序界面

  1. 打开VB;
  2. 新建一个“标准EXE”工程;
  3. 拖一个按钮控件(工具箱的第三行第二列)到界面上,如下图。

在VB中调用DLL里的函数

  在VB中调用DLL里的函数,首先要声明。声明的格式是
[Public|Private] Declare [Sub|Function] 函数名 Lib "DLL路径,可以是相对路径,也可以是绝对路径" (ByVal或ByRef等参数列表) [as 返回值类型]
  比如我们这里函数声明为:
Private Declare Sub HelloWorld Lib "dll.dll" ()
  声明后就可以调用了。
  1. 双击VB的窗口界面,打开代码窗口;
  2. 将一下代码复制到代码窗口里
    Private Declare Sub HelloWorld Lib "hello.dll" ()

    Private Sub Command1_Click()

        HelloWorld

    End Sub
  3. 点击“文件”-“生成工程1.exe”,路径选择刚才Dev-C++生成hello.dll所在的目录。
  4. 确保“工程1.exe”和“hello.dll”两个文件放在同一个目录下,双击运行“工程1.exe”。
  5. 点击按钮“Command1”,就会弹出一个窗口,显示“Hello World from DLL!”则表示调用DLL成功!如下图
  现在,你可以自由发挥来编写丰富多彩的GUI程序了!

附录A:C参数在VB中的声明

C语言的字符串要特殊处理
char *: ByVal args As String

short -> Integer
int -> Long
long -> Long
UNIT -> Long
ULONG -> Long
WORD,DWORD -> Long
WPARAM,LPARAM -> Long
WMSG,UMSG -> Long
HRESULT -> Long
BOOL -> Boolean
COLORREF -> Long
HWND,HDC,HBRUSH,HKEY,等等. -> Long
LPSTR,LPCSTR -> String
LPWSTR,OLECHAR,BSTR -> String
LPTSTR -> String
VARIANT_BOOL -> Boolean
unsignedchar -> Byte
BYTE -> Byte
VARIANT -> Variant
(任何以*或**结尾的数据类型)Long

2009-08-12

你的密码安全吗

你的密码安全吗

redraiment, 2009-08-12

想个好密码不容易





  Web 2.0时代需要用户主动参与,大大小小的站点都需要你注册登入(连期末课程设计也视此为最低指标)。密码原则上是一个烂在肚子里的字串,只有自己知道且容易回忆。容易回忆就意味着这一串字符对自己来说具有某种意义,但真要找到一串字符既有意义又不广为人知还的确不太容易。于是很多人选择迁就“容易记忆”,比如下列几类常用的密码:
  1. 类似111111、123456等潜意识型的密码;
  2. 和帐号一样或者稍做修改;
  3. 用自己(或家人)的名字、生日、身高、手机号码等;
  4. 用Ilovexxx,xxx520等,臭屁点的人还会用woshitiancai之类的密码。
  5. ...
  还有很多类似的密码,有兴趣的话可以下载一些“黑客字典”来参考。总结起来,大多数密码都是在自身或周边取材,或经过简单的变化。因此,破解密码的过程其实也就是了解对方的过程,如果我对你非常熟悉,了解你就像了解我自己一样,你的生活习惯、喜好厌恶我都清楚,甚至你在想什么我都知道。那才你的密码不就等于想像一下自己会设什么密码(黑客们觉得这样很有趣,反感暴力破解)。而在这个开发的Web 2.0时代,通过人肉搜索收集个人信息可谓轻而易举。
  所以,提高密码的复杂度可能并不是简单的组合数学问题,尤其是那些心里藏不住秘密的人。

驻扎的网站是否够安全

  即使找到了一个安全的密码,也不过是万里长征的第一步。你驻扎站点的安全性又如何呢?每个时期都有其代表性的漏洞,我刚接触计算机时SQL注入漏洞就像今天的XSS一样风靡,即使是《黑客防线》等专业黑客站点也一样难幸免。黑客在取得服务器的绝对权限后,所有用户的密码都成为了明码。
  这并不是问题的关键,真正糟糕的地方还是在人本身:人都是有惰性的!你可以检查一下自己的密码:QQ、邮箱、网游……是不是用的都是相同(或相似)的密码?取得其中任何一个,几乎就是一卡通了。
  用户尚且如此,很多站长也同样是懒人。有多少中小型站点是按默认配置来运行的,哪天你无聊完全可以拿/data/dvbbs7.mdb这个路径去匹配动网论坛,指不定就下载到后台数据库。
  碰到一些霸道的站点,下载个文件还得注册,对于这些一次性光顾的网站,你注册时得多留一个心眼了。

这些站点值不值得信赖

  纵使访问的网站铜墙铁壁,这些站点值得信赖吗?我们能放心将自己的数据或信息交托给他们保管吗?Google喊出“不作恶”的口号,不管这是不是商业口号,但这不是一件很可悲的事吗:不作恶原本就是一个人的基本素质,却需要如此大肆宣扬。就和褒奖诚实守信、拾金不昧等传统美德一样让人痛心,这其实就承认了这个世道人心本恶。
  姑且不论有人恶意在自己的站点挂木马钓鱼等。像Google这样的公司将“整个互联网保存到自己的计算机里”,通过对这些数据的分析就能了解一个民族现在关注的事件、我们这一代人的喜好等等敏感信息。兵家的说法是“知己知彼,百战不贻”,我们的信息人家了如指掌,是不是会感觉脊骨发凉呢?

身边的人需不需要警惕

  上面的技能还都是远程的,还有一些能物理性直接接触。所谓“日防也防,家贼难防”,你是不是了解每个微笑的内涵,是不是清楚电话那头客气的原因,是不是明白偶然邂逅中的必然?黑客们更崇尚用“社会工程学”来获得所需的信息,因为计算机的战争归根到底始终是人与人的战争。以前在瑞中混了三年,远道校网管中心、近到超市保险柜、大到校长办公室、小到心理咨询师,所有密码我都了如指掌,因为他们并不提防我这样一个傻头傻脑的学生。所幸后来是因为XX事情金盆洗手了,不然可能现在也差不多该闯祸了~

这不是结束

  生活在这开放的时代,到处充满了惶恐,办事都要小心翼翼,网上冲浪举步维艰,你的密码安全吗?


别拿面试题来折磨自己

别拿面试题来折磨自己

redraiment, 2009-08-12

起因





  临近毕业,QQ群里开始讨论就业话题,偶尔也有人发几道面试题上来给大家耍耍。今天又有同学发了一道自称是IBM里月薪8万的职位的面试题,大致意思就是8元买进一只鸡9元卖出,再10元买进11元卖出,问最终受益是多少?答案是-2元。这个匪夷所思的结果在群里引起激烈讨论,网上解释很多,大家Google一下。你甚至能搜到一些激昂的文章,摆事实、讲道理,最终得出结论:出这种面试题的公司是失败中的失败。

正文

  据说这道面试题90%的答题者都做错。这没什么值得惊讶的,甚至说99%的人做错我也相信。

  语言的表达是需要在配合特定的情景才能理解。你在厨房里和一位厨师说“刀”,他会理解成“菜刀”;而在仪表前和一位机械工程师说“刀”,他可能就理解成“模具抛光用的刀”。以前网络上盛传“大学教授不会做小学生课后习题”,其实道理也是一样。小学生今天刚学完“三角形”,在这样的前提下做课后习题自然会想到运用三角形的知识解题;而你在没有任何前置知识下突如其来地让你去解题,当然不能完成任务。这就好比嘲笑关公不会绣花、IT人员不会修电脑。

企业选人

  企业为某一职位招聘,选择的应该是最合适的人(最合适的人并不一定是最优秀的人),因此就需要通过“笔试”、“交谈”等方式来了解应聘者是否具有胜任该职位的素质。这些素质可能是相关的“专业技能”,也可能是“思维方式”。

  我家附近开了一家“人本超市”,招聘收银员时明确指出只要初中生或高职生,大专生和本科生反而被冷落了。并不是说大学生不及初中生,而是因为收银员的工作简单、单调,并不需要这么高的学历,大学生的工资比中学生高,而且可能不甘于长时间做这份工作,因此招聘大学生的成本反而比中学生高。

  微软的面试官曾坦言:“出类似‘美国有多少个加油站’这样的面试题,其实并不是真的想知道答案,而是想看看应聘者在这种有压力的环境下会做出什么样的反应。”在公司里工作难免会遇到加班、赶工等有压力的时刻,你又是如何面对这些困难的呢,是选择退却、放弃还是义无反顾地前进?

  因此面试成功不必骄傲,面试失败也无需自责,你只是不适合他们的需求而已。

我选企业

  我曾开玩笑说:早先的工作由国家分配,后来是按个人兴趣自己找工作,现在是按职业钱途找工作。不管是出于什么动机,要谋求一个职位,要做的就是努力提升相关职业技能。大可不必找一堆稀奇古怪的面试题来折磨自己,面试既是企业选人,也是你选择企业,这些面试题所筛选出来的职位未必是你追求的。

今天你犯贱了吗

今天你犯贱了吗

redraiment, Date




前言

  这是自醒文,不是自省文,是来提醒自己的。我还没铸成什么大错,用不着自我反省。

正文

  前几天好像又回到了小时候,同情心有点泛滥,觉得可恨之人也有可怜之处。但我这人一有同情心就容易犯贱!现在的我更加坚定当初的立场:可怜之人,必有可恨之处!!


  “可怜”是对自己的态度,是对自我的否定。如果一个人对自己的生活很知足,又如何会给人可怜的感觉?落水的人就会狼狈?穷人就不快乐?倒是有些人,生活在温馨的家庭里抱怨双亲太唠叨,孤儿抱怨父母为什么不能多陪伴自己一些时候。


  人之所以会痛苦就是因为对别人(可能也包括自己)要求太多,凡事都想绝对公平,体育考试大家在同一起跑线上你怎么跑不过人家?如果靠想就管用,我当初直接从娘胎里举着大学文凭出来好了。


  再说“帮助”。现在的捐款,权利大于义务!来借钱的人说:你钱这么多,就分一点给穷人好了。这就好比迈克尔·菲尔普斯一届奥运会能6枚金牌,反正他金牌这么多,分一块给我也让我做做奥运冠军好了。纵使他真的给你了,别人承认吗?这是帮助吗?即使你自己心安理得,那也只是阿Q精神胜利法的现代版——意淫!这不是“帮助”,而是嗟来之食。


  帮助就是要做到双赢!双赢并不可耻,老想着让别人单方面无私地为自己谋福利,那才是最可耻的!迈克尔·菲尔普斯如果打算帮你,不是把他获得的奖牌分给你,而是做你教练,指导和督促你练习,最后你靠自己实力获得金牌,而他也收获了一个金牌教练的美名。


  最后是“犯贱”,比如把别人家的棺材抬到自己家来哭。做一个自甘堕落、不自尊自爱,只会通过摇尾乞怜来引起别人的关注,这样的可怜虫是犯贱,与这样的可怜虫产生共鸣更是贱得不可原谅!以后得不时地扪心自问:“今天你犯贱了吗?”

附言

武当武功讲的是十八字秘诀、六路拳、十段锦和点穴法,其中十八字以“残”为首。“残”并非解为“残忍”,而是内家拳法之一,意思是比武交手时不存丝毫客气,出手绝不留情。所以流传“遇少林尤可活,遇武当不可活!”起初我无法理解:武当创始人张三丰号称宅心仁厚,口头禅就是“严以律己、宽以待人”,后期何以如此铁石心肠?现在我多少有点了解了。


四类程序

四类程序

redraiment, 2009-07-25





  前几天读了沈公的《也谈写写编译器》,很认同其观点。我也赞同“编译原理”就像数据结构一样是很基础、很实用的课程:“unix/linux 下随便哪个项目为了方便都可能随手做一个, 这是 unix 程序员的基本功”。但很可惜我们学校软件工程专业不开设编译原理,理由是学了没用。

  我们都知道“程序=数据结构+算法”,我们姑且通俗地说是程序由“数据”和处理数据的“行为”组成。根据程序对数据和行为的控制,可以将其归类为“硬编码”、“可配置”、“可控制”以及“可编程”四类。下面以简易计算器为例依次讨论。

硬编码

  此级别的程序,数据和行为都是硬编码到代码中,执行时用户不能改变。比如在C程序中直接printf ( "%d\n", 1+2 );。这时候程序的数据“1”、“2”和行为“+”都是固定不必的。


  硬编码的程序在实际应用中不常见。

可配置

  到了可配置级别,程序的行为依然固定,但数据由用户来决定。比如ACM的经典入门题“a+b”:scanf ( "%d%d", &a, &b ); printf ( "%d\n", a + b );。此时程序行为依然是求和,但数据是运行时才确定,程序变得比较灵活。


  为可配置的程序提供的数据文本,可以看作是一种数据格式(Data formats)。比如 /etc/passwd。

可控制

  可控制的程序比可配置更灵活,运行时用户不仅可以指定数据,还能指定处理该数据的行为。即运算符“+、-、×、÷”也由用户指定。例如scanf ( "%d%c%d", &a, &c, &b );,接下来用switch (c) 分别处理四则运算。可控制就是指程序的行为可控制,但行为的范围依然是固定的。也就是说用户指定的行为必须是程序本身提供的,程序只能进行四则运算,求根、阶乘等运算行为程序没提供,因此就无法使用。


  此时,程序的数据文本具有隐式操作,可以理解成一种暗含控制流的声明性语言。例如 fetchmail(1) 的运行控制语法可视为一种很弱的命令性语言。

可编程

  可编程的程序,已经同时具备“输入输出、算数运算、内存管理、按条件跳转”四种性质(请参考前文《用DOS批处理来做数字图像处理)。此时程序的行为是可扩展的,例如能通过迭代来运算阶乘。


  此时的程序已经发展到命令性(具有显示操作)的微型语言范畴,几乎快成为通用解释器。bc(1) 和 dc(1) 都是完备图灵机语言的好例子,它们都是命令性微型语言。



编程和语言之我见

编程和语言之我见

redraiment, 2009-07-25





  我觉得“编程”的概念相当宽泛,程序早在计算机出现之前就存在。我们现在进机关办事,仍不时会听到“做事要按程序/规矩/规 章制度来”。比如我们学生项目基金报销,要按先后顺序依次执行“填报销单、交团总支审核、院长助理签字、财务处复查”等步骤。而这些就是所谓的“程序”。

  因此,程序就是为达到某个目标而需要执行的步骤;而如何把这些步骤有意义地组合起来,这个过程就是“编程”


  用这个定义去匹配,会发现周边很多事情都是编程。比如编写文档随时要保存,我需要在记事本里执行:点击菜单“文件(F)”-点击菜单项“保存(S)”。这样就达到了保存文档的目标,但如果我们将这两个步骤执行顺序颠倒,则执行结果就无意义,在C语言里你或许会得到一个“Runtime Error”的提示(关于此话题的更多讨论,欢迎下载我在“子清行”中的《编程村一日游》)。


  程序设计(programming)好了,如果我们需要委托其他人或计算机帮忙执行,我们就需要将这些步骤用对方能理解的语言描述出来(coding)。比如上面报销的例子,财务室老师就是用自然语言向我描述。


  我最近对语言(主要是编程语言)很感兴趣,接触了一点DSL(领域特定语言),觉得它让软件和语言的边界变得模糊,使得语言的概念变得更加宽泛,甚至可以认为所有的软件都是一门语言


  先来简单地介绍一下DSL,它是 Domain-specific language 的缩写。顾名思义,就是为问题所在的特定领域设计一门通俗易懂的“方言”,使得解决该领域的问题变得更形象、更自然(比如 SQL 语言就是访问数据库这个特定领域的方言);语言是我们用来描述事物、传递思想的工具,不同的语言仅仅是对同一事物表述不同而已。比如中文管“0”叫“零”、英文里叫“zero”。


  我们使用软件未曾不是如此?“用鼠标点击计算器上的按钮1、按钮+、按钮2、按钮=”与“echo 1+2 | bc”描述的都是“求1+2=”,只是前者是针对 GUI,后者用了 CLI。如此看来,我们在处理人机交互时很多时候都是在为用户设计一门特定的语言。如果设计的语言迎合用户的口味、符合用户的操作习惯,就称为用户体验做得很到位,否则将无人问津。

每每想到这里,我都会憧憬一下未来的编程:可能以后会流行使用语言的语言——“元语言”来编程,首先用这门元语言快速地开发出一套“方言”,然后使用该“方言”来解决某个特定问题。到那时,程序员和普通用户的区别也就不明显了,程序员之间交流的不再是“我开发了某某功能库,发给你用用?”而是“我写一套某某方言,你要不要耍耍?”^_^。

下一步,用拼音搜索屏蔽词?

下一步,用拼音搜索屏蔽词?

redraiment, 2009-07-19





  最近,国外的Twitter、国内的饭否相继遭墙,与此相似的一些网站也都组织调整。

  比如“做啥网”表态准备上线搜索屏蔽词功能,就是类似 baidu 和 g.cn 的“据当地法律法规和政策,部分搜索结果未予显示。”


  这我让回忆起以前逛论坛时看的帖子,很多论坛(例如DVBBS)都自带屏蔽敏感词功能,如果帖子中有词组与后台敏感词数据库匹配得上,就用‘*’来代替。我尤记得周杰伦的《听妈妈的话》被系统自动改成《听妈**话》。


  但他们也提到:现在的网友也很厉害,会运用谐音啊或者自己创造一些词语,婉转表达敏感信息。理论上需要每条信息人工审核后才能发布,不过限于人力,目前“做啥”还没有准备这样做。


  这我在想起很多年前用WinTC时里面自带了一个点阵字模工具,除了能将一个汉字转换成点阵字模,还会用这个汉字的拼音来做数组名。当时很好奇,就去找了一点相关了资料,才知道像GBK、Unicode等编码本身就是和拼音相关的。撇开这些不算,即使直接对65536个汉字建立映射表,假设汉字2个字节,拼音最长的zhuang算6个字节,整个映射表也不到1MB的空间。


  所以,为相应有关部门的号召,也许不久的将来论坛、微博等会采用拼音来搜索敏感词汇的工具来。到时候“草泥马”此类神兽通通都得贴上和谐标签。


午夜惊魂

午夜惊魂

redraiment, 2009-07-12





  午夜时分,窗门紧闭的房间里突然传出一阵奇怪的声音:像是有人在走动,但又显得步履阑珊。好奇之下我打开电灯,灯光下映射出一个倒挂的身影:尖牙利爪、鼠耳猪鼻,狰狞的面孔上镶嵌这双颗绿豆大的眼珠,正直勾勾地盯着我...

  我刚醒来眼睛朦胧,第一反应是“谁把黑色垃圾袋挂到日光灯上了”。带上眼镜和它对视半响...像!非常得像!像是《奇人奇案》中那些咬人的大蝙蝠(喜欢到处串门),不过个头小很多。我不急着赶它走,我晓得它对我没兴趣。就寻思着几个问题:


    1. 门窗我很早就关了,晚上待房间这么久一直没发现它的存在。它是怎么进来的?
    2. 既然它进来了,房间里会不会还有其他的伙伴?
    3. 它不会也像电视里那些变态蝙蝠喜欢流口水吧?我的房间可是刚拖过地的T_T...

  没等我构思出第四,它很识趣地落到地上对着我做匍匐状。我暗自窃喜:“小子!没用的!即便你跪地求饶,像我这么洁癖的人,岂能容忍一只成天和苍蝇蚊子打交道兼职做做狂犬病菌传播事业的吸血恶魔和我共处一室!”


  我先四下检查门窗是否严实,我倒不是怕它逃跑而是怕外面援军进犯T T;接下来就是狙击!环顾四周,房间里一向歌舞升平,所以没准备什么大规模杀伤性武器,没有居安思危阿!翻箱倒柜找出一只箱子(在家我懒得跑上跑下去倒水,所以直接搬了一箱饮料上来,可见懒惰焉知非福呀)。于是和蝙蝠大哥商量商量:早闻先生超声波水平一流,正奈何此等阳春白雪非我辈凡夫俗子能欣赏,故为先生另辟雅间(手指纸盒),还望笑纳~恩,你既不作声我并算你答应,切莫抵抗,坦白从宽抗拒从严!


  好在小时候整天在蜘蛛、蜻蜓堆里鬼混,三两下就将它罩在箱内——“小样~叔叔可是练过的!”理论上本应处以极刑,但突发奇想对它独特的睡姿很着迷,又恰巧饮料盒上有一小块是透明的玻璃纸,借机观察观察。不料它不配合,我观察地眼皮打架它还没有要倒立的意思,静心一想才明白过来:蝙蝠是昼伏夜出型的哺乳动物!哎,白等了这么些时候~关灯睡觉!怎想我刚睡着它有开始隐隐作祟!于是我学如来佛祖镇压孙悟空,在“五指山”上再压上一碟DVD,总算将这斯镇住。

后记

  早上起床带上手套去料理这个家伙,不想它在我这个空调房里还挺惬意——以天为被地为席,全无蝙蝠该有的本色。做只蝙蝠好歹也敬业一点嘛,怎么可以趴着睡觉!多亏了你们蝙蝠不上网,不然也赶时髦给你拍几张玉照。本打算就地正法,突然想起美国佬控告肯德基一刀封喉是虐待鸡,要求将鸡置于密封塑料袋中闷死。我也怕他们控告我,于是将盖子盖好,抛到蚊子苍蝇最充足的垃圾堆里任其自生自灭。阿弥陀佛,小蝙蝠终于结束了它心惊胆战的一夜!


一个好玩的现象

一个好玩的现象

redraiment, 2009-07-05

一个好玩的现象





  这学期上了一门叫“软件工程实践”的课程。目的在于从需求分析、概要设计一直到验收结题,全程模拟真是的软件项目开发过程。让我们这些象牙塔里的本科生也有机会体验一下实战经历。

  一个学期做下来,对我来说印象最深的就是文档写作。相信很多程序员对写文档这档子事都是深恶痛绝。我们的需求频繁地更改(估计是老师们为了体现真实感而故意前后说得不一致),导致每次洽谈结果都是要修改大堆文档。但是我的厌恶倒并不在于需求变更,因为不管需求变化不变化我回来都照样工作,对于具体是什么工作我倒并不在乎。原本在Debian下我习惯用LaTeX来排版,但课程是硬性规定只能用Word排版、Visio画图、打包成rar提交。可惜了Word和LaTeX我都是半桶子水(不好意思,给咱们科班丢脸了),所以期间遇到了很多问题。但在用Word修改文档的过程中突然发现了一个很好玩的现象:“一个新手往往事必躬亲,每件事都亲历亲为;相反那些老手或者高手倒都是一个个懒人,能让机器做的绝不自己做。


  初看觉得很好笑,因为事必躬亲往往是那些能力强又追求完美的人喜欢做的:周围比自己好的人不多,事情交代下去就是不放心,干脆就自己解决掉算了。但环顾四周和计算机打交道的,猛然发现我们平时还真抢了不少计算机的饭碗!而且很多时候的烦恼都来自这些原本不属于自己的事情(的确有点杞人忧天,庸人自扰)。

从使用软件的角度看

  例如,作为一个Office(或者网页设计)新手,由于对软件功能的不熟悉同时也是在好奇心的驱使下,往往会不厌其烦地为每一句话甚至每一字设置字体、字号、颜色等,对每处细节都精雕细琢、力求完美(例如文档要求所有的引用需要用五号斜体宋体,新手们就手工一段一段地设置尺寸为五号、字体为宋体、风格为斜体,如果文章长的话就得花费很多时间),最终呈现的产品也可能完全符合要求。但这样的做法可维护性比较差,如果临时提出要求说所有引用的段落都要加粗,此时新手们可能要加班加点地给所有引用的段落添加粗体风格(可能会有遗漏。万一修改完成后又要求重新改回去,估计再温和的人都要发飙了^_^);老手们有更简便的方法,就是定义一些格式类型然后去套用(例如标题1、标题2等),要统一修改时只要右键“选择相同格式的文本”,就可以一次性全部重新定制。我们只需向计算机描述我们想要什么,比如告诉LaTeX,我要写一个报告(\documentclass{report}),标题是“Test”(\title{Test}),作者是“redraiment”(\author{redraiment})等等。至于“报告型文档”该怎么布局、标题该用多大尺寸、作者名是不是应该用斜体,都无需我们劳心,这些是LaTeX的工作。


  “绿色软件”这一概念也是一个很典型的例子!作为一个成熟的操作系统,统一管理软件包的安装与卸载属于份内之事。安装一款新的软件,不仅仅是把软件拷贝到硬盘上,将自己融入整个系统之中,在需要它的时候能很方便地调用(比如用IE在网页上打开一个pdf文件能自动调用Adobe Reader来显示)。而这些和操作系统打交道的工作交给系统本身是再合适不过了;“绿色软件”的思想是让应用程序与系统泾渭分明,目的在于尽可能少地产生系统垃圾。传统的“绿色软件”是很有益的,它们大部分都属于小工具,实在没必要向系统注册什么信息,这也恰巧体现了“物尽其用”的原则。只是最近“绿色软件”有被滥用的趋势:像office等通用软件也被制作成“绿色软件”。这意味着你要手工进行文件关联等操作,结果往往没系统自己做的好。我称他们为绿色发烧友,因为他们决定完全摒弃系统自动化的软件管理程序(由于抵触系统垃圾或其他什么原因)。

从开发软件的角度看

  产生上述这些现象有一部分原因在于新手对软件功能的不熟悉,也有一部分原因在于软件本身没做好本职工作(比如Windows环境下注册表体积增大的确会影响系统响应速度)。


  软件开发过程中也有很多此类现象:用Java开发GUI程序,新手普遍还不能理解Layout布局带来的优越性,为达到理想效果一般更倾向于用setLayout(null),把控件位置的控制权掌握在自己手中。但诸如不同平台上可能显示的位置不同,或出现重叠等棘手问题将接踵而至。


  另一个典型例子就是我们这些年轻程序员往往有一种“非自己做不可”的强烈情绪,相比于去理解和维护前辈们留下的代码更乐意于自己从零开始创作。这导致的结果会是文化没有沉淀、知识没有积累,从软件专业的角度来看就是代码没得到重用(重用的话题以后再聊)。一味地从零开始创作而不是在以往的基础上进行拔高,一般很难有所突破。

无为而治

  从上面的例子来看,似乎这是初学者过度到有经验者需要经历的一个阶段。这是不同的人,理解事物的方式不同:上述的新手们可能都是从结果到原因,而老手们则是从原因到结果。比如第一个例子中使用word排版,新手们就是因为“引用文字是斜体”这个结果才把某一段文字设置成斜体,而不是“因为这段文字是引用,所以它才是斜体”。如果一开始就本着这样的思想去学习,也许会少走一些弯路。


  事必躬亲虽然精神上值得鼓励,但可能不是长远之计。用这种方式去思考问题容易钻牛角尖,也容易沉浸于一些奇技淫巧中而学不到真正有价值的东西,终究只是看的见一棵树看不到整片森林。比如会有很多经验丰富C程序员告诫你“循环中用++i比i++快”、“整数的乘除尽量换成移位运算”等等。这些编程技巧基本上都是那些编程老手和自己的编译器混得太熟,以至于愿意为它们分担一些工作。但终归到底和语言本身无关,何况现代的高级编译器都已经具备自动优化功能。过度地手工优化不仅可能破坏代码的可读性和移植性,而且让编译器难以进行优化、发挥不出其长处,到底是聪明反被聪明误!


  而尽量让计算机来做事,这不仅体现“物尽其(奇)用”、“各司其职”,还反映了道家的无为思想(我所理解的无为不是不做任何事情,更确切的说应该是不做多余的事情。即“最小行为”或“按自然法则行为”。由于我的坚持,在中学里曾一度被语文老师树为反面教材)!它让我们摒弃一切不相干的事情,一心着眼于问题本身,提高解决问题的效率和质量。

后记

  “不做多余的事情”,这是与计算机打交道的方式,但不应该用来处理人际关系。虽然我们也都有各自的工作要做,但我还是挺愿意偶尔帮我老爸老妈干点活的~



用DOS批处理来做数字图像处理

用DOS批处理来做数字图像处理

redraiment, 2009-07-03

前言





  我最近对语言挺着迷的,很想学习一下《编译原理》。询问了老师才知道我们已经取消了这么课程(他们觉得学了没用) ,一时间也没找到什么好的教材,如果有好心的朋友可以推荐几本关于编译原理的经典书籍,感激不尽!

正文

  图灵机是由输入、输出和状态转移函数三要素组成的,广义上的自动机模型。理论上讲任何任何完备图灵机语言都可用于通用编程,并且和其他完备图灵机语言一样有效。但实际上有些此类语言作用在其特定领域之外时可能令人非常痛苦。例如m4是一种有意的完备图灵机,但实践中把m4当作通用语言使用则非常困难。


  最近对一些计算机语言进行分析,总结一门最简单的可编程的语言也应该具备:

  • 输入输出。获得待处理的数据,可以是从标准输入输出,也可以从文件;
  • 算数运算。计算机的核心当然是“计算”,就是普通计算机上提供的加减乘除运算;
  • 内存管理:临时变量值的获取和存储管理,其实有点像通过变量名来查找值的Hash表(这在DOS的批处理中体现的很到位);
  • 按条件跳转:拥有条件判断(test),加上语句跳转(jump),就能模拟出if、while、for和goto等语句(其中goto的条件为永真,就执行“test(true) jump xxx”一样)。


  按照上面的说法,程序解释器很像是一个功能加强了的计算器(原来写个计算器也这么不容易,以前低估它了T_T)。纵观周围的工 具,很多看似简陋的小工具原来都符合上面的要求。像UNIX里的命令行计算器bc(1)/dc(1),都是完备图灵机;DOS的批处理同样也具备,下面来详细讨论。


  批处理中可以用set 给变量赋值; set /a 可以进行算数运算,在命令行中执行set /? 可以查看所有支持的运算符;另外还有if、for、call、goto等语句支持跳转; set /p 和echo 可以实现从键盘和屏幕上输出文本信息,但对二进制文件的操作显得有点力不从心(可以用debug 来实现,但貌似 挺复杂)。所以我用C语言写了两个小程序(Bmp2Txt和Txt2Bmp,可到子清行下载二进制文件和C语言源码),解决批处理对BMP文件的输入输出。下面是我用这两个小工具写的拉普拉斯算子求边缘检测的批处理源码:

::用拉普拉斯算子来做边缘检测
@echo off
setlocal enabledelayedexpansion
if not "%~x1"==".bmp" goto error
if not "%~x2"==".bmp" goto error

Bmp2Txt %1 $$temp$$.txt
::将BMP的像素集合保存到数b
call Txt2Array b < $$temp$$.txt
set t.width=!b.width!
set t.height=!b.height!
for /l %%y in (0,1,!b.height!) do (
    for /l %%x in (0,1,!b.width!) do (
        set ny=%%y
        set nx=%%x
        call :calc
    )
)

::将数组转换成文本文件
call Array2Txt t > $$temp$$.txt
Txt2Bmp %2 $$temp$$.txt
del /q $$temp$$.txt
goto end

::Functions
:error
echo.&echo  usage: %0 Input_BMP_File Output_BMP_File
goto end

:calc
set /a t[%ny%][%nx%]=4*!b[%ny%][%nx%]!
set /a dy=%ny%-1
set /a dx=%nx%
if defined b[%dy%][%dx%] set /a t[%ny%][%nx%]-=!b[%dy%][%dx%]!

set /a dy=%ny%+1
set /a dx=%nx%
if defined b[%dy%][%dx%] (set /a t[%ny%][%nx%]-=!b[%dy%][%dx%]!)

set /a dy=%ny%
set /a dx=%nx%-1
if defined b[%dy%][%dx%] (set /a t[%ny%][%nx%]-=!b[%dy%][%dx%]!)

set /a dy=%ny%
set /a dx=%nx%+1
if defined b[%dy%][%dx%] (set /a t[%ny%][%nx%]-=!b[%dy%][%dx%]!)

goto :eof

:end


  在我的机子上跑了一两分钟居然也跑出结果来了,相应的效果图如下。


  原始图:原始图


  处理后的图片:Laplace处理后的图片




I Have a Dream

I Have a Dream

redraiment, 2009-07-03





  我们本学期学了数字图像处理,上机实验使用C语言,内容都相对比较简单。唯一复杂一点的也就是如何从BMP文件里读取图像信息,反倒是真正与课程相关的算法处理却像做加减法一样很简单。我觉得我们的课程安排上有很多不合理的地方,往往在学一门课程时需要很多前置知识。比如以前学“计算机图形学”是要求上机用C++&OpenGL,结果很多同学上机不成功不是因为课堂内容不理解,纯粹是因为OpenGL不晓得怎么使用。

  我一直憧憬着我们的计算机能平民化、大众化,降低大家的学习、使用门槛。如果我们学习时,有一门语言能屏蔽大部分和课程无关的细节,而只让我们专心于考虑和课程相关的问题,也许这样的效果会更好。这样的做法就好比我有一个月假期,我想去北京旅游一趟,而导游一路上一个劲地介绍说杭州有名胜、南京有古迹、山西还能看兵马俑……这样一路下来,估计一个月也未必能到达目的地北京,或者到了也不能尽兴。索性抛开一切坐飞机直达目标玩个痛快!


  本着这样的理想,我很想设计一门新的语言,尽量降低大家学习的难度,能专心的去做感兴趣的事情,苦于一直没找到一种通俗易懂、老妪能解、雅俗共赏的方式。传说面向对象的思想很接近人类的思维方式,理论上讲应该很好学、容易被普通人所接受,但事实是我们这些科班出身的人也未必能领悟到其精髓。


  我们所学的知识很多时候就像是工具,我们学习并使用它是希望能改进我们的工作方式、提高效率等等,但无论是出于什么目的,都绝不会为了自寻烦恼。可惜很多人就是喜欢玩弄自己的学识以求与众不同。


  例如,语言作为我们沟通的工具,其意义在于能相互交流思想,能将自己的想法传播出去。但很多专家就是喜欢玩弄语言:正话、反话、倒话连着说,十个人来理解能看出二十种意思,没人能明白其真正含义,但他们依然我行我素,陶醉于其中,完全脱离实际。做这样的学问,不免得有些孤芳自赏了吗?再比如,如果周围的人都认为“下里巴人”是个贬义词,我觉得这时候为了能正常沟通而放弃一下自己的原则也无可厚非。


  但愿计算机技术能避免卷入这些的漩涡中!但眼前也出现了少许并不“和谐”的景象:比如优秀的程序员就用C++、聪明的程序员用Delphi等言论;还有Unix是高手们用的,汝等草民还是回归Windows等。这让我联想到《无根的根》中无名师教导新门徒:“家猫也能欺负老虎,但猫叫永远比不过老虎吼。”


  我们应该时常扪心自问,我是不是在孤芳自赏?也许计算机也要时刻谨记党的宗旨:以广大人民为中心!



物尽其(奇)用

物尽其(奇)用

redraiment, 2009-07-02





  去年ACM竞赛的奖金发下来了,但队友都已经离开学校了,就趁周末回来领,顺便大家聚一聚。席间很自然地聊起了我们当初因志同道合而相识,如何为AC而疯狂,如何“保卫”我们的机房等等。我告诉他们说现在条件可不像我们那会儿了,学院已经设立一个专门的实验室供ACM集训队使用,人手一台计算机,进门用指纹锁,讨论时还有大屏幕……可谓是应有尽有。以前的机房没有节制:K歌的、看电影的、玩游戏的,甚至还有谈恋爱的!二三十来平米的机房即是KTV,又是游戏机房,也是免费网吧。我们当初就是在这样的环境中一天16小时不吃不喝(但会上厕所^_^,怕离开久了机子就不是我的,而是其他人&病毒的了T_T)地忘我编程;想进机房偶尔还得看一下楼管大叔的脸色。

  谈到这里,我们几个人都开怀大笑,我们都一致认为:那段时间虽然条件比不上现在,但的确比现在好玩多了。我们都庆幸自己有这样的经历,估计学弟学妹们是很难体会到了~


  原因很简单:杀鸡用牛刀可能没什么成就感,万一没成功还只会闹笑话;相反,物尽其用是一件让人很自豪的事情!我小时候比较好动,对数理化又非常感兴趣,当初经常在自己家里做点《自然》课本上的模拟小实验。没有硫酸盐酸,就用家里的白醋代替;没有碳酸钙,就买包旺旺雪饼,拿里面的干燥剂泡泡水就有了;没有试管,就拿写完的圆珠笔套来代替;没有显微镜,找四片老花镜相互调好焦距,也能放大好多倍……这些乱七八糟的东西可能本身没带给我什么伟大发现,但让我的童年生活过得很特别,我也因此对数理化更有兴趣,现在回忆起来我会很乐意告诉你:真的很好玩!


  有时候想想,条件差、资源不充分这些未尝不是一件好事,它用另一种方式鼓励大家开动脑筋去解决问题,也算置之死地而后生吧^_^。作为软件班的学生,使用计算机的频率很高,在寝室里配备一台电脑显得很有必要,不过我一直坚持到现在才买,更多的也是出于这样爱玩的心态。大一时在那个“KTV、游戏厅兼网吧”里混得很开心,后来承蒙老师们的眷顾在实验室里有了一台自己的Linux的计算机,并管理着一台对公网开放Web服务的HP服务器。而我那800块钱的山寨机也极其给面子,居然也能上Web网。于是乎我将很多日常活动移植到Web上,然后通过手机办公~因为手机容量有限,无形中也让我喜欢上简约的风格,并尽可能多地让服务器帮我做事情(这可以减少不少WAP流量哟,我也因此对古老的批处理式计算机怀有好感,因为它可以把计算机的能力发挥到极致,不浪费任何资源)。比较典型的几次搞怪就是让我的机子每日每夜地帮我玩校内网的好友买卖、古惑仔等游戏,结果是人家判我使用外挂把号给封了!还有很多其他好玩的轶事。服务器对外网只开放了HTTP服务,这一苛刻的限制却无意地让我更早接触到Web Services这一概念,也算因祸得福,无心插柳柳成荫~


  现在软件工具很多,硬件更新也奇快。但也许我们并不用急着升级我们的计算机,因为大部分情况下电脑和人脑一样,都没有让它们100%地工作。所以如果你是为了学习,尝试着去“折腾”手头的计算机的确是件很好玩的事情,希望大家不要让丰饶的工具抹杀了创造力。学会既要安于现状,也要不安于现状。安于现状是希望大家去接受和珍惜所拥有的,不要在抱怨客观条件不充分上花太多时间和精力;不安于现状是充分发挥自己所拥有的,去创造和收获更多的财富。愿大家尽量保持我们的创造力~

我终于活着回来了!

我终于活着回来了!

redraiment, 2009-07-01





  我不得不像个怨妇一样再次声明:我讨厌坐车!!!非常非常非常非常的讨厌!现在是极度憎恶!每次坐车都跟打仗一样,今天要不是强忍着,3个塑料袋已经不够我用了。

  今天在车上又吐成软体动物,突然灵光一闪,犹如醍醐灌顶,领悟到——我的反应真的很迟钝,总会慢半拍。这一点体现在很多方面:比如有惊喜的事情发生时,总是不能及时地给出一个合适的表情,以至于让人家误会我天生就一副嘴脸;再比如我每次学一门课,都不能按期达到课程要求,因此期末考试总是不能如意;坐了这么多年的车,学了这么久的英语,依然没有任何提高,这也是很好的体现。


  如此看来我是没什么天赋的人。但仔细回想一下这三年来的学习历程,发现我还挺有的恒心的,挺耐得住寂寞的,呵呵呵~当初Java考试我只有80分,在班级里比我分数高的人大有人在。但很可惜他们学完后没有好好利用这门语言;但我在学完之后,依然在各个地方使用Java来开发,慢慢地也就略有领悟,体会到Java的独特之处。现在我能有自信地说在班级里Java我还算比较熟的!


  想到这里,我不禁要感谢上苍待我不薄,没剥夺我这份执着(最后一点不算优点的优点)~



版权声明
本人的所有原创文章皆保留版权,请尊重原创作品。转载必须包含本声明,保持本文完整,并以超链接形式注明原始作者“redraiment”和主站点上的本文原始地址。


开源不应作为推荐的理由

开源不应作为推荐的理由

redraiment, 2008-09-04

前言





  明天去学校啦,近两个月的暑假结束了,来总结总结这个暑假的经历。早在放假前,我就计划好了,这个暑假一定要熟悉一下 Linux 的使用。在这个期间,我也看到很多开源人士和 Windows 的铁杆粉丝们在论坛等地方吵架。有个支持开源的朋友说:“当你听到开源软件时是什么感觉?给我的,是感觉亲切,没有浓重的商业气息。”;还有很多软件商,在向用户推荐自己的产品时,都不忘加上一句,“我们的产品是完全开源的”。

  于是我开始思考了,对我来说,开源的软件和非开源的软件区别在那儿

正文

  首先阐明一下,我是软件工程的学生,但现在先暂时搁下这个不说,我就从作为一个普普通通的用户来说,一个像我爸爸妈妈这样的电脑盲的角度来说:软件开不开源,与我何干?有一点不能否认,电脑再怎么神奇,充其量就是一个便捷的工具而已。既然它作为我的工具,我所在乎的仅仅是它能不能高效地替我完成任务而已。

  我来说说我这段时间用 Linux 的体验,我用的发行版是 FC6,在新华书店花68 RMB买的。总体感觉非常不错。我时常要赞叹一下它的强大和灵活。但是,有时让我也感觉很烦心。

  一开始,我先让自己去熟悉 Vim 编辑器,因为我要用它来编程,熟悉自己的开发工具,能提高开发效率。Vim 提供的功能确实想大,所以有人把他和 Emacs 并列称为最强大的编辑器。但是,刚默认安装完的 Vim,还是很简陋的,需要根据的需要进行设置。比如,我要开启语法高亮功能、智能缩进、自动填充语句、还要代码折叠等等。我用的都是一些简单的基本功能,但由于我是新手,不熟悉,配置还是花了老半天。

  接下来就是去看看浏览器,FC6 里自带的是 Firefox 1.5,我到官网下载了最新的3.1。然后安装了 Google toolbar、CHM Reader 等插件,再换上一套酷一点的主题,毕竟看浏览器的时间比较多,不赏心悦目一点怎么行。

  最后再动动系统本身,去掉一些不用的后台服务,卸载一些自己不用的软件包(比如蓝牙设备等),最后界面也美化一下。

  忙活了半天,总算是用得称心如意了。我在自己这样精心搭建的环境下能高效的工作。此时 Linux 给我的印象就是配置配置还是配置。但我突然想起了自己以前还没未接触 Linux 时,曾经和同学抱怨过:自从有了 Ghost 来安装系统,安装一个系统只要20来分钟,但接下来装驱动、装软件等配置一个满意的 Windows 却要花掉一天!所以 Windows 也一样。

  无论是 Windows 还是 Linux,我都是根据我自己的需要进行了个性化配置,而它们经过我的配置,都能满足的那些需要,完成我指定的任务。就这一点来说,至于我用的是不是开源软件,的确和我没太大关系。在我看来他们是一样的。

  那我关心的是什么呢?我举个例子,在 Windows 环境下,我用 Visual Stdio 2005 来编写代码,VS 2005 也提供了语法高亮功能、智能缩进、自动填充语句、代码折叠等功能。就功能上说,VS 2005 带给我的,和 Vim 是一样的。都能满足我的需求。但有一点,让我对 VS 2005 多一点好感,就是这些我想要的功能默认安装后就直接提供的,不需要自己额外去配置,去安装插件。

  这就是我比较在乎的问题,像我这样如此被动的用户,只有在不得已的情况下,才会去亲自动手配置软件。一般情况下,都是直接默认安装软件的。如果两款软件,实现的功能一样,但其中一款默认的设置最解决我的个人喜好,那我想我肯定会选择使用它!因为我安装完就能马上使用了,这软件就像是我老朋友一样,知道我的喜好,知道我需要什么样的功能。

  但我们老师一直在和我强调说,开发软件的真谛是“只提供机制,不提供策略”。其实我一直不苟同这一说法。我是觉得软件“既要提供机制,也要提供策略”。

  不晓得大家用的是什么中文输入法?在 Windows 下,我以前是用智能ABC ,智能ABC 虽然智能,但还不是非常好,它的词排列顺序是固定的。后来我用了谷歌输入法,它能把你频繁地输入的字自动考前,下次输入时词的排列顺序就按使用频率来排序了,自然用户能很快找到自己需要的字,就好像这个输入法知道自己在想什么,每次出来的都是我想要的。这样的软件我用起来感觉很舒心,虽然它不是开源的。

  但要真的实现如此舒心的软件,是非常困难的,它需要大量的需求调查,了解用户们真正的需求,甚至还包含一些心理学上的知识。而再神奇的功能,如果没有需求,那也是废物一个。有个经典的例子,至今有老外还在使用 Win 95 (原文请看这里),按他说的,这也是一个需求的问题,Win 95 提供的功能已经很好的满足它的要求了。

因此,对于我们用户,你和我说软件开源(不一定是无偿免费开源),对我来说那不关我的事,我在乎的是你的软件能不能高效地完成我给定的任务,是不是我每做一个小动作,都要先配置老半天?

  而对开源感兴趣的人,我想应该是此类产品的开发者,他们需要通过源代码来借鉴其他人的技术,并以此来交流和提高自己的水平。这个暑假中,我在编写一些  Linux 程序时,也借鉴了 tr、curl 等程序的源代码。所有,向开发团队去强调开源,那是比较明智的,而不是在一堆电脑盲面前吹嘘不停。

后记

  这两天我突然有了一个很“疯狂”的想法:是不是开源软件是故意这样做(只提供机制,不提供策略)的?因为开源软件是不通过买卖软件来賺钱的,而是通过后期的培训和维护等服务来赚钱的。但如果开源软件前期也做过充分的市场调查,了解用户的需求,然后在软件设计时,默认的设置最大地满足了大部分群体的需要。那也就意味着 Linux 等开源软件也简单易用,容易上手。这么以来,大部分用户就不需要去培训和维护服务了。那开源软件靠什么来赚钱?

  所以,撇开自己使用源代码这一点来说,纯粹的在用户使用这个立场上来讲,开发开源的软件比开发商业软件要容易:因为开源软件前期不用考虑用户的需求,只有后期用户需要什么需求我针对性的进行培训,这样每个用户手中的软件经过自己的配置,可能都是不一样,这样能满足所有用户的个性需求;而商业软件前期有点“预测性”的估计用户的需求,然后到了用户手中的软件配置都是一样,这样就不一定能满足所有用户的需求。要自己配置的话反而另外还得去培训等,这比起开源多了一个环节。

2009-08-10

  不过我最近又有新的想法:小孩子学自行车,辅助轮迟早是要卸下来的。
虽然 Windows 很容易让新手入门,但不能永远停留在初级阶段,终究有一天是要自己去配置系统的。




MD5算法实现注意点

MD5算法实现注意点

redraiment, 2008-08-29

前记





  最近很有危机感,发现自己相对别人毫无优势。虽然在班里成绩还算拔尖,但最近想静下来认认真真做一个小东西出来,却发现自己虽然感觉什么都知道一些,但却什么都做不出来!
盗版李宗盛《最近比较烦》的一句歌词“最近比较烦比较烦比较烦,我看那前方怎麽也看不到岸;那个后面还有一班天才追赶哎呦,写一段皆大欢喜的程序,是越来越难”...打击太大了。
这种时候最不能混乱了,我要安安稳稳、认认真真、集中精力只去做一件事。
就先编个MD5算法吧,很早就看它不爽了,但一直狠不下心来自己写一个。
所谓祸不单行,困难就好像约好了一样,本来一件简单的事情居然让我折腾到半夜,特来记下中间的坎坷。

正文

  早在高中的时候,做过一段时间工具黑客,每每入侵一个论坛(比如动网),获得管理员的密码后,都要拿工具暴力破解 md5 密码。打那会儿开始就没对它有好感。
现在学过C语言了,终于能自己来写个“乱七八糟”的程序了,回想起当年的雄心壮志,就开始自己动手来实现md5加密算法!

第一步当然是先到 Google 上搜索相关资料咯。先饿补一下 md5 的知识。
我这次鬼使神差地进入了 www.google.cn,而不是以往的 www.google.com 英文版。也因此埋下了祸根呀!
用关键词“md5”直接搜索,看到百度百科的链接。心想自己怎么糊涂了,这么出名的算法,百科里一定有的呀。
打开链接,简单地浏览了前面的历史背景介绍什么的,进入了主题“算法描述”。
看完之后,我感觉我这次又要黄了,根据它的描述,我实在无法实现这个算法,因为有太多地方描述不清楚了!
我一步一步写完程序后,本打算自己把所有可能的情况都试试看,希望找到正确的结果。但很快发现这不可能。
所幸,百科里留下一个链接:http://www.ietf.org/rfc/rfc1321.txt),这是一份最权威的文档,由 Ronald L. Rivest 在1992年8月向 IETF 提交。
我对照英文原文看,发现中文版里不仅有很多没描述清楚,甚至还有很多错误!

下面我按照算法实现步骤,把需要注意的地方列举一下,具体实现可以参考英文原文:

一、首先是要对信息进行填充

1.在原来的信息基础上,在后面进行填充,使其字节长度除64余56。即64*N+56的形式。
2.用于填充的位是:第一位为1,其他都为0。
3.填充必须进行!也就是说,即使原始信息长度余数本来就是56,那也得再填充64字节的信息。
4.最后8字节长度的空间来保存原始信息的长度。
1)单位是bit,即位。这一点我查可很多中文资料,都没有说明,所有一开始我一直在琢磨长度单位是bit还是byte。
2)最后8位的内存存储形式是低到高。这一点也没有说明的,开始我也一直在想,这8位到底是怎么用的?因为内存是从低到高的,而我们平时写数字,比如0x1234是从高到低的。最后我查看Linux下开源的程序md5sum,才知道是把8位作为一个整数从低到高存储的,所有在实现的时候,我直接用了long long来存储,然后用memmove()来追加到信息串里。
5.填充完后,整个信息串就是(N+1)*64个字节,关于N,百度百科里说N是一个正整数,也就是说填充完的信息最短是128字节;但实际上N是一个非负整数!也就是说,N可以为0,而信息的长度最短是64字节。这个错误让我郁闷很久。

二、四个初始常量的值

百度百科里原文:“MD5中有四个32位被称作链接变量(Chaining Variable)的整数参数,他们分别为: A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210。”
这又是一个错误的地方,英文原文中说这个四个常量的值从低到高依次是:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
  上面说过内存存储方向和我们平时书写是相反的,所以定义的时候应该是:
#define A 0x67452301UL
#define B 0xEFCDAB89UL
#define C 0x98BADCFEUL
#define D 0x10325476UL
  这一开始也让我郁闷。

三、四轮加密的函数

  四个非线性函数没有问题:
#define F( X, Y, Z ) ( ( (X) & (Y) ) | ( (~(X)) & (Z) ) )
#define G( X, Y, Z ) ( ( (X) & (Z) ) | ( (Y) & (~(Z)) ) )
#define H( X, Y, Z ) ( (X) ^ (Y) ^ (Z) )
#define I( X, Y, Z ) ( (Y) ^ ( (X) | (~(Z)) ) )
  但是四轮的加密函数就有问题,我看过几篇不同的md5算法文章,不知道是不是显示问题,函数表达式连括号都不匹配!所以想不用想,那些表达式没有参考价值!最后看 md5sum 的源代码才知道具体的实现方法:
#define FF( a, b, c, d, Mj, s, ti ) \
    (a = b + LOGIC_SHIFT_LEFT( ( a + F( b, c, d ) + Mj + ti ), s ))
#define GG( a, b, c, d, Mj, s, ti ) \
    (a = b + LOGIC_SHIFT_LEFT( ( a + G( b, c, d ) + Mj + ti ), s ))
#define HH( a, b, c, d, Mj, s, ti ) \
    (a = b + LOGIC_SHIFT_LEFT( ( a + H( b, c, d ) + Mj + ti ), s ))
#define II( a, b, c, d, Mj, s, ti ) \
    (a = b + LOGIC_SHIFT_LEFT( ( a + I( b, c, d ) + Mj + ti ), s ))

四、最后的输出

  几乎所有文章都是写道四轮加密就结束了。而我的算法实现到这里,产生的最终的四个数值:a, b, c ,d。这四个数都是32位的整数。于是我就直接用printf ( "%08x%08x%08x%08x\n", a, b, c, d ); 结果却怎么都不能正确!但按文档上的算法说明,没有错误呀。无奈还得参看 md5sum 的代码,单步跟踪下去,发现算法完全正确!再看他的输出函数,原来是先把结果在转入一个长度为16的 char 数组里,再逐个输出!又是数值存储的高低位顺序问题!改完就通过了!
下面附上我的代码,在 FC6 + GCC 下通过。其实代码还能再精简一下的。晚了,先睡觉!

程序清单

/*
 * md5 -- compute and check MD5 message digest.
 * this version only can calculate the char string.
 *
 * MD5 (Message-Digest algorithm 5) is a widely used, partially
 * insecure cryptographic hash function with a 128-bit hash value.
 *
 * Author: redraiment@ZJGSU.edu.cn
 * Date: Aug 27, 2008
 * Version: 0.1.6
 */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>

#define SINGLE_ONE_BIT 0x80
#define BLOCK_SIZE 512
#define MOD_SIZE 448
#define APP_SIZE 64
#define BITS 8

// MD5 Chaining Variable
#define A 0x67452301UL
#define B 0xEFCDAB89UL
#define C 0x98BADCFEUL
#define D 0x10325476UL

// Creating own types
#ifdef UINT64
# undef UINT64
#endif

#ifdef UINT32
# undef UINT32
#endif

typedef unsigned long long UINT64;
typedef unsigned long UINT32;
typedef unsigned char UINT8;
typedef struct
{
    char * message;
    UINT64 length;
}STRING;

const UINT32 X[4][2] = {{0, 1}, {1, 5}, {5, 3}, {0, 7}};

// Constants for MD5 transform routine.
const UINT32 S[4][4] = {
    { 7, 12, 17, 22 },
    { 5,  9, 14, 20 },
    { 4, 11, 16, 23 },
    { 6, 10, 15, 21 }
};

// F, G, H and I are basic MD5 functions.
UINT32 F( UINT32 X, UINT32 Y, UINT32 Z )
{
    return ( X & Y ) | ( ~X & Z );
}

UINT32 G( UINT32 X, UINT32 Y, UINT32 Z )
{
    return ( X & Z ) | ( Y & ~Z );
}

UINT32 H( UINT32 X, UINT32 Y, UINT32 Z )
{
    return X ^ Y ^ Z;
}

UINT32 I( UINT32 X, UINT32 Y, UINT32 Z )
{
    return Y ^ ( X | ~Z );
}

// rotates x left s bits.
UINT32 rotate_left( UINT32 x, UINT32 s )
{
    return ( x << s ) | ( x >> ( 32 - s ) );
}

// Pre-processin
UINT32 count_padding_bits ( UINT32 length )
{
    UINT32 div = length * BITS / BLOCK_SIZE;
    UINT32 mod = length * BITS % BLOCK_SIZE;
    UINT32 c_bits;

    if ( mod == 0 )
        c_bits = BLOCK_SIZE;
    else
        c_bits = ( MOD_SIZE + BLOCK_SIZE - mod ) % BLOCK_SIZE;

    return c_bits / BITS;
}

STRING append_padding_bits ( char * argv )
{
    UINT32 msg_length = strlen ( argv );
    UINT32 bit_length = count_padding_bits ( msg_length );
    UINT64 app_length = msg_length * BITS;
    STRING string;

    string.message = (char *)malloc(msg_length + bit_length + APP_SIZE / BITS);

    // Save message
    strncpy ( string.message, argv, msg_length );

    // Pad out to mod 64.
    memset ( string.message + msg_length, 0, bit_length );
    string.message [ msg_length ] = SINGLE_ONE_BIT;

    // Append length (before padding).
    memmove ( string.message + msg_length + bit_length, (char *)&app_length, sizeof( UINT64 ) );

    string.length = msg_length + bit_length + sizeof( UINT64 );

    return string;
}

int main ( int argc, char *argv[] )
{
    STRING string;
    UINT32 w[16];
    UINT32 chain[4];
    UINT32 state[4];
    UINT8 r[16];
    UINT32 ( *auxi[ 4 ])( UINT32, UINT32, UINT32 ) = { F, G, H, I };
    int roundIdx;
    int argIdx;
    int sIdx;
    int wIdx;
    int i;
    int j;

    if ( argc < 2 )
    {
        fprintf ( stderr, "usage: %s string ...\n", argv[ 0 ] );
        return EXIT_FAILURE;
    }

    for ( argIdx = 1; argIdx < argc; argIdx++ )
    {
        string = append_padding_bits ( argv[ argIdx ] );

        // MD5 initialization.
        chain[0] = A;
        chain[1] = B;
        chain[2] = C;
        chain[3] = D;

        for ( j = 0; j < string.length; j += BLOCK_SIZE / BITS)
        {
            memmove ( (char *)w, string.message + j, BLOCK_SIZE / BITS );
            memmove ( state, chain, sizeof(chain) );

            for ( roundIdx = 0; roundIdx < 4; roundIdx++ )
            {
                wIdx = X[ roundIdx ][ 0 ];
                sIdx = 0;

                for ( i = 0; i < 16; i++ )
                {
                    // FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
                    // Rotation is separate from addition to prevent recomputation.
                    state[sIdx] = state [ (sIdx + 1) % 4 ] + 
                        rotate_left ( state[sIdx] +
                        ( *auxi[ roundIdx ] )
                        ( state[(sIdx+1) % 4], state[(sIdx+2) % 4], state[(sIdx+3) % 4]) +
                        w[ wIdx ] +
                        (UINT32)floor( (1ULL << 32) * fabs(sin( roundIdx * 16 + i + 1 )) ),
                        S[ roundIdx ][ i % 4 ]);

                    sIdx = ( sIdx + 3 ) % 4;
                    wIdx = ( wIdx + X[ roundIdx ][ 1 ] ) & 0xF;
                }
            }

            chain[ 0 ] += state[ 0 ];
            chain[ 1 ] += state[ 1 ];
            chain[ 2 ] += state[ 2 ];
            chain[ 3 ] += state[ 3 ];
        }

        memmove ( r +  0, (char *)&chain[0], sizeof(UINT32) );
        memmove ( r +  4, (char *)&chain[1], sizeof(UINT32) );
        memmove ( r +  8, (char *)&chain[2], sizeof(UINT32) );
        memmove ( r + 12, (char *)&chain[3], sizeof(UINT32) );

        for ( i = 0; i < 16; i++ )
            printf ( "%02x", r[i] );
        putchar ( '\n' );
    }

    return EXIT_SUCCESS;
}


版权声明
本人的所有原创文章皆保留版权,请尊重原创作品。转载必须包含本声明,保持本文完整,并以超链接形式注明原始作者“redraiment”和主站点上的本文原始地址。


求完美数

求完美数

redraiment, 2008-07-10





  一个数如果恰好等于它的因子之和,这个数就称为“完美数”或“完数”,例如 6=1+2+3(6的因子是1,2,3)。完美数的一些性质:
    1. 欧几里德证明了:一个偶数是完数,当且仅当它具有如下形式:2(p-1)×(2p-1) 其中 p 和 2p-1 是素数。尽管没有发现奇完数,但是当代数学家奥斯丁·欧尔(Oystein Ore)证明,若有奇完全数,则其形状必然是 12p+1 或 36p+9 的形式,其中 p 是素数。在 1018 以下的自然数中奇完数是不存在的。
    2. 除 6 以外的偶完数,把它的各位数字相加,直到变成一位数,那么这个一位数一定是 1(亦即:除6以外的完数,被9除都余1) 28:2+8=10,1+0=1 496:4+9+6=19,1+9=10,1+0=1
    3. 因为 2p 是 2 的幂,用C语言也就是 1 << p,那么 2p-1 的二进制也就是 p 个 1 组成了,而 2(p-1) 是 2的幂,这两个数相乘,也就相当于把 2p-1 向左移 p-1 位,即 (2p-1) << (p-1),那所有完美数的二进制就是前面 p 个 1,后面跟着 p-1 个 0。 所以偶完数都可以表达为 2 的一些连续正整数次幂之和,如:
      6 = 2+ 22; 28 = 22 + 23 + 24; 8128 = 26 + 27 + ... + 212; 33550336 = 212 + 213 + ... + 224
      j = ((1 + (i ^ (i-1) )) >> 1) + i - 1;
      (j & (j + 1)) || (i & 1)
    4. 上面的代码可以判断整数 i 是否是前面 1 后面 0 的形式。
    5. 每一个偶完数都可以写成连续自然数之和: 6=1+2+3; 28=1+2+3+4+5+6+7; 496=1+2+3+…+30+31
    6. 除6以外的偶完数,还可以表示成连续奇数的立方和(被加的项共有): 28 = 13 + 33; 496 = 13 + 33 + 53 + 73; 8128 = 13 + 33 + 53 + ... + 153; 33550336 = 13 + 33 + 53 + ... + 1253 + 1273
    7. 每一个完数的所有约数(包括本身)的倒数之和,都等于2: 1/1 + 1/2 + 1/3 + 1/6 = 2; 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2
  了解了上面一些性质后,就可以简单的来写一个求完美数的程序了。
#include <stdio.h>

#ifndef WIN32
typedef long long ll;
#else
typedef __int64 ll;
#endif

int main(void)
{
    ll i, j, n, x;

    for (n = 2; n <= 31; n++)
    {
        x = (1 << n) - 1;
        for(i = 3; i*i <= x; i += 2)
            if(x % i == 0)
                break;
        if(i*i <= x) continue;
        printf("%lld\n", (1 << (n - 1)) * x);
    }

    return 0;
}

  运行结果:
6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
  到目前为止,已经求出的2p-1是素数的有25个:2、3、5、7、13、17、19、31、61、89、107、127、521、607、1279、2203、2281、3217、4253、4423、9689、9941、11213、19937、21701。 据说最后一个即221701-1是1978年两名美国大学生新发现的截止目前为止最大的一个素数,所以我们可以利用这个结果来求已知的完美数:
import java.math.BigInteger;

public class Main
{
    public static void main(String[] argv)
    {
        int [] prime = {
            2,3,5,7,13,17,19,31,61,89,107,127,
            521,607,1279,2203,2281,3217,4253,
            4423,9689,9941,11213,19937,21701
        };
        BigInteger x = BigInteger.ONE;
        for (int i = 0; i < prime.length; i++)
            System.out.println ( x.shiftLeft(prime[i]-1)
                .multiply(x.shiftLeft(prime[i])
                .subtract(x)));
    }
}
  最后一个完美数的长度是13066!堪称是BinIntegest




为JudgeOnline系统添加Java语言

为 JudgeOnline 系统添加 Java 语言

redraiment, 2008-04-09





  我校的ACM事业还处于萌芽阶段,目前用的 OJ 系统还是 PKU 上免费提供的版本。系统功能还不是非常完善,很多功能都没提供,不过毕竟是免费版本嘛,能用就行了。
  应同学们的要求,为学校 OJ 添加 Java 语言。在网上搜索了一下,都没有相关的文章介绍。在我们老师的指导下,自己摸索出了一种简单的方法,现介绍给大家。

  1. 安装JDK,到官网下载最新版本的J2SE。安装完后,配置环境变量。
  2. 打开服务器的配置文件“serverconfig.property”(默认安装的话在目录C:\JudgeOnline下)。
  3. 找到一下信息,红色部分是需要修改或者添加的部分。
LangCount=4
LanguageDescs
=G++,GCC,Pascal,Java
LanguageExtMemory
=668,668,700,10100
LanguageExtTime
=60,60,15,4000
#LanguageExtTime
=15,15,15
LanguageExts
=cc,c,pas,java
LanguageExes
=exe,exe,exe,class
LanguageTimeFactor
=1,1,1,1
CompileStreamOrder
=1,1,0,1

G++CompileCmd
=C:\JudgeOnline\bin\gcc\bin\g++.exe -fno-asm -s -w -O1 -DONLINE_JUDGE -o %PATH%%NAME% %PATH%%NAME%.%EXT%
GCCCompileCmd
=C:\JudgeOnline\bin\gcc\bin\gcc.exe -fno-asm -s -w -O1 -DONLINE_JUDGE -o %PATH%%NAME% %PATH%%NAME%.%EXT%
PascalCompileCmd
=C:\JudgeOnline\bin\fpc\fpc.exe -Sg -dONLINE_JUDGE %PATH%%NAME%.%EXT%
JavaCompileCmd
=javac %PATH%%NAME%.%EXT%

JavaRunCmd=java -classpath %PATH% %NAME%

  保存好文件重启 Tomcat 服务器就可以了。欢迎大家光临我校 ACM网站,我们另外提供了测试数据和参考源码下载功能。