level 4
请教一下爬楼梯的问题
某人上楼梯,一次可以走一步也可以走两步,求上楼梯的方法共有多少种
输入
仅一行,一个数据n,表示共有n个阶梯
输出
仅一行,一个数据,表示上楼梯的方法
本来是这样写的:
var
n:integer;
function dp(n:integer):integer;
begin
if n=1 then exit(1);
if n=2 then exit(2);
dp:=dp(n-1)+dp(n-2);
end;
begin
readln(n);
writeln(dp(n));
end.
但是题目要求使用动态规划,用重叠子问题来实现
否则大一点的数据就会爆掉
我就这样写的:
var
n:integer;
f:array[1..1000]of longint;
function dp(n:integer):integer;
begin
if n=1 then exit(1);
if n=2 then exit(2);
if f[n]<>0
then exit(f[n]);
if f[n]=0
then f[n]:=dp;
dp:=dp(n-1)+dp(n-2);
end;
begin
fillchar(f,sizeof(f),0);
readln(n);
writeln(dp(n));
end.
但是运行数据稍微大一点 就会显示:exited with exitcode=201;
然后我把修改了一下:function dp(n:integer):longint;
然后再运行,数据小能过,数据大就显示:exited with exitcode=215;
求解....
我想知道问题出在哪里..
请高手指教
2011年11月28日 14点11分
5
level 3
本人新手求解一道题:如果今天是星期六,那么从今天往后的第100天是星期几
2011年11月29日 04点11分
6
level 6
题目已经说得很清楚了,是用动规解的题目
所以我们知道,每一步都是由前一格或前两格来的,所以f[i]:=f[i-1]+f[i-2];也就是斐波拉切数列。
2011年11月29日 15点11分
8
level 1
txt 中英数全半角标点 UTF-8 or GBK
我只要能把一个一个的字隔开来就行了
2011年12月01日 12点12分
14
level 4
要求优化和剪枝啊!!否则数据大了运算就得用高精度,如果给出的N超过100,那么运行就会超过一秒,厄,是一秒的好几倍..只能用DP的重叠子问题来解决,至少要N在1000以内时秒过...
2011年12月01日 14点12分
15
斐波那契你可以用快速幂+矩阵乘法做。那么复杂度只有logn,再顺便加一个高精度,应对100000的数组没问题。
2013年08月27日 11点08分
level 6
就这样了,你那种写法会死得更惨,才开integer,不死才怪,估计一定要用高精了,实在不行就交表
2011年12月01日 14点12分
16
level 4
我知道怎么写了、昨晚灵感大发、、过了、、
高精就先不说了、
function dp(n:longint):longint;
begin
if n=1 then exit(1);
if n=2 then exit(2);
if f[n]=0
then f[n]:=dp(n-1)+dp(n-2);
exit(f[n]);
end;
重叠子问题嘛、、
就是
比如说
斐波那契数列
在计算dp(5)的时候
就会计算dp(5-1)和dp(5-2)
即dp(4)和dp(3)
而计算dp(4)又会计算一次dp(3)
而计算dp(3)时又会继续递归
就会浪费许多空间和时间
所以我们就用一个数组F[n]来储存每一个计算过的斐波那契数
以后再递归的时候就不必计算了,
直接调用就行了
就可以节省时间
即使计算很大的数据也不会爆了
顺便问一下
关于DP的三大原则
大侠们能不能给详细解释一下?
麻烦了……
2011年12月02日 04点12分
18
斐波那契不用开数组的,因为f[n]只跟f[n-1]和f[n-2]有关,所以你只要存储f[n-1]和f[n-2]即可,用两个变量就可以了。
2013年08月27日 11点08分
level 4
求教一个问题:听说PASCAL中可以通过某个使用单元来实现输入输出中文,
请问怎样使用?
厄、不是那个设置里的东西、、那个设置了中文就乱码了、而且中文也输入不上去、、
如果有了中文,怎样控制排序?
2011年12月02日 04点12分
19
level 6
如果是GBK编码,请去看看百科上关于GBK的描述
GBK亦采用双字节表示,总体编码范围为8140-FEFE,首字节在81-FE 之间,尾字节在40-FE 之间,剔除 xx7F一条线。总计23940 个码位,共收入21886个汉字和图形符号,其中汉字(包括部首和构件)21003 个,图形符号883 个。
按照这个思路,从头开始处理,一个个下来,就可以判断是一个汉字还是一个字符。
如果是UTF-8编码,windows提供了一个API函数,可以将UTF-8专成ANSI编码(在中文系统中ANSI编码就是GBK)。可以这样写:
uses windows;
var utf8str,ansistr:ansistring;
begin
readln(utf8str);
ansistr:=utf8toansi(utf8str);
end.
然后按照GBK的方式处理。
或者,你也可以参看UNICODE编码表,里面规定了汉字的编码范围。可是这样还要先将UTF-8转成UNICODE。你可以使用multibytetowidechar将UTF-8转成UNICODE编码。详细请参看网络教程。不过比较麻烦。
2011年12月02日 08点12分
20
level 6
某个单元?好吧我承认我不知道。但可以使用CMD自带的中文能力,这样写:
uses dos;
begin
exec(getenv('cmdspec'),' /c chcp 936');
{你想做的事}
end.
exec是执行某个EXE,getenv是获取环境变量。cmdspec指向当前系统的命令行,一般情况下是c:\windows\system32\cmd.exe./c chcp 936是传给CMD的参数。/c 表示命令完成后退出,chcp是改变代码页的意思,936是gbk编码。
系统会自动启动适用于cmd的输入法。ctrl+space启动。
2011年12月02日 08点12分
21
level 7
请问怎么把文件菜单里的以前的编程文件消除掉(原文件不删除)
谢谢
2011年12月02日 11点12分
22