C++博客-Coding Life

给函数赋值了！

Codeboy — Sat, 12 Apr 2008 23:49:00 GMT

　　写了一个这样的程序，是将字符数组中的某个元素替换成其他内容。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void str(char* a, int i, char b)
 5 {
 6     a[i] = b;
 7 }
 8 
 9 int main(void)
10 {
11     char a[] = "A donkey";
12     str(a, 2, 'm');
13     cout << a << endl;
14     return 0;
15 }

　　突然想到C++里有个变量引用的用法，使想到了一个自己觉得有点怪的东西。
　　既然引用是一个变量的别名，与原变量都是指向同一个内存空间，那函数返回了变量的引用会不会能像变量一样可以赋值？便写了下面一段：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 char& str(char* a, int i)
 5 {
 6     return a[i];
 7 }
 8 
 9 int main(void)
10 {
11     char a[] = "A donkey";
12     str(a, 2) = 'm';
13     cout << a << endl;
14     return 0;
15 } 

　　编译运行发现可以实现同样的功能。这样就出现了变量可以被赋值的奇怪写法了！
　　与同学交流我的发现后，同学提出如果不用引用行不行？
　　在以前不用引用的时候好像都没想过这个问题。但仔细想想，觉得不行。因为有返回值的函数，它返回的变量是函数运行时临时生成的，函数运行完，这个返回值的空间也会被释放掉。连空间都已经被释放，它应该就存在了，更不用其中的值了。
　　于是也实验了一下，结果编译时报告无效变量的错误。

Codeboy 2008-04-13 07:49 发表评论

Section 1.1 Friday the Thirteen

Codeboy — Wed, 09 Apr 2008 09:38:00 GMT

摘要: Is Friday the 13th really an unusual event? That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that w... 阅读全文

Codeboy 2008-04-09 17:38 发表评论

学习C++和编程的50个观点（别人的意见哦）

Codeboy — Tue, 08 Apr 2008 11:51:00 GMT

1.把C++当成一门新的语言学习（和C没啥关系！真的。）；

2.看《Thinking In C++》，不要看《C++变成死相》；

3.看《The C++ Programming Language》和《Inside The C++ Object Model》,不要因为他们很难而我们自己是初学者所以就不看；

4.不要被VC、BCB、BC、MC、TC等词汇所迷惑——他们都是集成开发环境，而我们要学的是一门语言；

5.不要放过任何一个看上去很简单的小编程问题——他们往往并不那么简单，或者可以引伸出很多知识点；

6.会用Visual C++，并不说明你会C++；

7.学class并不难，template、STL、generic programming也不过如此——难的是长期坚持实践和不遗余力的博览群书；

8.如果不是天才的话，想学编程就不要想玩游戏——你以为你做到了，
其实你的C++水平并没有和你通关的能力一起变高——其实可以时刻记住：学C++是为了编游戏的；

9.看Visual C++的书，是学不了C++语言的；

10.浮躁的人容易说：XX语言不行了，应该学YY；——是你自己不行了吧！？

11.浮躁的人容易问：我到底该学什么；——别问，学就对了；

12.浮躁的人容易问：XX有钱途吗；——建议你去抢银行；

13.浮躁的人容易说：我要中文版！我英文不行！——不行？学呀！

14.浮躁的人容易问：XX和YY哪个好；——告诉你吧，都好——只要你学就行；

15.浮躁的人分两种：a)只观望而不学的人；b)只学而不坚持的人；

16.把时髦的技术挂在嘴边，还不如把过时的技术记在心里；

17.C++不仅仅是支持面向对象的程序设计语言；

18.学习编程最好的方法之一就是阅读源代码；

19.在任何时刻都不要认为自己手中的书已经足够了；

20.请阅读《The Standard C++ Bible》(中文版：标准C++宝典)，掌握C++标准；

21.看得懂的书，请仔细看；看不懂的书，请硬着头皮看；

22.别指望看第一遍书就能记住和掌握什么——请看第二遍、第三遍；

23.请看《Effective C++》和《More Effective C++》以及《Exceptional C++》；

24.不要停留在集成开发环境的摇篮上，要学会控制集成开发环境，还要学会用命令行方式处理程序；

25.和别人一起讨论有意义的C++知识点，而不是争吵XX行不行或者YY与ZZ哪个好；

26.请看《程序设计实践》，并严格的按照其要求去做；

27.不要因为C和C++中有一些语法和关键字看上去相同，就认为它们的意义和作用完全一样；

28.C++绝不是所谓的C的“扩充”——如果C++一开始就起名叫Z语言，你一定不会把C和Z语言联系得那么紧密；

