UC知道pascal(Function Run Fun)求解
来源：百度知道 编辑：UC知道 时间：2024/06/08 08:08:32
原题:Function Run Fun
翻译:对于一个递归函数w(a,b,c):
如果a<=0 or b<=0 or c<=0就返回值1；
如果a>20 or b>20 or c>20就返回w(20,20,20)；
如果a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)；
其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)。
这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为15时，调用
的次数将非常的多。你要想个办法才行。
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
有哪位学PASCAL的大大能告诉我正确答案和思路吗?
翻译:对于一个递归函数w(a,b,c):
如果a<=0 or b<=0 or c<=0就返回值1；
如果a>20 or b>20 or c>20就返回w(20,20,20)；
如果a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)；
其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)。
这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为15时，调用
的次数将非常的多。你要想个办法才行。
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
有哪位学PASCAL的大大能告诉我正确答案和思路吗?
显然的动态规划.显然后面的数据不影响前面的数据,算过的不用算,最多也就算8000次,一闪就过了.下面用递归式动态规划实现:
function w(a,b,c:longint);
var ...
begin
if g[a,b,c]>0 then exit;
if (a<=0) or (b<=0) or (c<=0)
结果=1
else 递归:结果=...
g[a,b,c]=结果;
w=结果;
end;
g是一个三维数组,初始化全部为0
最后的g[a,b,c]就是结果
DP……我承认我很懒，第一反应就是打表。不过动规做出来表也就打好了，还是动态打表吧。