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

题目:
请将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 代码

package qinysong.arithmetic;

public class CubeProblem {

  public static void main(String[] args) {
    System.out.println("CubeProblem begin ........");
    searchPeekNumber();
    System.out.println("CubeProblem end   ........");
  }

  public static void printPeekNumbers(int[] peeks){
    System.out.println("the peek number:A1=" + peeks[0] + ";A2=" + peeks[1]
                       + ";A3=" + peeks[2] + ";A4=" + peeks[3]
                       + ";A5=" + peeks[4] + ";A6=" + peeks[5]
                       + ";A7=" + peeks[6] + ";A8=" + peeks[7]);
  }

  // 核心函数，探寻各个顶点的数值
  public static void searchPeekNumber(){
    int[] peeks = new int[8];
    int peekNumber = 0;
    for (int i=4; i<=8; i++){
      peeks[0] = 1;
      peeks[1] = i;
      for (int j=4; j<=8; j++){
        if (hasUsed(2,j, peeks)) continue;
        peeks[2] = j;
        peekNumber = getPeekNumber(3, peeks);
        peeks[3] = peekNumber;
        for (int k=4; k<=8; k++){
          if (hasUsed(4,k, peeks)) continue;
          peeks[4] = k;
          peekNumber = getPeekNumber(5, peeks);
          if (hasUsed(5,peekNumber, peeks)) continue;
          peeks[5] = peekNumber;
          peekNumber = getPeekNumber(6, peeks);
          if (hasUsed(6,peekNumber, peeks)) continue;
          peeks[6] = peekNumber;
          peekNumber = getPeekNumber(7, peeks);
          if (hasUsed(7,peekNumber, peeks)) continue;
          peeks[7] = peekNumber;
          printPeekNumbers(peeks);
        }
      }
    }
  }

  /**
   * 判断获取的顶点值是否在之前的顶点使用过
   * @param index int 将要赋值的顶点索引
   * @param peekNumber int  获取的顶点值
   * @return boolean  是否在之前的顶点使用过
   */
  public static boolean hasUsed(int index, int peekNumber,int[] peeks){
    if (peekNumber <= 0) return true;
    for (int i=0; i<index; i++){
      if (peeks[i] == peekNumber){
        return true;
      }
    }
    return false;
  }

  /**
   * 取得某一顶点的数值
   * 根据推导公式：
   * A4=18-A1-A2-A3；A6=18-A1-A2-A5；A7=18-A1-A3-A5；A8=2*A1+A2+A3+A5-18；
   * 这里取 A1=1
   * @param peek int  顶点标号
   * @return int 顶点数值
   */
  public static int getPeekNumber(int peek, int[] peeks) {
    switch (peek) {
      case 0:
        return 1;
      case 3:
        return 17 - peeks[1] - peeks[2];
      case 5:
        return 17 - peeks[1] - peeks[4];
      case 6:
        return 17 - peeks[2] - peeks[4];
      case 7:
        return peeks[1] + peeks[2] + peeks[4] - 16;
      default:
        return 0;
    }
  }
}

算法特性：
因为该算法是根据分析问题的数学模型，找到路径规律，然后直接推导答案，而不是采用通过遍历每一种可能性进行判断，所以效率比较好　

评论

28 楼 hifun 2007-01-31  

当然要高度抽象化才有其深层次的意义。。。

27 楼 qinysong 2006-11-27  

找到一种数值分布的较快方法：
1、将八个输入的整数从小到大排序，设排序后的整数在数组V[8]里；

2、
从一个顶点开始，设定该顶点为Ｂ１，为该顶点赋V[0]；
然后找Ｂ１的正方体对角顶点，设定为Ｂ２，为该顶点赋V[1]；
然后找Ｂ２的一个边相邻顶点，设定为Ｂ３，为该顶点赋V[2]；
然后找Ｂ３的正方体对角顶点，设定为Ｂ４，为该顶点赋V[3]；
然后找Ｂ４的一个边相邻顶点（排除已遍历的顶点），设定为Ｂ５，为该顶点赋V[4]；
然后找Ｂ５的正方体对角顶点，设定为Ｂ６，为该顶点赋V[5]；
然后找Ｂ６的一个边相邻顶点（排除已遍历的顶点），设定为Ｂ７，为该顶点赋V[6]；
然后找Ｂ７的正方体对角顶点，设定为Ｂ８，为该顶点赋V[7]；

结论是通过上面对八个数进行部署后，如果满足每个面相等的条件那么这就是一个解；否则输入的八个数无解。

