《精编》浅谈设计获胜策略

《《精编》浅谈设计获胜策略》由会员分享，可在线阅读，更多相关《《精编》浅谈设计获胜策略（9页珍藏版）》请在金锄头文库上搜索。

1、设计获胜策略设计获胜策略 一个好的取胜之道是制定在竞赛中指导你行动的策略。无论是在好的情况下还是在坏的情况下，它将帮助你决定你的行动。用这种方法你可以在竞赛中将时间花费在解决编程问题上而不是试图决定下一步该干什么这有点像预先计算好你面对各种情况的反应。 心理上的准备也很重要。 竞赛中的策略 首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节， 集体讨论所有可能的算法 然后选择最“笨”但却可行的算法。（注：请注意这一点，对参赛选手来说获奖就是唯一目的） 进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量） 试图证明该算法错误（？原文是Try to break the

2、 algorithm） 使用特殊的（退化的）测试数据。 将问题排序：根据你所需付出的努力，将最“短”（从原文理解是指解决问题费时最短）的问题排在前面。（从“短”到“长”的次序为：以前做过的，容易的，不熟悉的，困难的） 编写程序解决一个问题 对每一道题而言，一次一道题 确定算法 构造特殊情况的测试数据 写出数据结构 编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性） 编写并测试输出子程序 逐步细化：通过写注释来刻划程序的逻辑轮廓 一个部分一个部分地填充并调试代码 完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据） 试图证明代码错误（？原文是Try to break t

3、he code）使用特殊情况的测试数据来验证代码正确性 逐渐优化但足够了即可，并且保存所有的版本（使用困难情况的（即运行时间长的）测试数据来计算出实际运行时间） 时间安排策略和“故障控制”方案 制定一个计划决定在各种（可预测的！）故障发生时的行动；想象你可能遇到的问题并计算出你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你何时放弃并继续做下一题？”。考虑以下问题： 你已经花费了多长时间来调试它？ 你可能有什么样的BUG（BUG是指程序中的错误）？ 你的算法有错吗？ 你的数据结构需要改变吗？ 你是否对什么地方可能会出错有一些头绪？ 花费较短的时间（20分钟）在调试上比切换去

4、做其他别的事要好；但是你或许能够在45分钟内解决另一个问题（？原文是A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins.） 你何时返回到一个你先前放弃的问题？ 你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他事？ 从这里考虑出去（？原文是Consider from here out）忘记先前的努力，着眼于将来：你如何才能就你目前所有的抓住下

5、一个小时。 在你上交你的答案之前列出一个校验表： 在竞赛结束前五分钟冻结代码？（？原文是Code freeze five minutes before end of contest?） 将所有的声明关闭。 将调试输出关闭。 确认输入输出文件名正确。 确认输入输出格式正确。 重新编译并再测试一次。 将文件以正确的文件名复制到正确的位置（软盘）。 提示和技巧 如果可以就用暴力法（即穷举法）解决 （注：居然将这条作为技巧，可见竞赛的目的就是获奖，为此要“不择手段”。） 键索引顺序搜索（KISS= Keyed Indexed Sequential Search）：简单就是聪明！（？原文是KISS: S

6、imple is smart!） 提示：注意限制（在问题陈述中指明） 如果可以给你带来方便的话就浪费内存（假如你能侥幸逃脱处罚的话） 不要删除你额外的调试输出，将它注释起来 逐渐地优化，足够了即可 保留所有的工作版本 从编码到调试： 空白是好的（？原文是whitespace is good） 使用有意义的变量名 不要重复使用变量 逐步细化 在写代码之前先写注释 有可能的话尽量避免使用指针 避免使用麻烦的动态内存：静态地分配所有的东西。 尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝对不要测试两个浮点数相等） 对注释的注释： 不要写得太长，简洁的注解就可以了 解释复杂的

7、功能：+i; /* increase the value of i by 1*/ 这样的注释是毫无意义的。 解释代码中的技巧 将功能模块划定界限并且document （？原文是Delimit & document functional sections） 好像是写给某个了解该问题但并不了解程序代码的聪明人看的 任何你不得不考虑的东西 ？原文是Anything you looked at even once saying, now what does that do again? 总是注释数组的索引次序 记录你每一次竞赛的情况：成功之处、犯的错误，以及何处你可以做得更好；利用这些记录来改进你的策

