C語言使用DP動態(tài)規(guī)劃思想解最大K乘積與乘積最大問題
最大K乘積問題
設(shè)I是一個n位十進(jìn)制整數(shù)。如果將I劃分為k段，則可得到k個整數(shù)。這k個整數(shù)的乘積稱為I的一個k乘積。試設(shè)計一個算法，對于給定的I和k，求出I的最大k乘積。
編程任務(wù)：
對于給定的I 和k，編程計算I 的最大k 乘積。
需求輸入：
輸入的第1 行中有2個正整數(shù)n和k。正整數(shù)n是序列的長度；正整數(shù)k是分割的段數(shù)。接下來的一行中是一個n位十進(jìn)制整數(shù)。（n<=10）
需求輸出：
計算出的最大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ù)小于乘號，則為0)
描述 Description
今年是國際數(shù)學(xué)聯(lián)盟確定的“2000——世界數(shù)學(xué)年”，又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
設(shè)有一個長度N的數(shù)字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：
有一個數(shù)字串: 312，當(dāng)N=3，K=1時會有以下兩種分法：
（1）3*12=36
（2）31*2=62
這時，符合題目要求的結(jié)果是： 31*2=62
現(xiàn)在，請你幫助你的好朋友XZ設(shè)計一個程序，求得正確的答案。
輸入格式 Input Format
程序的輸入共有兩行：
1.第一行共有2個自然數(shù)N，K (6<=N<=40，1<=K<=6)
2.第二行是一個K度為N的數(shù)字串。
輸出格式 Output Format
屏幕輸出(結(jié)果顯示在屏幕上)，相對于輸入，應(yīng)輸出所求得的最大乘積（一個自然數(shù)）。
解法： 典型的DP問題
設(shè)w(h,q)表示從h位開始的q位數(shù)字組合所成的十進(jìn)制數(shù),m(i,j)表示前i位數(shù)字串所得的最大j乘積,初始值為：
m(i,0) = w(1,q) ;
動規(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)換成對應(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) /*如果長度小于乘號的個數(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ù)據(jù)結(jié)構(gòu) 順序棧的定義、初始化、空棧判斷、入棧、出棧操作的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)車票管理系統(tǒng)，連接數(shù)據(jù)庫MySQL，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的遍歷
本章將會詳細(xì)講解二叉樹遍歷的四種方式，分別為前序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷。在學(xué)習(xí)遍歷之前，會先帶大家回顧一下二叉樹的基本概念2022-02-02
這篇文章主要為大家詳細(xì)介紹了Qt自定義控件實現(xiàn)多彩色儀表盤，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
在進(jìn)行桌面應(yīng)用程序開發(fā)的時候，假設(shè)程序在某些情況要處理復(fù)雜邏輯， 如果一個線程去處理，就會導(dǎo)致窗口卡頓，無法處理用戶操作。這就需要使用多線程，其中一個線程處理窗口事件，其他線程進(jìn)行邏輯運算，多個線程各司其職，不僅可以提高用戶體驗還可以提升程序的執(zhí)行效率2022-09-09
C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
以下是對c語言中的雙鏈表進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-08-08
在Qt5以上提供了QtSerialPort模塊，方便編程人員快速的開發(fā)應(yīng)用串口的應(yīng)用程序。本文主要介紹了Qt5 串口類QSerialPort的實現(xiàn)，，感興趣的可以了解一下2022-05-05
C++11新特性之右值引用與完美轉(zhuǎn)發(fā)詳解
C++11標(biāo)準(zhǔn)為C++引入右值引用語法的同時，還解決了一個短板，即使用簡單的方式即可在函數(shù)模板中實現(xiàn)參數(shù)的完美轉(zhuǎn)發(fā)。本文就來講講二者的應(yīng)用，需要的可以參考一下2022-09-09
