Question

演算法是什麽？

演算法是计算机科学非常重要的基础科目。简单来说，演算法就是用电脑算数学的学问（古代人用算盘算、现代人用电脑算），可以说是数学科目。

想要解决现实生活当中的各种问题，电脑科学家就把现实问题对应到数学问题，然后设计公式、把公式写成程式，让电脑执行程式计算答案──这些公式就叫做演算法了。

儘管这裡用了“公式”这个字眼来形容演算法，然而并不是各位印象中的数学公式。由于电脑能够执行繁複的计算，所以公式可以设计成好几十行、好几百行，甚至用到很多数学理论。

因此呢，就算学习过演算法的人，也不见得懂得设计演算法；因为数学、程式的东西实在太複杂了。想把现实问题对应到数学问题，那就更複杂了。

电脑只会算数字

回过头来，电脑又是什麽？电脑是个很潮的中文翻译，不过实际上电脑的原意是“计算机”。电脑的英文叫做 computer，而计算的英文就叫做 compute。

电脑是一台计算机，只会计算、判断、储存数字。又快又准。

程式是一连串计算、判断、储存数字的步骤。

电脑只会处理数字（二进位数字）。电脑裡的每一个文字、每一种颜色、每一种声音，其实都有相对应的数字。

打个比方，我们规定：用 1 代表“一”，用 2 代表“乙”，用 3 代表“人”，……。一个数字对应一个中文字。电脑裡面的所有中文字，都依循人为规定，变作了数字。

再打个比方，“人”这个字，呈现电脑萤幕上是个“人”样。电脑萤幕的画面，是由许多小光点组成的；电脑萤幕上的“人”也是由许多小光点组成的。我们以“人”的左下角为座标原点，横向为 X 轴，直向为 Y 轴，那麽“人”其实是(0,1)、(1,2)、(2,3)、...这些座标画上黑点后所形成的。“人”这个字的的形状，在电脑中变作了一连串的数字。

同样的道理，呈现在电脑萤幕画面上的文字、颜色、图片、影像、声音，全部都可以化作数字。一切事物在电脑裡面都是数字。

电脑并没有想像中的那麽神奇。不过电脑最厉害的地方并不是电脑本身，而是在于电脑可以接上各式各样的设备。接上摄影机与萤幕，就可以把色彩变成数字、把数字变成色彩；接上麦克风与耳机，就可以把声音变成数字、把数字变成声音。

电脑一旦接上了设备，就额外有用处。接上话机和基地台，就可以互通有无；接上数位相机和印表机，就可以制造回忆；接上重量仪和筛子，电脑也会拣土豆；接上车厢、接上警示灯、再杂七杂八接上一堆东西，就变成了大众运输系统。

若要用电脑解决现实问题，通常要考虑两个方面：一、电脑应该接上那些设备？如何用电脑控制这些设备？二、现实问题如何对应到数学问题？如何设计演算法？

程式用来比对数字、改变数字、储存数字

举个例子，我们希望把萤幕上的“人”变成斜体字。过程大略是这样──首先呢，把“人”的形状(0,1)、(1,2)、(2,3)、...这些数字拿出来；然后呢，位置越高的座标，就往右移动多一点，如此一来就成为斜体字了。想让座标往右移动，就是让电脑做数字加法计算，然后把相加结果储存起来。

再举个例子，用滑鼠点选一个资料夹，资料夹的颜色会反白。过程大略是这样──首先呢，电脑侦测到滑鼠点击的座标之后，把座标转换成数字；然后呢，再把萤幕画面的资料拿出来，看看萤幕上每个东西的座标，是哪一个与滑鼠的座标相符合；噢，原来是一个资料夹的图示，把资料夹的显示颜色给反白过来。

再举个例子，电脑据说会拣选土豆。过程大略是这样──把每一颗土豆拿出来，利用特殊的仪器，把形状、重量、色泽、气味统统转换成数字，储存在电脑裡面；然后呢，用电脑比较这些数字，找出优良的土豆，如此一来就有绵绵鬆鬆的土豆了！

编写程式，计算数字，这就是程式设计师的工作。

数学和程式这麽複杂，为什麽要用电脑解决现实问题？

电脑的计算速度可说是非常的快，一秒钟可以进行好几千万次。就算文字多麽的多，图片多麽的大，电脑处理起来，也是轻鬆写意，顺畅无比。

打开电脑裡的任何一份文件，用滑鼠捲动一下文件画面，眼睛都还没眨一下，正确画面马上就呈现在萤幕上了。事实上在捲动画面的时候，电脑已经经过几千万次的计算，仅使用了极短的时间，就把萤幕上应该呈现的资料全部计算好了。

人类会想要用电脑解决问题，正是仰赖电脑的计算速度、正确性，以及电脑会自动按照程式计算的特性。程式设计师只要花心思写出一支好程式，接下来的工作就可以让电脑代劳了。电脑做的比人类更快更好，电脑做得到人类做不到的事情；儘管数学和程式很複杂，还是有很多人选择使用电脑解决问题。

那些现实问题是用演算法解决的？

