C语言使用DP动态规划思想解最大K乘积与乘积最大问题
最大K乘积问题
设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。
编程任务:
对于给定的I 和k,编程计算I 的最大k 乘积。
需求输入:
输入的第1 行中有2个正整数n和k。正整数n是序列的长度;正整数k是分割的段数。接下来的一行中是一个n位十进制整数。(n<=10)
需求输出:
计算出的最大k乘积。
解题思路:DP
设w(h,k) 表示: 从第1位到第K位所组成的十进制数,设m(i,j)表示前i位(1-i)分成j段所得的最大乘积,则可得到如下经典的DP方程:
if(j==1) m(i,j) = w(1,i) ; if(j >=1 && j<=i) m(i,j) = max{m(d,j-1)*m(d+1,i)}
其中: 1<=d< i (即从1开始一直到i-1 中找最大值
else if(i < j) m(i,j) = 0 ;
代码示例:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 51 #define MAXK 10 long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/ long w[MAXN][MAXN]={{0,0}} ; void maxdp(int n,int k,int *a) { int i,j,d,h,q,t,s; long temp,max; for(i=1; i<= n ; i++) /*分成1段*/ m[i][1] = w[1][i]; for(i=1 ; i<= n ; i++) /* DP 过程*/ for(j=2; j<= k ; j++) { max = 0; for(d=1; d < i ; d++) if ( (temp = m[d][j-1]*w[d+1][i]) > max) max = temp ; m[i][j] = max ; } } int main(void) { int n,k,i,j; int a[MAXN]={0},la=0; char c ; scanf("%d %d ",&n,&k); while ( ( c=getchar() )!=' ') /*读入数据*/ { a[++la] = c-'0' ; } for(i=1 ; i<= n; i++) { w[i][i]= a[i] ; for(j=i+1 ; j<= n; j++) w[i][j] = w[i][j-1]*10 + a[j] ; } /* for(i=1 ; i<= n; i++) { for(j=1 ; j<= n; j++) printf("%d ",w[i][j]); printf(" "); } */ maxdp(n,k,a) ; printf("%ld ",m[n][k]) ; /*system("pause");*/ return 0; }
乘积最大问题:
(和最大k乘积问题差不多,都是用DP,不过有些细节要注意一下,比如:位数小于乘号,则为0)
描述 Description
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串: 312,当N=3,K=1时会有以下两种分法:
(1)3*12=36
(2)31*2=62
这时,符合题目要求的结果是: 31*2=62
现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
输入格式 Input Format
程序的输入共有两行:
1.第一行共有2个自然数N,K (6<=N<=40,1<=K<=6)
2.第二行是一个K度为N的数字串。
输出格式 Output Format
屏幕输出(结果显示在屏幕上),相对于输入,应输出所求得的最大乘积(一个自然数)。
解法: 典型的DP问题
设w(h,q)表示从h位开始的q位数字组合所成的十进制数,m(i,j)表示前i位数字串所得的最大j乘积,初始值为:
m(i,0) = w(1,q) ;
动规方程如下所示:
if (j==0) m(i,j) = w(1,q) ; else if(j>0) m(i,j) = max { m(d,j-1)*w(d+1,i-d) }
ps: 其中 1 <= d < i
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 51 #define MAXK 10 long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/ long my_10_pow(int t) { long sum=1 ; int y; for(y=1 ; y<= t ; y++) sum *= 10 ; return sum ; } long w(int start,int len,int *a)/*把数字串转换成对应的十进制数*/ { long res = 0 ; int t,f; for(f=start,t=len-1;t >= 0 ; f++,t--) res += a[f]*my_10_pow(t) ; return res ; } void maxdp(int n,int k,int *a) { int i,j,d,h,q,t,s; long temp,max; for(i=1; i<= n ; i++) m[i][0] = w(1,i,a) ; for(i=1 ; i<= n ; i++) /*DP 过程。。。。*/ for(j=1; j<= k ; j++) { max = 0; if( i <= j) /*如果长度小于乘号的个数,则值为0*/ m[i][j] = 0 ; else { for(d=1; d < i ; d++) if ( (temp = m[d][j-1]*w(d+1,i-d,a)) > max) max = temp ; m[i][j] = max ; } } } int main(void) { int n,k,i,j; int a[MAXN]={0},la=0; char c ; scanf("%d %d ",&n,&k); while ( ( c=getchar() )!=' ') /*读入数据*/ { a[++la] = c-'0' ; } maxdp(n,k,a) ; printf("max = %ld ",m[n][k]) ; system("pause"); return 0; }
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04