蓝桥杯学习记录||ALGO-996 车的放置

车的放置

问题描述
　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)
输入格式

包含一个正整数n

输出格式

一个整数，表示放置车的方法数

样例输入

2

样例输出

7

数据规模和约定

n<=8【样例解释】一个车都不放为1种，放置一个车有4种，放置2个车有2种。

解析：从样例可以看出‘车’是被放在格子里面的，而不是点上。我们可以自由选择摆放车的个数，以达到最多的摆法。

解法：其实可以用概率论的方法解题
当棋盘为n * n 时，我们可以选择的棋子数为0 ~ n ,
　棋子数为0 这算一种
　棋子数为i 可以摆法的种数：

在n行格子中选择i行进行摆放就是C(i,n)
然后在摆放i个棋子时，第一个棋子有n种选择（n个列可以选），第二个有n-1种选择…就是A(i,n)

写代码时公式可以化简为 下图 ；cal（）就是A的计算函数

#include<stdio.h>
int n;
int sum = 0;
//看上图
int cal(int x){
	int factor=1,i;
	for(i=n;i>n-x;i--){ //求分子
		factor*=i;
	}
	factor *= factor; //分子平方
	for(i=x;i>=1;i--){ //除于i的阶层
		factor/=i;
	}
	return factor; //求出A
} 
 
int main(){
	int i;
	scanf("%d",&n);
	sum=1 + n*n; //先把摆放0个和摆放1个的加上
	for(i=2;i<=n;i++){
		sum+=cal(i);//表示用 i 个车 
	}
	printf("%d",sum);
	return 0;
}

本题:车的放置