if (emptystack(s)) flag= false else (x=Get Top(s) switch(a[I]) if(x=’(’)pop(s) else flag =fal case’]’:if(x=[]’)pop(s) else flag=false break case e’}’:if(x={}’)pop(s) else flag=false 8. int akm (int m, int n) fif (m==0)return(n+1); else if(n==0)return(akm(m-1, 1)) else return(akm(m-1, akm(m, n-I)) 9. int f(int m, int n fif(m*n==)return(m+n+1); else return(f(m-1, f(m, n-1)) } 10.用Knap(S,n)表示背包问题的解,这是一个布尔函数,其参数应满足S0,n≥1。背包问 题如果有解,其选择只有两种可能:一种是选择的一组物品中不包含Wn,这样Knap(S.n) 的解就是Knap(S,n1)的解,另一种是选择中包含Wn,这时Knap(S.n)的解就是Knap(S-Wan) 的解。另外可以定义:当S=0时,背包问题总有解,即 Knap(O,n)=true,只要不选择任何 物品放入背包即可:当S(0时,背包问题无解,即Knap(S,n)= false,因为无论怎样选择总 不能使重量之和为负值,当S>0但n<1时,背包问题也无解,即Knap(S,n)=alse,因为不取 任何东西就要使重量为正值总是办不到的。从而,背包问题可以递归定义如下: 当S=0 I false,当S<0 Knap(Sn)=< false,当s>0且n<1 I Knap(S, n-1)X Knap(S-, n-1) 当s>0且n>=1 上述递归定义是确定的,因为每递归一次n都减1,S也可能减少,所以递归若干 次以后,一定会出现S≤0或者n=0,无论哪种情况都可由递归出口明确定值 Int knap int s, int n lif (s==0) return( else if (s<o(>0&&n<1))return(0) else if (knap(s-w[n], n-1))printf( "%d",wn]); return(1): I else return(knap(s, n-1))9 if (emptystack(s)) flag= false; else{x=GetTop(s); switch(a[I]) {case’}‘:if (x=’(’)pop (s); else flag =false; break; case’]’:if (x=’[]’) pop(s); else flag=false; break; case’}’:if (x=’{}’) pop(s); else flag=false; }} I++; } } 8.int akm(int m ,int n) {if (m= =0) return(n+1); else if (n= =0) return(akm (m-1,1)); else return(akm(m-1,akm(m,n-1))); } 9. int f(int m, int n ) {if (m*n= =0) return(m+n+1); else return(f(m-1,f(m,n-1))); } 10. 用 Knap(S,n)表示背包问题的解，这是一个布尔函数，其参数应满足 S>0,n≥1。背包问 题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含 Wn，这样 Knap(S,n) 的解就是 Knap(S,n-1)的解，另一种是选择中包含 Wn，这时 Knap(S,n)的解就是 Knap(S-Wn,n) 的解。另外可以定义：当 S=0 时，背包问题总有解，即 Knap(0,n)=true ，只要不选择任何 物品放入背包即可：当 S〈0 时，背包问题无解，即 Knap(S,n)=false，因为无论怎样选择总 不能使重量之和为负值，当 S>0 但 n<1 时，背包问题也无解，即 Knap(S,n)=false，因为不取 任何东西就要使重量为正值总是办不到的。从而，背包问题可以递归定义如下： ╭ | true, 当 S=0 | false, 当 S<0 Knap(S,n)= < false, 当 s>0 且 n<1 | Knap(S,n-1)或 Knap(S- ,n-1)， 当 s>0 且 n>=1 | 上述递归定义是确定的，因为每递归一次 n 都减 1，S 也可能减少 ，所以递归若干 次以后，一定会出现 S≤0 或者 n=0，无论哪种情况都可由递归出口明确定值。 Int knap(int s ,int n) {if (s==0) return(1); else if (s<0||(s>0&&n<1)) return(0); else if (knap(s-w[n],n-1)){printf(“%d”,w[n]);return(1);} else return(knap(s,n-1)); }