※ 引述《peanut97 (丁丁)》之铭言： : 遇到一个国三生，有轻微亚斯伯格症，对电脑、程式非常有兴趣。 : 应该说，只让电脑进入他的世界。 : 家人已经放弃让他以课业升学。 : 他想要做一个浏览器、想要修改Android作业系统，喜欢Linux环境、 : 喜欢MAC。唯独程式语言不太会。 : 我正在教他PHP网页。 : 未来想帮助他往「程式设计竞赛」方向走，但是程式设计竞赛好像比较硬。 : 请问「程式设计竞赛」，有没有比较好入门的方向呢？ : 对未来要走软体的国三生来说。 版上有许多大大与一些我十分敬佩的学长也有在逛这个版 如果有哪里讲错麻烦站内信或推文指正一下 <(_ _)> 先从「程式设计竞赛」这件事情开始谈起好了 先来了解一下有哪些程式竞赛、赢了程式设计竞赛可以干嘛 因为国中生可以比的实在是很少，所以以下我所提到的都是国高中生 大部分都是高中生才能够参加 1. NPSC http://contest.cc.ntu.edu.tw/npsc2015/schedule.asp 台大举办的比赛，每年一次，有分国中组跟高中组 分初赛跟决赛，初赛是线上赛，在家里或是任何有电脑的地方都可以比 初赛过关之後比决赛，要去台大计算机中心比赛，有好吃的点心跟餐盒 题目的话可以自己上这个网站找一下历届题目 国中组的题目一般来说不会太难，有一些字串处理或是模拟题 难题大概是DFS（深度优先搜索）BFS（广度优先搜索）跟最短路径 （参加的年代有点久远，所以我不太确定） 高中组的题目难度就高了许多，DFS, BFS, DP（动态规划） 都是基本 可能会出现一些比较特别的演算法，或是网路流(flow)、计算几何之类的题目 我参加 NPSC 是从国二到高二 我高二是大概五年前的事情，所以算是有一点远了 但 NPSC 我觉得满不错的，而且是少数国中生也能参加的比赛 2. 北市赛（地区赛） http://contest.tp.edu.tw/?id=1412135239 升上高中以後，多一个地区赛可以比，我比的是台北市资讯能力竞赛 我们都简称北市赛，其他的我记得有中区跟南区，东部跟新北我就不是很确定了 北市赛有名额限制，如果同高中有太多人想参加，会先比个校内赛（学校自己办） 奖项分成四种：一等奖*5、二等奖*5、三等奖*10跟入选奖 前十名（也就是一二等）可以参加全国赛 这我高一有比过，有分成笔试跟上机 比重好像是30%跟70%，这我不太确定 3. 全国赛 各区的前十名来比 这我没参加过所以没什麽可以讲XD 全国赛的前十名可以保送TOI（等等会讲） 4. 台北市软体竞赛 http://tpc.taivs.tp.edu.tw/ 高中高职都可以比，组别也不同 高中组题目跟其他比赛大同小异 我高二有参加过，那时候是在松山工农比 5. TOI TOI就是台湾资讯奥林匹亚研习营Taiwan Olympiad in Informatics http://toi.csie.ntnu.edu.tw/ 听到奥林匹亚就觉得很厉害，因为这真的很厉害 上面讲过，全国赛前十名可以保送这个研习营 另外20个名额会再举办一个入营考招生 进去以後一共30人，我们称之为第一阶段，简称1! 1!会到师大住两个礼拜培训，每天都上一些资结/演算法的课 每个礼拜都会有一个小考试，会决定你能不能到第二阶段（俗称2!） 我高一的时候有进1! 在里面生活满愉快的，因为吃住都不用钱，而且学校那边可以请公假 请两个礼拜公假XDDD 1!的大约前12名可以进2!，然後再培训两个礼拜 最後取前4名，就是国手了，就可以参加 IOI 国际资讯奥林匹亚 http://toi.csie.ntnu.edu.tw/main_01.php?ID=17 每年举办的地方都不一样，2014在台湾办过 以上五个就是高中生基本上可以参加的竞赛 其中最重要的当然就是TOI 为什麽呢？因为如果你够强当上国手然後有拿牌，可以保送任一大学的资工系 你想去台清交成任何一间都可以 如果没有前四名，但你进2!而且名次在满前面，也可以靠推荐的方式去推资工系 这个推荐跟学测指考都没什麽关系，是另外一个特别的管道 所以，如果你把资料结构/演算法练到超级猛但是国英数超级烂，还是可以进112资工 但这种人极少而且超极端XD 谈完了资讯竞赛有哪些，来谈谈这些比赛考什麽跟计分方式 每个比赛大概会有六题以上，基本上都用英文代号，也就是pA, pB, pC, pD, pE... 答对叫做AC(Accept)，答错叫做WA(Wrong Answer) 超时叫做TLE(Time Limit Exceeded)，其他还有一些我就不再赘述 一般的比赛时间大概都三个小时起跳 每一题的得分是：答对时间 - WA次数*20，没答对的话则这题不加分不扣分 比赛的时候会有即时计分版，选手也看的到；但比赛结束前一小时会封盘 现场比赛的话满好玩的，只要答对一题就会送你一颗气球 你看谁前面气球多就知道谁最神XDD 考试类型的话就是大家所熟知的资料结构/演算法 http://www.csie.ntnu.edu.tw/~u91029/ 列出了许多有用的东西 通常会用一个很生活化的方式包装题目，让你觉得比较有趣 像是这一题：http://tioj.infor.org/problems/1026 其实就是考你二进位转换，但把题目包装过 有些题目很好玩包装的很好，你拆一拆之後会恍然大悟：阿！原来是这个！ 就是那个 moment，会让你觉得超级有趣（至少我自己这样觉得XD） 或是这一题，http://tioj.infor.org/problems/1143 说穿了就是 BFS 或这一题：http://zerojudge.tw/ShowProblem?problemid=b127 题目落落长，但看穿了其实就是费式数列 讲了这麽多，终於可以回到正题 程式解题这件事情，你要引起他的兴趣的话，我觉得可以从两个方向 第一个就是从利诱下手，跟他说「你这个很强的话可以保送台大资工喔」 第二个就是让他真的爱上这些解题的过程 怎麽做？先让他解一题看看 你先去各个online judge看一些答对率比较高的题目 找一题自己觉得有趣的又不会太难的，然後叫他解解看 解完了就再找一题，尽量找一些有趣一点的，试着引起他的兴趣 或是你可以直接拿一些经典题，一步一步引导他 例如说经典的背包问题： 你现在有一个容量是100公斤的背包 你有一堆物品，每一项都有一个价值V、重量W公斤 每一项物品都只有一个，也就是你只能选择拿/不拿 你要怎麽选择，才能让你拿到的价值最高？ 我有一个原则是：先求有，再求好 一个最简单的想法是：我穷举不就好了吗？ 如果有n个物品，一共有2^n种拿法，保证可以找到解答 这时候可以顺便带入时间复杂度的概念 问他说：那如果n是10000的话怎麽办？2^10000电脑跑不动耶 那就要想有没有更好的解法 一步步提示他，接着一起完成这一道题目 光是背包问题就有一堆可以继续延伸 像是刚讲的0/1背包、无限背包、二维背包等等 有兴趣的可以参考背包问题九讲：http://love-oriented.com/pack/ 除了这个，也可以教他最短路径 最短路径就有几种不同的演算法，每一种的思考方法都不太一样 或若你觉得这些太难，就从排序法开始吧 泡沫排序、插入排序、快速排序、合并排序、桶子排序... 每一种都有各自的想法跟想解决的问题 二分搜也是一个很好的入门 你可以说：现在你有1000个数字，如果我要问你：500在不在里面，你要怎麽做？ 他可能会回答：就从第1个扫到第1000个阿 接着你问说：那如果我要问你很多次呢？500, 501.., 600, 700在不在里面？ 他可能会回答：跟刚才一样，每次问都扫一次 你就问说：那有没有更好的方法呢？假如我们排序以後，会变怎麽样？ 话说我觉得用终极密码来讲二分搜还不错，两个有异曲同工之妙XD 如果以上都太难，就从一些基本的字串处理之类的开始 可以参考acm的一星题：http://luckycat.kshs.kh.edu.tw/ 或是一些online judge比较多人答对的题目 写完之後切记，一定要上传！ 为什麽？因为答对会超有成就感！成就感也是很重要的一部分 藉由这种线上解题系统，就可以增加成就感，而且有些还有排名 让你知道你这题时间第几名、code的长度第几名 有时候会为了缩code长度用一些奇淫技巧XD 一步步引导，从慢到快，从无限制到有限制 从这些过程试着引起他对程式解题的兴趣 试图让他为「阿！原来可以这样」的感觉感到兴奋 一旦引起他的兴趣，他应该会沉浸在这样的世界里面 像是有一题我就觉得超级有趣 http://tioj.infor.org/problems/1513 你有一个数列，除了一个数字以外两两成对，找出那个数字 数列长度<=100000，0<=数字<=2^31 例如说：1 2 3 2 1，答案就是3 0 0 0 777 0 0 0，答案就是777 这题就很适合先求有再求好 你可以 sort 之後比a[i]跟a[i+1]，但你发现这样不够快 你可以 map 存起来之後检查，但你发现这样记忆体耗太多 正解是什麽就留给大家思考，我自己是很爱这个简单但神奇的解答 最後附上一篇强者我学长的文：Re: [讨论] 所以练acm都底有啥好处？ https://webptt.com/cn.aspx?n=bbs/Programming/M.1411474900.A.746.html --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.216.67.187 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1451998694.A.9BA.html ※ 编辑: Y78 (61.216.67.187), 01/06/2016 19:59:07