蓝桥杯练习题三 - 纸牌三角形（c++）

题目如下

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。

下面就是一种排法

   A
  9 6
 4   8
3 7 5 2

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

以下程序实现了这一功能，请你补全以下空白处内容：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
      int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
      int res = 0;
      do
      {
         int x1 = a[0] + a[1] + a[2] + a[3];
         int x2 = a[3] + a[4] + a[5] + a[6];
         int x3 = a[6] + a[7] + a[8] + a[0];
         __________________;
      } while (next_permutation(a, a + 9));
      cout << res / 3 / 2 << endl;
      return 0;
}

提示：

1、正三角形有三个角，所以一个数字可以在三个角各出现一次，这就相当于旋转。
2、在生活中你照镜子的时候会发现，当你抬起左手时，你会看到镜子中的你会抬起右手。在本题中滤镜前后包括一个正三角形和该正三角形左右位置对称交换后的正三角形。

最终代码如下： 

#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int res = 0;
    do
    {
        int x1 = a[0] + a[1] + a[2] + a[3];
        int x2 = a[3] + a[4] + a[5] + a[6];
        int x3 = a[6] + a[7] + a[8] + a[0];
        //这里是刚刚增加的代码，判断x1 = x2 = x3，条件成立，则算作一种排法，详细解释放下面
        if (x1 == x2 && x2 == x3)
        {
            res++;
        };
    } while (next_permutation(a, a + 9));
    cout << res / 3 / 2 << endl;
    return 0;
}

 解析如下：

1.int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

按照顺时针顺序或者逆时针顺序，给每个数字所在的位置一个下标，谁是几其实无所谓，但需要下标的位置固定，数字可以轮换：

       A                                        0
     9 6         对应下标            1   8
    4   8                                  2      7
   3 7 5 2                             3  4  5  6

2.next_permutation的用法

bool next_permutation(iterator start,iterator end)

next_permutation(数组头地址，数组尾地址);    

按照所有可能出现的新的排列方式进行不重复的全排列，也称为全排列，若下一个排列存在，则返回true，如果不存在则返回false。很多人都觉得这是一种暴力破解方式，不过真的很方便有木有。

3.res / 3 / 2

重点来了，也是全篇最难理解的地方，不过，提示中给出了答案：

1、正三角形有三个角，所以一个数字可以在三个角各出现一次，这就相当于旋转。
2、在生活中你照镜子的时候会发现，当你抬起左手时，你会看到镜子中的你会抬起右手。在本题中滤镜前后包括一个正三角形和该正三角形左右位置对称交换后的正三角形。

res是最终出现的x1=x2=x3情况的总数，但是题目中说了三次旋转不算，镜像不算。

那么我们来算一下，三次旋转+镜像到底是怎么算次数的。

刚排列完，先忽略题目里不算的情况：

1.这时的排列方式可以通过三次旋转，变成三种排列方式，所以：

res = 1 * 3；

2.上面1中的每一次旋转后的排列都可以在镜子中作为镜像而存在另一种排列方式：

res = res * 3；

由于

res = 1 * 3；

所以

res = 1 * 3 * 2；

如果有n中满足注意条件的排法，那么：

res = n * 3 * 2；

next_permutation全排列之后就把旋转后的*3和镜像后的*2算在内了。

由于 res = n * 3 * 2；

所以n = res / 3 / 2；

n就是排列后满足题目中不算的条件的排列组合的总数。

你听明白了吗？欢迎评论区留言讨论。