现代人的生活已经离不开演算法了。比如说你的手机裡面就有上百个演算法。你可以 Google 一下新闻。下面的表格是随手整理出来的，可以参考看看。

物理 ⑴ 
化学 ⑴ ⑵ 
医学 ⑴ 
药学 ⑴ 
生物 ⑴ 
农业 ⑴ ⑵ 
天文
地理 ⑴ 
海洋
太空 ⑴ ⑵ 
地球 ⑴ 
环境 ⑴ ⑵ 
生态 ⑴ 
社会 ⑴ ⑵ 
心理
居家 ⑴ ⑵ 
生活 ⑴ 
设计 ⑴ 
艺术 ⑴ 
美术 ⑴ 
音乐 ⑴ 
文学 ⑴ 
历史 ⑴ ⑵ 
游戏 ⑴ ⑵ 
玩具 ⑴ 
演艺 ⑴ ⑵ 
经济
金融 ⑴ ⑵ 
讯息 ⑴ 
交通 ⑴ 
运输 ⑴ ⑵ 
物流 ⑴ 
鑑识 ⑴ 
治安 ⑴ ⑵ 
国防 ⑴ 
政治 ⑴ 
教育 ⑴ ⑵ 
救护 ⑴ 
安全 ⑴ ⑵ 
机械 ⑴ 
工厂 ⑴ ⑵ 
资源 ⑴ 
能源

Algorithm

演算法是什麽？

演算法 由三个部分组成：输入、计算步骤、输出。介绍这件事情的时候，有人连结到 函数 的概念，也有人连结到 黑箱白箱 的概念。

          -----------------
input --->| computational |
          | sequence      |---> output
          -----------------

输出、输入是一堆数字。实务上是将这些数字放在 资料结构 ，例如 array、list。输入来源，通常是硬碟裡面储存的档案，或者是藉由硬体装置撷取到的数字，例如数位相机、麦克风等等。输出去处，通常是硬碟裡面储存的档案，或者是藉由硬体装置转换之后以其他型态呈现，例如数位电视、数位音响等等。

计算步骤是一连串处理数字的指令。指令有两种类型，一类是运算，例如数学运算加减乘除、逻辑运算且或非、比较运算大于等于小于、位元运算左右反且或异或。另一类是读写，例如读取某处的数字、储存数字至某处，就跟 计算机 的 MR、M+按键的意义相似。

古人定义演算法，规定计算步骤的数量是必须是有限步，不是无限步。用程式语言的术语来说就是：演算法不能有无穷迴圈。

古人当初规定有限步，是为了方便统计总步数。但是实务上，很多电脑程式是开启之后就保持执行状态，直到当机、重开机，例如网路传输的演算法。因此实务上可以是无限步。

如何记载一个演算法？

有人用 虚拟码 来记载一个演算法。如要设计 电脑程式 ，虚拟码是比较恰当的。

GREATEST_COMMON_DIVISOR(a, b)
1   while a ≠ b do
2       if a > b then
3           a ← a - b
4       else
5           b ← b - a
6   return a

有人用 流程图 来记载一个演算法。如要设计 电子电路 ，流程图是比较恰当的。

大多数时候，我们无法光从虚拟码和流程图彻底理解演算法，就如同我们无法光从数学公式彻底理解数学概念。想要理解演算法，通常还是得藉由文字、图片的辅助说明。

如何实作一个演算法？

实作的意思是：实际去操作、实际去运行。

对于资工系学生来说，自然就是把演算法撰写成 电脑程式 ，例如 C 或者 C++程式，然后在 个人电脑 上面执行程式。

对于电机系学生来说，自然就是把演算法设计成 电子电路 ，在 麵包板 、 印刷电路板 、 PLD 上面执行。

电子电路也有加法器、减法器、AND 逻辑闸、OR 逻辑闸等等，所以也可以用电子电路实作演算法。例如电子錶、随身听、悠游卡等等，都是直接将演算法做死在晶片上面。在个人电脑、智慧型手机还没流行之前，以往都是用电子电路实作演算法。

电子电路的执行速度是飞快的，电脑程式的执行速度慢了一点。然而，制作电子电路的过程相当麻烦，需要精密的设备、複杂的制程、大量的人力和经费，而且制成之后就无法修改；相对地，写程式就简单轻鬆多了，在电脑上面很容易调整程式码，又可以储存很多程式码，最主要的是家家户户都有电脑。

时间複杂度、空间複杂度

要评断一个演算法的好坏，最基本的指标是时间和空间。

最直觉的方式，就是测量程式的执行时间、程式的记忆体使用量。但是由于相同演算法于不同电脑的执行时间会有差异，又由于每个人实作演算法所採用的程式语言、程式设计技巧都不一样，所以执行时间、记忆体使用量不是一个稳定的评断标准。

数学家于是计算步骤数量。

BUBBLESORT(A)
1 for i ← 0 to length(A)-1 do
2     for j ← 0 to length(A)-i-1 do
3         if A[j] < A[j+1] then
4             swap A[j] and A[j+1]

