最大长方体问题(动态规划\C++实现)

Description 一个长,宽,高分别是m,n,p的长方体被分割成m*n*p个小立方体。每个小立方体内含一个整数。 试着设计一个算法，计算所给长方体的最大子长方体。子长方体的大小由它内部所含所有整数之和确定。 约定：当该长方体所有元素均为负数时,输出最大子长方体为0。 Input 第一行3个正整数m,n,p，其中 1<=m,n,p<=50 接下来的m*n行中每行p个整数，表示小立方体中的数。 Output 第一行中的数是计算出的最大子长方体的大小。 Sample Input 3 3 3 0 -1 2 1 2 2 1 1 -2 -2 -1 -1 -3 3 -2 -2 -3 1 -2 3 3 0 1 3 2 1 -3 Sample Output 14 Hint 1，先编写一维的“最大字段和”的解法。 2，基于“最大字段和”，编写二维的“最大子矩阵和”的解法。 3，基于“最大子矩阵和”，编写三维的“最大子长方体和”的解法。

完全二叉树的种类(动态规划\备忘录方法\Catalan数\C++实现)

Description 构造n个(2<=n<=20)叶结点的的完全二叉树(完全二叉树意味着每个分支结点都有2个儿子结点),有多少种构造方法? 注意:不改变n个结点的相对顺序,左右儿子不调换. 例如: 4个叶子节点A1,A2,A3,A4，可构造出如下完全二叉树，共5种。 再例如:5个叶子结点,A1,A2,A3,A4,A5，可构造出如下若干种完全二叉树形状,像这样的完全二叉树共有14种. Input 输入n,表示构造的完全二叉树有n个叶结点(2<=n<=20). Output 输出构造的完全二叉树的种类. Sample Input 5 Sample Output 14 Hint 把所有叶节点从左到右编上号：1，2，…，n。 无论怎样构造的完全二叉树，根节点左边的左子树和右边的右子树又都是完全二叉树， 那么n个节点的完全二叉树构造方法数等于左子树的构造方法数乘以右子树的构造方法数， 且要列举所有可能的左子树和右子树情况，而后相加。假设左子树的叶子为1，…，i。 右子树的叶子就是：i+1，…，n。 设n个叶子的完全二叉树构造方法数为Total(n)。Total(n)的递归公式如下,这是Catalan数： Total(n) = for i=1 to n-1 sum(Total(i) * Total(n-i)) if n>=2 Total(n)=1 if n=1 考虑到计算Total(n)时，所有小于规模n的Total(n-1)，…，Total(1)都可能被计算多次， 存在大量重复计算的问题。因此比较好的方法是对i从2到n，边计算Total(i)，边用表记录下来， 即备忘录的方法，时间复杂度为O(n^2) 。

整数因子分解问题(分治法\C++实现)

Description 大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm 例如：当n=12时，共有8种不同的分解式： 12 = 12 12 = 6*2 12 = 4*3 12 = 3*4 12 = 3*2*2 12 = 2*6 12 = 2*3*2 12 = 2*2*3 对于给定正整数n，计算n共有多少种不同的分解式。 Input 第一行一个正整数n （1<=n<=1000000） Output 不同的分解式数目 Sample Input 12 Sample Output 8 Hint 此题因子讲顺序的.第一个因子可能是2~n之间的数. 比如对12而言,第一个因子可能是2,3,4,6,12. 将第一个因子为2的分解个数,加上第一个因子为3的分解个数,...,直至加到第一个因子为12的分解个数. 而第一个因子为2的分解个数又是多少呢?是6(因为12/2=6)的分解个数,递归求解! 可用“递归”和“备忘录方法”两种方法分别求解，并测试一下效率。 递归实现整数因子分解的计数。 假设对正整数n的因子分解计数为solve(n)。 1）当n=1时，计数加1。 2）当n>1时，对每个因子i，计算solve(n/i)。

不能移动的石子合并问题（动态规划/C++实现）

