动态规划之最大k乘积 C

文章图片

最近刚学了一下算法，看见有一个求最大k乘积的问题，这个问题可用动态规划来解决.具体解释如下：

/* * =========================================================================== * *Filename:max_k_product.c * *Description:动态规划之最大k乘积问题 * *Version:1.0 *Created:2013年11月21日 14时16分36秒 *Revision:none *Compiler:gcc *CopyRight: open , free , share *Author:yexingkong(zhangbaoqing) *Email: abqyexingkong@gmail.com *Company:Xi'an University of post and Telecommunications * * =========================================================================== */#include #include #include #include #include #defineARRAY_SIZE11/*定义数组大小 *//*1.问题描述: * 设I是一个n位十进制整数，如果将I划分为k段，则可得到k个整数，这k个整数 * 的乘积称为I的一个K乘积，试设计一个算法，对于给定的I和K，求出I的最大乘积 * *2.实现要求： *2.1: 对于给定的I和K，设计I的最大k乘积. *2.2: 由文件input.txt提供输入数据。文件的第1行中有2两个正整数n和k.正 *整数 n是序列的长度，正整数k是分割的段数。在接下来的一行中是一个 *n位十进制整数(n <= 10) *2.3: 将结果输出到文件output.txt。文件第一行中的舒适计算出来的最大K *乘积. * * * 3.算法分析与设计: *3.1:求I的k段最大乘积，可理解为在n位数中插入k-1个乘号，且使得各个整 *数乘积最大 *3.2: 要使k个数的乘积最大，则要使前k-1个数的乘积最大，同理，也要使前 *k-2个数的乘积最大，这说明此问题具有最优子结构和子问题重叠性， *故可用动态规划方法来解。。 *3.3: k_max(i,k)表示第1 ～ i位数中插入k个乘号所得的最大值,a[i,j]表示 *第i～j位所组成的自然数. *3.4: 现在假设将I分成K段后的最大乘积位K_max(n,k),且最后一组数为a(i,n), *，可得状态转移方程： k_max(i,k) = max( k_max(j,k-1) * a(j+1,i)). * * *//* -------------------------------------------------------------------*/ /** * @Synopsis=WriteFile用来随机生成长度为n的正整数I，并将其存入文件 * * @Returns= 用来验证函数是否正确执行 */ /* ----------------------------------------------------------------------------*/ int WriteFile() { int i,m=0; int n = 0, k = 0; int df[ARRAY_SIZE]; FILE*fp; fp = fopen("input.txt","w"); if (NULL == fp) { perror("fopen"); exit(1); }srand((unsigned)time(NULL)); n = 9.0 * rand() / (RAND_MAX + 1.0) + 1; //整数I的长度(1<= n <= 10)k = 1.0 * (n-1) * rand()/ (RAND_MAX + 1.0) + 1; //整数I的分为k段(1 <= k <= n )for (i = 0; i < n; i++) { m = 9.0 * rand() / (RAND_MAX + 1.0); if (0 == i && 0 == m) { n -= 1; continue; }df[i] = m; }fprintf(fp, "%d %d\n", n,k); for (i=0; i < n; i++) fprintf(fp, "%d",df[i]); fclose(fp); return 0; }/* -------------------------------------------------------------------*/ /** * @Synopsis=ReadFile 从文件中读取所保存的正整数I及其长度，和要分的段数 * * @Param= a[] 用来存储正整数I,info[]用来存储I的长度和所要分的段数k * * @Returns= 检验函数是否正确执行 */ /* ----------------------------------------------------------------------------*/ int ReadFile(char a[],int info[]) { FILE *fp; int i; int I_length = 0; fp = fopen("input.txt","r"); if (NULL == fp) { perror("fopen"); exit(1); }fscanf(fp,"%d%d\n",&info[0],&info[1]); printf("%d %d\n",info[0],info[1]); for (i = 1; i <= info[0]; i++) { fscanf(fp,"%c",&a[i]); }fclose(fp); return 0; }/* -------------------------------------------------------------------*/ /** * @Synopsis=intergration_num 将i～j位的十进制数合并成一个十进制数 * * @Param= a[] 保存的是正整数I * @Param= start 划分的起始位 * @Param= end 划分的终止位 * * @Returns= 返回合并后的数值 */ /* -------------------------------------------------------------------*/ int intergration_num(char a[],int start,int end) { long sum=0; int i; for (i = start; i <= end; i++) { sum = a[i] - 48 + sum * 10; }return sum; }/* -------------------------------------------------------------------*/ /** * @Synopsis=count_max_k_product计算最大k乘积 * * @Param= a[] 存储有正整数I * @Param= I 保存的是正整数I的长度， * @Param= K 保存的是所分的段数 * @Param = index[] 用来回溯记录最近一次的划分位置 * @Returns= 返回值用来验证函数是否成功执行 */ /* ----------------------------------------------------------------------------*/ int count_max_k_product(char a[], int I,int K,int index[]) { int i,j; int k_max[I][K] ; //k_max[i][j]表示1 ~ i十进制位分成j段所得的最大乘积 int sum =0, temp = 0; //分成一段 if (1 == K) { sum = intergration_num(a,1,I); return sum; }//假设先从最后一个数划分开,然后再乘上前面的k-1个不同划分的积， //找最大值，然后从倒数第二个数划分开，然后再乘上前面k-2个不同划分的积， //找到最大值，与前一个最大值比较得到最大值，然后从倒数第三个划分开，一 //次类推，直到倒数第I-(K-1)个数为止,for (i = I; i >= K; i--) { index[K-1] = i-1; //表示在第i-1个的数后面划分 temp = count_max_k_product(a,i-1,K-1, index,f) * intergration_num(a,i,I); if (sum < temp) { sum = temp; } }return sum; }int main(int argc, char *argv[]) { int info[2]; char a[ARRAY_SIZE]; int sum=0; int index[ARRAY_SIZE], fd[ARRAY_SIZE]; int i, j = 1; //其下为函数调用WriteFile(); ReadFile(a,info); sum = count_max_k_product(a,info[0],info[1],index); printf("%s分成%d段的最大乘积: %d\n",a+1,info[1],sum ); return EXIT_SUCCESS; }

【动态规划之最大k乘积】