C++程序石子合并问题Word文件下载.docx
《C++程序石子合并问题Word文件下载.docx》由会员分享，可在线阅读，更多相关《C++程序石子合并问题Word文件下载.docx（10页珍藏版）》请在冰点文库上搜索。
1）、此题表面上看是用贪心算法比较合适，实则不然，用贪心算法是每次都合并得分最大的或最小的相邻两堆，但不一定保证余下的合并过程能导致最优解，聪明的读者马上会想到一种理想的假设：
如果N－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后的得分总和必然是最优的，这就是动态规划的思想。
采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。
这些石子堆子序列包括：
｛第１堆、第２堆｝、｛第２堆、第３堆｝、……、｛第N堆、第１堆｝；
｛第１堆、第２堆、第３堆｝、｛第２堆、第３堆、第４堆｝、……、｛第N堆、第１堆、第２堆｝；
……｛第１堆、……、第N堆｝｛第2堆、……、第N堆、第１堆｝……｛第N堆、第１堆、……、第N－１堆｝
为了便于运算，我们用〔i，j〕表示一个从第i堆数起，顺时针数j堆时的子序列｛第i堆、第i＋１堆、……、第（i＋j）堆｝（注意：
此时的i+j可能已经超出N的范围，为此我们在读入每堆石子的数量时，把石子堆数扩展为2*N-1，有a[i]=a[i+N]，没有a[N+N]）
它的最佳合并方案包括两个信息：
2该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；
②形成最佳得分和的子序列１和子序列２。
由于两个子序列是相邻的，因此只需记住子序列１的堆数；
读者可以从以下详细的程序代码中体会到算法的思想：
//StonesMerger.h
#ifndefSTONESMERGER_H
#defineSTONESMERGER_H
classStonesMerger
{
public:
StonesMerger（）;
~StonesMerger（）;
voidrun（）;
//运行接口
private:
intnumber;
//石子的堆数
inttotalMax;
//记录合并成一堆的最大得分
intX;
//记录合并成一堆的最大得分的最优合并的起始堆
inttotalMin;
//记录合并成一堆的最小得分
intY;
//记录合并成一堆的最小得分的最优合并的起始堆
int*a;
//存储石子的数量
int**MAX;
//记录子序列合并最大得分
int**Smax;
//记录子序列合并最大得分的最佳断开位置
int**min;
//记录子序列合并最小得分
int**smin;
//记录子序列合并最小得分的最佳断开位置
boolinput（）;
//输入接口读取input.txt文件
voidmostValue（）;
//以第i堆开始合并后面的j堆j=0、1、2、......、n-1
voidoutput（）;
//输出显示
voidtraceback（int**s,intn,intm）;
//对应于Smax[n][m]或smin[n][m]寻找轨迹
};
#endif
//StonesMerger.cpp
#include<
iostream.h>
fstream.h>
cstdlib>
iomanip.h>
#include"
StonesMerger.h"
ifstreaminputFile（"
input.txt"
ios:
:
in）;
ofstreamoutputFile（"
output.txt"
out）;
#defineN100//根据实际问题规模大小设定恰当的初值
StonesMerger:
StonesMerger（）
number=0;
X=0;
Y=0;
totalMax=0;
totalMin=0;
a=newint[2*N];
MAX=newint*[2*N];
Smax=newint*[2*N];
min=newint*[2*N];
smin=newint*[2*N];
for（inti=0;
i<
2*N;
i++）
{
MAX[i]=newint[2*N];
Smax[i]=newint[2*N];
min[i]=newint[2*N];
smin[i]=newint[2*N];
}
}
~StonesMerger（）
delete[]a;
delete[]MAX[i];
delete[]Smax[i];
delete[]min[i];
delete[]smin[i];
delete[]MAX;
delete[]Smax;
delete[]min;
delete[]smin;
voidStonesMerger:
run（）//运行接口
if（input（））
mostValue（）;
output（）;
boolStonesMerger:
input（）
if（!
inputFile）
cerr<
<
"
input.txtcouldnotbeopened."
endl;
exit
（1）;
outputFile）
output.txtcouldnotbeopened."
inputFile>
>
number;
outputFile<
石子堆数为:
"
number<
各堆石子数量（堆编号为1-"
）:
;
for（inti=1;
=number;
inputFile>
a[i];
a[i+number]=a[i];
outputFile<
setw
（2）<
a[i]<
if（a!
=NULL）
returntrue;
returnfalse;
output（）
最小得分为:
totalMin<
traceback（smin,Y,number）;
最大得分为:
totalMax<
traceback（Smax,X,number）;
mostValue（）//寻找最优断开位置和最大/最小子序列
=2*number-1;
MAX[i][1]=0;
//只有一堆不用合并得分为0
min[i][1]=0;
for（intr=2;
r<
r++）//r为合并的石子堆数，r==1，为当前一堆不合并得分为0，r==2，合并后面的一堆
for（inti=1;
=2*number-r;
i++）//以第i堆开始合并r堆
{
intt=0;
intj=i;
for（intm=1;
m<
=r;
m++）
{
t+=a[j];
j++;
}
MAX[i][r]=MAX[i][1]+MAX[i+1][r-1]+t;
//r对合并最后一次的得分为原始r堆的总和
Smax[i][r]=1;
min[i][r]=min[i][1]+min[i+1][r-1]+t;
smin[i][r]=1;
for（intk=2;
k<
r;
k++）
intT1=MAX[i][k]+MAX[i+k][r-k]+t;
intT2=min[i][k]+min[i+k][r-k]+t;
if（T2<
min[i][r]）
{
min[i][r]=T2;
//确保子序列最优记录最优断开位置
smin[i][r]=k;
}
if（T1>
MAX[i][r]）
MAX[i][r]=T1;
Smax[i][r]=k;
}
for（i=1;
if（MAX[i][number]>
totalMax）//寻找最大得分并记录最大得分的序列的起始位置
{
totalMax=MAX[i][number];
X=i;
totalMin=totalMax;
if（min[i][number]<
totalMin）//寻找最大得分并记录最大得分的序列的起始位置
totalMin=min[i][number];
Y=i;
traceback（int**s,inti,intr）//寻找轨迹
if（r==1）
A"
（i>
number?
i%number:
i）;
elseif（r==2）
outputFile<
（A"
i）<
（（i+1）>
（i+1）%number:
（i+1））<
）"
else
（"
StonesMerger:
traceback（s,i,s[i][r]）;
traceback（s,i+s[i][r],r-s[i][r]）;
//main,cpp
intmain（）
StonesMergersm;
sm.run（）;
return0;
升级会员 