申論題

一、我們有下列的 C/C++語言程序。 void f(n) int n; { if (n==1) printf(“*”); else if (n==2) printf(“***”); else { f(n-1); f(n-2); f(n-2); } } 假設 a(n)是 f(n)列印出的星號數目。請寫出一個程式，可以算出 a(n)。這個程式必須具 有不可高於 O(n)的複雜度。此外，請列出 a(n)的遞迴方程式（recurrence equation）， 並寫出其解答。（25 分）