算法设计与分析习题答案1-6章

设计动态规划算法计算A(m, n)，要求算法的空间复杂性为O(m)。 //求ackman函数 //使用栈

#include using namespace std;

long ackman(long m, long n) { long stack[10000]; int pos=1;

stack[0]=m;stack[1]=n; while(pos) {

n=stack[pos--]; m=stack[pos]; if(m==0) stack[pos]=n+1; if(m!=0&&n==0) { stack[pos++]=m-1; stack[pos]=1; }

if(m!=0&&n!=0) { stack[pos++]=m-1; stack[pos++]=m; stack[pos]=n-1; }

}

return stack[0]; }

int main(int argc, char *argv[]) { long m,n; cin>>m>>n;

cout<

8. 考虑下面的货币兑付问题:在面值为(v, v, ?, v)的n种货币中，需要支付y值的12n

nn

xv,yx货币，应如何支付才能使货币支付的张数最少，即满足，且使最小(x是i,,iii,1i,1i

非负整数)。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。

#include #define N 100000 #define M 20 int a[N][M]; int value[M]; using namespace std; int main()

{

while(true) {

int i,j,k; int x,y,z;

cout<<\输入货币种类的个数:\cin>>x;

cout<<\从小到大输入货币的价值，其中第一个必须为一:\for(i=1;i<=x;i++)//x为货币种类的个数 {

cout<<\cin>>y; value[i]=y; }

cout<<\输入要兑换的钱的价值:\cin>>z;//z为钱 for(j=0;j<=z;j++) a[j][0]=0; for(k=0;k<=x;k++) a[0][k]=0; for(i=1;i<=z;i++) {

for(j=1;j<=x;j++) {

if(value[j]==i) a[i][j]=1;

else if(value[j]>i) a[i][j]=a[i][j-1]; else

a[i][j]=a[i-value[j]][j]+1;//相当于把乘法换成加法，即碰到一个钱数于 兑换货币自身价值时，返回到

钱数减去该货币值的地方，其值再加1// }//for }

cout<<\兑换的最小货币个数是:\}//while return 0; }

9. 多边形游戏。多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形，每个顶点具有一个整数值，每条边具有一个运算符“，”或“×”。游戏规则是每次选择一条边e以及和e相关联的两个顶点i和j，用一个新的顶点k取代边e、顶点i和j，顶点k的整数值是顶点i和j的整数值通过边e上的运算符计算得到的结果。当所有边都删除时，游戏结束，游戏的得分就是所剩顶点的整数值。设计动态规划算法，对于给定的多边形计算最高得分。