算法学习：分治法的其他例子

今天也是挺多事的一天，主要的生活重心集中在编程与游戏上
编程上努力学习算法以及Javascript，把博客搞得更好看更有料
游戏最近很被崩坏三的剧情吸引，时间就上去了。

今天博客本来想要试试butterfly主题的，开了一天，实在是太多Bug
我这才想起之前删掉这个主题包的缘由。
_config.yml文件是真的有点烦人，
改了一大通，但是因为其他主题文件中的问题以及node的很多问题
CSS渲染不出来，改了全没用，一点不带变的。

而且网上再怎么搜都是魔改教程，就有点，反衬。害。。

另外将之前学习的斐波那契数列的输出方式以及pow函数的正数部分给写完了。
想不到斐波那契数列还有这么多方式来输出，而且还与矩阵有关系。
但矩阵这个算法因为牵扯到浮点数与黄金比，在计算机上实现不了。
现在暂时就是中午想出来的递归以及线性版本。

1.Pow函数(半成品)

虽然Pow函数在C语言里可以直接用，
在其他语言中也有对乘n次方的表示
但是它的算法是确实可以优化的。

说到乘方，我们一般会直接使用一个n次的循环来对基数乘n次方。
也就是下面的写法：

1
2
3
4
5
6
7
8

long long ntimesa_naive(int a, int n)
{
    long long time = n;
    a -= 1; //如果0到a的话实际是a+1次。
    while(a--)
        n *= time;
    return n;
}

但是，实际上我们可以将这个O(n)的算法进行改进，
因为有一些计算的过程其实是可以省去的。

还是以分治法的思路，我们可以将这个问题的规模降到n/2或更小吗？
答案是肯定的。具体就是下面的式子了。

如果次数n为偶数，那么就等于n/2次乘n/2次
如果次数n为奇数，那么就直接使用上方的算法运算即可。

如此就可以使用递归的方式实现了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

long long ntimesa_recursion(int a, int n)
{
    long long time = n;
    if(n == 0) return 0;
    else if(a % 2 == 0)
        return ntimesa_recursion(a / 2, n) * ntimesa_recursion(a / 2, n);
    else
    {
        if(a == 1) return n;
        else 
        {
            a -= 1;
            while(a--)
                n *= time;
            return n;
        }
    }
}

这个函数还需要进一步的完善，因为之前试着实现了一下负数的部分。
发现在应对leetcode的题目的时候还是会时间超限。
我感觉有些数应该对基数讨论，这样应该会更好一些。
比如算1的2147932478(Whatever)次方，结果是1.

今天试着进一步实现一下吧。

2.斐波那契数列

1.定义递归法

• 算法展示
  我们都已经知道这个数列是如何递推出来的了。
  也就是这个式子 F(n) = F(n - 1) + F(n - 2)
  现在只需要将这个式子补充一些条件其实就可以直接使用了。
  首先得知道第一项0与第二项1，
  这样第三项及之后的项才能够推出来。
  这样我们也就可以开写了。

• 代码展示

  1 2 3 4 5 6

  COPY int Fibonacci_Recursion(int n) {     if(n == 0) return 0;     else if(n == 1) return 1;     else return Fibonacci_Recursion(n - 1) + Fibonacci_Recursion(n - 2); }

这样也就是不断地执行减1与减2的操作，直到这个数变成1或者0.
但是这样在n特别大的时候是特别慢的。

想一想，对于中间的每一个数字，都需要两个数字来算出来，
这个结果已经是2的指数次方级别的了

指数这就很可怕了，但是其中肯定有些明显可以优化的地方。
比如，我们在算n-1项的时候其实已经算完了n-2项，
但是两边却是完全独立的，数据的复用性很差。

那么有什么办法能够算出第n项呢？
我们可以从第一项推到第n项。
虽然这个办法也快不到哪里去，但比之前的指数级别的速度可要强多了。
我们这一次直接将它的时间复杂度降到了O(n).

2.线性递推法

• 算法展示
  同样，我们仍然要给以后的计算提供条件，
  但是我们计算的基础单位变成了an，an-1，an-2这三个数，
  要提供三个数据。
  由这三个数，我们是可以从1推到无穷大的（笑，如果计算机的储存空间允许的话）。

出个小思考题

如果现在an-2，an-1，an分别是1 2 3
如何编程将它们都推到下一项(an-2 = 2 an - 1 = 3 an = 5)？

其实可以这样想，对于新an，an其实是an-1，an-1其实是an-2.
往前也是一样的，又an-2 = an - an-1。
全都推出来了。

• 代码展示
  于是我们就可以这样写了

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  COPY int Fibonacci_Linear(int n) { if(n == 0) return 1; else if(n == 1) return 1; else if(n == 2) return 2; else { int i = 3; int anmin2 = 1, anmin1 = 1, an = 2; while(i <= n) { an += anmin1; anmin1 += anmin2; anmin2 = an - anmin1; i++; } return an; } }

注：其中的n为第n项，这里的数列也许不标准，因为第一项并不是0而是1。

然后就是有关于矩阵以及矩阵运算的内容了。
里面涉及的算法有些复杂，涉及的运算也很多，可以在算法导论这本书中查找到。
而且这里就不细讲了。

今晚从kmjj那里得到了一些对html文本的理解，
我起初是想解决输出换行的问题。
没成想反思下自己的这个想法其实不太好，
因为这并不是一个编程语言。
你要不换行直接写一行里就行。

过两天花点时间尝试换一下C++，
使用一些库以及数据结构。
回到面向对象语言。

这就是这一天学习的内容了，
因为实现原因内容并不多，明天要继续努力了。