石子合并 动态规划
有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。
此类问题比较简单，就是哈夫曼编码的变形，用贪心算法即可求得最优解。即每次选两堆最少的，合并成新的一堆，直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。
#include
#include
#include
#include
using namespace std;
#define MAXN 100
int sum[MAXN];
int mins[MAXN][MAXN], maxs[MAXN][MAXN];
int n, stone[MAXN];
int sums(int i, int j)
{
if(i + j >= n)
{
return sums(i, n - i - 1) + sums(0, (i + j) % n);
}
else
{
return sum[i + j] - (i > 0 ? sum[i - 1] : 0);
}
}
void getBest(int& minnum, int& maxnum)
{
//初始化，没有合并，花费为0
for(int i = 0; i < n; ++i)
{
mins[i][0] = maxs[i][0] = 0;
}
//还需进行合并次数
for(int j = 1; j < n; ++j)
{
for(int i = 0; i < n; ++i)
{
mins[i][j] = INT_MAX;
maxs[i][j] = 0;
for(int k = 0; k < j; ++k)
{
mins[i][j] = min(mins[i][k] + mins[(i + k + 1)%n][j - k - 1] + sums(i, j), mins[i][j]);
maxs[i][j] = max(maxs[i][k] + maxs[(i + k + 1)%n] [j - k - 1] + sums(i, j), maxs[i][j]);
}
}
}
minnum = mins[0][n - 1];
maxnum = maxs[0][n - 1];
for(int i = 0; i < n; ++i)
{
minnum = min(minnum, mins[i][n - 1]);
maxnum = max(maxnum, maxs[i][n - 1]);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", &stone[i]);
sum[0] = stone[0];
for(int i = 1; i < n; ++i)
{
sum[i] = sum[i - 1] + stone[i];
}
int minnum, maxnum;
getBest(minnum, maxnum);
printf("%d\n%d\n", minnum, maxnum);
return 0;
}
上面代码复杂度是O（n^3)，n为石子堆数目，那么还有没有复杂度更低的方法呢？有的。也是使用动态规划，由于过程满足平行四边形法则，优化后可以将复杂度降为O（n^2)。
石子合并问题报告
石子合并(动态规划)详细解题报告2007-02-25 14:58
一．试题 在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 编一程序，由文件读入堆数N及每堆的石子数（≤２０）， ①选择一种合并石子的方案，使得做N－1次合并，得分的总和最小； ②选择一种合并石子的方案，使得做N－1次合并，得分的总和最大。 例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３ 得分最大的方案为：１４＋１８＋２２＝５４ 输入数据： 文件名由键盘输入，该文件内容为： 第一行为石子堆数N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为output.txt 从第1至第N行为得分最小的合并方案。第N＋1行是空行。从第N＋2行到第2N＋1行是得 分最大合并方案。 每种合并方案用N行表示，其中第i行（1≤i≤N）表示第i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。要求将待合并的两堆石子数以相应的负数表示，以便标识。 输入输出范例：
输入文件内容： ４ ４５９４ 输出文件内容： －４５９－４ －８－５９ －１３－９ ２２ ４－５－９４ ４－１４－４ －４－１８ ２２ 二．算法分析 竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面 的一堆开始，沿顺时针方向排成一个序列。第一次选得分最小（最大）的相邻两堆合并，形成新的一堆；接下来，在N－1堆中选得分最小（最大）的相邻两堆合并……，依次类推，直至所有石子经N－1次合并后形成一堆。 例如有６堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为３４６５４２
算法设计题目
第2章 1、大整数乘法的O(nm log(3/2))算法 给定2个大整数u和v，它们分别有m位和n位数字，且mn。用通常的乘法求uv的值需要O(mn)时间。可以u和v均看作是有n 位数字的大整数，用教材第2章介绍的分治法，在O(n l og3)时间内计算uv的值。当m比n小得多时，用这种方法就显得效率不够高。试设计一个算法，在上述情况下用O(nm l og(3/2))时间求出uv的值。 2、O(1)空间子数组换位算法 设a[0:n-1]是一个有n个元素的数组，k(1kn-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。 3、段合并排序算法 如果在合并排序算法的分割步骤中，将数组a[0:n-1]划分为个子数组，每个子数组中有O()个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要的排好序的数组a[0:n-1]。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 4、合并排序算法 对拨给元素存储于数组和存储于链表中的2种情形，写出合并排序算法。 5、非增序快速排序算法 如何修改QuickSort才能使其将输入元素按非增序排序？
第三章 1、整数线性规划问题 考虑下面的整数线性规划问题 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。2、Ackermann函数 Ackermann函数A(m,n)可递归地定义如下： A（m，n）= 试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。 3、独立任务最优调试问题 问题描述：用2台机A和B处理n个作业。设第i个作业交给机器A 处理时需要时间a i，若由机器B来处理，则需要时间b i。由于各作业的选战和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有a iDP问题不完全总结
DP问题不完全总结 1.按状态类型分写在前面： 从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。 1.1.编号(长度)动态规划共性总结 本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。 一般来说，有两种编号的状态： 状态(i)表示前i个元素决策组成的一个状态。 状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。 题库 a)最长不下降子序列 以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。关于优化详见优化章。 一些问题可将数据有序化，转化成本题。 应用： 拦截导弹(NOIP99 Advance 1)就是原题。 Beautiful People(sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。
Segment(ural 1078)，将线段的左端点有序化就可以了。 b)LCS 状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。若有多个串要LCS，则加维，即几个串就几个维。我也将此题归入路径问题。 c)花店橱窗布置(IOI99) 见路径问题。 1.2.区间动态规划共性总结 本类问题与下一章的划分问题的决策的分割点无序交集比较大(占本类问题的30%)。 题库 a)石子合并 见划分问题 b)模版匹配(CEOI01,Patten) 这题特殊的地方是状态的值是一个集合而不是一个数。 c)不可分解的编码(ACM World Final 2002) d)Electric Path(ural1143) e)邮局(IOI2000 Day2 1) 若状态表示的思路从第i个村庄可以从属于哪个邮局，无最优子结构。转变一个方向：第k个邮局可以"控制"一个区间的村庄[i,j]。于是方程就显然了： f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1=p=i-1)
动归详解
动归详解 童仁伟 2010.2.1 嗯···我学动归不是很久，同样是迷惘过，估计两个月前刚刚开窍…… 你看他写的什么无后效性什么最优子结构的就头大，我也头大%………… 动态规划一般解决两类问题，一类是最优化问题,就是问你最大价值最小数什么的，另一类是方案总数问题。 细分的话类型很多， 我见得多的（我是高二学生，目前在筹备NOIP） （你那题多我就只说名字了） 背包，楼上连9讲都放上来了我就不多说了…… 最长不上升不下降子序列问题（比如说潘帕斯雄鹰生日模拟赛的飞翔，就是很经典的不下降的变形） 资源分配问题（比如说橱窗布置，马棚问题，机器分配问题） 区间动归（乘积最大，能量项链等等） 最长公共子序列问题（有个遗传编码好像）； 解决方案树的比如说爬楼梯问题…………………… 动态规划的类型很多很多，因为他很灵活的，我们老师曾经给我们找了100个DP方程，但是那都没有用，强记根本记不住，关键是理解。 深入一点的就有DP的优化，时间空间的降维（就是用别的方法去做，或者比如说背包本来是二维的空间优化过该成一维的了），树形DP（这个我也不会）。 （优化里面有个很经典的题《过河》） 我对DP是属于那种突然就开了窍的……别看说“动态规划”什么的唬人，其实就是一个比较一个计算，知道他干什么了题上来就有头绪，方程啊思想啊就有了…… 主要也是多看题吧，从简单的开始，理解他的思想……自己写动归的时候注意下面几个问题：1、大前提是确定你做的是动归题……看得多了也就知道自己面对的是什么类型的题了
2、次前提是想法要对（我做题的时候先想这道题时间空间的维度，然后根据这个去想方程），方程正确， 实在想不起来可以先看题解，去理解人家的思想之后，不要看标程把程序做出来……3、注意数组不要开的过小，一般都是左右都开大一点，比如他的数据范围是1~100，数组就开0~101.这个是防越界的，因为很多DP赋初值的时候会用到F[0],F[0,0] 4、初始值要正确，因为很多DP其他地方都是正确的因为初始值赋错了而全部过不了的情况是很常见的……（比如说USACO里面的货币系统） 5、DP循环的范围要正确，一般根据题来判断范围写多少的（比如说橱窗问题，今天下午写这个题因为循环写错了一直AC不了） USACO里也有很多DP题，可以做…… 以上全部手打，希望能对你有所帮助。 我也是正在学习的人，上面的东西不一定全部正确，但是对我而言很受用，也算是我的经验了。希望日后能一起学习交流外加进步喽 QQ：340131980 1.资源问题1 -----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2.资源问题2 ------01背包问题 F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]); 3.线性动态规划1 -----朴素最长非降子序列 F:=max{f[j]+1} 4.剖分问题1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5.剖分问题2 -----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a);
在一个圆形操场的四周摆放着n堆石子现要将石子有次序地
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。 #include
国家集训队2001论文集 毛子青
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。
poj刷题专题训练3
（一）：用的比较多的 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019,poj1942)
石子合并问题
石子合并问题 在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。分析： 假设有n堆石子需要合并,可以设计一个2*n-1个元素的数组来存储每堆石子的个数。 分析最优解的结构：假设有石头AiAi+1……Aj需要合并,简记为A[i,j].如果设最后一次合并发生在Ak与Ak+1之间(i<=k 石子合并(动态规划)详细解题报告 2007-02-25 14:58 一．试题 在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 编一程序，由文件读入堆数N及每堆的石子数（≤２０）， ①选择一种合并石子的方案，使得做N－1次合并，得分的总和最小； ②选择一种合并石子的方案，使得做N－1次合并，得分的总和最大。 例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３ 得分最大的方案为：１４＋１８＋２２＝５４ 输入数据： 文件名由键盘输入，该文件内容为： 第一行为石子堆数N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为 从第1至第N行为得分最小的合并方案。第N＋1行是空行。从第N＋2行到第2N＋1行是得 分最大合并方案。 每种合并方案用N行表示，其中第i行（1≤i≤N）表示第i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。要求将待合并的两堆石子数以相应的负数表示，以便标识。 输入输出范例： 输入文件内容： ４ ４５９４ 输出文件内容： －４５９－４ －８－５９ －１３－９ ２２ ４－５－９４ ４－１４－４ －４－１８ ２２ 二．算法分析 竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面 的一堆开始，沿顺时针方向排成一个序列。第一次选得分最小（最大）的相邻两堆合并，形成新的一堆；接下来，在N－1堆中选得分最小（最大）的相邻两堆合并……，依次类推，直至所有石子经N－1次合并后形成一堆。 石子合并问题 (2011-11-14 21:06:38) 描述：在一条直线上摆着N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小 解析： 采用动态递归，运用矩阵连乘思想即可解答此类题目 源程序： #include } } min=m[0][n-1]; return min; } int main() { int i,j,q; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &stone[i]); for(i=0;i 算法竞赛专题解析│四边形不等式优化 01理论背景 四边形不等式（quadrangleinequality）应用于DP优化，是一个古老的知识点。它起源于Knuth（高纳德）1971年的一篇论文，用来解决最优二叉搜索树问题。1980年，储枫（F.FrancesYao，姚期智的夫人）做了深入研究，扩展为一般性的DP优化方法，把一些复杂度O(n3)的DP问题，优化为O(n2)。所以这个方法又被称为“Knuth-YaoDPSpeedupTheorem”。 02应用场合 有一些常见的DP问题，通常是区间DP问题，它的状态转移方程是： dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i][j])其中i<=k 一、数学问题： 1、素数判断 a、判断一个数是不是素数 b、利用筛选法，求出2----1000000中素数的个数。 2、最大公约数 3、最小公倍数 4、素因数分解 二、数据处理： 1、数据查找：顺序查找、二分（折半）查找,查找第k小元素。 2、甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆可带一人的小车。又甲、乙两人步行速度相同。问，怎样利用小车才能使两人尽快同时到达。 输入：S=120 (AB两地之间的距离) a = 5 （步行速度）b = 25 (汽车速度) 输出：T= 9.60 输入：S=200 (AB两地之间的距离) a = 30 （步行速度）b = 50 (汽车速度) 输出：T= 5.143 3、数据插入：顺序插入、二分插入 4、排序：冒泡排序、选择排序、插入排序、快速排序 归并排序（提高组）、堆排序（提高组）、希尔排序（提高组） 5、数据合并：两个有序数组归并为一个有序数组（相同数据只取一个） 6、多项式。输入两个多项式的系数和指数，求两个多项式的和。 7、矩阵： a、矩阵相乘 b、稀疏矩阵的存储，相乘 三、高精度运算 1、任意进制转换 2、高精度四则运算 加、减、乘（高精*单精，高精*高精）、除法（高精/高精，高精/单精） 四、字符串 1、子串：求一个字符串的所有子串 2、回文数的判断 3、统计文章中单词的数目 五、数据模拟 1、约瑟夫问题（用静态指针模拟） 有编号为1，2…n的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码开始给定一个正整数m，从第一人按顺时针方向自1开始顺序报数，报到m者出围坐的圈子，不在参加报数，这时将出列者的密码作为m，出列者顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人都出围坐。 请编写程序输出出列的顺序。 e.g： 1 2 3 4 5 {围坐者的序号} 8 7 3 6 5{围坐者的密码} 初始态：m=18 当报数到序号为3的人时，应该出列，结果： 1 2 4 5 {围坐者的序号} 8 7 6 5{密码} 此时m=3，从4号开始报数…… 答案：出列的顺序：3 1 4 2 5 2、奇数幻方 设有n*n 方格的棋盘（n为奇数），将1，2，…..n*n个数填入到棋盘中，使所有的行、列、对角线的和都相等。 例如：N=3 采用对角线走向的算法 步骤1：1 的位置是(n div 2 +1, n ) 步骤2：若a[i,j] = k ，k+1的位置在k的右下角，如果右下角已经有数据，则放在k同一行的前一个位置；如果行溢出，则将其行号改为1；如果列溢出，则将其列号改为1;如果行列同时溢出，则放在k同一行的前一个位置。 六、排列组合问题 1、全排列非递归算法。1…N的全排列。（元素不重复） 组合的非递归算法。 2、1..n中选m个元素的递归算法。（元素不重复） 输入:m,n 输出：总个数、各种组合（排列） 3、n个元素中最多、最少取m个的排列、组合 4、全组合算法。 砝码称重：设有1g，2g,，5g,，10g，20g，50g的砝码个数分别为3 ，4，5，0，2，7，问用这些砝码可称出多少种不同的重量。 5、n个元素中取m个的排列、组合（n个元素可重复，元素重复个数不定）。 编著说明 本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。 本书共分8～10个实验，其具体要求和步骤如下： 目录 实验一、C/C++环境及递归算法...................................... 错误！未定义书签。实验二、递归与分治策略.. (5) 实验三、动态规划算法（一） (9) 实验四、动态规划算法（二） (12) 实验五、贪心算法（一） (15) 实验六、贪心算法（二） (17) 实验七、回溯法（一） (20) 实验八、回溯算法（二） (22) 实验九、分支限界法 (24) 实验十：随机化算法（选学） (29) 实验二、递归与分治策略 一、实验目的与要求 1、进一步熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归与分治策略的理解和运用； 二、实验内容： 1、分析并掌握“棋盘覆盖问题”的递归与分治算法示例； 2、分析并掌握“二分搜索问题”的递归与分治算法示例； 3、练习使用递归与分治策略求解众数问题或集合划分问题； 三、实验题 众数问题：给定含有N个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中重数最大的元素称为多重集合S的众数，众数的重数称为多重集合S的重数，试求一个给定多重结合的重数和众数； 例如：S={a,b,b,b,f,f,4,5}的重数是3，众数是b 集合划分问题：N个元素的集合{1，2，…，N}可以划分为若干个非空集合的子集，例如，当N=4时，集合{1，2，3，4}可划分为15个不同的非空子集如下：{{1}，{2}，{3}，{4}}；{{1，2}，{3}，{4}}；{{1，3}，{2}，{4}}； {{1，4}，{2}，{3}}；{{2，3 }，{1}，{4}}；{{2，4}，{1}，{3 }}； {{3，4 }，{1}，{2}}；{{1，2 }，{3，4}}；{{1，3 }，{2，4}}； {{1，4 }，{3，2 }}；{{2，3，4}，{1}}；{{1，3，4}，{2}}； {{1，2，4}，{3}}；{{1，2，3}，{4}}；{{1，2，3，4}}； 给定正整数N，计算出N个元素的集合{1，2，…，N}可以划分多少个非空集合的子集； 四、实验步骤 1．理解递归和分治策略的基本思想和算法示例； 2．上机输入和调试算法示例程序； 3．理解实验题的问题要求； 应用一图论算法 图论在计算机处理问题中占有重要地位，现实中的很多问题最终都可以转化成图论问题，或者要借助图结构来存储和处理。但是怎么把一图存入计算机就要涉及到数学建模的知识。 比如下面一图： 如果要求出从节点v1到节点v5的所有路径，就可以借助计算机来很轻松的解决。但前提条件是，必须要把图以一种计算机可以理解的形式存进去，即要把它抽象为数学问题。 在此，我们需要定义一些关于图的概念，以便更好的描述问题。 边与顶点的关系有如下几种典型情况： 简单图：无自回环，无重边的图。 无向图：边没有指向， 1212 e. i i i i i ψ（）={v,v}=v v此时称边e i与顶点12 i i v,v关联，称 顶点 1 i v与顶点 2 i v邻接。 有向图:边有指向， 1212 e. i i i i i ψ（）=（v,v）=v v 下面是具体涉及到图如何存储的问题： 1.图G(V,E)的关联矩阵x R=(r) ij n m ，若G(V,E)为无向图， 1 2 i j ij i j j i j j v e r v e e v e e ? ? =? ? ? 与不关联 与关联,为非自回环 与关联,为自回环 若G(V,E)为有向图， 1 2 i j ij i j i j v e r v e v e ? ? =? ? ? 与不关联 是的起点 是的终点 因此该图可以用关联矩阵表示出来，如下所示 1100000 1010100 0101001 0011010 0000111 R ?? ? ? ? = ? ? ? ?? 这样，我们就可以以矩阵的形式将图存入计算机 2. 邻接矩阵 图G(V,E)的邻接矩阵xn A=(a )ij n ,若G(V,E)为无向图，ij a =从 i v 到的j v 边数，若不邻接，取0；若G(V,E)为有向图，ij a =从 i v 到j v 的有向边数，若无，取0. 01100100111 00110110101110A ?? ? ? ? = ? ? ?? ? 应用二 动态规划问题 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman 等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。也是信息学竞赛中选 《算法设计与分析》教学大纲 一、课程的性质、目的与任务 （一）课程说明 课程编号：200556220 学分：4学分 总学时：64学时，学时分配：讲课32学时实验32学时 适用专业：计算机科学信息管理专业 （二）课程的性质、目的与任务 本课程是计算机科学信息管理专业的一门专业必修课程。课程的任务是使学生掌握Java程序设计语言，理解面向对象程序设计的思路和方法，掌握网络编程的基本技术，培养学生的编程能力，养成良好编码的习惯，为将来参与实际项目的开发奠定坚实的基础。 开设本课程的目的是让学生掌握这一在科研和市场应用方面非常重要的语言及其技术；通过本课程使学生掌握java技术的核心概念，编程方法；培养学生掌握面向对象的思想和程序设计方法；完成本课程的学习后能够熟练的、综合应用Java技术和面向对象的思想编写程序解决现实生活中的问题。 二、教学的基本要求 1.本课程强调理论和实践并重的原则，建议采用案例教学法、项目教学法。 2.为加强和落实动手能力的培养，每章课后应安排作业，作业应让学生尽 可能在Textpad环境下进行,要提交源代码。 3.要采用多媒体教学手段来进行教学。 4.如条件许可，应利用网络技术进行授课、答疑和讨论。 三、与其它课程的关系 其先行课程有：高等数学、计算机基础、C语言程序设计、数据结构。 四、本课程教学的重点、难点及教学中应注意的问题 （一）本课程教学重点 图形化用户界面程序、Applet程序。 （二）本课程教学难点 类与对象的概念，事件处理机制，Applet程序的开发，多线程。 （三）本课程教学应注意的问题 本课程教学应注意的问题是要将理论来源于实践，理论指导实践、理论与实践的结合，着重掌握运用Java解决问题。 五、教学进程安排 总学时：64学时。本课教学进度建议以下表分配，但可根据具体情况进行适当调整。 章序内容讲授时数实验时数总时数一Java语言概述 2 2 4 二Java语言基础 2 2 4 三java语言程序结构 2 2 4 四面向对象（-） 4 6 10 五面向对象（二） 4 4 8 六Java异常处理 6 6 12 七java图形界面编程 4 4 8 八Java多线程技术 4 4 8 九网络编程技术 4 2 6 总计32 32 64 六、教学内容要点与教学目标 第一章 Java语言概述 一、学习目的要求 1.了解java 的发展， 2.掌握java的特点， 3.掌握Java的运行机制， 4.掌握Java虚拟机的作用 5.了解常用的开发环境， 6.掌握简单的Java程序开发方法。 《算法设计与分析》课程实验与设计 福州大学王晓东 第1章算法引论 算法实现题1-1 统计数字问题 算法实现题1-2 字典序问题 算法实现题1-3 最多约数问题 算法实现题1-4 金币阵列问题 算法实现题1-5 最大间隙问题 第2章递归与分治策略 算法实现题2-1 输油管道问题 算法实现题2-2 众数问题 算法实现题2-3 邮局选址问题 算法实现题2-4 马的Hamilton周游路线问题 算法实现题2-5 半数集问题 算法实现题2-6 半数单集问题 算法实现题2-7 士兵站队问题 算法实现题2-8 有重复元素的排列问题 算法实现题2-9 排列的字典序问题 算法实现题2-10 集合划分问题 算法实现题2-11 集合划分问题2 算法实现题2-12 双色Hanoi塔问题 算法实现题2-13 标准2维表问题 算法实现题2-14 整数因子分解问题 算法实现题2-15 有向直线2中值问题 第3章动态规划 算法实现题3-1 独立任务最优调度问题 算法实现题3-2 最少硬币问题 算法实现题3-3 序关系计数问题 算法实现题3-4 多重幂计数问题 算法实现题3-5 编辑距离问题 算法实现题3-6 石子合并问题 算法实现题3-7 数字三角形问题 算法实现题3-8 乘法表问题 算法实现题3-9 租用游艇问题 算法实现题3-10 汽车加油行驶问题 算法实现题3-11 圈乘运算问题 算法实现题3-12 最少费用购物 算法实现题3-13 最大长方体问题 算法实现题3-14 正则表达式匹配问题 算法实现题3-15 双调旅行售货员问题 算法实现题3-16 最大k乘积问题 算法实现题3-17 最小m段和问题 算法实现题3-18 红黑树的红色内结点问题 第4章贪心算法 算法实现题4-1 会场安排问题 算法实现题4-2 最优合并问题 算法实现题4-3 磁带最优存储问题 算法实现题4-4 磁盘文件最优存储问题 动态规划案例 【石子合并】 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 【输入文件】 包含两行，第1 行是正整数n（1<=n<=100），表示有n堆石子。 第2行有n个数，分别表示每堆石子的个数。 【输出文件】 输出两行。 第1 行中的数是最小得分；第2 行中的数是最大得分。 【输入样例】【输出样例】 4 43 4 4 5 9 54 【分析】 本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子： 6 3 4 6 5 4 2 如果使用贪心法求最小得分，应该是如下的合并步骤： 第一次合并3 4 6 5 4 2 2,3合并得分是５ 第二次合并5 4 6 5 4 5,4合并得分是9 第三次合并9 6 5 4 5,4合并得分是9 第四次合并9 6 9 9,6合并得分是15 第五次合并15 9 15,9合并得分是24 总得分＝5＋9＋9＋15＋24＝62 但是如果采用如下合并方法，却可以得到比上面得分更少的方法： 第一次合并3 4 6 5 4 2 3,4合并得分是7 第二次合并7 6 5 4 2 7,6合并得分是13 第三次合并13 5 4 2 4,2合并得分是6 第四次合并13 5 6 5,6合并得分是11 第五次合并13 11 13,11合并得分是24 总得分＝7＋13＋6＋11＋24＝61 由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为13和11的相邻两堆。这两堆石头分别由最初的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2次合并的得分总和最优。为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１，第３堆为子序列２。第一次合并子序列１中的两堆，得分７；第二次再将之与子序列２的一堆合并，得分13。显然对于第１个子序列来说，这样的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列１，第５，６堆构成子序列２。第三次合并子序列２中的２堆，得分６；第四次再将之与子序列１中的一堆合并，得分13。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得出一个结论──６堆石子经过这样的５次合并后，得分的总和最小。 动态规划思路： 阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案 具体来说我们应该定义一个数组s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。 对于上面的例子来说，初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开始还没有合并，所以这些值应该全部为0。 动态规划入门练习题 1.石子合并 在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (1)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5 9 4 输出: －４５９－４ －８－５９ －１３－９ ２２４－５－９４ ４－１４－４ －４－１８ ２２ 最小代价子母树设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小. 输入、输出数据格式与“石子合并”相同。 输入样例： 4 12 5 16 4 输出样例： －１２－５１６４ １７－１６－４ －１７－２０ ３７ 2.背包问题 设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。 输入数据： 第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔； 第二行N个数,为Ｎ种物品重量；两个数用空格分隔； 第三行N个数,为N种物品价值; 两个数用空格分隔； 输出数据： 第一行总价值； 以下N行，每行两个数，分别为选取物品的编号及数量； 输入样例： 4 10 2 3 4 7 1 3 5 9 输出样例： 12 2 1 4 1 3.商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU 因为: 1朵花加2个花瓶: 优惠价:10 ICU 2朵花正常价: 4 ICU 输入数据 用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。两个文件中都只用整数。 第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。 第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。 输出数据 在输出文件OUTPUT．TXT中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）石子合并问题报告
石子合并问题(矩阵连乘求解)
算法竞赛专题解析-四边形不等式优化
C++基础算法
《算法分析与设计》_实验指导书
数学建模在计算机专业的应用
《 Java程序设计》教学大纲
《算法设计与分析》课程实验与设计 福州大学 王晓东
石子合并
经典的动态规划入门练习题