※ 引述《RJking (RJ-king)》之銘言：
: 我只會解第1題...RSA期待其他高手解答
: ※ 引述《tool11 (:))》之銘言：
: : 1.
: : In the following C code,
: : int foo(char * A , char * B){
: : if (*A == '\0' || *B == '\0') return 0;
: : else if (*A == *B) return 1 + foo(A+1, B+1);
: : else return max(foo(A+1,B), foo(A,B+1));
: : }
: : the function int max(int, int) returns the maximun value of its arguments.
: : Please answer the result of foo("abbacabc", "bbcaaca") by tracing the
: : execution.
: : 這題是完全看不懂在做什麼
: 要會這題必須先瞭解動態字元陣列跟指標
: 在這裡一開始先設定兩塊連續記憶體空間存放"abbacabc"跟"bbcaaca"
: 然後由A指向"abbacabc"的字首'a'，B指向"bbcaaca"的'b'
: 程式會做的事情就是對照A跟B所指向的記憶體內容，並且如果
: 1. A或B內容為'\0'，表示為字元陣列的結尾(為什麼？請去翻書)，回傳0
: 2. A跟B內容相等，表示是同一個字，AB兩指標都加一指向下一個記憶體空間，就是指向
: 下一個字，並將其foo函式的回傳+1後回傳
: 3. 其他情況，就AB內容不相等，則將foo(A+1,B)跟foo(A,B+1)最大的回傳
: 這是一個遞迴函式，做啥用的實在看不出來
這個遞迴的作用是比較最長的共同子序列(LCS)
{ 1 + LCS(A[i+1],B[j+1]) if A[i]=B[j]
A跟B的LCS = {
{ Max{ LCS(A[i+1],B[j]) , LCS(A[i],B[j+1] ) } if A[i] != B[j]
{
{ 0 if A[i] = null or B[j] = null
因此 "abbacabc"跟"bbcaaca" 之LCS 為:"bbaca" or "bbcac"
所以 答案為 5
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.204.143.242
※ 編輯: avogau 來自: 123.204.143.242 (04/06 18:25)