Pascal题目
描述 Description
有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？
输入格式 Input Format
只有一个整数N，独占一行。(1≤N≤50)
输出格式 Output Format
对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量 。
样例输入 Sample Input
样例输入1
4
样例输入2
20
样例输出 Sample Output
样例输出1
2
样例输出2
872
一定要用Pascal语言！！！！

var
n,i:byte;
f:array [0..51] of longint;
begin
read(n);
f[1]:=1;
f[2]:=1;
f[3]:=1;
for i:=4 to n do f[i]:=f[i-1]+f[i-3];
write(f[n]);
end.

递归做：（读入文件ｄ：／ｆｉｂｉ．ｔｘｔ）
function f(x:integer):integer;
begin
x:=x-3;
if x<=0 then
begin
f:=1;
exit(f);
end
else
f:=f(x+2)+f(x);
end;
var sum,i:longint;
begin
assign(input,'d:/fibi.txt');
assign(output,'d:/fibo.txt');
reset(input);
rewrite(output);
readln(input,i);
sum:=0;
if i<=3 then sum:=1
else
sum:=sum+f(i);
writeln(output,sum);
close(input);
close(output);
end.

n才50哎，打表不就好了。。
好吧，其实显然可以dp的：f[i]=f[i-1]+f[i-3]，f[1]=1。
看你这题做不出应该是新手简单地写就是
f[1]:=1;
for i:=2 to n do f[i]:=f[i-1]+f[i-3];
时空复杂度O(n)
那么如果n不是50而是500000000呢。。
可以矩乘。。
容易写出:
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 1 ×
a
b
c
d =
b
c
d
a+d
（矩阵都有括号）
于是快速幂f(x)=sqr(f(x>>1))*f(x and 1)秒之
时空复杂度O(logn)