极湖

从这儿看到题目，翻译如下：

任意偶数个队，进行单循环赛，须在最短日期之内举行完全部赛事，请作出日程表之一。
（补充：每个队每天只能举行一场比赛）

并非只有一解的情况也有。
如果有余力，请给出所有可能的答案。

这属于体育赛事日程安排的问题，在数学上，比较接近“柯克曼女生问题”。

例如，4个队的情况下

1-2 3-4
1-3 2-4
1-4 2-3

６个队的情况下

1-2 3-4 5-6
1-3 2-5 4-6
1-4 2-6 3-5
1-5 2-4 3-6
1-6 2-3 4-5

是其一解。

这个问题看起来简单，做起来却颇伤脑筋。
我在网上找了一个比较容易理解的算法，就是一个队不动，其它队组成一个“环”之后旋转，每转一次得到一天的赛程。

用 JavaScript 实现的程序如下：

/**
 * 旋转数组
 */
function rotateArray(aOld) {
    var iLast = aOld.length - 1;
    return [aOld[iLast]].concat(aOld.slice(0, iLast));
}

/**
 * 生成日程表
 */
function getLeageSchedule(aTeam) {
    var aResult = [];
    if(aTeam.length%2 != 0) {
        aTeam.push('');
    }
    var vFirst = aTeam[0];
    var aCycle = aTeam.slice(1);
    var iHalfLen = aTeam.length/2;
    for(var i=0; i<aCycle.length; i++) {
        var aLeft = [vFirst].concat(aCycle.slice(iHalfLen).reverse());
        var aRight = aCycle.slice(0, iHalfLen);
        var aGames = [];
        for(var j=0; j<aLeft.length; j++) {
            if(aLeft[j] != '' && aRight[j] != '') {
                aGames.push(aLeft[j] + '-' + aRight[j]);
            }
        }
        aResult.push(aGames);
        aCycle = rotateArray(aCycle);
    }
    return aResult;
}

//测试
var aTeam = [1,2,3,4,5,6];
var aSchedule = getLeageSchedule(aTeam);
for(var i=0; i<aSchedule.length; i++) {
    document.write(aSchedule[i].join('  ') + '
');
}

程序运行的结果如下：
1-2 6-3 5-4
1-6 5-2 4-3
1-5 4-6 3-2
1-4 3-5 2-6
1-3 2-4 6-5

这个算法可能不是太好，只不过比较简单，有一点自己的发挥就是还考虑了奇数队的情况。
问题后面有人用 Ruby 实现了这一算法，总共才8行，实在让人佩服。

昨天做的拆数程序，效率甚低。为提高速度，在网上找了一个筛选法求素数的算法，利用这个算法，修改了一下程序。具体做法是：先把设定上限之内的素数全部找出（初始化），而且把素数作为哈希表的键值，然后循环拆数。这样一来，果然速度有极大提高。修改后的程序如下：

define('N',1000);       //上限
$arrP = array();
init_arrP();
for($i=2; $i<=N; $i++) {
    if(isset($arrP[$i])) {
        echo "$i\n";
    } else {
        list($p1, $p2) = split2P($i);
        if($p2 != 0) {
            echo "$i = $p1 + $p2\n";
        } else {
            list($p1, $p2, $p3) = split3P($i);
            if($p3 != 0) {
                echo "$i = $p1 + $p2 + $p3\n";
            } else {
                echo "> $i\n";
            }
        }
    
}

//筛选法求素数(初始化素数数组)
function init_arrP()
{
    global $arrP;
    $arrOut = array();
    for($i = 2; $i <= N; $i++) {
        if(!isset($arrOut[$i])) {
            $arrP[$i] = 1;
            for($j = $i*2; $j <= N; $j += $i) {
                $arrOut[$j] = 0;
            }
        } else {
            unset($arrOut[$i]);  //释放内存
        }
    }
}

//把一个数分解为两个大于2的素数(4除外)之和，若分解失败，返回 原数 和 0
function split2P($i)
{
    global $arrP;
    foreach($arrP as $p1 => $val) {
        $p2 = $i - $p1;
        if($i > 4 && ($p1 == 2 || $p2 == 2)) {
            continue;
        }
        if(isset($arrP[$p2])) {
            if($p2 > $p1) {
                return array($p1, $p2);
            } else {
                return array($p2, $p1);
            }
        }
    }
    
    return array($i, 0);
}

//把一个数分解为三个大于2的素数之和，若分解失败，返回 原数 和 0 0
function split3P($i)
{
    global $arrP;
    foreach($arrP as $p1 => $val) {
        list($p2, $p3) = split2P($i - $p1);
        if($p1 == 2 || $p2 == 2 || $p3 == 2) {
            continue;
        }
        if($p3 != 0) {
            $a = array($p1, $p2, $p3);
            sort($a);
            return $a;
        }
    }
    
    return array($i, 0, 0);
}

附1: 源程序
split_num2.php

附2: 上限为100000的执行结果
output1-100000.zip

通过“砌砖”，可以发现关于素数的一些规律。

首先，砖头有两种：
　一种是“整砖”（素数），合数是由整砖合成的“合成砖”（合数）。

“合成砖”有两种做法：

　(一) 可用同样大小的“整砖”合成。（乘法合成）
　(二) 可用不同大小的“整砖”合成。（加法合成）

以上两种做法，可以增加一个条件：
　“合成砖”必须用最少数量的“整砖”合成。

方法一图解：

规律：
“合成砖”可以用相同大小的“整砖”合成。
　如：4=2*2 6=3*2 8=2*4 10=5*2 12=3*4

方法二图解：


规律：
“合成砖”可以用不同大小的“整砖”合成。
　如：8=5+3 12=7+5
长度为偶数的合成砖，可以用两块“整砖”合成。
　如：6=3+3 8=5+3 12=7+5 14=7+7
长度为奇数的合成砖，可以用不超过三块的“整砖”合成。（如果不用长度为2的砖，需用三块“整砖”）
　如：9=7+2=3+3+3 15=13+2=3+5+5 35=11+11+13

如果遵守“最少合成”的原则，那么：
　世界上的砖，可以分为三种：整砖(素数)，二合砖(偶数)，三合砖(奇数)。

再具体一点，整砖是素数，偶数是二合砖，奇数是三合砖。

哥德巴赫猜想，不就是这个砌砖的规律么？

*付：
拆数
拆数（二）