分类目录归档：递归

Openjudge 汉诺塔问题 题解

发表评论

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
真心是经典问题啊！

先贴代码：
继续阅读 →

Openjudge 爬楼梯 题解

发表评论

3089:爬楼梯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。

输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30 输出 不同的走法数，每一行输入对应一行输出 样例输入 5 8 10 样例输出 8 34 89 这个好像就有点类似于动态规划的感觉咯。但是其实这还是动规里最简单的题。但是初学感觉有点难度了。233 继续阅读 →

Openjudge 菲波那契数列

发表评论

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 继续阅读 →

Openjudge 逆波兰表达式

发表评论

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学习递归中涉及动态规划部分经典题目

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 f(m,m); //将m个苹果装到多于m个的盘子中必定不能装满，所以把m个苹果装到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 f(m,m); //n>m时，将n调至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); //只能不除
}

Openjudge Boolean Expressions

发表评论

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

这题递归写的真心累啊！

继续阅读 →

Openjudge 2的幂次方表示

发表评论

2的幂次方表示
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
任何一个正整数都可以用2的幂次方表示。例如：

137=27+23+20

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：

2(7)+2(3)+2(0)

进一步：7=22+2+20（21用2表示）

3=2+20

所以最后137可表示为：

2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：

1315=210+28+25+2+1

所以1315最后可表示为：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入
一个正整数n（n≤20000）。
输出
一行，符合约定的n的0，2表示（在表示中不能有空格）。
样例输入
137
样例输出
2(2(2)+2+2(0))+2(2+2(0))+2(0)
来源
NOIP1998复赛 普及组 第一题

参考http://blog.csdn.net/u011954296/article/details/51029600写成代码，不胜感激！
继续阅读 →

Openjudge全排列题解

发表评论

全排列

总时间限制: 1000ms 内存限制: 65536kB
描述
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有’a’ < ‘b’ < … < ‘y’ < ‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。
输出
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S = s1s2…sk , T = t1t2…tk，则S < T 等价于，存在p (1 <= p <= k)，使得
s1 = t1, s2 = t2, …, sp – 1 = tp – 1, sp < tp成立。

样例输入
abc
样例输出
abc
acb
bac
bca
cab
cba

继续阅读 →