论坛首页 → 综合技术论坛 →

一道“正方体六个面上的四个角点整数之和相等”的求解问题

浏览 23677 次
锁定老帖子 主题：一道“正方体六个面上的四个角点整数之和相等”的求解问题
该帖已经被评为精华帖
作者 正文
  • qinysong
  • 等级: 四星会员
  • 性别:
  • 文章: 136
  • 积分: 479
  • 来自: 北京
   发表时间：2006-11-18  

题目:
请将8个给定的正整数（如1，2，3，4，5，6，7，8）分别放在一个正方体的8个角的顶点上，以实现如下要求（如果可能）：正方体六个面上的四个角点整数之和相等？输出结果如：A1=1,A2=2...

求解如下

正方体
算法思路
根据题境，我们先做如下设定和术语说明，以便于后面的讨论：
１、正整数以１，２，３，４，。。。８表示，以便进行分析；
２、正方体顶点标示如上所示；
３、每一个面的四个顶点数总和，我们称为该面的面积；
４、每一条边的两个顶点数和，我们称为该边的长度；

通过分析,可以得到如下断言为真（采用上面设定及术语）：
１、每个面的面积相等，且每个面的面积为３６／２，即１８；
２、正方体的对边相等，如A1A2=A7A8、A2A6=A3A7等等；
３、整数１和（２，３）不在同一边，整数７和８不在同一边；

根据所得断言，可以得到如下求导公式和约束：
A1=1;
A4=18-A1-A2-A3=17-A2-A3;
A6=18-A1-A2-A5=17-A2-A5;
A7=18-A1-A3-A5=17-A3-A5;
A8=A1+A2-A7=2*A1+A2+A3+A5-18=A2+A3+A5-16;

A2，A3，A5为可变量，但是A2，A3，A5不等于２，３

程序实现
通过以上算法分析，可用程序实现如下（Java实现）：

java 代码
  1. package qinysong.arithmetic;   
  2.   
  3. public class CubeProblem {   
  4.   
  5.   public static void main(String[] args) {   
  6.     System.out.println("CubeProblem begin ........");   
  7.     searchPeekNumber();   
  8.     System.out.println("CubeProblem end   ........");   
  9.   }   
  10.   
  11.   public static void printPeekNumbers(int[] peeks){   
  12.     System.out.println("the peek number:A1=" + peeks[0] + ";A2=" + peeks[1]   
  13.                        + ";A3=" + peeks[2] + ";A4=" + peeks[3]   
  14.                        + ";A5=" + peeks[4] + ";A6=" + peeks[5]   
  15.                        + ";A7=" + peeks[6] + ";A8=" + peeks[7]);   
  16.   }   
  17.   
  18.   // 核心函数，探寻各个顶点的数值   
  19.   public static void searchPeekNumber(){   
  20.     int[] peeks = new int[8];   
  21.     int peekNumber = 0;   
  22.     for (int i=4; i<=8; i++){   
  23.       peeks[0] = 1;   
  24.       peeks[1] = i;   
  25.       for (int j=4; j<=8; j++){   
  26.         if (hasUsed(2,j, peeks)) continue;   
  27.         peeks[2] = j;   
  28.         peekNumber = getPeekNumber(3, peeks);   
  29.         peeks[3] = peekNumber;   
  30.         for (int k=4; k<=8; k++){   
  31.           if (hasUsed(4,k, peeks)) continue;   
  32.           peeks[4] = k;   
  33.           peekNumber = getPeekNumber(5, peeks);   
  34.           if (hasUsed(5,peekNumber, peeks)) continue;   
  35.           peeks[5] = peekNumber;   
  36.           peekNumber = getPeekNumber(6, peeks);   
  37.           if (hasUsed(6,peekNumber, peeks)) continue;   
  38.           peeks[6] = peekNumber;   
  39.           peekNumber = getPeekNumber(7, peeks);   
  40.           if (hasUsed(7,peekNumber, peeks)) continue;   
  41.           peeks[7] = peekNumber;   
  42.           printPeekNumbers(peeks);   
  43.         }   
  44.       }   
  45.     }   
  46.   }   
  47.   
  48.   /**  
  49.    * 判断获取的顶点值是否在之前的顶点使用过  
  50.    * @param index int 将要赋值的顶点索引  
  51.    * @param peekNumber int  获取的顶点值  
  52.    * @return boolean  是否在之前的顶点使用过  
  53.    */  
  54.   public static boolean hasUsed(int index, int peekNumber,int[] peeks){   
  55.     if (peekNumber <= 0) return true;   
  56.     for (int i=0; i<index; i++){   
  57.       if (peeks[i] == peekNumber){   
  58.         return true;   
  59.       }   
  60.     }   
  61.     return false;   
  62.   }   
  63.   
  64.   /**  
  65.    * 取得某一顶点的数值  
  66.    * 根据推导公式：  
  67.    * A4=18-A1-A2-A3；A6=18-A1-A2-A5；A7=18-A1-A3-A5；A8=2*A1+A2+A3+A5-18；  
  68.    * 这里取 A1=1  
  69.    * @param peek int  顶点标号  
  70.    * @return int 顶点数值  
  71.    */  
  72.   public static int getPeekNumber(int peek, int[] peeks) {   
  73.     switch (peek) {   
  74.       case 0:   
  75.         return 1;   
  76.       case 3:   
  77.         return 17 - peeks[1] - peeks[2];   
  78.       case 5:   
  79.         return 17 - peeks[1] - peeks[4];   
  80.       case 6:   
  81.         return 17 - peeks[2] - peeks[4];   
  82.       case 7:   
  83.         return peeks[1] + peeks[2] + peeks[4] - 16;   
  84.       default:   
  85.         return 0;   
  86.     }   
  87.   }   
  88. }   


