㈠ Ackerman函数的动态规范算法
试设计一个计算A(m，n)的动态规划算法，该算法只占用O(m)空间。
用两个一维数组，ind[i]和val[i]，使得当ind[i]等于t时，val[i]=A(i，ind[i])。
i ind[i] val[i]
0 0 1
1 -1 0
2 -1 0
……
初始时，令ind[0]=0，val[0]=1，ind[i]=-1(i>0)，val[i]=0(i>0)。
1当m=0时，A(m，n)=n+1。
任给一个t，当ind[0]=t时，能够求出val[0]的值，val[0]等于ind[0]。
2当n=0，m>0时，A(m，n)=n+1。
能够求出当ind[i]=0时，val[i]的值，此时val[i]等于当ind[i-1]等于1时val[i-1]的值。
3当m>0，n>0时，A(m，n)=A(m-1，A(m，n-1))。
当ind[i]=t，val[i]=s时，要求当ind[i]’=t+1时val[i]’的值。
Val[i]’=A(i，ind[i]’)=A(i-1，A(i，ind[i]’-1)=A(i-1，A(i，ind[i]))=A(i-1，val[i])
所以，当ind[i-1]=val[i]时，能够求出当ind[i]’=k+1时，val[i]’=val[i-1]。
#include <stdio.h>
int ack(int& m,int& n)
{
int i,j;
int *val=new int[m+1];
int *ind=new int[m+1];
for(i=1;i<=m;i++)
{
ind[i]=-1;
val[i]=-1;
}
ind[0]=0;
val[0]=1;
while(ind[m]<n)
{
val[0]++;
ind[0]++;
printf("%d ",val[0]);
for(j=1;j<=m;j++)
{
if(1==ind[j-1])
{
val[j]=val[j-1];
ind[j]=0;
}
if(val[j]!=ind[j-1])
break;
ind[j]++;
val[j]=val[j-1];
}
}
printf("\n");
printf(" i ind[i] val[i]\n");
for(i=0;i<=m;i++)
printf("%5d %6d %6d\n",i,ind[i],val[i]);
return val[m];
}
㈡ 简单理解 n-gram
N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念，通常在NLP中，人们基于一定的语料库，可以利用N-Gram来预计或者评估一个句子是否合理。另外一方面，N-Gram的另外一个作用是用来评估两个字符串之间的差异程度。这是模糊匹配中常用的一种手段。本文将从此开始，进而向读者展示N-Gram在自然语言处理中的各种powerful的应用。
基于N-Gram模型定义的字符串距离
模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的“差异”。这种差异通常又称为“距离”。这方面的具体算法有很多，例如基于编辑距离的概念，人们设计出了 Smith-Waterman 算法和Needleman-Wunsch 算法，其中后者还是历史上最早的应用动态规划思想设计的算法之一。现在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息学领域也有重要应用，研究人员常常用它们来计算两个DNA序列片段之间的“差异”（或称“距离”）。
我们除了可以定义两个字符串之间的编辑距离（通常利用Needleman-Wunsch算法或Smith-Waterman算法）之外，还可以定义它们之间的N-Gram距离。N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念。假设有一个字符串 ，那么该字符串的N-Gram就表示按长度 N 切分原词得到的词段，也就是 中所有长度为 N 的子字符串。设想如果有两个字符串，然后分别求它们的N-Gram，那么就可以从它们的共有子串的数量这个角度去定义两个字符串间的N-Gram距离。但是仅仅是简单地对共有子串进行计数显然也存在不足，这种方案显然忽略了两个字符串长度差异可能导致的问题。比如字符串 girl 和 girlfriend，二者所拥有的公共子串数量显然与 girl 和其自身所拥有的公共子串数量相等，但是我们并不能据此认为 girl 和girlfriend 是两个等同的匹配。
为了解决该问题，有学者便提出以非重复的N-Gram分词为基础来定义 N-Gram距离这一概念，可以用下面的公式来表述：
此处，|GN(s)| 是字符串 s 的 N-Gram集合，N 值一般取2或者3。以 N = 2 为例对字符串Gorbachev和Gorbechyov进行分段，可得如下结果（我们用下画线标出了其中的公共子串）。
结合上面的公式，即可算得两个字符串之间的距离是8 + 9 − 2 × 4 = 9。显然，字符串之间的距离越小，它们就越接近。当两个字符串完全相等的时候，它们之间的距离就是0。
利用N-Gram模型评估语句是否合理
从现在开始，我们所讨论的N-Gram模型跟前面讲过N-Gram模型从外在来看已经大不相同，但是请注意它们内在的联系（或者说本质上它们仍然是统一的概念）。
为了引入N-Gram的这个应用，我们从几个例子开始。
首先，从统计的角度来看，自然语言中的一个句子 s 可以由任何词串构成，不过概率 P(s) 有大有小。例如：
显然，对于中文而言 s1 是一个通顺而有意义的句子，而s2 则不是，所以对于中文来说，P(s1)>P(s2) 。但不同语言来说，这两个概率值的大小可能会反转。
其次，另外一个例子是，如果我们给出了某个句子的一个节选，我们其实可以能够猜测后续的词应该是什么，例如
the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?
显然，如果我们知道这个句子片段更多前面的内容的情况下，我们会得到一个更加准确的答案。这就告诉我们，前面的（历史）信息越多，对后面未知信息的约束就越强。
如果我们有一个由 m 个词组成的序列（或者说一个句子），我们希望算得概率 P(w1,w2,⋯,wm) ，根据链式规则，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)
这个概率显然并不好算，不妨利用马尔科夫链的假设，即当前这个词仅仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上诉算式的长度。即
P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)
特别地，对于 n 取得较小值的情况
当 n=1, 一个一元模型（unigram model)即为
当 n=2, 一个二元模型（bigram model)即为
当 n=3, 一个三元模型（trigram model)即为
接下来的思路就比较明确了，可以利用最大似然法来求出一组参数，使得训练样本的概率取得最大值。
使用N-Gram模型时的数据平滑算法
有研究人员用150万词的训练语料来训练 trigram 模型，然后用同样来源的测试语料来做验证，结果发现23%的 trigram 没有在训练语料中出现过。这其实就意味着上一节我们所计算的那些概率有空为 0，这就导致了数据稀疏的可能性，我们的表3中也确实有些为0的情况。对语言而言，由于数据稀疏的存在，极大似然法不是一种很好的参数估计办法。
这时的解决办法，我们称之为“平滑技术”（Smoothing）或者 “减值” （Discounting）。其主要策略是把在训练样本中出现过的事件的概率适当减小，然后把减小得到的概率密度分配给训练语料中没有出现过的事件。实际中平滑算法有很多种，例如：
▸ Laplacian (add-one) smoothing
▸ Add-k smoothing
▸ Jelinek-Mercer interpolation
▸ Katz backoff
▸ Absolute discounting
▸ Kneser-Ney
对于这些算法的详细介绍，我们将在后续的文章中结合一些实例再来进行讨论。
搜索引擎（Google或者Bai）、或者输入法的猜想或者提示。你在用网络时，输入一个或几个词，搜索框通常会以下拉菜单的形式给出几个像下图一样的备选，这些备选其实是在猜想你想要搜索的那个词串。再者，当你用输入法输入一个汉字的时候，输入法通常可以联系出一个完整的词，例如我输入一个“刘”字，通常输入法会提示我是否要输入的是“刘备”。通过上面的介绍，你应该能够很敏锐的发觉，这其实是以N-Gram模型为基础来实现的，如果你能有这种觉悟或者想法，那我不得不恭喜你，都学会抢答了！
参考： https://blog.csdn.net/mafujinji/article/details/51281816
㈢ 动态规划 最长公共子序列 过程图解
首先需要科普一下，最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。
这里给出一个例子：有两个母串
cnblogs
belong
比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个。
子串是要求更严格的一种子序列， 要求在母串中连续地出现 。
在上述例子的中，最长公共子序列为blog（cnblogs,belong），最长公共子串为lo（cnblogs, belong）。
给一个图再解释一下：
如上图，给定的字符序列： {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}
求解LCS问题，不能使用暴力搜索方法。 一个长度为n的序列拥有 2的n次方个子序列，它的时间复杂度是指数阶 ，太恐怖了。解决LCS问题，需要借助动态规划的思想。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 为了避免大量的重复计算，节省时间，我们引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。
解决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小节举的例子（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），并结合上图来说：
假如S1的最后一个元素 与 S2的最后一个元素相等，那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。
假如S1的最后一个元素 与 S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的LCS就等于 ： {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。
假设Z=<z1,z2,⋯,zk>是X与Y的LCS， 我们观察到
如果Xm=Yn，则Zk=Xm=Yn，有Zk−1是Xm−1与Yn−1的LCS；
如果Xm≠Yn，则Zk是Xm与Yn−1的LCS，或者是Xm−1与Yn的LCS。
因此，求解LCS的问题则变成递归求解的两个子问题。但是，上述的递归求解的办法中， 重复的子问题多，效率低下。改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。这就是动态规划（DP)的核心思想了。
DP求解LCS
用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度，则可得到状态转移方程
以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图：
图中的空白格子需要填上相应的数字（这个数字就是c[i,j]的定义，记录的LCS的长度值）。填的规则依据递归公式，简单来说：如果横竖（i,j）对应的两个元素相等，该格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表：
S1的元素3 与 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])，图中c[1,2] 和 c[2,1] 背景色为浅黄色。
继续填充：
至此，该表填完。根据性质，c[8,9] = S1 和 S2 的 LCS的长度，即为5。
本文S1和S2的最LCS并不是只有1个，本文并不是着重讲输出两个序列的所有LCS，只是介绍如何通过上表，输出其中一个LCS。
我们根据递归公式构建了上表，我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
c[8][9] = 5，且S1[8] != S2[9]，所以倒推回去，c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。
c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去，c[8][8]的值来源于 c[7][7]。
以此类推，如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 这种存在分支的情况，这里请都选择一个方向（之后遇到这样的情况，也选择相同的方向）。
这就是倒推回去的路径，棕色方格为相等元素，即LCS = {3,4,6,7,8}，这是其中一个结果。
如果如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 这种存在分支的情况，选择另一个方向，会得到另一个结果。
即LCS ={3,5,7,7,8}。
构建c[i][j]表需要Θ(mn)，输出1个LCS的序列需要Θ(m+n)。
参考：
https://blog.csdn.net/hrn1216/article/details/51534607
https://blog.csdn.net/u012102306/article/details/53184446
㈣ 动态规划算法详解
动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。
将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解（这部分与分治法相似）。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。通常可以用一个表来记录所有已解的子问题的答案。
问题的一个最优解中所包含的子问题的解也是最优的。总问题包含很多个子问题，而这些子问题的解也是最优的。
用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
：很显然，这道题的对应的数学表达式是
其中F(1)=1, F(2)=2。很自然的状况是，采用递归函数来求解：
参考：
http://blog.csdn.net/zmazon/article/details/8247015
http://blog.csdn.net/lisonglisonglisong/article/details/41548557
http://blog.csdn.net/v_JULY_v/article/details/6110269
http://blog.csdn.net/trochiluses/article/details/37966729
㈤ 求多个矩阵联乘的最优算法!
程序功能：用分而治之算法计算两个n维矩阵相乘的结果
其中n必须是2的正整数次幂。
运行过程：首先，根据提示输入矩阵的维数n
其次，根据提示分别输入矩阵A和B
最后，显示矩阵A和矩阵B以及其相乘结果矩阵C
****************************************/
#include "stdio.h"
#define mytype int//矩阵元素的数据类型
#define myinputmode "%d"//矩阵元素的输入格式
#define myprintmode "%4d"//矩阵元素的输出格式
/*以上参数的设置可根据所计算矩阵的元素的数值类型进行相应改变
如更改为浮点型数据则可以使用下面的设置
#define mytype float
#define myinputmode "%f"
#define myprintmode "%6.2f"
*/
/////////////////////////////////////////
/****************************************
函数名：is2
参数：m为长整型整数
功能：检测m是否是2的正整数次幂
返回值：返回布尔型变量
true则表示m为2的正整数次幂
false则表示m不是2的正整数次幂
****************************************/
bool is2(long m)
{
if(m<0)return false;
if(m>=2)
{
if((m%2)==0) return is2(m/2);
else return false;
}
else
{
if(m==1)return true;
else return false;
}
return false;
}
/////////////////////////////////////////
/****************************************
函数名：inputmatrix
参数：M为指向数组的指针，用来存储输入的矩阵
m长整型，是数组M所存矩阵的维数
name字符型数组，是需要进行数据输入的矩阵的名字
功能：矩阵数据输入的函数，通过输入矩阵的每个元素将
矩阵存入数组
返回值：无
****************************************/
void inputmatrix(mytype * M,long m,char *name)
{
long i,j;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
printf("Please input the %s(%d,%d):",name,i+1,j+1);
getchar();
scanf(myinputmode,&M[i*m+j]);
}
}
/////////////////////////////////////////
/****************************************
函数名：printmatrix
参数：M为指向数组的指针，数组中存储着矩阵
m长整型，是数组M所存矩阵的维数
name字符型数组，是需要进行数据输入的矩阵的名字
功能：矩阵数据输出显示的函数，将矩阵元素一一显示一在屏幕上
返回值：无
****************************************/
void printmatrix(mytype * M,long m,char *name)
{
long i,j;
printf("\nMatrix %s:\n",name);
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
printf(myprintmode,M[i*m+j]);
}
printf("\n");
}
}
/////////////////////////////////////////
/****************************************
函数名：Matrix_add_sub
参数：A，B为指向数组的指针，数组中存储着矩阵
C为指向数组的指针，用来存储运算结果
m长整型，是数组A、B、C所存矩阵的维数
add为布尔型变量，为true则C=A+B，为false则C=A-B
功能：根据add值对A、B进行加减运算并将结果存入C
返回值：无
****************************************/
void Matrix_add_sub(mytype * A,mytype * B,mytype * C,long m,bool add)
{
long i;
for(i=0;i<m*m;i++)
{
if(add)
C[i]=A[i]+B[i];
else
C[i]=A[i]-B[i];
}
}
/////////////////////////////////////////
/****************************************
函数名：GetHalfValue
参数：B为指向数组的指针，数组中存储着矩阵。其中B是指向m维矩阵中的一个元素。
A为指向数组的指针，用来接收B中的四分之一数据
m长整型，是数组B所指矩阵的维数
功能：从B所在位置向左和向右取矩阵的m/2维的子矩阵（子矩阵中包括B所指元素）并存入A
返回值：无
****************************************/
void GetHalfValue(mytype * A,mytype * B,long m)
{
long i,j;
for(i=0;i<m/2;i++)
{
for(j=0;j<m/2;j++)
{
A[i*m/2+j]=B[i*m+j];
}
}
}
/////////////////////////////////////////
/****************************************
函数名：UpdateHalfValue
参数：B为指向数组的指针，数组中存储着矩阵。其中B是指向m维矩阵中的一个元素。
A为指向数组的指针，存储着一个m/2维矩阵
m长整型，是数组B所指矩阵的维数
功能：把A矩阵所有元素存入从B所在位置向左和向右的m/2维的子矩阵（子矩阵中包括B所指元素）
返回值：无
****************************************/
void UpdateHalfValue(mytype * A,mytype * B,long m)
{
long i,j;
for(i=0;i<m/2;i++)
{
for(j=0;j<m/2;j++)
{
B[i*m+j]=A[i*m/2+j];
}
}
}
/////////////////////////////////////////
/****************************************
函数名：Matrix_multiplication
参数：A，B为指向数组的指针，数组中存储着矩阵。
C为指向数组的指针，用来存储计算结果
m长整型，是指针A、B所指矩阵的维数
功能：用分而治之算法和Strassen方法计算A与B的乘积并存入C
返回值：无
****************************************/
void Matrix_multiplication(mytype * A,mytype * B,mytype * C,long m)
{
if(m>2)//当矩阵维数大于2时
{
//将矩阵A、B分为四个小矩阵，分别为A1、A2、A3、A4、B1、B2、B3、B4
mytype *A1=new mytype[m*m/4],*A2=new mytype[m*m/4],*A3=new mytype[m*m/4],*A4=new mytype[m*m/4],*B1=new mytype[m*m/4],*B2=new mytype[m*m/4],*B3=new mytype[m*m/4],*B4=new mytype[m*m/4],*C1=new mytype[m*m/4],*C2=new mytype[m*m/4],*C3=new mytype[m*m/4],*C4=new mytype[m*m/4];
GetHalfValue(A1,&A[0],m);
GetHalfValue(A2,&A[m/2],m);
GetHalfValue(A3,&A[m*m/2],m);
GetHalfValue(A4,&A[m*m/2+m/2],m);
GetHalfValue(B1,&B[0],m);
GetHalfValue(B2,&B[m/2],m);
GetHalfValue(B3,&B[m*m/2],m);
GetHalfValue(B4,&B[m*m/2+m/2],m);
//利用Strassen方法计算D、E、F、G、H、I、J
mytype *D=new mytype[m*m/4],*E=new mytype[m*m/4],*F=new mytype[m*m/4],*G=new mytype[m*m/4],*H=new mytype[m*m/4],*I=new mytype[m*m/4],*J=new mytype[m*m/4];
mytype *temp1=new mytype[m*m/4],*temp2=new mytype[m*m/4];
//D=A1(B2-B4)
Matrix_add_sub(B2,B4,temp1,m/2,false);
Matrix_multiplication(A1,temp1,D,m/2);
//E=A4(B3-B1)
Matrix_add_sub(B3,B1,temp1,m/2,false);
Matrix_multiplication(A4,temp1,E,m/2);
//F=(A3+A4)B1
Matrix_add_sub(A3,A4,temp1,m/2,true);
Matrix_multiplication(temp1,B1,F,m/2);
//G=(A1+A2)B4
Matrix_add_sub(A1,A2,temp1,m/2,true);
Matrix_multiplication(temp1,B4,G,m/2);
//H=(A3-A1)(B1+B2)
Matrix_add_sub(A3,A1,temp1,m/2,false);
Matrix_add_sub(B1,B2,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,H,m/2);
//I=(A2-A4)(B3+B4)
Matrix_add_sub(A2,A4,temp1,m/2,false);
Matrix_add_sub(B3,B4,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,I,m/2);
//J=(A1+A4)(B1+B4)
Matrix_add_sub(A1,A4,temp1,m/2,true);
Matrix_add_sub(B1,B4,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,J,m/2);
//利用Strassen方法计算C1、C2、C3、C4
//C1=E+I+J-G
Matrix_add_sub(E,I,temp1,m/2,true);
Matrix_add_sub(J,G,temp2,m/2,false);
Matrix_add_sub(temp1,temp2,C1,m/2,true);
//C2=D+G
Matrix_add_sub(D,G,C2,m/2,true);
//C3=E+F
Matrix_add_sub(E,F,C3,m/2,true);
//C4=D+H+J-F
Matrix_add_sub(D,H,temp1,m/2,true);
Matrix_add_sub(J,F,temp2,m/2,false);
Matrix_add_sub(temp1,temp2,C4,m/2,true);
//将计算结果存入数组C
UpdateHalfValue(C1,&C[0],m);
UpdateHalfValue(C2,&C[m/2],m);
UpdateHalfValue(C3,&C[m*m/2],m);
UpdateHalfValue(C4,&C[m*m/2+m/2],m);
//释放内存
delete[] A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D,E,F,G,H,I,J,temp1,temp2;
}
else
{
//当矩阵维数小于2时用Strassen方法计算矩阵乘积
mytype D,E,F,G,H,I,J;
//D=A1(B2-B4)
D=A[0]*(B[1]-B[3]);
//E=A4(B3-B1)
E=A[3]*(B[2]-B[0]);
//F=(A3+A4)B1
F=(A[2]+A[3])*B[0];
//G=(A1+A2)B4
G=(A[0]+A[1])*B[3];
//H=(A3-A1)(B1+B2)
H=(A[2]-A[0])*(B[0]+B[1]);
//I=(A2-A4)(B3+B4)
I=(A[1]-A[3])*(B[2]+B[3]);
//J=(A1+A4)(B1+B4)
J=(A[0]+A[3])*(B[0]+B[3]);
//C1=E+I+J-G
C[0]=E+I+J-G;
//C2=D+G
C[1]=D+G;
//C3=E+F
C[2]=E+F;
//C4=D+H+J-F
C[3]=D+H+J-F;
}
}
/////////////////////////////////////////
int main()
{
long n;
//提示输入n维矩阵的维数
printf("Please input the dimension of the Matrix.(n):");
//获得用户输入的n维矩阵维数
scanf("%d",&n);
while(!is2(n))//检查维数是否是2的幂，不是则要求重新输入
{
printf("Please reinput the dimension of the Matrix.(n):");
scanf("%d",&n);
}
//开辟空间存储用来存储n维矩阵元素
mytype *A=new mytype[n*n];
mytype *B=new mytype[n*n];
mytype *C=new mytype[n*n];
//输入矩阵A、B
inputmatrix(A,n,"A");
inputmatrix(B,n,"B");
if(n>1)//矩阵维数大于1则用分而治之算法计算
Matrix_multiplication(A,B,C,n);
else//矩阵维数为1则直接计算
*C=(*A)*(*B);
//输出矩阵A、B、C
printmatrix(A,n,"A");
printmatrix(B,n,"B");
printmatrix(C,n,"C");
//释放内存
delete[] A,B,C;
getchar();getchar();
return 1;
}
㈥ 排课专家算法是用来做什么的
1课题背景与研究意义
排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。
目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。
在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。
加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。
2课题的应用领域
本课题的研究对开发高校排课系统有指导作用。
排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。
3 课题的现状
年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。次后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。
近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。
此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。
进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。
在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（A University Timetable Scheling System）系统，清华大学的TISER（Timetable SchelER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。
从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。
4解决NP问题的几种算法及其比较
解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。
动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一颗子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步骤进行：
1. 分析最优解的性质，并刻划其结构特征。
2. 递归的定义最优解。
3. 以自底向上的方式计算出最优解。
4. 根据计算最优解时得到的信息，构造一个最优解。
步骤1~3是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。
（二）贪心算法
当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。
在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。
（三）回溯法
回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。 本文来自CSDN博客，转载请标明出处： http://blog.csdn.net/hanpoyangtitan/archive/2009/04/03/4046709.aspx