【蓝桥杯】五星填数

要求每条直线上数字和相等。

注意：旋转或镜像后相同的算同一种填法。

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

参考答案：12

题目分析：

        注意我题目中我标红的地方，旋或镜像后相同的算同一种算法。先看旋转镜像，且看五个角如果有一种填法为12345，也就同时存在23451/34512/45123/51234都满足判断，但都是可以通过旋转后得到的所以5种为一种填法。12345和15432、54321和51234、43215和45123、32154和34512、21543和23451都为镜像关系,有此可得，任意一种组合经过镜像和旋转都有10种不同的组合满足判断，所以最后结果需除以10。

C++代码一：采用算法库中的全排列函数

#include <iostream>
#include <algorithm>
using namespace std;int main() {int sum = 0;int v[10] = {1,2,3,4,5,6,8,9,10,12};do {int t = v[0]+v[2]+v[5]+v[8];if(t == v[0]+v[3]+v[6]+v[9] && t == v[1]+v[2]+v[3]+v[4]&& t == v[1]+v[5]+v[7]+v[9]&& t == v[4]+v[6]+v[7]+v[8])sum++;} while(next_permutation(v, v+10)); //全排列求所有组合 cout << sum/10; return 0;
}

C++代码二：自定义全排列函数

#include <iostream>
using namespace std;int v[10] = {1,2,3,4,5,6,8,9,10,12};
int sum = 0;
void pumutation(int n) {if(n == 10) {int t = v[0]+v[2]+v[5]+v[8];if(t == v[0]+v[3]+v[6]+v[9] && t == v[1]+v[2]+v[3]+v[4]&& t == v[1]+v[5]+v[7]+v[9]&& t == v[4]+v[6]+v[7]+v[8])sum++;return;}for(int i = n; i < 10; i++) {swap(v[i],v[n]);pumutation(n+1); swap(v[i],v[n]);}
}int main() {pumutation(0);cout << sum/10;return 0;
} 

C++代码三：用深度优先算法遍历

#include <iostream>
using namespace std;int v[10] = {1,2,3,4,5,6,8,9,10,12};
int book[13] = {0}; 
int result[10];
int sum = 0;
void dfs(int n) {if(n == 10) {int t = result[0]+result[2]+result[5]+result[8];if(t == result[0]+result[3]+result[6]+result[9]  && t == result[1]+result[2]+result[3]+result[4]&& t == result[1]+result[5]+result[7]+result[9]&& t == result[4]+result[6]+result[7]+result[8])sum++;return;}for(int i = 0; i < 10; i++) {if(!book[v[i]]) {result[n] = v[i]; // 记录当前的数book[v[i]] = 1; // 走过标记dfs(n+1);book[v[i]] = 0; // 走完复位}}
}int main() {dfs(0);cout << sum/10;return 0;
} 

Java代码一：自定义全排列函数

public class Test {static int[] v = new int[]{1,2,3,4,5,6,8,9,10,12};static int sum = 0;static void pumutation(int n) {if(n == 10) {int t = v[0]+v[2]+v[5]+v[8];if(t == v[0]+v[3]+v[6]+v[9] && t == v[1]+v[2]+v[3]+v[4]&& t == v[1]+v[5]+v[7]+v[9]&& t == v[4]+v[6]+v[7]+v[8])sum++;return;}for(int i = n; i < 10; i++) {swap(i, n);pumutation(n+1); swap(i, n);}}static void swap(int m, int n) { int temp = v[m];v[m] = v[n]; v[n] = temp; }public static void main(String[] args) {pumutation(0);System.out.println(sum / 10);return ;}}

Java代码二：用深度优先算法遍历

public class Test {static int[] v = new int[]{1,2,3,4,5,6,8,9,10,12};static boolean[] book = new boolean[13]; static int[] result = new int[10];static int sum = 0;static void dfs(int n) {if(n == 10) {int t = result[0]+result[2]+result[5]+result[8];if(t == result[0]+result[3]+result[6]+result[9]  && t == result[1]+result[2]+result[3]+result[4]&& t == result[1]+result[5]+result[7]+result[9]&& t == result[4]+result[6]+result[7]+result[8])sum++;return;}for(int i = 0; i < 10; i++) {if(!book[v[i]]) {result[n] = v[i]; // 记录当前的数book[v[i]] =true; // 走过标记dfs(n+1);book[v[i]] = false; // 走完复位}}}static void swap(int m, int n) { int temp = v[m];v[m] = v[n]; v[n] = temp; }public static void main(String[] args) {dfs(0);System.out.println(sum / 10);return ;}}