浙大远程教育数据结构与算法离线作业参考答案(4)

for (i=1; i<=n; i++) cin >> A[i]; dp[1] = 1; // 有n个阶段

for (i=2; i<=n; i++) {

dp[i] = 1;

// 每个阶段只有1个状态

// 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度 for (j=i-1; j>=0; j--) {

if (A[i]>A[j])

dp[i] = max(dp[i], dp[j]+1); } }

int maximum = dp[1]; for (i=2; i<=n; i++)

maximum = max(maximum, dp[i]); cout << maximum; }

16

【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？ 答：

共有34种不同的输出序列

12345 12354 12435 12543 13245 13254 14325 15432 21345 21435 21543 23145 23154 23415 23451 23541 24315 24351 24531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321

【10，3，2】请编写程序将中缀表达式转换为后缀表达式。 答:

#include #include #include using namespace std; int prior(char op) {

if(op=='+'||op=='-') return 1;

if(op=='*'||op=='/')

17

return 2; return 0; }

string middletolast(string middle) {

stack op; string ans;

for(int i=0;i

char c=middle[i]; if(c>='0'&&c<='9') {

ans.append(1,c); } else {

if(c=='(') op.push('('); else {

18

if(c==')') {

while(op.top()!='(') {

ans.append(1,op.top()); op.pop(); }

op.pop(); } else {

if(op.empty()) {

op.push(c); } else {

if(prior(c)>prior(op.top())) op.push(c); else

19

{

while(!op.empty()&&prior(c)<=prior(op.top())) {

ans.append(1,op.top()); op.pop(); }

op.push(c); } } } } } }

while(!op.empty()) {

ans.append(1,op.top()); op.pop(); }

return ans; }

20