Home

从分治策略到动态规划,再到贪心算法

引言 分治, 动态规划和贪心算法, 是算法设计中非常重要的三种思想, 它们各不相同, 却又息息相关. 本文会介绍三种思想之间的共同点和不同之处, 并且列举一些典型算法的例子, 试图探索算法设计的一般思路. 分治策略 我们先来看比较熟悉的快速排序. 快速排序是一个非常典型的分治策略算法. 它采取的方法是把数组中的某一个数移动到数组中的某一个位置, 使得它前面的数都小于它, 它后面的数都大于它. 然后, 对前面的数组和后面的数组做同样的操作. 直到数组全部有序. 下面是快速排序的代码 function qsort(a, l, r) if l >= r then return end local x = a[r] local p = l - 1 ...

Read more

避免使用无符号数

考察这样一段代码: int a = -1; unsigned int b = 1; if (a < b) printf("a < b\n"); else printf("a > b\n"); a是有符号整数,b是无符号整数。C语言在比较他们的大小时会进行隐式类型转换。如果执行的是 if ((unsigned int)a < b) 则-1被转换成4294967295,结果是 a > b;如果执行的是 if (a < (int)b) 则结果是 a < b。采取哪种方式依赖于编译器。 在g++中,输出的结果是a > b。当然,也会打出警告:warning: comparison between signed and u...

Read more