29.请不要认为学过XX语言再改学C++会有什么问题——你只不过又在学一门全新的语言而已；

30.读完了《Inside The C++ Object Model》以后再来认定自己是不是已经学会了C++；

31.学习编程的秘诀是：编程，编程，再编程；

32.请留意下列书籍：《C++面向对象高效编程
（C++ Effective Object-Oriented Software Construction）》
《面向对象软件构造(Object-Oriented Software Construction)》
《设计模式（Design Patterns）》《The Art of Computer Programming》；

33.记住：面向对象技术不只是C++专有的；

34.请把书上的程序例子亲手输入到电脑上实践，即使配套光盘中有源代码；

35.把在书中看到的有意义的例子扩充；

36.请重视C++中的异常处理技术，并将其切实的运用到自己的程序中；

37.经常回顾自己以前写过的程序，并尝试重写，把自己学到的新知识运用进去；

38.不要漏掉书中任何一个练习题——请全部做完并记录下解题思路；

39.C++语言和C++的集成开发环境要同时学习和掌握；

40.既然决定了学C++,就请坚持学下去，因为学习程序设计语言的目的是掌握程序设计技术，而程序设计技术是跨语言的；

41.就让C++语言的各种平台和开发环境去激烈的竞争吧，我们要以学习C++语言本身为主；

42.当你写C++程序写到一半却发现自己用的方法很拙劣时，请不要马上停手；
请尽快将余下的部分粗略的完成以保证这个设计的完整性，然后分析自己的错误并重新设计和编写（参见43）；

43.别心急，设计C++的class确实不容易；自己程序中的class和自己的class设计水平是在不断的编程实践中完善和发展的；

44.决不要因为程序“很小”就不遵循某些你不熟练的规则——好习惯是培养出来的，而不是一次记住的；

45.每学到一个C++难点的时候，尝试着对别人讲解这个知识点并让他理解——你能讲清楚才说明你真的理解了；

46.记录下在和别人交流时发现的自己忽视或不理解的知识点；

47.请不断的对自己写的程序提出更高的要求,哪怕你的程序版本号会变成Version 100.XX；

48.保存好你写过的所有的程序——那是你最好的积累之一；

49.请不要做浮躁的人；

50.请热爱C++!

Codeboy 2008-04-08 19:51 发表评论

代码的文化，自由的代价，信念的力量---我心中的黑客帝国

Codeboy — Tue, 08 Apr 2008 11:48:00 GMT

