8 300 207 155 300 299 170 158 65
6
简单动态规划：
继续阅读
求排列的逆序数
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。
输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入
6
2 6 3 4 5 1
样例输出
8
提示
1. 利用二分归并排序算法（分治）；
2. 注意结果可能超过int的范围，需要用long long存储。
来源
习题(15-4)
继续阅读
6261:汉诺塔问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615
这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
假定圆盘从小到大编号为1, 2, …
输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。
输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。
样例输入
2 a b c
样例输出
a->1->c
a->2->b
c->1->b
真心是经典问题啊！
先贴代码：
继续阅读
3089:爬楼梯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。
输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30
输出
不同的走法数，每一行输入对应一行输出
样例输入
5
8
10
样例输出
8
34
89
这个好像就有点类似于动态规划的感觉咯。但是其实这还是动规里最简单的题。但是初学感觉有点难度了。233
继续阅读
1755:菲波那契数列
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数是多少。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 20)
输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小
样例输入
4
5
2
19
1
样例输出
5
1
4181
1
继续阅读
1696:逆波兰表达式
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ – * /四个。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值。
可直接用printf(“%f\n”, v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
提示
可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。
来源
计算概论05
感受到咱们国家的前缀表达式和递归真是博大精深啊！！！！
继续阅读
最近参加了中国大学MOOC的程序设计与算法（二）：http://www.icourse163.org/learn/PKU-1001894005?tid=1001994002#/learn/announce
该课程的目标：
本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。这些算法的基本思想容易理解，用它们来解决的问题，可以很容易，也可以很难。本课程中一部分的例题，难度与中学信息学奥赛NOIP提高组的较难题相当，也和ACM国际大学生程序设计竞赛中的中等题相当。掌握了本课程的内容，学员的算法水平和实现能力将超过国内大部分高校计算机专业本科毕业生。
第一周的枚举考试没有赶上，就从第二周的递归开始写，然后就把递归部分的视频看完了、考试题都写完了。
本人没有系统的学习过这一部分内容。个人感觉到递归本身应该不是特别不好理解。但是这个郭老师在递归中掺杂了一些动态规划的内容，例如分苹果，分解因数，划分整数等等问题，基本上是初次接触动态规划，之前只写过动规的01背包，其他的就不会了。所以这些转移方程很难写。根本写不出来，都是看到网上的解答才能自己慢慢思考一点。希望以后思维能力能够有所长进。
部分例题：Openjugde题库：
666:放苹果 http://noi.openjudge.cn/ch0202/666/
1751:分解因数 http://noi.openjudge.cn/ch0202/1751/
简单的整数划分问题 http://cxsjsxmooc.openjudge.cn/2017t2springhw3/2/ （可能只有题面，不能够再提交）
这三个问题的递推式总结在我之前的一篇文章里：MOOC学习递归中涉及动态规划部分经典题目
2017-07-14更新放苹果问题：参考http://www.cnblogs.com/wxgblogs/p/5742618.html
放苹果
设函数f(M,N)为把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放的分法的数量。（5，1，1和1，5，1 是同一种分法。）
求该函数的递推式
解答：
f(m,n)={
m==0||n==1 -> 1;
m
m>=n -> f(m-n,n) + f(m,n-1); //分成两种情况，f(m-n,n)是没有空盘子：把n个盘子里每个都装上一个苹果，剩下的m-n个苹果再装到n个盘子里；f(m,n-1)是有空盘子，把那一个不装扔出来就好。
}
简单的整数划分问题
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。设函数f(m,n)为将整数m划分为每个数最大为n的划分数。
求该函数的递推式
解答：
f(m,n)={
m==1|| n==1 -> 1; //m==1时，只能分成1个1；n==1时,只能分成m个1。
m
m==n -> 1+f(m,n-1); //当m==n时，因为整数m可以自己算作一个划分，那么就要把n-1传递下去
m>n -> f(m-n,n)+f(m,n-1); //m>n时，可以在当前状态下分出去n或者不分出去n，对应两个f();
}
分解因数
给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * … * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意a = a也是一种分解。
解答：设函数f(m,n)为将整数m划分成小于等于整数n的划分数。
f(m,n)={
n==1 -> 0; //划到1就不能再往下分了
m==1 -> 1;
m%n==0 -> f(m/n,n) + f(m,n-1); //当m可以整除n的时候，可以除完了划分下去，也可以不除
m%n!=0 -> f(m,n-1); //只能不除
}
Boolean Expressions
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next:
Expression: ( V | V ) & F & ( F | V )
where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed.
To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file.
输入
The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown.
The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below.
输出
For each test expression, print “Expression ” followed by its sequence number, “: “, and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line.
Use the same format as that shown in the sample output shown below.
样例输入
( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))
样例输出
Expression 1: F
Expression 2: V
Expression 3: V
来源
México and Central America 2004
这题递归写的真心累啊！