-----------------------------------------------
| pseudo code                      | step     |
|---------------------------------------------|
| BUBBLESORT(A, n)                 |          |
| 1 for i ← 0 to n-1 do            | n        |
| 2     for j ← i to n-i-1 do      | n(n-1)/2 |
| 3         if A[j] < A[j+1] then  | n(n-1)/2 |
| 4             temp ← A[j]        | n(n-1)/2 |
| 5             A[j] ← A[j+1]      | n(n-1)/2 |
| 6             A[j+1] ← temp      | n(n-1)/2 |
-----------------------------------------------
total = n + 5n(n-1)/2
      = n + 2.5n2 - 2.5n
      = 2.5n2 - 1.5n
      = O(n2)

数学家把步骤数量写成代数式子。例如当输入资料有 n = 1000 个数字，步骤数量一共是 2.5×1000² - 1.5×1000 = 2498500 步。

有了步骤数量之后，还可以进一步粗估执行时间。假设一个步骤需要 10 个 clock，而电脑中央处理器 CPU 的时脉是 2GHz：每秒钟执行 2000000 个 clock，那麽程式执行时间大约 12.4925 秒。

但是这不是精准的步骤数量。由于实作的关係，係数很容易变动，所以係数的意义不大。因此数学家只取出代数式子的最高次方，并且规定 n 必须足够大（类似微积分的趋近无限大）。儘管这是非常不精准的估算方式，不过还是可以对常见的演算法进行简易分类，粗略地比较快慢。

               | time*       | space
---------------+-------------+--------
bubble sort    | O(n2)       | O(n)
insertion sort | O(n2)       | O(n)
merge sort     | O(n log(n)) | O(n)
quicksort      | O(n2)       | O(n)
heapsort       | O(n log(n)) | O(n)
counting sort  | O(n+r)      | O(n+r)

*worst case

空间的计算方式与时间类似，就不多提了。

解决问题的成效

要评断一个演算法的好坏，除了时间和空间的用量以外，主要还是看演算法解决问题的成效如何。

数学问题，通常可以明定解答好坏，例如数字越大越好。通常这种情况，有多种演算法可以求得正解，那麽这些演算法的成效是一样好的。

真实世界的问题，通常难以界定绝对的好坏优劣，例如美丑、乐音噪音、喜怒哀乐、是非对错等等，此时演算法的成效，则由人类自行判断，利用两两比较、投票表决等等方式来决定成效。

数学与计算学

数学是以基本元件来构筑事物、表达概念。而数学家藉由数，尝试构筑每一件事物、表达每一个概念，拼凑出世界的全貌。比如位置、形状、关係、转换、递迴、极限、比较、排列、正反、假设，这些东西都是数。又比如有、无、聚、散、疏、密、盈、亏、弯、直、交、错、动、静，这些东西也都是数。与物体的行为有关的数，就是物理；与物质性质变化有关的数，就是化学；与生命运作有关的数，就是生物学。继续细分下去的话，我们所知的各种东西，其实皆可说是数。

在数当中，可以用数量来表示的，便可以计量。像是情绪、风格、谋略，难以用数量来表示，也就难以计量，甚至不可计量。像是动作、旋律、次序，可以部分地或完全地用数量表示，便得以计量。计算学是以数量来构筑事物、表达概念。而计算学家藉由数量，尝试量度各种事物、各种概念，掌握其确切的程度与层次。

Algorithm

学习程式语言

学习程式语言，有两个层次：一、程式语言本身的语法；二、把想法转换成程式码。

第一个层次称做“程式语言 Programming Language”。目标是背熟规格书、灵活运用程式语言。

第二个层次称做“程式设计 Programming”。目标是设计程式码解决问题。然而现今世界上还没有一套固定的流程。

学习演算法

学习演算法，有两个层次：一、演算法本身的运作过程；二、把想法转换成演算法。

第一个层次称做“演算法 Algorithm”。目标是理解演算法、灵活运用演算法。读者可以参考本站首页的各大栏位，例如图论、计算几何、字串学等等。

第二个层次称做“演算法设计 Algorithm Design”。目标是设计计算步骤解决问题。读者可以参考本站首页的 Algorithm Design 栏位，以及从各种演算法当中汲取经验、撷取灵感。

学习函式库、工具

很多现实问题及其计算步骤，已经成为标准流程 SOP，没有什麽改动的馀地，成为了演算法。因此科学家就把这些演算法编写成函式库（Library），接著把现实生活的常见需求编写成工具（Toolkit），让程式设计的过程更加迅速。

时间就是金钱。现今的软体产业当中，绝大部分都是直接使用现成的函式库、工具，只有从事研发才会从无到有设计程式码、设计演算法。优秀的工程师，总是擅于活用函式库、工具，快速实现自己想要的功能。网路上已经有许多现成的函式库和工具，通常也附带详细的使用说明书，方便工程师运用。

由于大家看事情习惯只看表面，因此衍生了一种奇怪的现象：大家把使用工具称做“使用技术”，大家把背熟使用说明书、依样画葫芦称做“学习技术”。大家常常自诩拥有许多“技术”，将“技术”奉为圭臬；但是却很少人懂得背后的程式码技巧、演算法原理，也很少人有能力研发、创新、解决目前尚未解决的现实问题。这是本末倒置的奇怪现象。

