差三角

wayne

不错，chyanog的Mathematica用的简直是炉火纯青啊

G-Spider

虽然是可以筛选的，还是来两个比较慢的c实现，M=5的时候，基本上没法忍受等多久。

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int datacmp(int *data,int n)
   
5. {
   
6.     int i,j;
   
7.     if( data[0] != abs(data[1]-data[2]) )
   
8.         return -1;      
   
9.     for(i=1;i<n-1;i++)
   
10.         for(j=0;j<n-1;j++)
    
11.             if( data[2*i+j-1] != abs(data[2*i+j+1]-data[2*i+j+2]) )
    
12.                 return -1;
    
13.    
    
14.     return 0;
    
15. }
    
16.    
    
17. void main()
    
18. {
    
19.     int a,b,c,d,e,f;
    
20.     int i,j;
    
21.     int data[6]={0};
    
22.     for(a=1;a<=6;a++)
    
23.     {
    
24.         for(b=1;b<=6;b++)
    
25.         {
    
26.             if(a==b)
    
27.                 continue;
    
28.             for(c=1;c<=6;c++)
    
29.             {
    
30.                 if(a==c||b==c)
    
31.                     continue;
    
32.                 for(d=1;d<=6;d++)
    
33.                 {
    
34.                     if(a==d||b==d||c==d)
    
35.                         continue;
    
36.                     for(e=1;e<=6;e++)
    
37.                     {
    
38.                         if(a==e||b==e||c==e||d==e)
    
39.                             continue;
    
40.                         for(f=1;f<=6;f++)
    
41.                         {
    
42.                             if(a==f||b==f||c==f||d==f||e==f)
    
43.                                 continue;
    
44.                             data[0]=a;data[1]=b;data[2]=c;data[3]=d;data[4]=e;data[5]=f;
    
45.                             if(0 != datacmp(data,3))
    
46.                                 break;
    
47.                             printf("%d %d %d %d %d %d \n",data[0],data[1],data[2],data[3],data[4],data[5]);
    
48.                         }
    
49.                     }
    
50.                 }
    
51.             }
    
52.         }
    
53.     }
    
54. }

复制代码

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define M   4        /* 差三角的层数 */
   
5. 
   
6. #define N   (((M)*(M+1))/2)
   
7. 
   
8. int datacmp(int *data,int n)
   
9. {
   
10.     int i,j;
    
11.     if( data[0] != abs(data[1]-data[2]) )
    
12.         return -1;     
    
13.     for(i=1;i<n-1;i++)
    
14.     {
    
15.         for(j=0;j<n-1;j++)
    
16.             if( data[2*i+j-1] != abs(data[2*i+j+1]-data[2*i+j+2]) )
    
17.                 return -1;
    
18.     }
    
19.     return 0;
    
20. }
    
21.    
    
22. void swap(int *data, int i, int offset)
    
23. {
    
24.     int tmp;
    
25.     tmp = data[offset];
    
26.     data[offset] = data[i];
    
27.     data[i] = tmp;
    
28. }
    
29. 
    
30. void order(int *data,int offset)
    
31. {
    
32.     int i,tmp;
    
33.     if(offset == N-1)
    
34.     {
    
35.         if(0 == datacmp(data,M))
    
36.         {
    
37.             for(i=0;i<N;i++)
    
38.                 printf("%d ",data[i]);
    
39.             printf("\n");
    
40.         }
    
41.         return;
    
42.     }
    
43.     for(i = offset; i < N; i++)
    
44.     {
    
45.         swap(data,i, offset);
    
46.         order(data,offset + 1);
    
47.         swap(data,i, offset);
    
48.     }
    
49. }
    
50. 
    
51. void main()
    
52. {
    
53.     int i,data[N];;
    
54.     for(i = 0; i<N; i++)
    
55.         data[i] = i+1;
    
56.     order(data,0);
    
57. }

复制代码

zgg___

呵呵，今天试了试，1-36的也没有找到呢。

chyanog

