有多少人参加考试

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; }