算法特性：
因为该算法是根据分析问题的数学模型，找到路径规律，然后直接推导答案，而不是采用通过遍历每一种可能性进行判断，所以效率比较好　
返回顶楼
         
  • qinysong
  • 等级: 四星会员
  • 性别:
  • 文章: 136
  • 积分: 479
  • 来自: 北京
   发表时间：2006-11-18  
后来一考虑，发现以上实现并不完整，把八个整数的特例1，2，3...8作为了题目的一部分，加强了题目约束。
如果完整的实现该题目，8个整数应该是作为参数输入系统，且也不能假定这些整数两两不等
返回顶楼
          回帖地址
0 请登录后投票
  • cookoo
  • 等级: 五钻会员
  • 性别:
  • 文章: 817
  • 积分: 1951
  • 来自: Shanghai
   发表时间：2006-11-19  
暴力算法(in Haskell)： 

module Main where
import List

--参数值
node = [1..8]

--所有排列
permutation [] = [[]]
permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)] 

--约束条件
condition (a1:a2:a3:a4:a5:a6:a7:a8:xs) = (a1 + a2 == a7 + a8) &&
                                         (a1 + a3 == a6 + a8) &&
                                         (a2 + a4 == a5 + a7) &&
                                         (a3 + a4 == a5 + a6) &&
                                         (a1 + a5 == a4 + a8) &&
                                         (a2 + a6 == a3 + a7)

--筛选（并去重复，如果参数值里有重复的话）
result = nub (filter condition (permutation node))

--打印个数
main = print (length result)


结果有144个，约束只使用按原题简化的‘对边相等’条件，便于以后用任意8个参数值做实验，比如[2,2,3,3,5,6,7,8]有24个结果。然后可以考虑一下何时无解的问题。。。
返回顶楼
          回帖地址
0 请登录后投票
  • deafwolf
  • 等级: 二星会员
  • 性别:
  • 文章: 222
  • 积分: 164
   发表时间：2006-11-19  
个人认为，解决这种问题，暴力的方法是穷举，那么相对不暴力的是回溯

