Note.Markdown MachineLearning Algorithm Skill Tool Other From Easy On, Just Do It

Algotithm Rel since 2012-10-10

卡特兰数(Catalan)

卡特兰数是在组合数学各种计数问题中常出现的一个数列，其前几项： 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670...

设第n个卡特兰数为，其一般项公式为：

递推关系:

还满足：

第二个递推公式提供了快速计算卡特兰数的方法，同时也揭示了卡特兰数的组成规律，这是判断一个问题是不是卡特兰数的关键！

应用：

  1. 连乘序列括号问题：如a_1 × a_2 × ... × a_n 用括号表示成对的乘积，有多少种扩括号的方案
  2. 已知进栈顺序，求出栈序列个数
  3. 将凸多边形划分为三角形，总共的方法个数
  4. n个顶点的二叉树有多少种结构

称球游戏

12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。

坏球可能是12个球中的任意一个，这就是12种可能性；而其中每种可能性下坏球可能轻也可能重。于是“坏球是哪个球，是轻是重”这个问题的答案就有12×2=24种可能性。

现在我们用天平来称球，就等同于对这24种可能性发问，由于天平的输出结果有三种“平衡、左倾、右倾”，这就相当于我们的问题有三个答案，即可以将所有的可能性切成三份，我们应当尽量让这三个分支概率均等，即平均切分所有的可能性为三等份。

如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3，三次就能缩减为1/27。而总共才有24种可能性，所以理论上是完全可以3次称出来的。

生成函数(母函数)

当物件只能使用一次是时

有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？

每个砝码都有两种状态，要和不要，用x表示砝码，其指数表示砝码重量:

4中砝码组合在一起:

指数为重量，系数为方案种类

当物件使用次数无限制时：

求用1分、2分、3分的邮票贴出不同数值的方案数

用表示i分邮票，则i分邮票的组合方案有:

三种邮票组合在一起:

同理，结果中的指数为邮票面值之和，系数则是方案数量

如何Coding

比如求1中的砝码问题，分别考虑只有1克砝码的情况，之后加上2克砝码，3克砝码，最后4克砝码

使用数组作为存储结构：数组Ａ，坐标i表示砝码的重量，A[i]表示方案个数，不断更新Ａ即可

完整代码

神奇的异或运算

异或运算(Xor)是位运算的一种，具有交换率,结合率：a^b^b = a^(b^b)= a^0= a.这些性质有两个显著应用：

两数交换

void swap(int *a, int *b){
    //当a==b时，会置零!!!
    if(a!=b){
        *a=*a^*b;
        *b=*a^*b;
        *a=*a^*b;
    }
}

找出单独的数

现在给你2n+1个正整数,其中有n对数和1个单独的数,这里规定一对数的意思是这两个数相等,然后让你设计一种算法,把这个单独的数给找出来,要求时间复杂度为O(n).

很简单,把2n+1个数全部进行异或操作,最后得到的数就是那个单独的数

如果有两个单独的数怎么处理？思路是转化为已知子问题：设两个单独的数字分别是A和B ，先做一次所有数的异或，异或结果就是A^B，设A^B中第k位是1，则可以根据数字第k位将所有的数字分成两组，这样就可以将AB分到不同的组中，之后就转化为前面的问题，更多参考

异或的另外一个神奇性质是满足消去率,即a^c = b^c ==> a==b.这个特性可以解决Nim游戏问题：

像Nim游戏这种博弈问题,最重要的是寻找必败态.这个必败态的的意思就是,这样一种局面摆在面前的话先手必败.其严格定义如下:

  1. 无法进行任何移动的局面是必败态；
  2. 可以移动到必败态的局面是非必败态；
  3. 在必败态做的所有操作的结果都是非必败态.

就是自己处在非必败态上总能移动到必败态把必败态留给对方,而对方处在必败态的话总是只能移动到非必败态,把非必败态留给自己,然后自己继续虐对方.

而对于Nim游戏,局面是必败态当且仅当所有堆硬币的数量都异或起来结果为0,即a1^a2^…^an=0,我们只要证明它满足上述必败态的三条性质即可.

  1. 第一个命题显然,最终局面只有一个,就是全0,异或仍然是0.
  2. 第二个命题,对于某个局面(a1,a2,…,an),若a1^a2^…^an!=0,一定存在某个合法的移动,将ai改变成ai’后满足a1^a2^…^ai’^…^an=0.不妨设a1^a2^…^an=k,则一定存在某个ai,它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）.这时ai^k<ai一定成立.则我们可以将ai改变成ai’=ai^k,此时a1^a2^…^ai’^…^an=a1^a2^…^an^k=0.

  3. 第三个命题,对于某个局面(a1,a2,…,an),若a1^a2^…^an=0,一定不存在某个合法的移动,将ai改变成ai’后满足a1^a2^…^ai’^…^an=0.因为异或运算满足消去率,由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’.所以将ai改变成ai’不是一个合法的移动.证毕.

  4. 参考: Nim游戏的必胜策略和Xor运算的神奇应用

找寻最大循环周期

HDU1021 Fibonacci Again
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2). Judge if 3 divide evenly into F(n).

这道题目输出前20个结果就能总结出规律,但是可以从理论上证明这个结果序列是循环的,而且可以确定最大循环的周期,考虑到两点：
* 每个数字由前两个决定,也就是说两个连续的数字重复后,就会出现循环（Fabonacci的重要规律） * 被3整除,使得每个结果只有0,1,2三种可能,连续两个结果的组合有3*3=9中组合,所以循环周期最大为9

这个貌似可以考虑计算理论中的有限状态机原理…

预测分支

Consider an if-statement, at the processor level, there is a branch prediction problem

read-more

Basic

  1. input
    • while(scanf(“%s%s”, &str1, &str2)!=EOF)…
    • char buf[20]; gets(buf)
    • char a = getchar()
  2. output
    • printf(“%d\n”,res)
    • printf non-cached output
  3. misc…
    • __int64–long long
    • sprintf(str, “%d”, num)
    • int main()…
TOP