演算法营队

台大资讯系资讯之芽 
热心学生自动自发举办的高中营队

演算法学术会议

SODA 
FOCS 
STOC 

CiteSeer ， CiteSeerX 
资讯学术论文的搜寻引擎，统计论文引用情形。有时可以抓到论文的电子档。

arXiv 
收集物理学、数学、计算机科学、生物学的论文草稿。
有机会可以找到一些期刊论文的草稿。

国家教育研究院：双语词彙、学术名词暨辞书资讯网 
提供英文对繁体中文的学术名词翻译。

全国科学技术名词审定委员会：术语知识服务平台 
提供英文对简体中文的学术名词翻译。

演算法书籍

演算法网站

Jeff Erickson 
演算法课程网站，有许多课程讲义。

Erik Demaine 
演算法课程网站，有许多特殊主题。

David Eppstein 
计算几何和图论。维基百科有很多内容是他写的。

GeeksforGeeks 
程式语言、数学、演算法益智问题。

Algorithms Notes 
演算法益智问题。

高中职资讯科技融入教学网 
提供很多教学 flash。

数学网站

Matrix67 
一位中国学生 Matrix67 的个人部落格，
他的专长是文史，然而他閒暇之馀也喜欢研究数理。
作者经常写下令人惊艳的数学文章！
偶尔也会谈谈有趣的演算法！
是非常值得常常去逛的网站。

Wolfram Math World 
这个网站收集了丰富的数学资料，同时也不断的收集新知放到网站上。
如果遇到了数学问题，可以到这裡查询资料。
这个网站是 Wolfram 公司制作的一个数学网站。
该公司在数学领域上有很多研究，开发了有名的 mathmatica 软体。

planetmath.org 
这个网站的目标是成为数学的百科全书。
收集了丰富的数学资料，同时也不断的收集新知放到网站上。
可以找到很多好读的数学文章。

The On-Line Encyclopedia of Integer Sequences 
这个网站含有各式各样、包罗万象的数列资讯。
你可以参考网站的操作范例，输入一串数列，就可以找到该数列的详细资料，
有名称、公式、解释、相关连结。包你看的目不暇给、眼花撩乱。
若是你遇到了莫名奇妙的数列，可以试著来这裡找找看，铁定找得到！

演算法故事书

繁：《勇闯资讯新未来：打造资讯科技的幕后英雄》
简：《奇思妙想：15 位计算机天才及其重大发现》

繁：《改变世界的九大演算法：让今日电脑无所不能的最强概念》
简：《改变未来的九大算法》

繁：《演算法统治世界》 介绍此书的广播节目 
简：《算法帝国》

Competitive Programming

Competitive Programming

“ Association for Computing Machinery (ACM) ”是一个致力于电脑科学教育的协会，出版大量的专业期刊文献，举办重大的计算机科学会议，在资讯界举足轻重、名闻遐迩。

ACM 每年度都会举办一次“ The ACM-ICPC International Collegiate Programming Contest (ACM-ICPC) ”，是一个给全世界大专院校学生参加的演算法程式设计比赛，比赛目的在于考验选手临场的演算法设计能力、程式编写能力。ACM 首先在世界各地举办初赛，再从各个赛区选拔出表现优秀的队伍，角逐世界总决赛。

ACM-ICPC 带动了演算法程式设计的风气。世界上许多大专院校的资讯系所，仿照 ACM-ICPC 的比赛模式，纷纷自行开发出即时线上比赛系统，能够自动批改、评分、计时、统计。学生不必齐聚一堂，藉由网际网路，就可以相互切磋程式设计技巧。比赛结束之后，便将比赛题目编列题库，开放线上批改程式的功能，供学生赛后练习检讨。这套系统大家普遍称呼为“Online Judge”。

从事这项活动，不仅可以熟悉程式设计、学习演算法、锻鍊智力，还可以培养自主学习与独立解题的能力──此即程式设计师的核心价值。

这项活动开始获得大家重视。产业界举行演算法竞赛，发掘优异人才；学术界开设课程，促进演算法的研究发展。由于竞赛的缘故，大家将这项活动称呼为“ Competitive Programming ”。

UVa Online Judge 工具网站

最古老、最有知名度的 Online Judge，是由西班牙知名的瓦雅多利大学“ Universidad de Valladolid (UVa) ”开发的“ UVa Online Judge ”。资源非常丰富。

Lucky 猫的 ACM 园地 、 Ruby 兔的 ACM 园地 、 Unfortunate 狗的 ACM 园地 
UVa Online Judge 题目中译！非常伟大的工作，请大家要心怀感激！

uHunt 
可以查询自己在 UVa Online Judge 的解题进度、简单题列表、世界排名等等。
另外也整理了一套题库，适合初学者循序练习。输入使用者名称就会出现。
是你不得不知道的网站！

uDebug 
提供 UVa Online Judge 题目解答的执行档，
自行输入资料，可以生成正确输出，进而测试自己的程式。

World of 7 
uHunt 站长的兄弟所制作。
整理了 UVa Online Judge 题目的解法提示、演算法动画。

