高行行的个人博客

言归正传，首先让我们复习一下矩阵连乘的有关知识。对于矩阵知识很了解的人可以跳过矩阵知识这块内容，不过笔者建议最好复习一下。

矩阵知识:

矩阵的乘法：

极值是高等数学中一个基本但又重要的知识点，首先看一下极值的定义。

Radio Garden:一个网站让你听遍全球电台广播

电台花园(Radio Garden)是一个以地图的形式来展示收录世界各地的广播电台频道，让我们在浏览器上快速即时收听，不用安装或下载任何软体，从广播来认识一个城市。全球电台随心选，带你听遍全世界的优秀电台。

Radio Garden

1.基本概念

首先需要科普一下，最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。什么是子序列呢？即一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢？给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下：

如上图，给定的字符序列： {a,b,c,d,e,f,g,h}，它的子序列示例： {a,c,e,f} 即元素b,d,g,h被去掉后，保持原有的元素序列所得到的结果就是子序列。同理，{a,h},{c,d,e}等都是它的子序列。
它的字串示例：{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理，{a,b,c,d},{g,h}等都是它的字串。

这个问题说明白后，最长公共子序列（以下都简称LCS）就很好理解了。

给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的相同子序列，且该子序列的长度最长，即是LCS。

s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

2.动态规划

求解LCS问题，不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列，它的时间复杂度是指数阶，太恐怖了。解决LCS问题，需要借助动态规划的思想。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

3.特征分析

解决LCS问题，需要把原问题分解成若干个子问题，所以需要刻画LCS的特征。

设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：

如果am=bn，则zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列；

如果am!=bn，则若zk!=am，蕴涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；

如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一个最长公共子序列。

有些同学，一看性质就容易晕菜，所以我给出一个图来让这些同学理解一下：

棋盘覆盖问题算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include<stdio.h>
int tile=1;
int board[100][100];
 //可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。这里设置成100，来容纳棋盘 
 //为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
void ChessBoard(int tr,int tc,int dr,int dc,int size) 
//子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
//用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;
{
	if(size==1) return;//递归边界 
	int t=tile++; //L型骨牌号
	int s=size/2;//分割棋盘 
//覆盖左上角子棋盘  
    if(dr<tr+s&&dc<tc+s)  
    //特殊方格在此棋盘中  
    ChessBoard(tr,tc,dr,dc,s);  
        else  
        {   
		    //此棋盘中无特殊方格 ,用t号L型骨牌覆盖右下角  
            board[tr+s-1][tc+s-1]=t;  
            //覆盖本子棋盘中的其余方格  
            ChessBoard(tr,tc,tr+s-1,tc+s-1,s);  
        }  
//覆盖右上角子棋盘  
         if(dr<tr+s&&dc>=tc+s)  
         //特殊方格在此棋盘中  
         ChessBoard(tr,tc,dr,dc,s);  
         else  
         {
		 	//特此棋盘中无特殊方格 ,t号L型骨牌覆盖左下角  
            board[tr+s-1][tc+s]=t;  
            //覆盖本子棋盘中的其余方格  
            ChessBoard(tr,tc+s,tr+s-1,tc+s,s);  
         }  
//覆盖左下角子棋盘  
        if(dr>=tr+s&&dc<tc+s)  
    	//特殊方格在此棋盘中  
        ChessBoard(tr+s,tc,dr,dc,s);  
        else  
         {
		 	//此棋盘中无特殊方格 ,t号L型骨牌覆盖右上角  
       		board[tr+s][tc+s-1]=t;  
            //覆盖本子棋盘中的其余方格  
            ChessBoard(tr+s,tc,tr+s,tc+s-1,s);  
         }  
//覆盖右上角子棋盘  
         if(dr>=tr+s&&dc>=tc+s)  
         //特殊方格在此棋盘中  
         ChessBoard(tr+s,tc+s,dr,dc,s);  
         else  
         {
		 	//此棋盘中无特殊方格 ,t号L型骨牌覆盖左上角  
            board[tr+s][tc+s]=t;  
            //覆盖本子棋盘中的其余方格  
            ChessBoard(tr+s,tc+s,tr+s,tc+s,s);  
         }         
}  
int main()      
{  
    int size,r,c,row,col;  
    printf("输入棋盘大小：\n");  
   	scanf("%d",&size);//输入棋盘大小  
   	printf("输入特殊方格位置：row,col\n");  
    scanf("%d,%d",&row,&col);//输入特殊方格位置  
    ChessBoard(0,0,row,col,size);  
    printf("输出棋盘覆盖结果：\n");  
    for (r = 0; r < size; r++)//输出棋盘覆盖结果  
    {  
       for (c = 0; c < size; c++)  
       {  
       printf("%-4d ",board[r][c]);  
       }  
       printf("\n");  
    }  
        return 0;  
}  

高快省的排序算法-快速排序

博客转载自http://developer.51cto.com/art/201403/430986.htm

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

排序算法显神威

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

《化身孤岛的鲸》改编自香港歌手谢安琪演唱的歌曲《我们都被忘了》，由沃特艾文儿重新填词，只佛（填词原唱）、兔裹煎蛋卷、卡布（周深）、人衣大人、云の泣、不才、东篱、鲸鱼岛乐队主唱白森、司夏等演唱，这首歌在网络中红极一时，许多网友被细腻优美又充满意境的歌词打动，纷纷跟风翻唱，甚至连原唱者谢安琪都对改编后的歌词大加赞赏。
这首歌凭借细腻优美的歌词及婉转的曲调，让很多网友联想到了著名动画大师宫崎骏的作品中所包含的温柔治愈的感觉，迅速在网络中走红。

作曲 : 徐浩
作词 : 沃特艾文儿
原曲：谢安琪《我们都被忘了》
我是只化身孤岛的蓝鲸
有着最巨大的身影
鱼虾在身侧穿行
也有飞鸟在背上停
我路过太多太美的奇景
如同伊甸般的仙境
而大海太平太静
多少故事无人倾听