8、略。 复杂度 基础和阶符号 复杂度分析的基本原理围绕着符号“大O”，例如：O(N).这意味着算法的执行速度或内存占用将会随着问题规模的增倍而增倍。一个有着O(N 2)的算法在问题的规模增倍时其运行时间将会减慢4倍（或者消耗4倍的空间）。常数时间或空间消耗的算法用O(1)表示。这个概念同时适用于时间和空间；这里我们将集中讨论时间。 一种推算一个程序的O( ) 运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢的）循环支配着运行时间，同时它也是在讨论O( ) 符号时唯一考虑的循环。有一个单重循环和一个单层嵌套循环（假设每个循环每次执行N次）的程序的复杂度的阶是O(N 2)，尽管程序中同时有一个

9、O(N)循环。 当然，递归也像循环一样计算，并且递归程序可以有像O(b N)， O(N!)， 甚至O(N N)的阶。 经验法则 在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第一条经验法则是：现代（1999）计算机每秒可以进行10M次操作。对于一个有五秒钟时间限制的程序，大约可以处理50M次操作。真正优化的好的程序或许可以处理2倍甚至4倍于这个数目的操作。复杂的算法或许只能处理这个数目的一半。 640K确实是苛刻的内存限制。幸运的是，1999-2000赛季将是这个限制的最后一次起作用。 210 约等于10 3 如果有k重嵌套的循环，每重大约循环N次，该程序的复杂度为O(

10、N k)。 如果你的程序有l层递归，每层递归有b个递归调用，该程序复杂度为O(b l)。 当你在处理有关排列组合之类的算法时，记住N个元素的排列有N!个，N个元素的组合或N个元素组成的集合的幂集的有2 n个。 对N个元素排序的最少时间是O(NlogN)。 进行数学计算！将所有的数据加起来。（？原文是Plug in the numbers.） 例子： 一个简单的重复N次的循环复杂度为O(N)： 1 sum=0 2 fori=1ton 3 sum=sum+i 一个双重嵌套循环的复杂度通常为O(N 2)： #fill array a with N elements 1 fori=1ton-1 2 f

11、orj=i+1ton 3 if(aiaj) swap(ai,aj) 注意，虽然这个循环执行了N(N+1)/2 次if语句，但他的复杂度仍然是O(N 2)，因为N加倍后执行时间增加了四倍。 解决方案的范例 产生器 vs. 过滤器 产生大量可能的答案然后选择其中正确的（比如8皇后问题的解答），这样的程序叫做过滤器。那些只产生正确答案而不产生任何错误节点的叫做产生器。一般来说，过滤器较容易（较快）编程实现但是运行较慢。通过数学计算来判断一个过滤器是否足够好或者是否你需要尝试制作一个产生器。 预先计算 有时生成表格或其他数据结构以便快速查找结果是很有用的。这种方法叫做预先计算（在这里用空间换取时间）。

12、你可以将需要预先计算的数据和程序一起编译，在程序开始时计算；也可以干脆记住预先计算出的结果。比如说，一个程序需要将大写字母转化为小写字母，可以不需任何条件地利用一个表格进行快速查找来实现。竞赛题经常要用到素数生成一长串素数在程序中某处使用通常是很实用的。 分解（编程竞赛中最困难的事） 虽然在竞赛中经常使用的基本算法不超过20种，但是某些需要将两种算法结合才能解决的组合型问题却是很复杂的。尽量将问题不同部分的线索分离开来以便你可以将一个算法和一个循环或其他算法结合起来以独立地解决问题的不同部分。注意，有时你可以对你的数据的不同（独立）部分重复使用相同的算法以有效地改进程序的运行时间。 对称 许多问题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是相同的）。对称可以是2路的（？原文是2-way），4路的，8路的或是更多的。尽量利用对称以减少运行时间。 例如，对于4路对称，你只需解决问题的四分之一，就可以写下4个结果，这四个结果和你所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。 正向 vs. 逆向 令人惊讶地，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一种基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。