Problem Classification on Spanish Archive 
题目分类。

演算法题库

UVa Online Judge 
西班牙 Valladolid 大学的 Online Judge。
是最古老也是全世界最知名的 Online Judge，题库目前约有 4000+题。
题目类型非常广泛。绝大部分的题目难度偏易，适合初学者磨练程式设计功力。

ACM-ICPC Live Archive 
专门收集 ACM-ICPC 的比赛题目，依照年份与赛区进行编目。
可惜的是题库尚未收集完整，尚待大家合力完成。

PKU JudgeOnline 
中国北京大学的 Online Judge。中国最大的 Online Judge。
题目类型偏向演算法竞赛，可以找到比赛常见题型。
好处是网路上能轻鬆找到中文的解题报告。

Timus Online Judge 
俄国 Ural 大学的 Online Judge。俄国最大的 Online Judge。
有比较进阶的演算法题目，难度偏高。

Sphere Online Judge 
波兰 Sphere 实验室建立的 Online Judge。波兰最大的 Online Judge。
会员可自创题目，题目很有特色，但是品质良莠不齐。

URI Online Judge 
巴西最大的 Online Judge。

高中生程式解题系统 ZeroJudge 
台湾高雄师大附中建立的 Online Judge。台湾最大的 Online Judge。

演算法例赛

TopCoder ， 简介 
全世界规模最大的程式竞赛网站，其中包含了演算法竞赛。

Codeforces 
俄国最大的演算法例赛。
题目较有挑战性。赛后会提供详细的题目讲评，是个自主学习的好地方！

CodeChef 
印度最大的演算法例赛。

AtCoder 
日本最大的演算法例赛。

BestCoder 
中国最大的演算法例赛。由中国杭州电子科技大学维护。

ITSA & PTC 线上程式设计竞赛 
台湾最大的演算法例赛。台湾教育部提供的例行赛事。

演算法面试考题

leetcode 
世界知名的演算法面试考题网站。
想要省时省力的面试主考官从裡面挑题目，
于是求职者不得不去练习这些题目。
然而工作上用不到这些知识，已经发展到了病态的地步。

PAT 计算机程序设计能力考试 
中国的证照考试。

CPE 大学程式能力检定 
台湾某些教授联手搞出来的证照考试，你懂的。

演算法竞赛

2016TW 、 2015TW 、 2014TW	ACM International Collegiate Programming Contest 缩写：ACM-ICPC 对象：大专院校学生 　　　（学士班一年级至硕士班一年级） 时间：台湾站 11～12 月 　　　亚洲各站是 8～12 月 　　　世界总决赛是隔年 5～7 月 主办：Association for Computing Machinery 承办：台湾赛区由台湾大专院校轮流承办
	ACM SIGMOD Programming Contest 对象：大专院校学生 时期：2～4 月
	Google Code Jam 对象：社会大众 时期：4 月～7 月
	TopCoder Open 对象：社会大众 时期：4 月～8 月 比赛项目相当多元，其中一个项目是演算法竞赛。
	Facebook Hacker Cup 对象：社会大众 时期：1 月～3 月
Taipei	HP CodeWars 对象：高中学生、大专院校学生，各分公司就地举办 时期：台北 4 月
	Internet Problem Solving Contest 对象：社会大众 时期：5～6 月
NCPC 2016 、 2015 、 2014	全国大专电脑软体设计竞赛 缩写：NCPC 对象：台湾大专院校学生 时间：9～10 月 主办：教育部 承办：由台湾师范大学与中山大学轮流办理
NCPU 2016 、 2015 、 2014	全国私立大专院校程式竞赛 缩写：NCPU 对象：台湾私立大专院校学生 时间：6 月 主办：各私立大学轮流办理 备注：ICPC 台湾站衍生赛事
NCTU 2016	全国科技大专院校程式竞赛 缩写：NCTU 对象：台湾科技大专院校学生 时间：6 月 主办：各科技大学轮流办理 备注：ICPC 台湾站衍生赛事
NPSC	网际网路程式设计全国大赛 缩写：NPSC 对象：台湾高中学生、国中学生 时期：11～12 月 主办：科技部 承办：台湾大学

ACM International Collegiate Programming Contest

资讯界规模最大、历史最悠久的竞赛，最近几届竞赛皆有上千所学校、数万名选手参加。

ACM-ICPC 是一个气氛相当活泼，非常具有特色的竞赛。一场 ACM-ICPC 的赛事，由许多活动所组成，主轴当然是现场上机竞赛，另外还有安排晚餐宴会、娱乐表演、城市游览等行程。整个赛程为期两至三天，过程有吃有玩，游乐的成分比竞赛的成分还多，对于参赛选手来说是相当新鲜的体验。活动细节请参考历年的 ACM-ICPC 区域赛网站。

ACM-ICPC 的竞赛方式是三人一队，并且要有一位同校教授作为领队教练。教练的主要作用，是负责向大会接洽赛事行程，替选手打点赛事期间的生活细节，让选手无后顾之忧，得以倾尽全力比赛，教练就如同经纪人的角色。另外，报名时可以额外登记一名后备队员，发生紧急状况时得替补上阵。