21# wayne
wayne兄过奖了，我不会的地方多着呢，
前面的Mathematica代码又优化了一下，n=5时半秒就够了，构造"table"时发现这里Table比Map快的多

1. (n = 5;
   
2.   k = n (n + 1)/2;
   
3.   table = Quiet@With[{
   
4.       expr=Evaluate[Join@@NestList[Abs@Differences@# &, Slot~Array~n, n-1] /.  Slot[x_] :> i[[x]]]
   
5.       },
   
6.   Table[expr, {i, Permutations[Range@k, {n}]}]];
   
7.   table = Pick[table, Total[table, {2}], Tr@Range@k];
   
8.   fmt = MatrixForm@Internal`PartitionRagged[Reverse@#, Range[n]] &;
   
9.   Do[If[Unequal @@ i, Print@fmt@i], {i, table}]
   
10.   ) // AbsoluteTiming
    
11. Clear["`*"]

复制代码

hujunhua

上面的程序将5改成6就蹦出很多行错误信息。

我猜想n>5时就无解了，而且证明起来可能不会太难。有时间了试一下。

chyanog

25# hujunhua
看提示是似乎内存不够了

G-Spider

22# G-Spider
datacmp函数写法有误，改一下：

1. int datacmp(int *data,int n)
   
2. {
   
3.     int i,j;   
   
4.     for(i=1;i<n;i++)
   
5.         for(j=1;j<n;j++)
   
6.             if(j<=i)
   
7.                 if( data[( ( (i)*(i+1) )/2)-i+j-1] != abs(data[( ( (i+1)*(i+1+1) )/2)-(i+1)+j-1]-data[( ( (i+1)*(i+1+1) )/2)-(i+1)+j+1-1]) )
   
8.                     return -1;
   
9.     return 0;
   
10. }

复制代码

KeyTo9_Fans

经验证，$9$阶、$10$阶、$11$阶都无解。

我同意$25$楼hujunhua版主的猜想。

#####

为了使问题更有趣，我们将楼主的条件放松，变成下面的问题：

————————————————————
给定$n$，求最小的$m$，使得：

存在一个$n$阶的、数字范围是$1$到$m$的、每个数字最多出现$1$次的差三角。
————————————————————

于是当$n\leq 8$时，结果如下：（为了图个方便，我将三角形横着摆了。）

1. 1: 1
   
2.    1
   
3. 2: 3
   
4.    3
   
5.    2   1
   
6. 3: 6
   
7.    6
   
8.    2   4
   
9.    5   3   1
   
10. 4: 10
    
11.    9
    
12.   10   1
    
13.    3   7   6
    
14.    8   5   2   4
    
15. 5: 15
    
16.   13
    
17.    3  10
    
18.   15  12   2
    
19.   14   1  11   9
    
20.    6   8   7   4   5
    
21. 6: 22
    
22.   13
    
23.   21   8
    
24.    3  18  10
    
25.   22  19   1   9
    
26.   20   2  17  16   7
    
27.    6  14  12   5  11   4
    
28. 7: 33
    
29.   19
    
30.   32  13
    
31.    3  29  16
    
32.   33  30   1  15
    
33.   31   2  28  27  12
    
34.    6  25  23   5  22  10
    
35.   17  11  14   9   4  18   8
    
36. 8: 44
    
37.   29
    
38.    6  23
    
39.   43  37  14
    
40.   44   1  36  22
    
41.    3  41  40   4  18
    
42.   42  39   2  38  34  16
    
43.   33   9  30  28  10  24   8
    
44.    7  26  17  13  15   5  19  11

复制代码

hujunhua

当我感觉n>5无解的时候就在暗想，或许 KeyTo9_Fans能从中发现一个新数列，果然苗头初现。

我曾试图估算三角形顶尖上那个数的上限u(n)，感觉当n充分大时，应有u(n)  <1而导致无解。

hujunhua

28# KeyTo9_Fans
算到11阶了，我想都不敢想哦！
是机器超强，还是算法高超？