数学和计算机科学板块_辛酸网

数据结构与算法20

  如何计算指数很大的整数幂？例如a⁵⁰，如果我们只是从乘法单位元开始一个一个乘， 那么做乘的动作就有50次，从a开始就49次。但是我们知道指数的相乘就是幂的乘方，既然a⁵⁰=a^25×2=(a²⁵)²， 那就可以先算a²⁵，再平方一下，如此就只需26次乘法。所以我们还能更进一步地拆分下去： a²⁵=(a¹²)²×a，a¹²=(a⁶)²， a⁶=(a³)²，a³=a²×a。 至此递归到底了，我们看一下整个的指数的演变过程：50→25→12→6→3→2。 显然，对于指数很大的整数幂，我们可以每次将指数除以2向下取整，计算这个指数只有一半的幂，然后平方。 如果是指数原本是奇数，就要多做一次乘法，偶数则只是平方。

  以对整数的整数次幂为例，代码如下：

int quickpower(int a,int b){
	if(b==1)return a;
	else if(b==2)return a*a;
	else if(b==3):return a*a*a;//递归奠基
	else{//之所以是m*m而非quickpower(a,b/2)*quickpower(a,b/2)是为了少一次函数调用的时间，真正让一次函数级的时间复杂度降为对数级
	if(b%2==0){int m=quickpower(a,b/2);return m*m;}//偶数则指数除以2，平方
	else{int m=quickpower(a,b/2);return m*m*a;}//奇数则多一个乘法	}
}

  不管是什么样的乘法群都如此，包括矩阵，在矩阵乘法中还可以用前文提到过的斯特森方法。 在模乘群中，每次乘完了以后还有一次取余操作。

   对于矩阵A=$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$，平方，可得A²=$\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$。

  立方，可得A³=$\left[\begin{array}{cc}3& 2\\ 2& 1\end{array}\right]$。

  接着，是A⁴=$\left[\begin{array}{cc}5& 3\\ 3& 2\end{array}\right]$……

  在这个矩阵的乘方中，观察左上角的数字，设其为f(n)，其中n为指数。 因为A的第一行都是1，所以f(n)等于上一个乘方结果的第一列相加。在上一个乘方结果的第一列里，左上角是f(n-1)。 而A的第二行是[1 0]，故第n次的乘方结果的左下角刚好等于上一次乘方结果的左上角，也就是f(n-1)。 同理，在上一个乘方结果里的左下角就是上上次的左上角，也就是f(n-2)。

  因此，第n轮乘方结果的左上角，等于第(n-1)轮乘方结果的左上角和左下角相加，而第(n-1)轮乘方结果的左上角为f(n-1)，左下角是f(n-2)，故f(n)=f(n-1)+f(n-2)。观察起始的左上角和左下角都是1，相加得2，满足斐波那契数列的定义。 所以我们可以用A的乘方来计算斐波那契数列，Aⁿ的左上角就是斐波那契数列里的第(n+1)个数。

  用矩阵$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$求斐波那契数列的代码这里就省略了。反正其所需要的快速幂指数算法和斯特森矩阵乘法前面已讲过。

  贪心，目光短浅之意。贪心算法是指：当一个问题的解分为多个步骤时，就一步一步走，每一步都把当前的局部最优解求出来，然后把每一步各自的最优解合成整体的解。 迪杰斯特拉算法是典型的贪心算法。但要注意：绝大多数情况下贪心算法求出来的解都不是整体的最优解而仅仅是局部最优解，甚至是错的。迪杰斯特拉算法是少数能求出正确答案的贪心策略。

  在求多元函数的最值时，一种简单的方法是最小梯度法：从起点开始走，每次选取梯度最大的方向往那里走，一步步走下去，直到周围所有方向的梯度都小于等于0为止，此时的位置上函数值就取得了一个极大值； 每次选梯度最小的方向走，直到周围所有方向的梯度都大于等于0时，可得极小值。 最典型的应用就是爬山，每次取最陡峭的方向向上走能到山顶，向下可达山底。最小梯度法也是典型的贪心算法，然而，它却不能保证得到整体最优解，事实上一般来说得到的都是局部最优解。 就比如在爬山的时候，不同的地方山的高度不同，当你用这种方式爬到一处山顶时，抬头，你才会发觉虽然和邻域一比此处最高，但往远了看却很可能不是最高的地方。 它只能让你爬到一处山顶，却不能保证这是最高的山顶。要爬到最高山顶还得用遗传算法和蚁群算法等模拟类算法。

  所以求可导函数最值，往往是求导使其导数为0，然后从二阶导数是否大于0来判定。 一元函数看二阶导数是直接判断的，多元函数则是要看二阶导数的矩阵是不是正定矩阵，这就涉及到二次型了。

  已知有这样一个背包，内含S的空间，还有n种东西，每种东西的单价和数量都不一样。 问：从所有东西里面挑选哪几种，分别放多少，可以在背包放得下的情况下使得整体能带走的东西价格最大？这个就是连续背包问题。

  该问题的最大特点是：要放的东西之数量是连续的，也就是允许任意切割的。 这就意味着，我们可以把高价的东西一股脑地放进去，而且是尽可能多放，如果高价的东西放不下了，我们再放低价的也不亏。 考虑背包空间中的一个微分dS及其所带有的价格微分dV，显然，同样的空间，带有的价格越大越好。 那么我们就得考虑$\frac{\mathrm{dS}}{\mathrm{dV}}$是大是小。由此我们可以看出一个简单、朴素但确实有用的办法：

  1.对所有的东西按照单价从高到低排序
  2.把最贵的东西先放进去，如果还有剩余空间就放第二贵的，以此类推，直到背包被塞满为止。

连续背包长这样，只要东西够多最优解一定是把背包装满的，离散背包就不一定啦。

辛酸网 ©版权所有