现场上机竞赛的过程，是所有队伍聚集于会场，一支队伍分配一张桌子、三张椅子、一台电脑、一份英文题本。开赛后所有队伍同时开始作答，选手必须迅速调校好电脑环境，然后编写程式解决问题，将程式码上传给裁判批改。

所有作答皆是即时批改，几分钟内回覆结果，结果只有对与错两大类，答错还可以再答。成绩的计算方式，是以答对题数作为主要的排名依据；但是作答的错误次数、上传答案的时刻，统统列入扣分，最后作为次要的排名依据。因此选手除了要尽力答出问题，也要尽快答出问题，还要尽量避免答错问题又一错再错。实力在伯仲之间的队伍，胜负的差距往往取决于审题与答题的效率。动作慢人一步，或者大意发生失误，就很可能名落千丈。

选手有五小时时间，要解出十道左右的演算法问题，期间可以喝水、外出上厕所、享用大会提供的奢华点心、在题本上涂鸦、把题本拆了摺纸鹤、睡觉、谈情说爱、玩电脑游戏；唯一的限制，就是不得与队伍之外的人交流。

比赛规则看似轻佻，但是事实上，五小时时间解十道左右的题目，电脑却只有一台，所以比赛过程是非常紧迫的，就算是技艺高超的选手，也几乎无暇休息，必须分工合作、争取时间。通常是一人随时坐在电脑前作答，充分运用电脑，发挥时效；另外两人则在旁解读其馀题目，在脑中罗织解法，伺机轮换上阵。五小时的比赛过程，选手克服环境限制、调适心理压力、发挥大脑潜能，也可以说是一场精神的对抗赛。

至于教练必须在会场外等待，不得与选手交谈。不过教练们可以彼此交流，也可以观战和吃点心。现场上机竞赛可以说是教练在整个赛程当中最轻鬆的时刻，也是辛苦之后验收成果的时刻。

现场上机竞赛还有许许多多的有趣的地方，此处只做初步介绍，详细过程留给各位选手们自行体验吧！

历年比赛题目： ACM-ICPC Live Archive 
ACM-ICPC 官方消息： https://www.facebook.com/ICPCNews 
ACM-ICPC 亚洲区指导员： 西杰的博客与阿雄 
台湾 ACM-ICPC 非官方协会： ACM-ICPC Contest Council for Taiwan 
中国 ACM-ICPC 非官方协会： ACM-ICPC 中国区竞赛指导委员会 
中国非官方消息： ACM/ICPC 信息站 
日本非官方消息： ACM-ICPC Japanese Alumni Group 
教练感想： 2016 ACM-ICPC World Finals — MZ’s log 

根据规定，ACM-ICPC 区域赛必须要有全国性（或者两省以上）的预赛。台湾历年都是以 NCPC 作为预赛，然而实际上 NCPC 根本就不是预赛。会有这种现象，主要原因是台湾的参赛队伍十分稀少，无从筛选队伍。直至 2015 年，台湾才开始正式举办网路预赛，跟随亚洲各国的比赛模式，时序如下：

一、区域预赛（网路赛）：由 ACM-ICPC 台湾区负责人负责组织比赛，各大专院校教授热情协助。国内外选手透过网路比赛，最后根据当年承办人员的战斗力，从中选出 40 至 80 队，参加现场赛。由于国外队伍出国参加现场赛，需要时间打点准备，所以网路赛往往很早举办，3 至 6 个月前就会举办。

二、全国赛：与 ACM-ICPC 无关。台湾教育部举办的 NCPC，全国学生一较高下。成绩优秀的队伍，教育部全额补助参加 ACM-ICPC。

三、区域正式赛（现场赛）：请参考前面介绍的内容，国内外选手齐聚一堂进行较量。最后依照複杂的公式和规则，评量各个区域的战斗力之后，从各赛区选出至少 1 队，参加世界总决赛。

四、世界总决赛：每年都从世界五大洲轮流选择一间学校，作为主办学校；从全世界筛选一百多队参加总决赛。以往台湾大专院校实力较差，总是被国外学校痛宰，鲜少晋级总决赛。直到近年才有改善迹象，与国外学校互有进退（一群无名英雄前仆后继苦心经营数年的成果）；同时也积极的参与其他国家的区域赛，争取其他赛区的总决赛门票。目前台湾仅台湾大学、交通大学有能力进入总决赛。

营队

台湾大学程式解题竞赛培训营 
热心学生自动自发努力办理的营队。

交大竞技程式训练冬令营、夏令营 
热心老师和学生自动自发努力办理的营队。

讲义

台大资讯系资讯之芽算法班 
热心学生自动自发举办的高中营队以及教材。

板桥高中资讯社演算法讲义 
热心学生自动自发努力彙整的教材。

建国中学资讯科培训讲义 
热心学生自动自发努力彙整的教材。

交通大学 PSPT 课程讲义 
热心老师自动自发努力彙整的教材。

Stanford CS 97SI: Introduction to Competitive Programming Contests 
Stanford 大学开设的课程。

竞程日志 
热心网友的解题心得分享