做如下两个模型的石子合并，如下模型石子都不能移动出列，且合并都仅发生在相邻两堆石子中： （1）第一个模型：一行排列且相邻合并 有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，相邻两堆可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。 （2）第二个模型：一圈排列且相邻合并 有n堆石子形成首位相连的一个环形(a1,a2,…,an，ai为第i堆石子个数，an和a1相邻)，相邻两堆可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。 例如4堆石子，每堆石子个数：9 4 4 5 若排成一行，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+4)+(13+4)+(17+5)=52。 若排成圈状，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+5)+(14+4)+(18+4)=54。 此题以第一模型的最低得分为例，很多同学想着采用总是从最小的相邻两堆下手的思想，最后获得的也就是最低得分。但这个贪心策略是不对的。 如下反例： 石子：9 4 6 1 5 贪心策略： 9 4 6 6 6 9 10 6 10 9 16 16 25 25 得分共计：6+10+16+25=57 但9 4 6 1 5 若如下方式合并： 13 6 1 5 13 13 6 6 6 13 12 12 25 25 13+6+12+25=56 或 9 4 6 6 6 9 4 12 12 13 12 13 25 25 6+12+13+25=56 后两种方式合并出的56都比贪心策略的57来的更低，因为总选择最小的相邻两堆去合并，并不能保证后续每步都可以最小，也许这轮最小导致后续几轮分值较大。 Input 两行。第一行n，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100 Output 两行。第一行是第一个模型的最低得分和最高得分，中间空格相连，第二行是第二个模型的最低得分和最高得分，中间空格相连。 Sample Input 4 9 4 4 5 Sample Output 43 52 43 54 Hint 第一个石子合并模型,和书上3.1节的矩阵连乘问题类似. 假设m[i,j]为合并石子ai…aj, 1≤i≤j≤n，所得到的最小得分，若没有“合并”这个动作，则为0。原问题所求的合并最小值即为m[1,n]。 递推公式如下,其中min表示求最小,sum表示求和. (1) m[i,j]=0, if i=j (2) m[i,j]=min{m[i,k]+m[k+1][j] | for i<=k<j} + sum{a(t) | for i<=t<=j}, if i<j 至于求最大值完全同理. 至于第二个石子合并的环行模型,完全可以转化为第一个模型来求解.

动态规划解决不能移动的石子合并问题

Description 做如下两个模型的石子合并，如下模型石子都不能移动出列，且合并都仅发生在相邻两堆石子中： （1）第一个模型：一行排列且相邻合并 有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，相邻两堆可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。 （2）第二个模型：一圈排列且相邻合并 有n堆石子形成首位相连的一个环形(a1,a2,…,an，ai为第i堆石子个数，an和a1相邻)，相邻两堆可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。 例如4堆石子，每堆石子个数：9 4 4 5 若排成一行，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+4)+(13+4)+(17+5)=52。 若排成圈状，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+5)+(14+4)+(18+4)=54。 此题以第一模型的最低得分为例，很多同学想着采用总是从最小的相邻两堆下手的思想，最后获得的也就是最低得分。但这个贪心策略是不对的。 如下反例： 石子：9 4 6 1 5 贪心策略： 9 4 6 6 6 9 10 6 10 9 16 16 25 25 得分共计：6+10+16+25=57 但9 4 6 1 5 若如下方式合并： 13 6 1 5 13 13 6 6 6 13 12 12 25 25 13+6+12+25=56 或 9 4 6 6 6 9 4 12 12 13 12 13 25 25 6+12+13+25=56 后两种方式合并出的56都比贪心策略的57来的更低，因为总选择最小的相邻两堆去合并，并不能保证后续每步都可以最小，也许这轮最小导致后续几轮分值较大。 Input 两行。第一行n，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100 Output 两行。第一行是第一个模型的最低得分和最高得分，中间空格相连，第二行是第二个模型的最低得分和最高得分，中间空格相连。 Sample Input 4 9 4 4 5 Sample Output 43 52 43 54 Hint 第一个石子合并模型,和书上3.1节的矩阵连乘问题类似. 假设m[i,j]为合并石子ai…aj, 1≤i≤j≤n，所得到的最小得分，若没有“合并”这个动作，则为0。原问题所求的合并最小值即为m[1,n]。 递推公式如下,其中min表示求最小,sum表示求和. (1) m[i,j]=0, if i=j (2) m[i,j]=min{m[i,k]+m[k+1][j] | for i<=k<j} + sum{a(t) | for i<=t<=j}, if i<j 至于求最大值完全同理. 至于第二个石子合并的环行模型,完全可以转化为第一个模型来求解.

钱币组合方法数的问题(C++实现)

问题描述：设有 n 种不同的钱币各若干张，可用这 n 种钱币产生许多不同的面值。试设计一个算法，计算给定的某个面值，能有多少种不同的产生方法。例如有 1 分3 张，2 分3 张，5 分 1 张，则能组成 7 分面值的方法有：3 个 1 分+2 个 2 分，1 个 1 分+3 个 2 分，2个 1 分+1 个5 分，1 个2分+1 个5 分共四种。 编程任务：对于给定的 n 种不同钱币，编程计算某个给定面值能有多少种不同的产生方法。 Input 第1行有1个正整数n(1<=n<=10)，表示有n种不同的钱币。 第2行有n个数，分别表示每种钱币的面值。 第3行有n个数，分别表示每种钱币的张数k(0<=k<=10)。 第4行有1个数，表示给定的面值m(1<=m<=20001)。 Output 计算出的给定面值的不同产生方法种数 Sample Input 3 1 2 5 3 3 1 7 Sample Output 4

SQL基础教程(第3版)

本书是一本SQL的入门书，介绍如何使用最常用的SQL语言维护和查询数据库信息。书中介绍了各种DBMS，关系模型理论，SQL语法，从表中检索数据，操作符和函数，汇总和分组数据，联结，子查询，集合操作，创建、更改和删除表，索引，视图，事务和SQL技巧等。本书比较了各种DBMS中的SQL实现，并给出大量实例代码及经验技巧。 本书适合SQL初学者，同时也可作为数据库应用开发人员和最终用户的参考书。