论坛 › C\C++交流 › 蓝桥杯 [五星填数] 问题

helloxiaoc 发表于 2019-1-27 17:03:23

蓝桥杯 [五星填数] 问题

解题思路:求1-12除7, 11的全排列, 问题是在求全排列的过程中会出现重复的数字


标题：五星填数

如【图1.png】的五星图案节点填上数字：1~12，除去7和11。
要求每条直线上数字和相等。

如图就是恰当的填法。

请你利用计算机搜索所有可能的填法有多少种。
注意：旋转或镜像后相同的算同一种填法。

请提交表示方案数目的整数，不要填写任何其它内容。

代码如下
static/image/hrline/1.gif
#include <iostream>
#include <list>
#define SIZE 10

using namespace std;

// 参与排列的数
int numArray = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12};
// 储存已经排列的数
int nNumber = {0};
// 储存所有排列好的数列
list<int*> listNumber;
static void printStar(int* array)
{
        cout<< "第一条线"<< array<< array<< array<< array<< "\n";
        cout<< "第二条线"<< array<< array<< array<< array<< "\n";
        cout<< "第三条线"<< array<< array<< array<< array<< "\n";
        cout<< "第四条线"<< array<< array<< array<< array<< "\n";
        cout<< "第五条线"<< array<< array<< array<< array<< "\n\n";
}
// 检查array是否包含v
bool repeat(const int *array, int v, int end)
{
        for(int i = 0; i < end; i++)
        {
                if(array == v) return true;
        }
        return false;
}
// 将array元素置于五角星每个顶顶, 判断每条直线上的数字之和是否相等, 相等返回true
bool group(const int* array)
{
        // 五角星五个顶点
        int line = {
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array}};
        // 计算第一条线上的和
        int sum = line + line + line + line;
        for(int i = 1; i < 5; i++)
        {
                // 计算每条线上的和并于第一条线之和进行比较, 不相等则返回false
                int lSum = line + line + line + line;
                if(sum != lSum) return false;
        }       
        return true;
}
// 检查结果翻转(逆序),旋转(位移)之后是否相等
static bool _count(const int*array, const int* array1)
{
        int i, n, b;
        // 下面是他们组成的五角星点阵
        int line = {
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array},
                {array, array, array, array}},
        line1 = {
                {array1, array1, array1, array1},
                {array1, array1, array1, array1},
                {array1, array1, array1, array1},
                {array1, array1, array1, array1},
                {array1, array1, array1, array1}};
        // 镜像翻转
        for(i = 0; i < 5; i++)
        {
                for(n = 0; n < 4; n++)
                {
                        if(line != line1) return false;
                }
        }
        // 旋转 (H代表的是旋转的次数)
        for(int H = 0; H < 5; H++)
        {
                b = true;
                for(i = 0; i < 5; i++)
                {
                        for(n = 0; n < 4; n++)
                        {
                                if(line[(H+i)%5] != line1)
                                {
                                        b = false;
                                        break;
                                }
                        }
                        if(!b) break;
                }
                if(b) return true;
        }
        if(!b) return false;
        return true;
}
// 检查重复, 有重复返回true
bool count(const int* array)
{
        list<int*>::iterator iter;
        for(iter = listNumber.begin(); iter != listNumber.end(); iter++)
        {
                if(_count(array, *iter)) return true;
        }
        return false;
}
// 将array1复制到array中
int* toArray(int* array, const int* array1)
{
        for(int i = 0; i < SIZE; i++)
        {
                array = array1;
        }
        return array;
}
// dfs求numArray的全排列, 参数是当前所在位置
void dfs(int pos)
{
        if(pos >= SIZE)
        {
                // 每条线不相等则返回
                if(!group(nNumber)) return;
                // 每条线相等但是翻转或旋转之后在listNumber中能找到对应的数列则返回
                if(count(nNumber)) return;
                // 将nNumber添加到list中
                listNumber.push_back(toArray(new int(SIZE), nNumber));
                printStar(nNumber);
                return;
        }
        for(int i = 0; i < SIZE; i++)
        {
                for(int n = 0; n < pos; n++) cout<< nNumber;
                cout<< "x"<< pos<< "----\n";
                // 检查重复
                if(repeat(nNumber, numArray, pos)) continue;
                nNumber = numArray;
                dfs(pos+1);
        }
}

int main(int argc, char* argv[])
{
        dfs(0);
        cout<< listNumber.size();
       
        return 0;
}

零度冷咖啡 发表于 2019-1-27 20:22:36

我是第一个？虽然我看不懂

helloxiaoc 发表于 2019-1-28 15:23:10

零度冷咖啡 发表于 2019-1-27 20:22
我是第一个？虽然我看不懂

抄袭了一下网上的答案, 突然感觉好简单..

查看完整版本: 蓝桥杯 [五星填数] 问题