对于规则的八个数，比如等差数列，上面的探索路径可以证明，但是对于随意的八个正整数，我还是没有证明出来，也没有找到反例可以推翻那种遍历寻找的正确性。

26 楼 garman 2006-11-27  

如果存在，面点和必为 18
结果有：
A1=4 ;
A2=5 ;
A3=7 ;
A4=2 ;
A5=1 ;
A6=8 ;
A7=6 ;
A8=3 ;

25 楼 cookoo 2006-11-24  

clamp 写道

cookoo 写道

对了，clamp还没说是什么应用背景呢？

以前我看的一篇文章找不到了，google了半天还是只有ieee的一篇讲的比较清楚
http://ieeexplore.ieee.org/iel5/8159/23900/01094073.pdf
大致意思是在频分复用(FDMA)系统中，需要在一个有限的频率段内划分出尽可能多的通道，
但是由于干扰的存在（术语叫三阶互调变失真)，因此通道数量受到极大的限制。
而其中一种划分通道的方法被称为fang-sandrin数列，其数学表现形式就是这道题目了。

这道题目解的结果会直接影响到频率段利用的情况，价值很大，需要的数学知识其实也很简单，基本数论就够了，是一道很标准的算法题。

（我不是这方面出身的，具体用词可能不太正确，请专业人士指正）


补充：终于找到一篇中文的
http://www.policetech.com.cn/2005_shownews.asp?newsid=838

多谢提供资料，文中说的两种算法（其实是一种，第二种先简化穷举范围，不过我们这题没有什么间隔条件）都是暴力算法。我已经写了一个简单的暴力程序，但是算得实在太慢了，看来还需要更多灵感来优化一下。

24 楼 clamp 2006-11-23  

cookoo 写道

对了，clamp还没说是什么应用背景呢？

以前我看的一篇文章找不到了，google了半天还是只有ieee的一篇讲的比较清楚
http://ieeexplore.ieee.org/iel5/8159/23900/01094073.pdf
大致意思是在频分复用(FDMA)系统中，需要在一个有限的频率段内划分出尽可能多的通道，
但是由于干扰的存在（术语叫三阶互调变失真)，因此通道数量受到极大的限制。
而其中一种划分通道的方法被称为fang-sandrin数列，其数学表现形式就是这道题目了。

这道题目解的结果会直接影响到频率段利用的情况，价值很大，需要的数学知识其实也很简单，基本数论就够了，是一道很标准的算法题。

（我不是这方面出身的，具体用词可能不太正确，请专业人士指正）


补充：终于找到一篇中文的
http://www.policetech.com.cn/2005_shownews.asp?newsid=838

23 楼 jesse 2006-11-23  

clamp 写道

4-1=7-4=3所以，1，2，4，7……不可能是解

sorry,题目没理解清楚：）

可总结的公式有：
Mn >= n*(n-1)/2 + 1
对于每一个选定的Mn,按照以下公式进行递归，
i * (i - 1)/2 + 1 <= Mi <= Mn - (n-i)*(n-i+1)/2

不过很复杂，需要记录太多中间数据

22 楼 cookoo 2006-11-23  

对了，clamp还没说是什么应用背景呢？

21 楼 clamp 2006-11-23  

引用

哦，我没有小看这个题，已经仔细思考过了，如果方法或者结果不对，请指出。

4-1=7-4=3

所以，1，2，4，7……不可能是解

20 楼 jesse 2006-11-23  

clamp 写道

jesse 写道

最大值 = n*(n-1)/2 + 1
(因为数列1,2,4,7,....,Mi，Mi+i-1,....,是其中一个规则解)
（这个题目的问题应该是判断n个正整数时，有多少最优解，否则没任何意义，当然可以通过程序把所有的最优解列举出来。
最优解的个数＝（n-2）*(n-3)* ......* 2 * 1
（通过递规的方式穷举所有的结果）

//sigh，不要这么小看这道题目好不好？
再仔细思考思考吧

btw:你给出的所谓规则解是错的。

哦，我没有小看这个题，已经仔细思考过了，如果方法或者结果不对，请指出。

19 楼 clamp 2006-11-22  

jesse 写道

最大值 = n*(n-1)/2 + 1
(因为数列1,2,4,7,....,Mi, ,是其中一个规则解)
（这个题目的问题应该是判断n个正整数时，有多少最优解，否则没任何意义，当然可以通过程序把所有的最优解列举出来。
最优解的个数＝（n-2）*(n-3)* ......* 2 * 1
（通过递规的方式穷举所有的结果）

