Question

free Pascal程序 高手进~

1。用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板，共有多少种方案？
2。圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？
最好用递推的算法！3.9号之前的回答追加！急~
美错。。就是递推题。干脆全部搬上来吧。
问题一：
在所有的N位数中，有多少个数中有偶数个数字3？
样例输入：2
样例输出：73

问题二：
用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板，共有多少种方案？
样例输入：2
样例输出：3

问题三：
从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
样例输入：2
样例输出：7

问题四：
圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？
样例输入：4
样例输出：9

问题五：
在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？
样例输入：1
样例输出：4

同志们帮帮忙啊。。。多加分

Answer 1

由于我自己测试时数据太大，所以我都除了12345，你可以把mod12345去掉就可以了 （我不知道什么是生成树）
第一题
var
a,b:array[0..1000]of longint;
i,n:longint;
begin
a[1]:=8;
b[1]:=1;
readln(n);
if n=1 then writeln(1)
else
begin
for i:=2 to n do
begin
a[i]:=(9*a[i-1]+b[i-1]) mod 12345;
b[i]:=(9*b[i-1]+a[i-1]) mod 12345;
end;
writeln(a[n]);
end;
end.

第二题
program p1399;
var
i,j,k,t,n:longint;
a:array[0..1000] of longint;
begin
readln(n);
a[1]:=1;
a[0]:=1;
for i:=2 to n do
a[i]:=(a[i-2]*2+a[i-1]) mod 12345;
writeln(a[n]);
end.

第三题
program p1400;
var
a:array[0..1000]of longint;
i,n:longint;
begin
a[0]:=1;
a[1]:=3;
readln(n);
for i:=2 to n do a[i]:=(a[i-1]*2+a[i-2])mod 12345;
writeln(a[n]);
end.

第四题
var
a:array[0..1000]of longint;
i,n,k:longint;
begin

a[0]:=1;
a[1]:=1;
readln(n);
for i:=2 to n do
begin
for k:=0 to i-2 do
a[i]:=(a[i]+a[k]*a[i-2-k])mod 12345;
a[i]:=(a[i]+a[i-1]) mod 12345;
end;
writeln(a[n]);

end.

Answer 2

有样例输入和输出吗？你可以自己找规律啊，例如说把n=1，n=2……时的情况列出来再找规律啊，你现在几年级了，我初一。

Answer 3

给你个网址。。。

http://www.matrix67.com/blog/archives/276

里面有个类似的问题

经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果

我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

第二题排列组合就可以了，问数学老师

Answer 4

这个不是Matrix67的递推专项训练中的第二题和第四题吗？我写过题解^_^。
问题二：用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板，共有多少种方案？
我们令f[i]表示铺满i*3地板方案数，那么如果第i行只用1*1铺满的话，因为只有一种情况，那么方案数就是铺满（i-1）*3 的格子f[i-1]。如果第i行与i-1行一起用2*2和1*1的格子铺的话，因为有两种方案（2*2铺满上面四个，或下面四个）所以方案数为2*f[i-2].那么f[i]=f[i-1]+2*f[i-2]。
程序：
Program P2;
var
i,j,k,t,n:longint;
a:array[0..1000] of longint;
begin
readln(n);
a[1]:=1;
a[0]:=1;
for i:=2 to n do
a[i]:=a[i-2]*2+a[i-1]；
writeln(a[n]);
end.

问题四：圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？
我感觉很类似catalan数，枚举第i个点和那些点相连，把图分成两部分，即f[i]=求和f[j]*f[i-j-2](j=0,1,2...i-2);同时地i个点还可能谁也不连，那么f[i]=f[i-1]。求f[n].
程序：
Program P4;
var
a:array[0..1000]of longint;
i,n,k:longint;
begin
a[0]:=1;
a[1]:=1;
readln(n);
for i:=2 to n do
begin
for k:=0 to i-2 do
a[i]:=a[i]+a[k]*a[i-2-k];
a[i]:=a[i]+a[i-1];
end;
writeln(a[n]);
end.
注：程序均为Matrix67的标程，并非本人所写（我写的代码比较丑>_<).