UC知道两道Pascal递推题
来源：百度知道 编辑：UC知道 时间：2024/06/25 12:44:30
棋盘控制（Broad）
【程序名称】board.exe
【源程序名】board.(pas/c/cpp)
【输入文件】board.in
【输出文件】board.out
【问题描述】
在一个N×N的棋盘上放置K（K≤N）个中国象棋中的“车”，要求这K个“车”不能相互攻击，请问总共有多少种摆放方法。
【输入数据】
输入数据仅一行，包含两个整数N（1≤N≤20）和K，数字中间用空格隔开。
【输出数据】
输出数据仅一个整数，即总摆放方法数。
【样例】
braod.in
3 2
broad.out
18
多米诺骨牌（Domino）
【程序名称】domino.exe
【源程序名】domino.(pas/c/cpp)
【输入文件】domino.in
【输出文件】domino.out
【问题描述】
有N块1×2大小的骨牌需要放入一个2×N的牌盒中，请问共有多少种放法（输出总放法数的最后100位即可）。
【输入数据】
输入数据仅一个自然数N（N≤106）。
【输出数据】
输出数据共4行，每行25位，共100位。表示总放法数的最后100位。不满100位时高位用0补足。
【样例】
domino.in
5
domino.out
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000008
这两个的递推式是什么？
【程序名称】board.exe
【源程序名】board.(pas/c/cpp)
【输入文件】board.in
【输出文件】board.out
【问题描述】
在一个N×N的棋盘上放置K（K≤N）个中国象棋中的“车”，要求这K个“车”不能相互攻击，请问总共有多少种摆放方法。
【输入数据】
输入数据仅一行，包含两个整数N（1≤N≤20）和K，数字中间用空格隔开。
【输出数据】
输出数据仅一个整数，即总摆放方法数。
【样例】
braod.in
3 2
broad.out
18
多米诺骨牌（Domino）
【程序名称】domino.exe
【源程序名】domino.(pas/c/cpp)
【输入文件】domino.in
【输出文件】domino.out
【问题描述】
有N块1×2大小的骨牌需要放入一个2×N的牌盒中，请问共有多少种放法（输出总放法数的最后100位即可）。
【输入数据】
输入数据仅一个自然数N（N≤106）。
【输出数据】
输出数据共4行，每行25位，共100位。表示总放法数的最后100位。不满100位时高位用0补足。
【样例】
domino.in
5
domino.out
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000008
这两个的递推式是什么？
1.分析：
n*n的正方形等价于n排n个格子的矩形，将n排排列便有了p(n,k），
（其实就是将格子平移，每个格子都是不同的）
再在1-n中选出k个数，依次填进前k排，又有了c(n,k),
所以f(n,k)=c(n,k)*p(n,k）。
2.对于第n项，可以由第n-1项加一个竖着的矩形得到
也可以由n-2项加两个横着的矩形得到；
所以.f(n）=f(n-1)+f(n-2)
接着只要知道前两项即可
f(1)=1，f（2）=2.（看图更明了）
1.f(n,k)=c(n,k)*p(n,k）排列组合
2.f(n）=f(n-1)+f(n-2) 递推f(0)=1 f(1)=1
1.f(n,k)=c(n,k)*p(n,k）排列组合
2.f(n