作者avogau ( 假 装)
看板TransCSI
标题Re: [问题] 计概问题
时间Mon Apr 6 18:24:19 2009
※ 引述《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)