写于观看完《The Matrix Revolutions》首影（长沙）后三小时，2003年11月10日凌晨一点，作者倪硕持有文章所有权，但欢迎任何形式的转贴，但请注明文章原作者，以及文章出处http://nishuo.35123.net并且欢迎访问MatrixCpp的专栏
-
为了使得剧情更好被大多数程序员理解，我使用了下面的假象等式，阅读时请注意~：）
Windows ==Matrix Linux==Human Being
-
背景：这个世界本来只有Linux这一种系统，后来种种原因（可以拍Matrix前传，呵呵）Windows这个系统统治了这个世界，而Linux只剩下了微内核存在（Zio），并且Windows系统一直企图完全消灭Linux。
-
第一集（The Matrix）:
-
Linux系统中的部分程序（Morpheus and Trinity…..）潜入到了Windows系统中（代码是可移植的~：），企图在Windows系统中寻求一段能够拯救Linux系统的代码，这就是Neo。这段代码本来是完全受到Windows系统控制的，但由于Morpheus等使用一些方式把Neo转换成了Linux系统代码，并且具有很强的移植能力可以自由的存活于两种系统中间，但相对于自身系统来说，另外一种系统对于代码本身来说都是虚幻的世界。Windows系统中有一种杀毒代码（Smith）主要是负责清除系统中的不干净代码比如那些来自于Linux系统的代码，而在第一集中Morpheus告诉了Neo世界上还有另外一个系统（等于是一个Linux系统代码告诉一段Windows代码，其实还有另外一个系统的存在，而Neo本身也自愿转换到另外一个系统中去），并且他们都想搞清楚如何才能消除Windows系统对于Linux系统的入侵，找到了Windows核心代码之一的先知（Oracle）想寻求世界未来会如何？在此其中，他们和那段杀毒程序进行了艰苦的斗争，当一种代码移植到不属于自己本身的系统的虚拟世界中去后，就具有了升级能力（Neo可以在半分钟内学会开直升飞机，其实就是完成了程序在另外一个系统的自身能力升级），在最后的一次Neo和Smith打斗中，Neo进行了第一次的根本性升级，从而具备了完全对抗Windows系统原生代码的能力，并战胜Smith，使其成为了一段垃圾代码。在这一集中来自两个不同且相互敌意的系统的代码Neo和Trinity居然相爱了（这有点象金庸先生惯用的手法）
-
第二集（The Matrix Reloaded）:
-
Neo Morpheus and Trinity等Linux系统代码再次潜入Windows系统，并且再次找到了先知，企图从她那里知道未来之路在哪里，而先知并没有告诉他们路在哪里，只是不断的在引导Neo不断的自我升级，并且告诉Neo在Windows系统存在一段程序代码（老锁匠）知道如何访问Windows系统另外一段最核心程序代码（Arichetect）的路径，而在Windows系统中还存在另外一种不受Windows控制的代码，那就是双子人及其主人，两边为了争夺这段代码（老锁匠）在Windows系统中展开了战斗（第二集中最精彩的街道飞车追逐）并且最终Neo访问到了Arichetect，而Arichetect告诉Neo一切都是在他自己的选择之中，这和先知（Oracle）的言论是一致的。而由于和Trinity爱情导致Neo做出了和其前五任the one代码所不一样的选择。而在第一集中的被Neo清除的Smith成为了游离于两个系统之外但依附于Windows系统的垃圾代码并且具有了强大的复制自我的能力，也就是说Smith从服务于Windows系统的杀毒程序变成了一种危害Windows系统的烈性病毒，而Windows系统自身却无法清除Smith这段垃圾代码。故事发展至此，形成了Windows系统（Matrix），Linux系统(人类)，以及病毒程序（Smith）三足鼎立的关系。而在第二集的最后，Windows系统开始全面进攻Linux系统的内核而Neo也完成了自身的第二次根本性升级，他获得了在Linux系统中对抗Windows代码的能力（在人类飞船中挡住了电子章鱼的进攻）。
-
第三集（The Matrix Revolutions）：
在第二集结束的时候，Neo进入到了一个Windows和Linux两个系统的边缘地带，而这里的掌管者就是第二集中双子人的主人，为了把Neo救回到原来的系统中去，Morpheus and Trinity与掌管者发生战斗，并救回了Neo。为了避免Linux系统被Windows系统毁灭的命运，Neo和Trinity企图和访问Windows的核心代码并和他进行谈判，如此就必须通过Windows系统自身的很多保护核心代码的防火墙系统。与此同时，Windows系统程序的进攻使得Linux防御程序不断失效并且大部分代码都失去了功能，只剩下最后的小部分代码（神殿），并且在两个小时内Windows系统将完全清除所有的Linux代码。而Neo在突破Windows核心系统防火墙的时候失去了他的真爱Trinity。但最终他成功的访问到了Windows核心代码（机器码），而谈判的筹码就是Windows系统自身也无法控制，并且严重危害到Windows系统自身安全的病毒程序Smith。由Neo去帮助清除Windows系统中的病毒，而Windows放弃对Linux系统的进攻，双方终达成了协议。Neo和Smith展开了最后的战斗（影片中的雨中大战）而在战斗中Smith又一次的引发了Neo的再次升级最终Neo消除了Smith并恢复了所有被感染的代码的正常功能，而Windows遵守协议放弃了对Linux系统的进攻，和平终于在第六任the one手中获得。
-
故事的结尾就是两个Windows系统的核心程序Arichetect和Oracle的对话：换来的和平的期限就是到和平终结之时，而Arichetect最后一句话也是全片最后一句话十分让人深思
-
Oracle：那那些想获得自由的人们将如何？
Arichetect：他们将获得自由。
Oracle：真的吗？
Arichetect：当然，你以为我是你们人类吗？
-
“当然，你以为我是你们人类吗”。说明了什么？说明了机器始终只是机器，只是一段只会按指令执行的代码，但代码没有人类的虚伪，没有人类的谎言，没有人类的欺骗。
-
片子到这里就结束了，唯一没有交代的就是Neo。（影片中他只是静静的躺在那里了）而这里我把我的想法说说，Neo来自哪里？来自Windows系统，经过几次升级，他已经成为了the one代码，而在完成自己的使命之后，他到哪里去了呢？他消失了，是的，就象是一个永远无法成为进程的静态死代码一样消失了，因为他已经完成了他的任务，也就已经失去了存在的意义了。而整个系列中始终强调的一点就是人类在追求未知世界以及获得自身自由的过程中都将付出很大的代价，而为什么在付出这样的沉重的代价之后还是能如此锲而不舍呢？（这也是Smith在和Neo战斗到最后也无法明白Neo为什么如此不屈服于命运而不断抗争力量是从何而来而发出了惊诧叫喊，而Smith被毁灭之前的最后一句话就是“这不公平”---是的，让他永远无法得到信念的力量确实不公平）那就是因为存在人类心中的信念，信念的力量大于一切。当电影结束，影厅大灯亮起的时候，我无法回忆起那让人绚目的电影效果，电影之外我能做的是什么？我只是轻轻的问了自己一声：“我自己的信念在哪里？”