资料结构与演算法/leetcode/lintcode 题解 
面试题目教学。

书籍

	Discrete Mathematics and Its Applications Kenneth Rosen McGraw-Hill 离散数学，资工系用书，演算法的数学知识。 此书含有许多程式解题的基础概念。 细读此书，对程式解题有一定帮助。 此书有繁体中文译本。
	数学思考 台北市建国高中第 49 届 314 班合译 九章出版社 很有趣的数学书籍，教导如何解决数学问题。 书中提到的思考方式，其实和程式解题是相通的。 这本书由《Thinking Mathematically》改著， 原书作者为 John Mason。
	How to Solve It G. Pólya Princeton University Press 经典的数学教育著作。 这本书有繁体中文译本《怎样解题》。
	名题精选百则:技巧篇 冼镜光 儒林出版社 收集程式设计的经典问题， 而且这些问题不会用到特殊的资料结构与演算法。 题目大多小巧精緻，非常具有启发性。
	Cracking the Coding Interview Gayle Laakmann McDowell CareerCup 收集面试问题， 其中包含许多演算法益智问题！ 这本书有繁体中文译本 《来自程式的试鍊： 专为程式开发人员所写的技术面试完全攻略》。
	Competitive Programming Steven Halim, Felix Halim Lulu 世界上第一本演算法竞赛教科书！ 详细介绍竞赛常用演算法， 精心挑选大量 UVa Online Judge 练习题， 配有追踪解题进度的网站 UVa Hunting， 规划相当完善的教材。
	프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 구종만 인사이트 将演算法竞赛的所有经典主题分门别类， 依照学习顺序编排例题，仔细说明解题思路。 这本书有简体中文译本《算法问题实战策略》。
	プログラミングコンテストチャレンジブック 秋叶拓哉、岩田阳一、北川宜稔 マイナビ 选录大量题目，以题目为主角，介绍各种演算法。 这本书有繁体中文译本 《培养与锻鍊程式设计的逻辑脑： 世界级程式设计大赛的知识、心得与解题分享》。
	算法竞赛入门经典 刘汝佳 清华大学出版社 算法竞赛入门经典——训练指南 刘汝佳、陈锋 清华大学出版社 http://code.google.com/p/aoapc-book/ 这是一套系列作，目前只出版两本。 知识水平是所有书籍之中最高的。 想要跻身高手行列的人，绝对不要错过此系列作。 第一本书有繁体中文译本 《打下好基础：程式设计与演算法竞赛入门经典》。 第二本书有繁体中文译本 《提升程式设计的解题思考力─ 国际演算法程式设计竞赛训练指南》。

Computer Science

国内的资讯工程系学些什麽？

计算机的学问，分成计算机工程（Computer Engineering）与计算机科学（Computer Science）两大系列。

计算机工程。制造电脑、操控电脑的学问（台湾把计算机翻译成电脑）。制造电脑的部分，属于电机系的专业；操控电脑的部分，属于资工系的专业。在国外，有些学校乾脆把电机系和资工系合在一起，让整件事情完美圆满。下面列出国内资工系应该学得到的计算机工程课程：

电子学：讨论电流与电子元件的行为。
数位逻辑：操控电流与电子元件的行为，并且赋予意义。
微处理机：讨论中央处理器。等登等登。
计算机组织与结构：讨论电脑如何组成、如何运作，讨论电脑的零件。
组合语言：操控电脑的指令。
程式设计：程式语言也是操控电脑的指令，设计成稍微贴近人类思惟。通常学 C 或 C++。
编译器：如何把程式码变成操控电脑的指令。
系统程式：发挥电脑零件功能的程式，让电脑执行特定作业。
作业系统：人与电脑的介面，让使用者便于执行系统程式。
资料库：电脑结合储存设备，用来记录。
计算机网路：电脑结合网路设备，用来通讯。
分散式系统：电脑结合网路设备、储存设备，用来分工合作。
嵌入式系统：电脑结合其他机械，有著各种功能。
程式语言：如何设计程式语言，方便人类撰写、方便电脑作业。
软体工程：程式员很多、程式码很长的情况，要如何应对。
人机互动：人类如何操控电脑。
普适计算：电脑与这个世界如何相互依存。

计算机科学。运用电脑实施计算、达成任务的学问。电脑是计算机，只会算数学，因此计算机科学皆是数学。计算机科学是资工系学生必备的基础理论，是计算机的深奥之处。事实上，计算机工程的后半课程，就需要计算机科学的知识作为辅助。下面列出国内资工系应该学得到的计算机科学课程：

资料结构：电脑实施计算时、储存资料的方法。
演算法：电脑计算的方法。
平行处理：许多台电脑一起计算的方法。
自动机理论：讨论电脑的计算模式，用数学表达。
计算理论：讨论电脑的计算能力，用数学表达。
字串学：连成一串的文字（数列）的数学知识，著重比对。
数位讯号处理：连成一串的数列的数学知识，著重转化。
密码学：改变资料外观的数学知识。
资讯理论：资料本身的数学知识。entropy！
编码理论：压缩资料的数学知识。用到资讯理论。
模式识别：比对资料的数学知识。
机器学习：分析资料的数学知识。用到模式识别。
人工智慧：搜寻资料的数学知识。用到机器学习。

