下面的演算法Delta能解決哪個問題，其中m，n >=0是整數？
所以我發現由于嵌套遞回的性質以及它如何呼叫另一個遞回演算法，這個演算法很難被分解。如果讓我猜測，我會說Delta解決了LCS（最長共同子序列）問題，但我無法很好地解釋為什么。
誰能幫我分解一下這個演算法，解釋一下遞回和它是如何作業的？
uj5u.com熱心網友回復：
正如你自己發現的，delta計算的是兩個整數的乘積。
遞回確實讓人看得一頭霧水，但獲得直覺的最佳方式是在一些示例資料上手工執行計算。但是，通過分別觀察這些函式，你會發現：
Gamma只是一個簡單的函式。
Gamma只是求和。Gamma(n,m) = gamma(n, m - 1) 1 本質上是執行一個天真的求和，在這個求和程序中，你會減去第二項，同時給第一項加1。例子：
3 3 =
(3 2) 1 =
((3 1) 1) 1 =
((3 0) 1) 1 =
6
知道了這一點，我們可以簡化Delta：
Delta(n, m) = n Delta(n, m - 1)（如果m!=0，否則回傳0）。
以同樣的方式，我們在第二個因子上進行倒數，但是我們不是加1，而是加n。這確實是乘法的一個定義。如果你像上面那樣手動解決一個例子，就很容易理解。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/308807.html
標籤：