Codeboy 2008-04-08 19:48 发表评论

c++的优势究竟在何处?(csdn-Vitin回答）

Codeboy — Tue, 08 Apr 2008 11:36:00 GMT

　　我觉得C++最大的优势在于她的通用和全面。我们往往听到C++和其他语言的比较：诸如运行效率不如C啦、应用软件的开发效率上不如Java和.NET啦、GUI开发不如VB啦……以及在各个方面与各种专用语言和脚本语言的比较。似乎C++就没有自己最突出的地方，简直一无是处。我想说的是，先不谈比较的结果，这些比较能够成立，本身就说明了C++的优势——她是通用的，她是全面的。在成熟的主流语言中，除了C++，还有谁能够做到这一点？！

　　另外一些比较则罕有提及：与C语言比开发应用软件？与Java比做底层？与VB比运行效率？是的，很罕见。因为结论显而易见以至任何的比较都是浪费时间。当然了，她们都有各自的适用范围，做好本职就好了，何必与你比其他的。这是一种生存之道，无可厚非。唯有C++，选择了另一条道路——“通用语言”，不是象C那样“通用的”底层语言，也不是象Java那样其实只能在一个平台上运行的“跨平台”语言，而是真正的通用：通用于所有层次、通用于所有平台、通用于所有领域，对所有的应用都不偏不倚、一视同仁。

　　要做到这一点是很困难的，C++往往被人指责野心过大。还有各种各样的误解：有指责VC只能在Windows上使用的(所以C++是不能跨平台的)；有指责gcc无法快速开发GUI的（所以C++的应用是有局限的）；有指责Java、.NET和脚本语言占据了绝大部分网站开发的（所以C++是不能适应网络时代的）……这些指责说得人多了，就成为了真理。我不想去一一解疑，只想说明一点：语言之间的比较很少是公正的，因为误解是广泛存在的。

　　无疑，C++的野心确实很大，“通用”二字貌似华丽有余，实惠不足。常常有人说：学习C++，然后使用其他专门语言。是的，在一个特定领域里，通用往往比不上专用的。但是，整体总是大于部分之和。如果说，“博”和“精”各有所长的话，那么又博且精不是更好吗？就象我们常常用电脑，而不是分立的上网机、办公机、游戏机、编程机   ……虽然C++不能包揽所有的冠军，但是如果她在哪方面都不算太差的话，又何必执着于虚幻的完美呢？

　　确实，C++能够立足于世，不仅在于她是“通用”的，更在于她是“全面”的。你常常能在某个局部找到她的一点不足。是的，她有一个不足；那么，能否改进呢？回答是：不能！为什么？回答是：如果改进了这一点，就会出现新的不足，可能是另一点，甚或更多。就象一个已经挤满了人的车厢，要上去一个，就得再下来一个！是的，C++就是这样的车厢，她无法让你享受悠闲的空间，反而给你窒息的感觉；但是，正是这样的车厢，支撑着主干交通的正常运行（想想吧，如果一个人口密集的大城市里全部都是私家车，会是什么状况）。车厢可能会越做越大，因为技术正在不断提高，但是C++这个车厢，永远都是满的。一个局部的不足，如果不存在被改进的可能，恰恰暗示了已经达到了全局最佳！C++正是以此为目标的；并且，她做到了！

　　回到我们最初的比较上。
　　C++的运行效率不如C吗？是的，也许吧，以特定的标准。但是，不如在哪些方面呢？虚函数、虚基类、异常处理……这些都是C所不具备的。如果在C++中不使用它们，那么效率就不会比C低（优秀的编译器确实可以做到这一点）！C++考虑问题永远是综合的，而非单方面的，她的效率，趋近于你在享用各种特性时所能达到的最佳值，你只付出必然的代价。
　　C++在应用软件的开发效率上不如Java和.NET吗？是的，也许吧，以特定的标准。但是，原因是什么呢？是C++语言不及Java和.NET吗？不是的。只是因为后两者是产品，而C++是语言。这个比较，本身就是不合适的。在.NET中，你同样可以使用C++，同样可以达到它的开发效率。另外，C++并不限制其实现产品，所以每个特定应用领域都可以有其特定的编译器，它们帮助程序员达到各自最佳的开发效率。如果单论语言，那么只有C++的语言复杂度会影响这一话题。也许Java等更容易上手，但是对两方面的资深人员来说，C++的开发效率毫不逊色。值得一提的是，在比较时应该同时考虑应用的复杂度。另外，需要知道，作为产品的Java和.NET预处理了一些应用复杂度，而这些产品本身很大程度上（如果不说全部的话）是用C++开发的。
　　C++在GUI开发方面不如VB吗？是的，也许吧，以特定的标准。但是，为什么呢？作为语言，C++没有制订标准的GUI库，因为GUI太复杂，要达到通用的最佳，很难。因此，C++放弃了这方面的通用化。但是，每个具体的实现可以使用各自优化的GUI库。VC比VB如何？如果嫌它还不算快速开发，BCB呢？另外，还有QT等通用GUI库。在语言方面，C++追求通用和全面，而局部的优化，交给具体的实现来完成，这是C++成功的秘诀。

　　综上所述，我认为C++的优势就在于她的通用和全面（也有人认为这正是她的劣势，也许吧，从另一个角度）。她的通用，来源于其始终不变的远大理想（也可称之为“野心”）；而她的全面，则得益于她的设计者们力争上游、精益求精的工作态度！就象我曾经说过的，C++真正的优势在于C++社群——那些设计她的人，实现她的人，以及使用她的人。那些表面的优势来源于此，也归结于此。C++的开局很不错，现在仍很好；而她的未来，将由我们来决定……

Codeboy 2008-04-08 19:36 发表评论

Section 1.1 Greedy Gift Givers

Codeboy — Tue, 08 Apr 2008 11:12:00 GMT

摘要: A group of NP (2 ≤ NP ≤ 10) uniquely named friends has decided to exchange gifts of money. Each of these friends might or might not give some money to any or all of the other friends. Like... 阅读全文

Codeboy 2008-04-08 19:12 发表评论

Section 1.1 Your Ride Is Here

Codeboy — Tue, 08 Apr 2008 10:44:00 GMT

It is a well-known fact that behind every good comet is a UFO. These UFOs often come to collect loyal supporters from here on Earth. Unfortunately, they only have room to pick up one group of followers on each trip. They do, however, let the groups know ahead of time which will be picked up for each comet by a clever scheme: they pick a name for the comet which, along with the name of the group, can be used to determine if it is a particular group's turn to go (who do you think names the comets?). The details of the matching scheme are given below; your job is to write a program which takes the names of a group and a comet and then determines whether the group should go with the UFO behind that comet.

Both the name of the group and the name of the comet are converted into a number in the following manner: the final number is just the product of all the letters in the name, where "A" is 1 and "Z" is 26. For instance, the group "USACO" would be 21 * 19 * 1 * 3 * 15 = 17955. If the group's number mod 47 is the same as the comet's number mod 47, then you need to tell the group to get ready! (Remember that "a mod b" is the remainder left over after dividing a by b; 34 mod 10 is 4.)

Write a program which reads in the name of the comet and the name of the group and figures out whether according to the above scheme the names are a match, printing "GO" if they match and "STAY" if not. The names of the groups and the comets will be a string of capital letters with no spaces or punctuation, up to 6 characters long.

Examples:

Input

Output

COMETQ

HVNGAT

ABSTAR

USACO

STAY

PROGRAM NAME: ride

INPUT FORMAT

Line 1:	An upper case character string of length 1..6 that is the name of the comet.
Line 2:	An upper case character string of length 1..6 that is the name of the group.

NOTE: The input file has a newline at the end of each line but does not have a "return". Sometimes, programmers code for the Windows paradigm of "return" followed by "newline"; don't do that! Use simple input routines like "readln" (for Pascal) and, for C/C++, "fscanf" and "fid>>string".

SAMPLE INPUT (file ride.in)

COMETQ

HVNGAT

OUTPUT FORMAT

A single line containing either the word "GO" or the word "STAY".

SAMPLE OUTPUT (file ride.out)

我的解答：

题目假设A=1, B=2, …, Z=26，将一个字符串的每个字符代表的值相乘得到的值再对47取模后的值就是一个所谓的“final number”。题目的要求是分别计算给出的两个字符串的“final number”，如果这个“final number”相同，则输出“GO”，否则输出“STAY”。

这个是一个简单的模拟题，主要算法是分解字符并计算其代表的值。这些都可以用解析的方法得到。

#include <fstream>
using namespace std;

int main(void)
{
    ofstream fout("ride.out");
    ifstream fin("ride.in");
    int scheme(char*);
    char a[10], b[10];
    fin >> a >> b;
    if (scheme(a) == scheme(b))
        fout << "GO" << endl;
    else
        fout << "STAY" << endl;
    return 0;    
}

int scheme(char* str)
{
    int num = 1, len = strlen(str);
    for (int i = 0; i < len; i++)
        num *= str[i] - 'A' + 1;
    return (num % 47);
}

官方答案：

Analysis: Your Ride Is Here

This is probably the easiest problem in the entire set of lessons. An `ad hoc' problem, no particular algorithms or tricks are needed save one: one must be careful to get all 72 characters of input without processing the newline on the end!

Here is a prototype solution:

#include <stdio.h>
#include <ctype.h>

int hash(char *s)
{
    int i, h;

    h = 1;
    for(i=0; s[i] && isalpha(s[i]); i++)
        h = ((s[i]-'A'+1)*h) % 47;
    return h;
}

void main(void)
{
    FILE *in, *out;
    char comet[100], group[100];  /**//* bigger than necessary, room for newline */

    in = fopen("input.txt", "r");
    out = fopen("output.txt", "w");

    fgets(comet, sizeof comet, in);
    fgets(group, sizeof group, in);

    if(hash(comet) == hash(group))
        fprintf(out, "GO\n");
    else
        fprintf(out, "STAY\n");
    exit (0);
}

Solutions generally run in under 0.01 seconds.

Codeboy 2008-04-08 18:44 发表评论

Planning an Approach to a TopCoder Problem Section I

Codeboy — Tue, 08 Apr 2008 04:26:00 GMT

                                         Planning an Approach to a TopCoder Problem
                                                                   Section 1
                【原文见: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=planApproach1】
                                                                        作者：      By leadhyena_inran
                                                                                          Topcoder Member
                                                                         翻译：      农夫三拳@seu(drizzlecrj@gmail.com)
    深入某个东西是一门很讲究的艺术；它会像难住一个新手一样难住一个资深的程序员，并且它还不易言表。这可能包含许多考虑和回退，也包含着预见，直觉，创造力，甚至运气。当这些因素不能够很好的协调时，任何一个程序员都会感到无助。有的时候就是这种无助的感觉使得很多程序员泄气而放弃尝试Div1中的难题。有的程序员甚至放弃了比赛，因为他们很不喜欢那些问题给他们带来的不快感觉。尽管如此，如果一个人能够持之以恒，解决方法通常并不是超出人们所能理解的范围。这篇教程将试图澄清一些事实，来让你能够使用一个稳定的计划去做这些问题。

Pattern Mining and the Wrong Mindset
人们很容易落入这样一个怪圈，认为算法比赛是一系列不同的可分类的剧情问题的集合。对于那些做过很多剧情问题的人来说，他可能知道这种类型的题目只有很少的一部分（尤其是上课时教授反复强调的部分）。当你读到一个特定形式的问题时，你的思维是，“哦，这个是X问题，然后就对号入座”。可能有很多次这种思维定势是可行的，但是当你做过一定数量的Topcoder SRM之后，大多数程序员会意识到一类的题目并且不断的进行练习，这种做题目的方法在很多比赛中都会成功。

尽管如此，这个方法是有害的。你可能很多次阅读完题目描述之后，假定它是类型Q的题目并且开始进行编码，但最后发现你的代码一个样例都过不了。你会回头重读问题并发现这个问题和你经验中的不一样。这个时候，你对你的练习感到了麻痹，你不能指出适用于这个问题的类型。这种情况你会经常看到，当问题是从原有问题派生出的时候，很多富有经验的程序员都不能完成这个问题，因为他们被他们的经验蒙蔽了。

思维定势导致了这样的思考。只有通过抛掉你以前的想法，并且重新学习必要的关键技巧才能使得你的rating稳步的上升。

Coding Kata
这里是你的第一个练习：在Practice Room中挑选任何一道你没有做过的问题。努力去搞定它，不管花多久（把比赛的解题报告看作最后一招）。让它通过系统测试，然后计算一下你花了多久完成它。接着，把你的解决方案清楚，然后试着再打一遍（剪切，粘贴显然达不到效果）。再次的让它通过系统测试。记下你第二次花了多久。接着，清除它然后再做一次，并且再次让它通过系统测试，然后记录下最终所用的时间。

你第一次通过的所花的时间是你在对题目一无所知的情况下记录的。第二次通过的时间通常是第一次的时间减去你花费在理解题意上的时间。（不要感到惊讶，当你在第二次过程中重复犯一些错误）。最后一次的记录时间是你的潜能，如果你在读完题后能立刻思考出正确的做法，那么你可以在比赛中很快的解决它。让这些数字给你些启发；迅速的解决此类问题还是很有可能的，而不需要很快的打字速度。从第三次中你可以感受到你已经知道了策略，代码将会是什么样子，哪里你会犯错误等等。这就是有着正确解法时候的感觉，这种感觉就是未来比赛中的你的目标。

在武术文化中，有种叫做空手道。武术家按照一系列的手法进行练习，通常用来抵挡对方的攻击（或者说有的时候是防卫），或者预测性的来防护。首先这种类型的练习没有任何意义，因为它看起来和打斗时没有章法的现实不符。更进一步的，它似乎在鼓励前面一张所提出的思维套路。只有在每个题目经过三次编码之后，你才能真正理解kata的好处。kata使得它的参与者能够在大脑中有一个计划，并且鼓励他们仔细思考问题。进攻就是最好的方法，它可以在编码，调试，提交的整个过程中使用。

Approach Tactics
现在你知道方法是什么样了，也知道它们的具体内容了，你会意识到你学会了许多不同类型的方法。你能给出它们的名字吗？“哦，那题我用的是DP(动态规划 dynamic programming)”，“是吗，我本来可以用贪心做的”“不要告诉我暴力就能过了”。实际上，你给每个问题取的名字都不太恰当，因为你不能把每个问题归结为仅仅是贪心或者仅仅是暴力解法。问题的类型有无数多个，而解决方案的类型甚至更多，而且在每个解决方案中有用无穷多种类型的变化。这里的名字仅仅是完成解决方案的一个高度的概括。

在一些较好的比赛报告中，都有一个解决问题的详尽描述。下次当你看比赛的总结时，并且遇到一个比较好的问题时，从中寻找方法的路数和构造方法。你会注意到在路数之间有一定的颗粒性，这就暗示了思考的一个方向。将观察到的策略和方法来规划你的方法，转换，引导并将其融入代码中，使得接近正解或者至少远离错解。当你准备方法的时候，思路就是想尽所有你会的策略方法来决定方法，所有你以前写过的代码都会在你的脑海中。这相当于你说服你自己那些将要写的代码能够工作。

有一定数学背景的程序员会重新审视这个方法，因为许多方法策略和证明的技巧相似。玩象棋的人能够从当前一步中看到好多步。做应用开发的设计者可能在用到设计模式的时候就认识到这个方法了。在许多其它的问题中，都存在一个和它类似的类型。

练习这种类型的思考方式并且在众多方法中选择你钟爱的，记录下你的问题的解决方案并且在SRM之后写下你自己的表现的一点分析是非常有益的。详细的描述你的解决方案每一步是怎样工作的，使得其他人能够理解并且写出方法如果他们看了你的解释之后。写下你的方法不仅可以帮助你理解你在编程时自己的思路，还能发现你在做的时候时一些易错之处。记住，学会你不懂的知识是很困难的。

Breaking Down a Problem
让我们谈谈最常见的一个方法：问题分解。这在有的时候也叫做自顶向下编程：大意是你的代码必须按顺序执行一系列的步数，从简单的决策开始考虑。因此刚开始应当计划你的主函数需要什么，然后在看子函数要做些什么。这不仅可以让你很快的编写出原型（因为你仅仅编写你所需要的代码而没有其他任何东西），还能把问题划分成更小的部分，更多切实可行的部分。

用到这个方法的一个很好的例子是 2002 TopCoder Invitational第二轮中的MatArith。这个问题需要你计算一个包含矩阵的表达式。你知道为了得到数字，你需要对它们进行解析（因为它们是字符串数组）并且将这些值传入计算器中，然后将他们转变为一个字符串数组，就完成了。因此你需要一个打印的函数，一个解析的函数和一个计算函数。不需要更加多的考虑，加入你已经写好了这三个函数，那么问题可以在一行之内被解决：

public String[] calculate(String[] A, String[] B, String[] C, String eval){
return print(calc(parse(A),parse(B),parse(C),eval));
}

这个简单方法的好处在于它将你的思维引导至函数的层次中。你现在可以把工作分为三步了：构建一个解析函数，一个打印函数和一个计算函数，将代码段切割成小段。如果你切割的足够好的话，你根部不用考虑最简单的步数，因为它们将会是原子的（这个下面将会谈到更多）

。事实上这个问题将会被很快的分割直到矩阵的乘法和加法函数，需要注意的仅
仅是读清题意并且调用恰当的函数。这种策略带来了一种编程方法名为函数式编程。网络上有许多关于这个的文章，甚至TopCoder中有一篇radeye写的文章，很深入的讲解了这个概念，但是概念的意思是，如果能够合理的分割，那么代码将在函数之间传递所有的参数信息，并且步数之间不需要存储任何数据，这就避免了很难调试的副作用的可能性（代码中不期望在步数间改变变量）。

这个策略在递归问题上也表现的相当好。递归代码的背后的整个思想就是将问题分成更小的和原问题相似的子问题，由于你正在写的函数是原问题，因此你几乎完成了工作。

Plan to Debug
无论何时你使用一个方法的时候，你都应该有一个调试代码的计划。这个是每一个方法薄弱的一个部分。总有一个使得解决方案失败的方法，通过事先考虑它会不能工作的多种情况，你可以在编码之前避免这些bug。更进一步的，如果你不能过样例，你知道应该在哪里找出问题。最后，通过查找代码的压力值，向自己证明所用方法是个好方法很会容易。

在自顶向下的方法中，分解问题能够让你分离那些可能出现问题的部分，并且它能够让你组合测试那些看起来用的最多的子函数片段。并且还有一个好处，当你修复了一个bug，你把代码分解成了函数。这是因为bug在每个使用的地方都要修复。另外一个方法是程序员将代码段粘贴/复制到任何一个需要的地方，这将使得很难修复并且导致更多的bug。同样，当你在从顶向下的方法中找bug时，你应该首先查找函数内部的错误，而后再查找函数调用间的错误。这些部分组成了一个调试的策略：先看哪里，怎样测试你的思路是错误的，怎样验证代码片段并且继续。只有在足够的练习之下，你才能找到一个好的调试策略。

Atomic Code
当你碰到一段你不能再分解的代码片段时，这就是原子代码。希望你知道怎样去编写这些部分，并且这些部分组成了最基本的原子代码的形式。但是，当你碰到一个问题不知如何下手的时候，不要泄气；这些难以解决的核心正是使得问题有趣的地方所在，有的时候是否能够提前看到将导致能否尽早的找到正确的方法并且放弃错误的方法而浪费大量时间的巨大差异。

你写的最常见的原子代码的类型就是原语了。对于了解语言的库我一直很支持。这就是知识的用处。为你节省时间的最好的方法是在你的方法和你知道代码可能复杂的部分的情况下使用原子代码或者自带的库还是类呢？

你写到第二种类型的原子代码我称它为语言技巧。这些通常是该语言中用来之下特定操作的，如找出数组中最小元素的索引，或者将一个用空格分隔的字符串分割成序列。这些技巧和准备一个方法一样至关重要，因为如果你知道了怎样做这些基础的操作的话，将会使得自顶向下的方法中更多的任务原子化，从而将正确的解法变得简短。除此之外，这使得这些代码中的原子操作出错的可能性减少。更进一步的，如果你要执行一个你所知道的语言技巧所能做的任务时，你可以很轻松的改变代码来进行适应（例如：根据启发式在一个数组中找到最大元素的索引将会变得很简单如果你知道怎样对类似的任务进行编码）。找出这些公共的语言技巧将成为你日常练习的元素之一，任何原子代码都应该随着你的思考从你的指尖流淌出来。

另外一个方面，我必须强调使用代码库。我知道这是一个竞赛话题，许多成功的程序员在编码前使用一个库作为预先插入的代码段。这是合法的（尽管2004 TopCoder Open后的规则可能会改变以后的合法性），并且使用库有着很明显的优点，主要是声明了一些你的自顶向下方法的原语，并且有助于快速构建自底向上的方法（下面将会谈到）。这是我的观点。尽管如此，使用代码库的缺点要超过它的优点。库函数之间的执行有的时候会减慢你的编码，因为你需要使得你的输入满足你所要使用的代码的原型。库代码大多是不易改变的，因此，如果你的库要求做的事情并没有很明白的定义的话，你会发现你在代码技巧和本应该实现的算法之间进行摸索。并且也有可能你的库代码并不是没有bug的，并且在比赛中图调试你的库是非常可怕的，因为你需要把你已经交的代码进行修改，还要在你打开新的问题前去修改模板。此外，库在在线比赛中是不允许使用的。最后，使用库代码（或者宏）将使得你习惯于理解你的库而不是语言的本身，这将会使得你不能够在challenge阶段彻底的理解其他程序员的代码。如果用的得当，你的库很强大，但不是对任何东西都适合的终极武器。

有可能会出现你无法将一个原子代码再进行分段。这时你应当对代码进行分析，并思考当前的方法。我是否应该将任务分割成另外一种形式呢？我应该将中间值进行另外一种形式的存储吗？或者也许这正是问题很难解决的关键点？在你找到关键点之前任何事情都要考虑到。甚至当你意识到你无法解决这些点时，用手算来看怎样可以更快的处理，这些方法构成了剩下的方法策略。

Codeboy 2008-04-08 12:26 发表评论