日度归档：10 2 月, 2017

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

这题递归写的真心累啊！

继续阅读 →