试题 蓝桥杯算法训练-车的放置

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

输入格式

　　包含一个正整数n

输出格式

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

样例输入

2

样例输出

7

数据规模和约定

n<=8

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

算法思路：首先当棋盘上一个都没有和只有一个的时候很容易得出有1和n*n中方法，由于车是直行的所以在同一行和列上只能有一辆车，所以最多能放n辆车。当放n辆车时第一列有n种放法，第二列有n-1种(由于不能和第一列在同一行上)，以此类推直到n列可以放1种。所以放n辆车的放法为n*(n-1)*(n-2)*…………*1;当放n-1辆时，可以理解为在n列里面选1列不放，所以是C1,n(高中所学的排列组合),然后乘以n*(n-1)*(n-2)*…………*2(注意这里由于少了一列所以变成了乘2)，同理放n-i辆时，C(n-i),n*(n)*(n-1)*…………*(n-i+1);

#include

int n;
int sum=1;

int deal(int x,int y){
	int factor=1,i,t=n;
	int element=1;
	for(i=y;i>y-x;i--){
		factor*=i;
	}
	for(i=x;i>=1;i--){
		factor/=i;
	}
	for(i=n;i>=n-x+1;i--){		
		element*=i;
	}
	element*=factor;
	return element;
	
} 

int main(){
	int i;
	scanf("%d",&n);
	sum+=n*n;
	for(i=2;i<=n;i++){
		sum+=deal(i,n);
	}
	printf("%d",sum);
	return 0;
}