最大K乘积.doc

课内实验报告 实验名称： 最大K乘积问题 专业名称： 计算机科学与技术班 级： 计科1203 学生姓名： 学号(8位)： 指导教师： 实验日期： 2015年5月12日一. 实验目的及实验环境实验目的：加深对动态规划算法原理及实现过程的理解，熟悉并掌握最大k乘积问题的算法。实验环境：Code：Blocks二. 实验内容问题描述：设I是一个n位十进制整数，如果将I划分为k段，则可以得到k个整数，这n个整数的乘积成为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。数据输入：由文件input.txt提供输入参数。文件的第一行中有两个正整数n和k。正整数n是序列的长度，正整数k是分割的段数在接下来的一行中是一个n位十进制整数（n=10）。数据输出：将计算结果输出到问津output.txt中，文件第一行中的数是计算出的最大k乘积。三方案设计(1)假定给定了正整数I。I(i,j)是I由s为开始的t位数字组成的十进制数；mul(i,j)表示I(0,i)的j乘积.sub(i,j)表示从i位到j位十进制数的子数字段。假定j乘积的第j段的起始位置为d位，其中0di；则存在关系：mul(i,j)=mul(d,j-1)*sub(d+1,i);设max表示I(0,i)的最大j乘积，则原始问题的最优值为muln-1k-1.(2) 现在有两个矩阵，mulij,subij;mulij用来记录前i位分成j段的最大乘积;subij用来记录第i位到第j位所组成的十进制数子段。初始(3) 修改mul矩阵中的元素：a.当k=1时，muli0=sub0i;b.当k!=1时，若计算muln-1k-1的第k段的起始位置为第d位，0dmax时，修改mulij的值。若将mulij的断开位置记为dij后，就可以递归由dij得出相应的最优解。测试要求:(4) 化sub矩阵，用所有的子十进制数段初始化矩阵；设计程序时最好用随机数的方法来产生n，k，data(n位十进制数)，方便生成测试用例并自动测试，使得测试比较全面。4 测试数据及运行结果1. 正常测试数据(3组)及运行结果5 总结1 实验过程中遇到的问题及解决办法：基于上次写过的动态规划之编辑距离问题，读写文件已经能够使用自如。文件这部分基本没有问题。具体算法实现这块，由于思想比较复杂较难理解，所以在理解算法上遇到了一点问题，刚开始想不通那个递推公式是怎么来的，之后仔细研究了一下算法，最后弄明白了整体算法思想结构。2 对设计及调试过程的心得体会针对本次实验，我深刻体会到算法设计的重要性。一个功能完整，性能健壮的代码，必须建立在大量的算法优化和测试工作之上。在算法上，我们需要一步一步的进行优化，直到找到效率最高的一种算法为止，这样不仅能够提高代码的运行速率，而且还有可能节省内存空间。在性能上，我们需要对所写的代码进行边界值测试和功能测试，处理每一中可能发生异常的情况。这样会使代码的健壮性更强。另外在编写程序打过程中，注释也是非常重要的，其次代码规范也很重要，所以我们需要在每次写代码的过程中都保持一个良好的习惯，是自己的代码更加清晰易懂。通过此次实验。已经熟悉掌握了最大K乘积的算法思想和过程。在以后的实验中，要更加努力的做到代码规范完整。6 源代码#include#include#include#include#include#includeusing namespace std;#define MAXN 51#define MAXK 10int mulMAXNMAXN=0,0 ; /前i位分成j段的最大乘积int subMAXNMAXN=0,0 ; /第i位到第j位所组成的十进制数子段void random_data(int *n,int *k,char *a);void max_k_mul(int n,int k,char *a) /求最大K乘积 int i,j,d; long temp,max; for(i=0; i n ; i+) /分成1段（k=1） muli0 = sub0i; /最大k乘积等于十进制数本身 for(i=0 ; i n ; i+) for(j=1; j k ; j+) max = 0; for(d=0; d max) max = temp; mulij = max ; int main(void) int n=0,k=0,i,j,t; char aMAXN,bMAXN; string strMAXN; char c; random_data(&n,&k,a); coutendl; ofstream in(F:input.txt);if(!in)cout文件打开失败！n;return -1;inn kn;int la=0; for(t=0;tn;t+) innka;read.close(); for(i=0 ; i n; i+) subii= ai-0; /从第i位到第i为所组成的十进制数段即第i位数字 for(j=i+1 ; j n; j+) subij = subij-1*10 +( aj-0); /从第i位到第j位所组成的十进制数段为第i位到第j-1位的数据段加上第j位数字 max_k_mul(n,k,a); coutendl最大K乘积:muln-1k-1endl ; ofstream out(F:output.txt); if(!out) cout文件打开失败！n; return -1; outmuln-1k-1; /将最大K乘积写入文件中 return 0;void random_data(int *n,int *k,char *a) int la=0; srand(unsigned)time(NULL);while(*n=*k)*n=rand()%