紧接著列出计算机科学的实际应用课程。通常会在大四、研究所开课，通常只能学到皮毛；若要有所小成，就必须加入相对应的实验室，认真做研究：

资料探勘：用数学解析、转化数值资料。
自然语言处理：用数学解析、转化文字资料。
语音处理：用数学解析、转化声音资料。
图像处理：用数学解析、转化图片资料。
影像处理：用数学解析、转化影片资料。
计算机图学：用数学制造图片、影片。
计算机视觉：用数学辨识图片、影片。
几何模型：用数学解析、转化物体资料。
数值方法：用电脑计算数学方程式。
计算几何：用电脑计算数学几何。
计算物理：用电脑解决物理问题。
计算化学：用电脑解决化学问题。
生物资讯：用电脑解决生物学问题。
医学资讯：用电脑解决医学问题。
机器人学：上述所有东西加上机械设备，计算机工程与计算机科学集大成。

另外还有一些数学课程。计算机科学的各个应用领域都会用到数学，因此数学课程通常在大一、大二就会用力教完。虽说是数学，但是资工系与数学系的学习方向有著极大差异──资工系属于实务导向，所以没有太多晦涩的内容，也不需要推导定理，只要懂得原理、懂得运用就可以了，内容反而比数学系有趣。下面列出国内资工系的基础数学课程：

线性代数、机率论、离散数学。

另一方面还有理工科系的共同课程：微积分、工程数学。微积分就不讨论了，总是有人认为有用、有人认为没用，各人心裡有底。至于工程数学，计算机科学用不到，计算机工程用得比较多，尤其是在制造电脑、操控机械方面。

还有一些其他的数学，计算机科学有时候会用到，像是统计学、随机过程、赛局理论、图论、组合最佳化、数论等等。有些课程资工系没有开课，电机系、数学系才有开课。

国外的计算机科学系学些什麽？

国外大学的课程更加丰富细腻！请大家看看 UIUC 和 UCSD 这两间大学的课程总表：

https://cs.illinois.edu/courses/full-curriculum

http://ucsd.edu/catalog/courses/CSE.html

这两间大学的计算机科学系乐于分享教材，绝大部分课程都公开了课程讲义。大家可以透过网路自主学习：将课名代号、课名全名，放到 Google 搜寻，马上就能找到课程讲义。有时候则是要搜寻开课教授的姓名，从教授的个人网页找到课程网站连结。

课程总表实在太笼统。有人依照工作性质，将课程归类。

http://www.computerscienceonline.org/courses/

除了学校的正规课程，也有网路的影音课程。诸如 Coursera、Udacity、edX，都有计算机科学的课程。课程种类正在持续增加当中，大家可以一睹国外教授的风采。

https://www.coursera.org/browse/computer-science

如果还不过瘾，那麽还可以找 QS 世界大学排名，找前 100 大计算机科学系，再用 Google 搜寻这些学校的课程。

http://www.topuniversities.com/university-rankings/university-subject-rankings/2016/computer-science-information-systems

世界上还有许多比台清交更优秀的学校。打开心胸放眼全世界，不要自我设限，相信大家会有更多的收穫。

资讯工程系

资讯工程不是主流词彙。从字面上来看，意思是处理资料的工程──架设一些电脑设备、运用一些计算机科学，来处理资料这样。

资讯工程系是非常奇怪的系名。国外大学的计算机科学系所，系名都没有包含资讯工程的字眼。在台湾，资讯工程系的英文系名是 Department of Computer Science and Information Engineering，直接翻译是“计算机科学与资讯工程系”，故意在计算机科学的后方添上了资讯工程，而且只取资讯工程的部分当成了中文系名。我不清楚这种乱象是如何产生的，或许是当时某些老人家想要譁众取宠、追逐潮流，因此更改系名，欺骗学生就读、保全自己地位。各位可以参考台湾交通大学资讯工程系的改名历程：

https://www.cs.nctu.edu.tw/cswebsite/intro/history

国内计算机科学发展

台湾政府接受美援，引进国外设备，建造电子工厂、电脑工厂。台湾政府指派党政军人士前往海外观摩，回国后设立研究院和大学，担任校长和教授，督促学生解读技术原理、创业开工厂。因此台湾并未发展计算机科学。

以学界而言，许多大学教授的水准，不如自学的中学生。比如 引入计算机科学的先驱，只写得出虚有其表的烂教材 。资工系毕业生，一个班级只有两三人学会写程式。

以业界而言，只要去 补习班 接受短期训练，就能写程式，完全不必经过资工系的专业训练。程式员如同临时工，花钱请就有，人力流动相当频繁。大部份公司都没有完善的专案管理机制，修改规格、程式出错、加班工作是家常便饭。

在台湾，光是学会写程式，就是个大问题，更遑论计算机科学。如果你对计算机科学有兴趣，就必须自立自强，学校教育帮不了你。

国外计算机科学发展

请参考 维基百科 以及 谷歌搜寻结果 。