Function Run Fun
http://poj.org/problem?id=1579
Description
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.
Output
Print the value for w(a,b,c) for each triple.
Sample Input
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
Source
Pacific Northwest 1999
很明显,这里的函数w定义就是个递归函数。不过w的递归过于复杂,如果直接按照题意编写模拟函数,肯定是TLE的。
这样在递归过程中记录一下中间结果,如果需要用到的时候则可以查表。由于有当a,b,c大于20的时候都视为20,则这个表是三维,最大元素为20的数组。
下面代码使用e数组作为表,每次先看是否在表中有对应结果,如果有则直接使用,没有就按照递归计算,计算完成后同时记录结果到表中。
http://poj.org/problem?id=1579
Description
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.
Output
Print the value for w(a,b,c) for each triple.
Sample Input
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
Source
Pacific Northwest 1999
很明显,这里的函数w定义就是个递归函数。不过w的递归过于复杂,如果直接按照题意编写模拟函数,肯定是TLE的。
这样在递归过程中记录一下中间结果,如果需要用到的时候则可以查表。由于有当a,b,c大于20的时候都视为20,则这个表是三维,最大元素为20的数组。
下面代码使用e数组作为表,每次先看是否在表中有对应结果,如果有则直接使用,没有就按照递归计算,计算完成后同时记录结果到表中。
#include <stdio.h> #include <stdlib.h> #include <string.h> int e[21][21][21]; int fun (int a, int b, int c) { if (a <= 0 || b <= 0 || c <= 0) return 1; if (a > 20 || b > 20 || c > 20) return fun(20, 20, 20); if (a < b && b < c) { if (e[a][b][c]) return e[a][b][c]; else e[a][b][c] = fun(a, b, c-1) + fun(a, b-1, c-1) - fun(a, b-1, c); } else { if (e[a][b][c]) return e[a][b][c]; else e[a][b][c] = fun(a-1, b, c) + fun(a-1, b-1, c) + fun(a-1, b, c-1) - fun(a-1, b-1, c-1); } return e[a][b][c]; } int main (int argc, char const* argv[]) { int a, b, c; memset(e, 0, sizeof(e)); while (1) { scanf("%d %d %d", &a, &b, &c); if (a == -1 && b == -1 && c == -1) { break; } printf("w(%d, %d, %d) = %d\n", a, b, c, fun(a, b, c)); } return 0; }
发表评论
-
fhloj1051 投票
2013-07-04 19:42 0投票 源文件: b(.bas/.c/.cpp/.pas) 输 ... -
fhloj1050 足球赛
2013-07-04 19:36 566足球赛 源文件: a(.bas/.c/.cpp/.pas) ... -
fhloj1092 五子棋
2013-07-04 12:01 671五子棋 源文件: gobang(.bas/.c/.cpp/ ... -
fhloj1091 拼单词
2013-07-04 11:53 703拼单词 源文件: words ... -
fhloj1090 21点游戏
2013-07-04 11:44 59821点游戏 源文件: poker(.bas/.c/.cpp ... -
fhloj1089 帮奶奶算帐
2013-07-04 11:17 561帮奶奶算账 源代码:bill.bas/pas 输入文件:bil ... -
hdu1019 gcd和lcm
2012-12-06 15:09 742Least Common Multiple http://a ... -
hdu1021 推理规律
2012-12-06 09:24 891Fibonacci Again http://acm.hdu ... -
hud1008 电梯 迭代模拟计算
2012-12-04 18:24 990Elevator http://acm.hdu.edu.cn ... -
hdu1001 求和
2012-12-03 22:05 727Sum Problem http://acm.hdu.edu ... -
hdu1000 A+B
2012-12-03 18:37 782A + B Problem http://acm.hdu.e ... -
hdu2035 乘方取余
2012-12-02 18:02 1042人见人爱A^B http://acm.hdu.edu.cn/ ... -
hdu2034 差集
2012-12-02 17:43 815人见人爱A-B http://acm.hdu.edu.cn/ ... -
hdu2033 时间计算
2012-12-02 16:24 858人见人爱A+B http://acm.hdu.edu.cn/ ... -
HDU1003最大连续子序列和
2012-12-01 15:08 1406Max Sum http://acm.hdu.edu.cn/ ... -
hdu2081 字符串拼接
2012-12-01 14:35 778手机短号 http://acm.hdu.edu.cn/sho ... -
poj1163 树型结构动态规划和最大路径
2012-11-30 22:05 1149The Triangle http://poj.org/pr ... -
POJ1050 最大子矩阵
2012-11-30 11:34 1157To the Maxhttp://poj.org/proble ...
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj题目2775文件子目录源代码,递归经典题目,
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告