差三角

wayne

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

G-Spider

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

1. #include <stdio.h>
2. #include <math.h>
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;
14. return 0;
15. }
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>
4. #define M 4 /* 差三角的层数 */
6. #define N (((M)*(M+1))/2)
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. }
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. }
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. }
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阶了，我想都不敢想哦！ 是机器超强，还是算法高超？