程式設計之道

2012年1月09日 category:编程 tag:冼镜光, 思想, 程序设计

今天下午在看各大公司面试题集，发现有很多题目与《C名题精选百则--技巧篇》中的类似，再次佩服冼镜光的功力，这本写于1986年的书，即使现在还是如此有用。在维基百科中找到作者曾经写过《程式設計之道》一文.写的相当有趣和精炼，摘抄几段于此。

2.2 節

.大師Turing曾經夢到他是一部電腦, 醒後道:

. "不知是我Turing作夢變成機器, 還是一部機器作夢變成我我Turing."

.一家大電腦公司的程式員參加軟體會議後, 向他的經理報告說:"你知道其他電腦

公司有什麼程式員嗎? 他們不修邊幅, 頭髮長而邋遢, 衣服既舊且皺, 他們破壞

了氣氛, 而且我簡報時老是製造噪音."

.經理說:"我根本就不應該派你參加會議, 這些程式員超然物外, 他們把生命看成無稽,

意外的結合. 他們往來而無藩籬, 為他們的程式而活, 為什們他們一定要受社會積習

的約束?

.他們生活在道中."

ps.看吧，程序员。

4.3 節 .大師對弟子說:"不論軟體之為大為小, 道在所有軟體中."

." 桌上型計算機有道嗎?"弟子問.

." 有!"大師答.

." 電動玩具程式中有道嗎?"弟子續問.

." 也有!"大師說.

." 那個人電腦的DOS 中有道嗎?"

.大師咳一下, 輕輕挪動了位置,"下課",他說.

ps.这是在骂windows吧

6.3 節

.某個經理快被炒魷魚了, 但是他底下的一個程式員寫了一個叫好又叫座的程式;

當然, 這位經理因而保住了飯碗.

.經理打算給這位程式員一點獎勵, 但他拒絕接受, 並且說:"因為我覺得這是個有

趣的概念, 才會寫這個程式, 所以我不希望有獎勵."

.經理聽了之後說:"這個程式員雖然職位不高, 但卻充份了解做為一個職員的責任,

讓我們把他升成崇高的管理顧問吧!"

.在告訴程式員時, 他再度拒絕, 說:"我之存在是因為可以寫程式, 如果升了我,

那除了浪費每一個人的時間外而成不了事. 我可以走了嗎? 我還得寫程式."

ps.谁说程序员的出路非得是管理层的，看看这个。

逆波兰式

2011年9月04日 category:编程 tag:C名题百则, 冼镜光, 栈, 程序设计, 逆波兰式

最近在看《C语言名题精选百则--技巧篇  冼镜光》问题6.2是有关逆波兰式的,一下介绍一下逆波兰式。所谓逆波兰式是用来表示一道表达式的常见写法，是由波兰学派的逻辑学家发展出来表示逻辑式子用的。它有一个很重要的特性，就是不会用到括号。在普通的算术式中，运算符在操作数之间，而在逆波兰式中，运算符在操作数后面。例如普通式子a+b,如果写成逆波兰式则是ab+;普通式子a+bc,写成逆波兰式则是abc+;式子ab+c,写成abc+.现在解释这是为什么。对于a+b,+的操作数是a和b,把运算符写在操作数后面，很明显写成ab+;对于a+bc,要先算bc,得到bc,这时+的操作数是a和bc,所以是abc+;同理可得到ab+c的逆波兰式。

如果算术式子中有括号，括号中的部分对运算而言就是一个完整的操作数。例如在(a+b)(c+d)中，a+b写成ab+,c+d写成cd+,最终整个式子写成ab+cd+.对于式子a(b+c)-(e+f)/g,a与bc+是的操作数，这一部分写成abc+;ef+与g是/的操作数,这一部分写成ef+g/,最终式子写成abc+ef+g/-.

可以看出，一旦写成逆波兰式，括号就没有了。这是它方便的地方，那么如何将算术式转变成逆波兰式呢？冼同学给出了提示。对于a+bc，读入+就无法知道这个加法能不能计算，一直到出现才能做出决定。同样，对于a+b(x+y)，读入也无法知道这个乘法能不能计算，要等到x+y算出之后才能算*。其实就是在下个运算出现之前，并不知大目前这个运算可不可以算。如此，用栈是个好方法，把不能算的运算先压在栈中，于是现在的这一个就在栈顶，当下一个运算出现了，就看看顶上这个与下一个运算的关系，如果栈顶上的这个可以算，也就是栈顶上的运算的优先级大于等于下一个运算的优先级，就把它输出，如果不行，将下一个运算入栈。这里很关键要处理左右括号。

