C語言使用DP動(dòng)態(tài)規(guī)劃思想解最大K乘積與乘積最大問題
最大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 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() )!=' ') /*讀入數(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)在，請你幫助你的好朋友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 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)/*把數(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;
}
相關(guān)文章
數(shù)據(jù)結(jié)構(gòu) 棧的操作實(shí)例詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 順序棧的定義、初始化、空棧判斷、入棧、出棧操作的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)車票管理系統(tǒng)，連接數(shù)據(jù)庫MySQL，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的遍歷
本章將會(huì)詳細(xì)講解二叉樹遍歷的四種方式，分別為前序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷。在學(xué)習(xí)遍歷之前，會(huì)先帶大家回顧一下二叉樹的基本概念2022-02-02
這篇文章主要為大家詳細(xì)介紹了Qt自定義控件實(shí)現(xiàn)多彩色儀表盤，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
在進(jìn)行桌面應(yīng)用程序開發(fā)的時(shí)候，假設(shè)程序在某些情況要處理復(fù)雜邏輯， 如果一個(gè)線程去處理，就會(huì)導(dǎo)致窗口卡頓，無法處理用戶操作。這就需要使用多線程，其中一個(gè)線程處理窗口事件，其他線程進(jìn)行邏輯運(yùn)算，多個(gè)線程各司其職，不僅可以提高用戶體驗(yàn)還可以提升程序的執(zhí)行效率2022-09-09
C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
以下是對(duì)c語言中的雙鏈表進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-08-08
Qt5 串口類QSerialPort的實(shí)現(xiàn)
在Qt5以上提供了QtSerialPort模塊，方便編程人員快速的開發(fā)應(yīng)用串口的應(yīng)用程序。本文主要介紹了Qt5 串口類QSerialPort的實(shí)現(xiàn)，，感興趣的可以了解一下2022-05-05
C++11新特性之右值引用與完美轉(zhuǎn)發(fā)詳解
C++11標(biāo)準(zhǔn)為C++引入右值引用語法的同時(shí)，還解決了一個(gè)短板，即使用簡單的方式即可在函數(shù)模板中實(shí)現(xiàn)參數(shù)的完美轉(zhuǎn)發(fā)。本文就來講講二者的應(yīng)用，需要的可以參考一下2022-09-09
