动态规划题目.doc

动态规划专题测试考试时间:3小时题一、递增序列(EASINGSEQUENCES)源程序名INCSQ.???(PAS,C,CPP),请你插入若干个逗号,使得该数字串成为一个严格递增的数列且最后一个数要尽可能小,在这个问题中,前导的零是允许出现在数的前面的。输入输入数据仅含一行,为一个长度不超过80的数字串。输出输出一个严格递增且最后一数最小的数列,相邻两个数之间用一个逗号隔开,如果有多个数列满足要求,则输出第一个数最大的那个数列,若这样的解还不止一个,则输出第二个数最大的那个数列,以此类推。,000101题二、DOLLARS源程序名DOLLARS.???(PAS,C,CPP)。编写程序帮助戴维何时应买或卖马克或美元,使他从100美元开始,最后能获得最高可能的价值。输入输入文件的第一行是一个自然数N,1≤N≤100,表示戴维学习汇率的天数。接下来的N行中每行是一个自然数A,1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率,在这一天中,戴维既能用100美元买A马克也能用A马克购买100美元。输出输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元,保留两位小数)。注意:考虑到实数算术运算中进位的误差,,戴维必须在最后一天结束之前将他的钱都换成美元。(无需输出)Day1...=...=...=...=、最大的算式源程序名BIGEXP.???(PAS,C,CPP),给出N个数字,不改变它们的相对位置,在中间加入K个乘号和N-K-1个加号,(括号随便加)使最终结果尽量大。因为乘号和加号一共就是N-1个了,所以恰好每两个相邻数字之间都有一个符号。例如:N=5,K=2,5个数字分别为1、2、3、4、5,可以加成:1*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45……输入输入文件共有二行,第一行为两个有空格隔开的整数,表示N和K,其中(2<=N<=15,0<=K<=N-1)。第二行为N个用空格隔开的数字(每个数字在0到9之间)。输出输出文件仅一行包含一个整数,(1+2+3)*4*5=120题四Kitty猫基因突变源程序::::