//sigh，不要这么小看这道题目好不好？
再仔细思考思考吧

btw:你给出的所谓规则解是错的。

18 楼 jesse 2006-11-22  

最大值 = n*(n-1)/2 + 1
(因为数列1,2,4,7,....,Mi, ,是其中一个规则解)
（这个题目的问题应该是判断n个正整数时，有多少最优解，否则没任何意义，当然可以通过程序把所有的最优解列举出来。
最优解的个数＝（n-2）*(n-3)* ......* 2 * 1
（通过递规的方式穷举所有的结果）

17 楼 cookoo 2006-11-22  

那个公式不对的，看那个超长的帖子47,50,74楼也有人得出1，2，5，10，12的结果，而且最优解的数列还不唯一。。。穷举没戏了。

16 楼 deafwolf 2006-11-22  

应该不是，那贴我找过，推出来的规律是最大的差应该是n*(n-1)/2，所以n=5时，最大的是11

http://www.web-nb.com/archivers/tid-3d0811-00-931488/

15 楼 cookoo 2006-11-22  

n=5时是1,2,5,10,12么？

14 楼 clamp 2006-11-21  

想要算法题？多的是，只怕根本没本事做

以前csdn上就有过一道，任意给定n个正整数，要求其两两之间的差都不相等，并且使得最大的数和最小的数的差最小。（不妨设最小数为1）

当n=3时，1,2,4
当n=4时，1,2,5,7
……

注意：这道题是有应用背景的，google一下应该可以搜到。

13 楼 deafwolf 2006-11-21  

hurricane1026 写道

qinysong 写道

下面是另一道问题，供大家娱乐

问题描述：
任意给定一个正方形，将正方形的各边做n等分,并将相应各点连接成水平或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角(n,n),请用程序计算并输出所有可能的路径总数和具体线路.输出结果按以下方式:

以n=1为例:
n = 1
Path1: (0,0) - (0,1) - (1,1)
Path2: (0,0) - (1,0) - (1,1)
Total = 2

这有什么好做的？
一个组合就完了，一共2n步，其中一半是向上， 你只要确定哪些步是向上就可以了。Cn/2n

麻烦给个代码看看

我的思路是用stack遍历，因为这是一个有向无环图
虽然遍历很容易，输出那种格式的结果就比较麻烦了，还没想到好的

12 楼 qinysong 2006-11-21  

jkit 写道

不知道这个贴的精华之处在什么地方。让人脑代替电脑做特定思考似乎不是什么值得称道的事。
大家不妨思考一下足球的每个面上的顶点之和都相等解法。看看人脑可以帮电脑做些什么，电脑可以帮人脑做些什么。

“让人脑代替电脑做特定思考似乎不是什么值得称道的事。”

我不太同意这种看法，首先电脑是不会做特定思考的，程序所做的只是一种计算、判断和选择，这种判断和选择是需要条件的，而这些条件必然是一种直接或间接的输入（发展到黑客帝国时代，或许会期待到你说的样子，呵呵），对于一个算法，哪怕其很简单，发现其内在实质，都是很有价值的，都是比一股脑的抛给电脑，让他在那狂奔要好

希望谁拿出一个真正的算法问题出来讨论。:wink:

11 楼 cookoo 2006-11-21  

qinysong 写道

３、最小的数（如1）不能和次小的两个（如2，3）在同一边，最大的不和次大的两个在同一边；

这样表述就没有问题了吧？

这个推断是建立在8个参数不等的前提下的巴？否则这条不成立。

BTW, jkit去海版申请评议好了，天知道谁投的。。。

10 楼 qinysong 2006-11-20  

下面是另一道问题，供大家娱乐

问题描述：
任意给定一个正方形，将正方形的各边做n等分,并将相应各点连接成水平或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角(n,n),请用程序计算并输出所有可能的路径总数和具体线路.输出结果按以下方式:

以n=1为例:
n = 1
Path1: (0,0) - (0,1) - (1,1)
Path2: (0,0) - (1,0) - (1,1)
Total = 2

9 楼 qinysong 2006-11-20  

hurricane1026 写道

jkit 写道

不知道这个贴的精华之处在什么地方。让人脑代替电脑做特定思考似乎不是什么值得称道的事。
大家不妨思考一下足球的每个面上的顶点之和都相等解法。看看人脑可以帮电脑做些什么，电脑可以帮人脑做些什么。

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

欢迎大家贴出有意思的算法题目，一起研究