有多少人参加考试

nlrte13

排了半天也只排出个13人的解……
如下：
A, C, C, B, A, A
B, B, B, C, C, A
C, A, A, A, B, A
C, A, C, C, B, C
B, B, B, B, B, B
A, B, A, A, B, B
B, C, B, C, B, C
C, C, A, A, C, B
B, A, A, C, A, B
A, A, B, C, C, C
C, B, B, A, A, C
B, B, C, A, C, B
C, A, A, B, C, C

nlrte13

难道答案真是13人么？排不出14人的了……

nlrte13

发现可以建立一个网格覆盖的模型。。。。。

nlrte13

有三种答案，那么应该是立体空间格覆盖^^
技巧发现多了可以组织成理论，嘿嘿

shshsh_0510

14# nlrte13
兄弟，讲透彻点啊，让俺学习一下

nlrte13

14# nlrte13
兄弟，讲透彻点啊，让俺学习一下
shshsh_0510 发表于 2009-7-16 16:14

换一种思路，先不考虑有几道题目，而是考虑有多少人考试。
如果有N人参加考试，那么需要覆盖C(3, N)个格子。

若N能被3整除，对于第一道题目来说，最多能覆盖( N / 3 )^3 个格子；
若余数为1，对于第一道题目来说，最多能覆盖( N / 3 )^2 * ( 1 + N / 3 )个格子；
否则，对于第一道题目来说，最多能覆盖( N / 3 ) * ( 1 + N / 3 )^2 个格子；
这三种情况，必然有 [ ( C(3, N)-1 )/3 ] + 1 个重复的 A或B或C，这也是最小重复的情况。

在不考虑和第一题重复覆盖，第二道题目亦是如此。
每一题相当于若干“块”的集合，考虑重复覆盖的情况下，用最少的“块”集覆盖满 C(3, N)个格子。

对任意N>0, 第一题之后，若 [ ( C(3, N)-1 )/3 ] + 1 不等于 1，说明还有重复覆盖，需要有后一题来解决
在最优的情况，令 n1 = [ ( C(3, N)-1 )/3 ] + 1，第二题使得剩余重复覆盖 = [ ( n1-1 )/3 ] + 1
如此迭代下去，直到剩余重复覆盖数 = 1。那么迭代次数就等于满足N人任取3人能有一题不重复的最小题目数。

用计算机编程迭代以下，很快可以得到，N=13时，通过6次迭代使得n7 = 1；
N=14时，通过7次迭代使得n8=1。

所以13人参加已是最多的，14人至少需要7题。

nlrte13

突然想到一个更好的模型，不过只是刚有一点萌芽^^
待俺再好好想想

数学星空

呵呵,能否给出一个估计....
或者一个递推关系??

nlrte13

我想的第二种方法和第一种结果竟然不一样，第二种方法算出最多可以有19人。
初步感觉应该是第一种方法错了，可是手工排太难排了，始终没排出超过13人的。

明天或者后天我把代码发上来^^

nlrte13

程序还是比较简单的，几行就搞定，先贴出来了：

int fun( int n )
{
        if( n < 3 )
                return 0;
               
        int iRet = 0;
        while( n > 2 )
        {
                n = n / 3 * 2 + n % 3;
                ++iRet;
        }
        return iRet;
}

int main( void )
{
        for( int n = 0; n < 730; ++n )
        {
                if( fun( n ) > 6 )
                        break;
        }
        return n - 1;
}