㈠ 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