标题：计算差三角

仔细观察下面的数字组成的三角形：

    3
   1 4
  5 6 2

看出什么特征吗？
首先，它包含了1~6的连续整数。
重要的是：每个数字都是其下方相邻的两个数字的差（当然是大数减去小数）
满足这样特征的三角形，称为：差三角。

你的任务是找出1~15的整数组成的一个更大的差三角。其形如：

      ?
     4 ?
    ? ? ?
   * ? ? ?
  ? ? ? ? ?

其中，只给出了一个确定的数字：4
请确定出“*” 代表的是哪个一个数字。

直接提交该数字，不要提交多余的内容。

有意思的问题。初想了一下，差三角的独立变量是最底一行数，也就是说只要确定了最底一行数，数个三角就是确定的，那么遍历最底一行数的所有方案即可求出满足要求的差三角。应用回溯法可以在加快遍历。也许差三角还有其它更有意思的性质，不过目前没想到呵呵。

我用全排列写的，没有结果，应该是哪里错了

#include <stdio.h>
#include <stdlib.h>

#define M  5
#define N  15

int a[N];
void init()
{
    int i = 0;
    while (a[i] = i+1, ++i < N);
}
int sub(int i, int j, int k)
{
    return (a[i] + a[j] == a[k])
        || (a[i] + a[k] == a[j]);
}
int judge(int n)
{
    switch(n)
    {
    case  2: case  4:
    case  7: case 11:    return 1;
    case  3: return sub(0, 1, 2);
    case  5: return sub(1, 3, 4);
    case  6: return sub(2, 4, 5);
    case  8: return sub(3, 6, 7);
    case  9: return sub(4, 7, 8);
    case 10: return sub(5, 8, 9);
    case 12: return sub(6, 10, 11);
    case 13: return sub(7, 11, 12);
    case 14: return sub(8, 12, 13) && sub(9, 13, 14);
    }
    return 0;
}
void Output()
{
    int i, j, k = 0;
    for (i = 0;i < M;++i, puts(""))
    for (j = 0;j <= i;++j)
        printf("%3d", a[k++]);
    printf("\n");
}
void fun(int ip)
{
    int i, tmp;
    if (ip >= N)          return;
    if (!judge(ip))       return;
    if (ip == N-1)        Output();
    for(i = ip;i < N;++i)
    {
        tmp = a[i], a[i] = a[ip], a[ip] = tmp;
        fun(ip+1);
        tmp = a[i], a[i] = a[ip], a[ip] = tmp;
    }
}
int main(void)
{
    init();
    a[0] = 1;    a[1] = 4;
    a[2] = 2;    a[3] = 3;
    fun(2);
    a[0] = 2;    a[1] = 4;
    a[2] = 1;    a[3] = 3;
    fun(2);
    a[0] = 3;    a[1] = 4;
    a[2] = 1;    a[3] = 2;
    fun(2);
    return 0;
}

[ 本帖最后由 azzbcc 于 2013-5-3 11:21 编辑 ]

好深奥

能写一下代码吗？求指教，谢谢！

测试了一下，看起来这种差三角只存在于5阶以下（包括5阶），至少6到8阶是不存在题目定义下的差三角的。

由对称性可知如果某阶（1阶除外）存在差三角，那差三角的数量必然是偶数。关于这种差三角的性质我分析的还不透彻，或许也没别的什么性质了。

下面的代码修改主函数中cal的第一个参数可以观察各阶差三角。

如果想尝试更多阶（超过5阶）的需要修改宏N的值，不过随着阶数的增大，消耗的时间是指数级增长的，呵呵怕你受不了。

#include<stdio.h>

#define N    5
#define LEN    (N * (N + 1) / 2)

void cal(int n, int layer)
{
    static char flag[LEN];
    static int map[N][N], s[LEN];
    
    int i, j, k, t;
    
    if(layer == 0)
    for(i = 0; i < LEN; i++) flag[s[i] = i + 1] = 0;
        
    if(layer >= n)
    {
        for(i = n - 1; i >= 0; i--, puts(""))
        for(j = 0; j < n - i; j++) printf("%3d ", map[i][j]);
        puts("");
        return;
    }
    
    for(i = layer; i < n * (n + 1) / 2; i++)
    {
        t = s[layer], s[layer] = s[i], s[i] = t;
        if(!flag[s[layer]])
        {
            flag[map[0][layer] = s[layer]] = 1;
            for(j = 1, k = layer - 1; j <= layer; j++, k--)
            {
                map[j][k] = abs(map[j - 1][k] - map[j - 1][k + 1]);
                if(flag[map[j][k]]) break;
                flag[map[j][k]] = 1;
            }
            if(j > layer) cal(n, layer + 1);
            while(--j >= 0) flag[map[j][layer - j]] = 0;
            flag[s[layer]] = 0;
        }
        t = s[layer], s[layer] = s[i], s[i] = t;
    }
}

int main()
{
     cal(5, 0);
     return 0;
}

我二了以为最上面的数必然小于 4。。。。。。

1-15组成差类似三角不存在!

修改之后的

#include <stdio.h>
#include <stdlib.h>

#define M 5

int a[M][M];
void init()
{
    int i, j, k = 1;
    for (i = 0;i < M;++i)
    for (j = 0;j <= i;++j)
        a[i][j] = k++;
}
int judge(int x, int y)
{
    if (x < 2 || y == 1)
        return 1;
    if (0 != y)
        return a[x-1][y-2] + a[x][y-2] == a[x][y-1]
            || a[x-1][y-2] + a[x][y-1] == a[x][y-2];
    else
        return a[x-2][x-2] + a[x-1][x-2] == a[x-1][x-1]
            || a[x-2][x-2] + a[x-1][x-1] == a[x-1][x-2];
}
void Output()
{
    int i, j;
    for (i = 0;i < M;++i, puts(""))
    for (j = 0;j <= i;++j)
        printf("%3d", a[i][j]);
    printf("\n");
}
void fun(int ip_x, int ip_y)
{
    int i, j, tmp;
    
    if (!judge(ip_x, ip_y))    return;

    if (ip_x == M-1 && ip_y == M-1)
        if (judge(M, 0))    Output();

    for (i = ip_x;i < M;++i)
    for (j = 0;j <= i;++j)
    {
        if (i == ip_x && j < ip_y)
            continue;
        
        tmp = a[i][j], a[i][j] = a[ip_x][ip_y],
            a[ip_x][ip_y] = tmp;

        if (ip_x == ip_y)
            fun(ip_x+1, 0);
        else
            fun(ip_x, ip_y+1);

        tmp = a[i][j], a[i][j] = a[ip_x][ip_y],
            a[ip_x][ip_y] = tmp;
    }
}
int main()
{
    init();
    fun(0, 0);
    return 0;
}

[ 本帖最后由 azzbcc 于 2013-5-3 21:42 编辑 ]

存在的，有两组结果：

    5
   4 9
  7 11 2
 8 1 12 10
6 14 15 3 13
   
    5
   9 4
  2 11 7
 10 12 1 8
13 3 15 14 6