冼同学还说，其实，可以在其他书上找到答案，但建议不要这样做，因为在计算机刚问世是这是个难题，如果能够独立解决它而不求助外力的话，是很值得自豪的。正因为后面这句话，我没有立刻去找答案。折腾了一个上午，总算有点眉目，但我竟会想到用递归。还算我有点常识，递归程序一般都可以用栈实现的，既然在程序中已经用了栈了，就不应该再用递归了。困惑之际，上网查了一下逆波兰式，可恶，我看了算法，最终还是借助了外力。

与《C名题精选百则--技巧篇》相识，是在大一时，也就是四年前了。那时只会写求素数等基本程序，看了序言就知道这是本好书，做了序曲中最长平台这一题，被这本书折服了，之后就没有再看这本书。时隔四年，再次拿起这本书，总算可以坦然面对。看来算法水平有所提高了。这本书是台湾人写的，于1989年出版，中国大陆于2005年出版。差距。想到《计算机程序的构造和解释》作为MIT计算机科学的入门教材，而我国计算机科学的入门教材是什么呢？我也不知道，反正我是《C语言程序设计》。差距啊。

空闲时玩的游戏manufactoria

2011年9月02日 category:游戏 tag:manufactoria, 程序设计

在matrix67的博客上看到这个游戏，于是玩这个游戏，确实有难度。翻开日志，看了一下玩游戏的整个过程。

2011年1月2日，20:36通过任晓祎的博客访问到matrix67的博客。花费40分钟。

1月3日，15:26玩游戏“manufactoria" 花费3小时。

1月5日 10:30 去实验室，玩manufactoria。花费30分钟，11:16玩manufactoria 花费40分钟。

1月7日 11:30 玩manufactoria。花费30分钟   18:15 回实验室，玩manufactoria花费 40分钟。   21:27 玩manufactoria 花费30分钟。

1月9日，被有一关卡住了，没办法通过，于是叫同学玩，希望他们能解决。 18：00教杨俊玩manufactoria。花费1小时。  21:42 教陈海龙玩manufactoria。花费44分钟。后来发现是由于对题意理解错误，之后这关很快解决。

3月18日  18:26 去实验室，玩manufactoria,花费2小时。

3月20日，9:30 又被一关卡住了，教黎扬玩manufactoria，他解决了这关。花费2小时20分

3月26日， 14:20 玩manufactoria 花费2小时10分。

5月25日 15:23 玩manufactoria 花费2小时

7月25日 至 8月1 晚上睡觉是考虑manufactoria,试着像特斯拉一样在大脑中想象机器的运转过程，但终究比不上特斯拉，没有那么精确，但想通了加一，减一，逆序输出字符。

8月11日   20:30 玩manfactoria 解决加减，逆序输出字符 花费2小时。 23:30 玩manufactoria 花费1小时10分

8月12日， 9:40 玩manufactoria 解决对称 花费1小时20分。

总游戏时间为22小时14分钟。当然还没有加上吃饭时考虑这个游戏，睡觉时考虑这个游戏的时间。总游戏时间相当长，而且很遗憾的是，现在还没有将游戏通关。想想matrix67花费一个下午加晚上的时间就把游戏通关了。但我想他之所以能做到这样，此前必定付出很多努力。于是在他的网站中寻找证据，果然被我找到一条，在他的博客中《我中学时代的作文一：换一个角度思考问题》。matrix67考虑的是这样一个问题：22, 2, 53, 10, 19, 0, 53, 7, 0, 79, 28, 8, 69, 1, 100, 104, 0, 74, 18, 39。每一个数字代表一个字母，合起来组成一个简单的英文句子，用通常的方法无法的到答案，需要换一个角度思考。读者会在某特定的场合下想出答案。为了这个问题，读初三的他竟会探索半年之久。这也证实了我的想法。

希望有哪位空闲的能人异士将游戏通关，然后告诉我最后一关的算法。