本文为"Algorithms"一书的笔记 fibonacci 书上给出了另外一种我想不到的解法： #include <stdio.h> #define MAXN 100 int fib[MAXN]; int get_fib(int num); int main(int argc, char *argv[]) { printf("%d\n", get_fib(10)); return 0; } int get_fib(int num) { int i; fib[0] = 0; fib[1] ...

最近在看快速求fibonaci数列的方法，需要用到快速求幂法，于是参考了这篇文章 ， 做下笔记。 最直观的方法 如果叫我求一个整数的n次幂，我要么用pow，要么写个循环直接相乘。 比如要求： 5 ^ 55 的结果，很明显，要进行54次乘法。要知道，在目前的计算机体系架构中，乘法的计算 是非常慢的。 效率高的求法 有的聪明人（不是我）就想到了减少乘法次数的方法： 5 ^ 2 = 5 * 5 5 ^ 4 = (5 ^ 2) * (5 ^ 2) 5 ^ 8 = (5 ^ 4) * (5 ^ 4) 5 ^ 16 = (5 ^ 8) * (5 ^ 8) 5 ^ 32 = (5 ^ 16) * (5 ^...

动机 看了一本叫做《C/C++面试题》的电子书，里面提到找子字符串的算法，最好的是KMP， 于是开始了KMP之旅！ 在网上看了好几篇中文文章，没一篇看得懂，最后找到了2篇英文文章，深有启发： searching-for-patterns-set-2-kmp-algorithm the-knuth-morris-pratt-algorithm-in-my-own-words 特别是第2篇，让我深刻理解了KMP中的预处理，而第1篇则让我学会了如何用高效的方法 实现预处理。 于是，我也来写一篇文章，用自己的理解来实现KMP算法。 在哪里优化？ 如果要让我写一个程序来找到子串，唯一能想到的方法就是...

基本代数 加法 十进制有一个很傻逼但是很有趣的性质： 任意3个个位数相加的和最多是两位数 事实上，对于任意进制，都有这个性质。 另外一个很有用的性质： 对于一个基数为b的k位数，它能表示的最大数为$b^{k^ {-1}}$ 想要知道一个基数为b的数有多少位k，则： $ k = log_b(N + 1) $ 乘法和除法 这里出现了一种神奇的乘法算法，对于计算机来说效率非常高， 引用wikipedia 的例子： Decimal: Binary: 11 3 1011 11 5 6 101 110 2 12 10 1100 #w...

There is an interview problem. Given a string without duplicate characters, return all permutations of the string. First Try The straightforward idea is using recursive algorithms. We enum all characters for the first position and concatate the permutations of the rest substring. However, the speed ...