Question

阳春召我以烟景，大块假我以文章。《李白．春夜宴桃李园序》

Simulation

撰写程式，模拟行为。没有前例，那就创例。

范例：印出直角三角形

不加思索，穷举试误。

Modeling

前事不忘，后事之师。《战国策》

Modeling

把问题对应到耳熟能详的模型，套用既有模型解决新问题。

范例：平行四边形面积

小学数学老师教过：长方形的面积是“长乘宽”。儘管不知道原因，不过这个公式肯定是正确的。那麽，请问平行四边形面积如何计算？

把平行四边形凸出的三角形切下来，补在另一边，平行四边形就变成了长方形。想要计算平行四边形面积，可以直接套用长方形面积公式。

平行四边形的底，就是长方形的长；平行四边形的高，就是长方形的宽。平行四边形的元件，一一对应到长方形。

范例：约瑟夫问题（Josephus Problem）

8 个人围成一圈，现在从第一个人开始报数，数到第 5 人时，就杀死这第 5 人；然后从被杀的下一位继续重新报数，数到第 5 人时，就杀死这第 5 人。如此不断数 5 人、杀此人，直到最后会剩下一个人，请问他是谁？

数人和杀人的动作可以对应到伫列（queue）的操作。首先把每个人依序放进伫列，接著连续 pop 和 push 4 人，接著 pop 第 5 人时，不要将他放回伫列裡面即可！

范例：用图论作为模型，模拟小画家倒墨水。

图论的观点之下，Flood Fill Algorithm 其实就是运用 Depth-first Search 找到 Connected Component。

范例：System of Difference Constraints in Linear Programming

问题：给定变数 x1 到 xN，并给定一些 xi-xj≤c 的式子，作为条件限制。请判断有没有解，如果有解就求出其中一组解。

这个问题可以巧妙的转换成最短路径问题。x1 到 xN 看作是图上的 N 个点，一条 xi-xj≤c 的限制式子看作是一条 xj 到 xi 的边，其权重是 c。

如果无解，那麽图上有负环。如果有解，那麽图上各点的最短路径长度就是其中一组解。为了让图上各点都有最短路径长度值，可参考 Johnson's Algorithm 的做法。

UVa 515 ICPC 2058

范例：Sentiment Relation in Social Balance Theory

从前有一位心理学者认为，人与人之间的关係，可以粗略分为两种：互相喜欢、互相讨厌。这种关係称作 Sentiment Relation，是一种双向关係，而且拥有喜欢与讨厌两种类型。假使两人之间好恶分明，没有亦敌亦友的情况，就会形成 Sentiment Relation。

   like            hate
A<------>B      A<------>B

另外 Sentiment Relation 还具有相当特殊的性质，有点像是 transitivity、symmetry、antisymmetry 的总合。这种性质的最佳写照，诸如同仇敌忾、合纵连横等等，翻成白话就是这样：

1. 朋友的朋友就是我的朋友。
2. 朋友的敌人就是我的敌人。
3. 敌人的朋友就是我的敌人。
4. 敌人的敌人就是我的朋友。

在 Sentiment Relation 所形成的社交结构当中，如果产生了好与恶的矛盾，那麽这样的社交结构就是不平衡的；如果好与恶合理，那麽这样的社交结构就是平衡的。心理学者相信，当社交结构不平衡的时候，个体会尝试改变自己的观点，让社交结构趋向平衡。

balance:

      A                A           like   like
like / \ like    hate / \ hate      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     like             like         hate   hate
 
imbalance:

      A                A           like   like
hate / \ hate    like / \ like      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     hate             hate         like   like

后来心理学者进一步发现，当社交结构达到平衡，所有人可以分成两大阵营，使得阵营内部的关係都是互相喜欢，阵营与阵营之间的关係都是互相讨厌。

说了这麽多终于要提到重点。现在问题来了，假设社交结构是平衡的，而我们也知道一些两两相互喜欢、相互讨厌的资讯时，我们该如何确认谁在同一阵营、谁在不同阵营呢？

