穷举——六角填数

约定不等于承诺〃 2022-08-20 15:25 150阅读 0赞

六角填数

如图![六角形](https://img-blog.csdn.net/20160305094252158)所示六角形中，填入1~12的数字。
    
    使得每条直线上的数字之和都相同。
    
    图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？

> 心态不行，不知道为什么竞赛的时候非常容易紧张，感觉大脑缺氧，而且一出现bug就手忙脚乱的不知道该怎么做，然后就一点一点的把时间浪费过去了。当时一看到这题的时候，直接蒙了，感觉无从下手，甚至自己想在纸上推导或是建一个二维数组写程序，然后没推出来，也写不出程序，最后就不了了之了，在最后让同学一提醒，才想起来这用穷举做不就行了吗！！！

全排列：

public class Main {
        static boolean judge(){
            int t = nums[0]+nums[2]+nums[5]+nums[7];
            if((t==(nums[0]+nums[3]+nums[6]+nums[10]))&&(t==(nums[1]+nums[2]+nums[3]+nums[4]))
                &&(t==(nums[1]+nums[5]+nums[8]+nums[11]))&&(t==(nums[4]+nums[6]+nums[9]+nums[11]))
                &&(t==nums[7]+nums[8]+nums[9]+nums[10])){
                //System.out.println(t);
                return true;
            }
            return false;
        }
        static int[] nums = {
       1,8,2,4,5,6,7,9,10,11,12,3};
        static void show(){
            System.out.println("nums");
            for(int i=0;i<=11;i++){
                System.out.print(nums[i]+" ");
            }
            System.out.println();
            System.out.println("nums[5]:"+nums[5]);
        }
        static void permutation(int s,int e){
            if(s==e){
                if(judge()){
                    show();
                    return;
                }
            }
            for(int i=s;i<=e;i++){
                int t = nums[s];
                nums[s] = nums[i];
                nums[i] = t;
                permutation(s+1,e);
                t = nums[s];
                nums[s] = nums[i];
                nums[i] = t;
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            //for(int i=0;i<12;i++) System.out.print(nums[i]+" ");
            permutation(2,10);
        }
    
    }

搜索：  
开一个标记数组

import java.util.Arrays;
    
    public class Main {
        static boolean judge(){
            int t = nums[0]+nums[2]+nums[5]+nums[7];
            if((t==(nums[0]+nums[3]+nums[6]+nums[10]))&&(t==(nums[1]+nums[2]+nums[3]+nums[4]))
                &&(t==(nums[1]+nums[5]+nums[8]+nums[11]))&&(t==(nums[4]+nums[6]+nums[9]+nums[11]))
                &&(t==nums[7]+nums[8]+nums[9]+nums[10])){
                //System.out.println(t);
                return true;
            }
            return false;
        }
        static int[] nums = {
       1,8,2,4,5,6,7,9,10,11,12,3};
        static boolean[] visited = new boolean[20];
        static void show(){
            System.out.println("nums");
            for(int i=0;i<=11;i++){
                System.out.print(nums[i]+" ");
            }
            System.out.println();
            System.out.println("nums[5]:"+nums[5]);
        }
        static boolean DEBUG = true;
        static void test(){
            System.out.println("test");
        }
        static void DFS(int i){
            //test();
            if(i==11){
                if(judge()){
                    show();
                    return;
                }
            }
            for(int j=1;j<=12;j++){
                if(!visited[j]){
                    nums[i] = j;
                    visited[j] = true;
                    DFS(i+1);
                    visited[j] = false;
                }
            }
        }
        static boolean isEqual(int v){
            if(v==1||v==8||v==3) return true;
            return false;
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            //for(int i=0;i<12;i++) System.out.print(nums[i]+" ");
            Arrays.fill(visited, false);
            visited[1] = visited[8] = visited[3] = true;
            //nums0,nums1,nums11已经确定了
            DFS(2);
            System.out.println("final");
        }
    
    }

毛病：  
写程序一点都不严谨，每一步都要确定无误了，才能继续向下进行，否则还要再回去找错，太浪费时间了。  
不细心，怎么能把数组的元素给填错了呢！  
不会调试，一出现bug就不知道该从哪儿开始调试了。

> 穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

注意全排列算法：

产生list[k,m]的全排列
    void Perm（Type list[],int k ,int m){
            if(k==m){
       //只剩下一个元素
                print();
                return;
            }
            else{
                for(int i=k;i<=m;i++){
                    swap(list[i],list[k]);
                    Perm(list,k+1,m);
                    swap(list[i],list[k]);
                }
            }
    }

注意swap函数最好使用加一个变量的交互元素方法，因为异或运算曾经出现了bug没找到。