只从题目上来看，唯一的判定条件是
引用
正方体六个面上的四个角点整数之和相等

而
引用

１、每个面的面积相等，且每个面的面积为３６／２，即１８
２、正方体的对边相等，如A1A2=A7A8、A2A6=A3A7等等

是由人推断出来的，对这个题目各种输入都成立的断言，其他断言不具有普遍意义，所以只能用于特定输入，这点上面已经提到了

所以这种问题需要遍历所有的可能性，因此提高效率的途径莫过于简化判定条件和尽早终止对某一分支的遍历（回溯）

在楼上思路的基础上，把类似a1=1,a2=2,a3=3,a4=4这种明显不成立的情况排除，就可以大幅减少判断次数，这时候效率就比较高了

PS：楼上的代码还真清爽，Haskell很有意思，受教了，多谢
返回顶楼
          回帖地址
0 请登录后投票
  • deafwolf
  • 等级: 二星会员
  • 性别:
  • 文章: 222
  • 积分: 164
   发表时间：2006-11-19  
恩，我是说除了我引用的1和2，其他的都不算通用规则
返回顶楼
          回帖地址
0 请登录后投票
  • qinysong
  • 等级: 四星会员
  • 性别:
  • 文章: 136
  • 积分: 479
  • 来自: 北京
   发表时间：2006-11-20  
按照8个整数可以是任意的正整数,修正上面三个断言后为

１、每个面的面积相等，且每个面的面积为（8个数的总和）／２；
２、正方体的对边相等，如A1A2=A7A8、A2A6=A3A7等等；
３、最小的三个数（如1，2，3）肯定不在同一边，最大的三个数肯定不在同一边（通过这一推论可以减少探索方案）；
返回顶楼
          回帖地址
0 请登录后投票
  • jkit
  • 等级: 五星会员
  • 性别:
  • 文章: 253
  • 积分: 575
  • 来自: 仙界
   发表时间：2006-11-20  
1：从小到大排序,为了叙述方便假定得到数组v
2：如果v[0]+v[7]==v[1]+v[6]==v[2]+v[5]==v[3]+v[4]不成立则无解
3：输出v[0],v[7],v[6],v[1],v[5],v[2],v[3],v[4]
返回顶楼
          回帖地址
0 请登录后投票
  • jkit
  • 等级: 五星会员
  • 性别:
  • 文章: 253
  • 积分: 575
  • 来自: 仙界
   发表时间：2006-11-20  
不知道这个贴的精华之处在什么地方。让人脑代替电脑做特定思考似乎不是什么值得称道的事。
大家不妨思考一下足球的每个面上的顶点之和都相等解法。看看人脑可以帮电脑做些什么，电脑可以帮人脑做些什么。
返回顶楼
          回帖地址
0 请登录后投票
  • qinysong
  • 等级: 四星会员
  • 性别:
  • 文章: 136
  • 积分: 479
  • 来自: 北京
   发表时间：2006-11-20  
３、最小的数（如1）不能和次小的两个（如2，3）在同一边，最大的不和次大的两个在同一边；

这样表述就没有问题了吧？
返回顶楼
          回帖地址
0 请登录后投票
  • qinysong
  • 等级: 四星会员
  • 性别:
  • 文章: 136
  • 积分: 479
  • 来自: 北京
   发表时间：2006-11-20  
hurricane1026 写道
jkit 写道
不知道这个贴的精华之处在什么地方。让人脑代替电脑做特定思考似乎不是什么值得称道的事。
大家不妨思考一下足球的每个面上的顶点之和都相等解法。看看人脑可以帮电脑做些什么，电脑可以帮人脑做些什么。

说实在的，我也不理解为什么这个是精华，可能是讨论算法的太少了吧。不过这个帖子里面的也算不上真正的算法。因为问题复杂度太低。你说的这个很有难度，等我找找足球的相关资料区。。。

欢迎大家贴出有意思的算法题目，一起研究
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics