編寫具有如下函數(shù)原型的遞歸與非遞歸兩種函數(shù)equ，負(fù)責(zé)判斷數(shù)組a與b的前n個(gè)元素值是否按下標(biāo)對(duì)應(yīng)完全相同，是則返回true，否則返回false。并編制主函數(shù)對(duì)它們進(jìn)行調(diào)用，以驗(yàn)證其正確性。
bool equ(int a[], int b[], int n)
提示：遞歸函數(shù)中可按如下方式來分解并處理問題，先判斷最后一個(gè)元素是否相同，不同則返false；相同則看n是否等于1，是則返回true，否則進(jìn)行遞歸調(diào)用（傳去實(shí)參a、b與 n-1，去判斷前n-1個(gè)元素的相等性），并返回遞歸調(diào)用的結(jié)果（與前n-1個(gè)元素的是否相等性相同）。
編寫具有如下函數(shù)原型的遞歸與非遞歸兩種函數(shù)equ，負(fù)責(zé)判斷數(shù)組a與b的前n個(gè)元素值是否按下標(biāo)對(duì)應(yīng)完全相同，是則返回true，否則返回false。并編制主函數(shù)對(duì)它們進(jìn)行調(diào)用，以驗(yàn)證其正確性。
bool equ(int a[], int b[], int n)
提示：遞歸函數(shù)中可按如下方式來分解并處理問題，先判斷最后一個(gè)元素是否相同，不同則返false；相同則看n是否等于1，是則返回true，否則進(jìn)行遞歸調(diào)用（傳去實(shí)參a、b與 n-1，去判斷前n-1個(gè)元素的相等性），并返回遞歸調(diào)用的結(jié)果（與前n-1個(gè)元素的是否相等性相同）。
Instead of finding the longest common
subsequence, let us try to determine the
length of the LCS.
Then tracking back to find the LCS.
Consider a1a2…am and b1b2…bn.
Case 1: am=bn. The LCS must contain am,
we have to find the LCS of a1a2…am-1 and
b1b2…bn-1.
Case 2: am≠bn. Wehave to find the LCS of
a1a2…am-1 and b1b2…bn, and a1a2…am and
b b b
b1b2…bn-1
Let A = a1 a2 … am and B = b1 b2 … bn
Let Li j denote the length of the longest i,g g
common subsequence of a1 a2 … ai and b1 b2
… bj.
Li,j = Li-1,j-1 + 1 if ai=bj
max{ L L } a≠b i-1,j, i,j-1 if ai≠j
L0,0 = L0,j = Li,0 = 0 for 1≤i≤m, 1≤j≤n.
