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

问题描述：

在一个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);

#includeint 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;}