一、以 Bipartite Graph 作为模型：

把社交结构看作是 Bipartite Graph，Bipartite Graph 的两侧分别是两大阵营。首先利用 Graph Traversal 走访喜欢的边，找出所有连通分量，并各自缩成一点。然后再度利用 Graph Traversal 走访讨厌的边，尝试建立 Bipartite Graph，如果无法建立则表示社交结构不平衡。

二、以联集为基础来建立新模型：

当 x 与 y 是朋友：
　x 及朋友、y 及朋友，都是好朋友。
　x 的敌人、y 的敌人，都是好朋友。

当 x 与 y 是敌人：
　x 及朋友、y 的敌人，都是好朋友。
　x 的敌人、y 及朋友，都是好朋友。

用 Disjoint Sets 的 union，把好朋友们联集在一起。要判断同一阵营，就看看大家是不是同一群好朋友；要判断不同阵营，就看看对方的敌人是不是跟自己是同一群好朋友。由于一开始每个人都没有敌人，所以替每个人都设定一个虚拟的假想敌。

Programming: Array Indexing

Array Indexing

“索引”是电脑的绝技！一个元素存放到阵列之后，不论是在阵列的哪个地方，只要利用索引值（index），就能一瞬间找到元素。大多数的演算法都运用了“索引”的技巧，让程式执行速度更快。

以下介绍索引的常见运用方式。

一、定位

将物件放入阵列中，array[位置] = 物件。

当元素很多时，我们可以放到阵列裡。我们只要记录索引值，依旧可以常数时间得到元素。

范例：求最大值

将元素连续地放入阵列，若想记录一元素，仅需一索引值。

范例：求子字串

将元素连续地放入阵列，若想记录一区间，仅需头尾的索引值。

Programming: Recursion

Recursion

在函式内部呼叫原本的函式，叫做“递迴”。

递迴与迴圈一样，将一件事情重複很多次，每次都改变一点点。递迴与迴圈一样，必须设定起始条件、结束条件、改变量，以避免无穷递迴。

范例：阶乘

1 乘以 2 乘以 3……乘以 n。

范例：兔子数列

0 1 1 2 3 5 8……，求第 n 项。公式 f(n) = f(n-1) + f(n-2)。

迴圈辅以堆叠才能树状分枝。递迴可以轻易地树状分枝。

UVa 110 177 183 839

Programming: Metaprogramming

Metaprogramming

设计一支程式来制造程式码，令该程式码充分运用程式语言自身拥有的能力，轻鬆地、更有效率地完成更多事情。

范例：四则运算式

5 + 8 * (2 - 3) + 7 * -6 / (2 - 1) + 1

身经百战的演算法设计高手，必然不假思索说出：stack，把所有符号依序放入 stack，依照运算符号的优先次序 push 和 pop。听来简单，实作起来还是颇麻烦。

这裡要介绍的是更轻鬆、更强悍的方法：写程式制造一支会进行四则运算的程式。大家都知道 C/C++的语法当中，就有四则运算的语法了。现在来设计一支程式，制作出四则运算的程式码吧！

如果输入方才的四则运算式，就会产生如下程式码，档名为 temp.cpp。

然后编译 temp.cpp、执行一下，就有答案了。甚至可以把编译、执行的指令，统统写进程式码当中：

范例：quine

一支程式，其功能是输出本身程式码。纯娱乐。

Template Metaprogramming

C 有个功能叫 macro，可以代换程式码。C++有个更厉害的功能叫 template，可以代换并且递迴展开程式码。

运用 template，编译时期即可计算答案，令答案变成程式码的一部分；执行时期不必花时间计算，直接印出答案！

不过这是个怪招，平常没人这样做，大家当作娱乐看看就好。儘管在 C++裡面是怪招，但是在 Haskell 裡面却是基本功。

范例：阶乘