最大K乘積問題
設(shè)I是一個(gè)n位十進(jìn)制整數(shù)。如果將I劃分為k段，則可得到k個(gè)整數(shù)。這k個(gè)整數(shù)的乘積稱為I的一個(gè)k乘積。試設(shè)計(jì)一個(gè)算法，對(duì)于給定的I和k，求出I的最大k乘積。
編程任務(wù)：
對(duì)于給定的I 和k，編程計(jì)算I 的最大k 乘積。
需求輸入：
輸入的第1 行中有2個(gè)正整數(shù)n和k。正整數(shù)n是序列的長度；正整數(shù)k是分割的段數(shù)。接下來的一行中是一個(gè)n位十進(jìn)制整數(shù)。（n<=10）
需求輸出：
計(jì)算出的最大k乘積。
解題思路：DP
設(shè)w(h,k) 表示: 從第1位到第K位所組成的十進(jìn)制數(shù),設(shè)m(i,j)表示前i位(1-i)分成j段所得的最大乘積,則可得到如下經(jīng)典的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 10long 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() )!=' ') /*讀入數(shù)據(jù)*/ { 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，不過有些細(xì)節(jié)要注意一下，比如：位數(shù)小于乘號(hào)，則為0)
描述 Description
今年是國際數(shù)學(xué)聯(lián)盟確定的“2000――世界數(shù)學(xué)年”，又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動(dòng)，你的一個(gè)好朋友XZ也有幸得以參加。活動(dòng)中，主持人給所有參加活動(dòng)的選手出了這樣一道題目：
設(shè)有一個(gè)長度N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲蟆?br />同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：
有一個(gè)數(shù)字串: 312，當(dāng)N=3，K=1時(shí)會(huì)有以下兩種分法：
（1）3*12=36
（2）31*2=62
這時(shí)，符合題目要求的結(jié)果是： 31*2=62
現(xiàn)在，請(qǐng)你幫助你的好朋友XZ設(shè)計(jì)一個(gè)程序，求得正確的答案。
輸入格式 Input Format
程序的輸入共有兩行：
1.第一行共有2個(gè)自然數(shù)N，K (6<=N<=40，1<=K<=6)
2.第二行是一個(gè)K度為N的數(shù)字串。
輸出格式 Output Format
屏幕輸出(結(jié)果顯示在屏幕上)，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。
解法： 典型的DP問題
設(shè)w(h,q)表示從h位開始的q位數(shù)字組合所成的十進(jìn)制數(shù),m(i,j)表示前i位數(shù)字串所得的最大j乘積,初始值為：
m(i,0) = w(1,q) ;
動(dòng)規(guī)方程如下所示：
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 10long 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)/*把數(shù)字串轉(zhuǎn)換成對(duì)應(yīng)的十進(jìn)制數(shù)*/{ 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) /*如果長度小于乘號(hào)的個(gè)數(shù)，則值為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() )!=' ') /*讀入數(shù)據(jù)*/ { a[++la] = c-'0' ; } maxdp(n,k,a) ; printf("max = %ld ",m[n][k]) ; system("pause"); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
