脑满肠肥1001夜

来源: BlogBus 原始链接: http://1001night.blogbus.com:80/logs/2006/01/1975886.html 存档链接: https://web.archive.org/web/20061106175538id_/http://1001night.blogbus.com:80/logs/2006/01/1975886.html

<< Windows下练C++编程请用 VC Toolkit 让firefox支持blogbus的编辑器 >> OnlineJudge 编程练习的选择 2006-01-13, by 碧蓝右耳 我在原来的Blog上写过一篇介绍OnlineJudge的东西，后来被到处地转载。可见OJ这种不为人知的好东西是应该向大家推荐的。 有没有觉得学编程到一定阶段就无事可干呢。你已经掌握了语言的基本语法，教材后的练习题也全部完成了，但你就是不知道这语言能干什么，也不知道要怎样才能编写自己程序。莫非要马上写一个Office或是魔兽世界，似乎毫无头绪。就象学写作，掌握了大量优美的词句、熟练的语法和丰富的修辞手段，是不是立刻就可以来创作《战争与和平》了呢。似乎还缺点什么，是的，难道不要先写点随笔散文之类的练练手吗。我们需要的是具有实际应用背景的题目，他们比教材上那些注重语法本身练习的题目要高级些，但要比真正的生产实际要简单。那么，到哪里去找这些合适的题呢。如果能够有答案或者指导以便判断对错那就更好了。如果你也在找这样的东西，那么来试试OnlineJudge系统吧。 Online Judge系统——简称OJ——是在线的裁判系统。她可以对程序原代码进行编译和执行，并通过预先设计的测试数据来检验程序原代码的正确性。首先，他是一个在线的题库，有很多习题，你可以任选其中之一来解答。然后，系统的编译器能够编译执行你所提交的代码。如果编译通过，针对每个题目，系统将使用自带的多组测试数据检验你的程序，如果程序都能得到正确的输出，那么你顺利地解决了这个问题。最后，系统还能对所有参与答题的用户进行统计和排名。 OJ的题目大部分是关于算法的。题目的输入输出通常是命令行方式，而非图形界面。也就是说，要关注的不是平台的兼容性、文件的格式抑或窗口的布置这种无关紧要的细节，而是问题本身的逻辑实现。本文最后附带的例题就可以清楚的表现出 OJ题目的特征。 一个用户提交的程序在Online Judge系统下执行时将受到比较严格的限制，包括运行时间限制，内存使用限制和安全限制等。用户程序执行的结果将被Online Judge系统捕捉并保存，然后再转交给一个裁判程序。该裁判程序或者比较用户程序的输出数据和标准输出样例的差别，或者检验用户程序的输出数据是否满足一定的逻辑条件。最后系统返回给用户一个状态。 OJ接受的语言，包括C C++ java 和pascal等，因不同的系统提供者而有所不同。由于java本身的特性，通常，java程序的允许运行时间是其他几种语言的5到6倍。 Online Judge系统来自ACM大赛。由美国计算机协会（ACM Association for Computing Machinery）发起和组织的ACM国际大学生程序设计竞赛（简称ACM/ICPC）是目前世界上规模最大的计算机学科赛事。他发起于1977年，要比国际信息学奥林匹克竞赛（IOI）的首届还早12年。世界各地的知名大学都会派队参加，每年的下半年在各个洲进行预赛，全世界大约有60多个队可以参加最后的决赛。我国的成绩十分让人骄傲，目前已在ACM取得冠军两次及其它名次若干。 无论从哪个角度看，Online Judge系统都可以看成IOI或ACM的训练题库。我一直怀疑，Online Judge系统最早可能就是ACM的评分系统，但这一点无法确认。可以确认的是，现在很多大学开设了Online Judge系统，用以训练自己的ACM/IOI队员。系统通常摆放在他们的网站上，同时对公众开放。而其中规模最大、参与人数最多、水平最高的，当属 University of Valladolid 开设的OJ系统（简称UVA），据称那就是ACM官方的。全世界有n十万的兄弟姐妹们在搞上面的题目，除了个人排名，还有国家地区排名。目前，中国大陆排第四，第三名是中国台湾省，第二名是孟加拉，第一名是欧共体。香港特区也在前十名，位列第九。说是训练题库，题目的难度可不低。最基础的大约有二十个左右题目，纯属熟悉系统环境用，比较难的题，程度与ACM的试题不相上下。只要意识到即使有这么多人在做，还是有个别题目至今无人能够解答的情况，你对UVA的OJ系统的难度也就有了大体的估量吧。同时题量也不小，大约是1800题。按民间的说法，如果你能够完成总量的80%到90%，试着向微软或者IBM等大公司的技术研发部投一封求职信吧，应该会有所收获哦。当然不是每个OJ系统难度都那么高，也不是每个OJ的题库都那么庞大，不过100~200题的量总是有的。 相信你已经跃跃欲试了，那我就给你介绍几个可去的OJ吧。 浙江大学的Online Judge 国内最早也是最有名气的OJ，有很多高手在上面做题。特点是数据比较刁钻，经常会有你想不到的边界数据，很能考验思维的全面性。 北京大学的Online Judge 建立较晚，但题目加得很快，现在题数和ZOJ不相上下，特点是举行在线比赛比较多，按某位访客的留言，数据比ZOJ上的要强很多，有时候同样的题同样的程序，在ZOJ上AC(accomplished)，在POJ上就能WA(wrong answer) 同济大学的Online Judge 强烈建议初学者和新手前往的地方。题数上不能与上两个相比，推荐这个OJ的原因是它是中文的，这对很多对英文不太感冒的兄弟是个好消息吧。它也因此吸引了众多高中的OIer，上面的题目也更偏向高中的信息学竞赛一些。 西班牙的Universidad de Valladolid 世界上最大最有名的OJ，题目巨多而且巨杂，数据也很刁钻，全世界的顶尖高手都在上面。据说如果你能在UVA上AC一千道题以上，就尽管向IBM、微软什么的发简历吧，绝对不会让你失望的。 俄罗斯乌拉尔大学 也是一个老牌的OJ，题目不多，但题题经典。 USACO 全美计算机奥林匹克竞赛（USACO）的训练网站，特点是做完一关才能继续往下做，与前面的OJ不同的是测试数据可以看到，并且做对后可以看标准解答，所以如果大家刚开始的时候在上面那些OJ上总WA却找不到原因的话，可以试着来这里做做，看看测试数据一般是从什么地方阴你的。 最后，附上一道OJ题让大家先睹为快，此题十分简单 题名：防御导弹 Time Limit:1s Memory Limit:1000k Total Submit:3461 Accepted:1116 问题描述： 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 Input 最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数） Output 两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。 Sample Input 300 250 275 252 200 138 245 Sample Output 5 2 发布于: 20:00:54 | 分类: 原创 教程 C++ | 引用(0) | 编辑 0 条评论: 添加评论