算法分析与设计题目 救助~!~!
1.设B是一个n x n棋盘,n是2的幂,用一个分治论证描述怎么样用一个L型条块去覆盖B的除一个方格外的所有方格。例如:如果n =2,则存在四个方格,其中的3个可被一L型条块覆盖,当n=4.则存在16个方格,其中15个方格被5个L型条块覆盖。2.用一种组合论证,证明如果n是2的幂,则n*n=1(mod 3) (可利用上题结果)
3.考虑金钱兑换问题,有一个货币系统,它有n种货币,它们的面值为v1,v2,v3,...,vn, 其中v1=1.我们想这样来兑换价值为y的钱,要让硬币的数目最少。更形式地,我们要让下面的量 x1+x2+x3+...+xn
在约束条件 x1*v1+x2*v2+...+xn*vn=y 下极小,其中x1,x2,...,xn是非负整数(可能是0)
(a)设计求解这个问题的动态规划算法
(b)你的算法的时间和空间复杂度是什么
只要写程序就行
哪位高手帮帮忙啊,,完了发我QQ邮箱,,77803629@