试探与回溯 找出更大差三角


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

   3
 1 4
5 6 2

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

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

    ?
   4 ?
  ? ? ?
 ? ? ? ?
? ? ? ? ?

源码FindNum.java


public class FindNum {
//  static int z=0;
    
    static boolean c1(int[] a) {
        return a[0]==Math.abs(a[1]-a[2]);
    }
    static boolean c2(int[] a) {
        return a[1]==Math.abs(a[3]-a[4]) && a[2]==Math.abs(a[4]-a[5]);
    }
    static boolean c3(int[] a) {
        return a[3]==Math.abs(a[6]-a[7]) && a[4]==Math.abs(a[7]-a[8])
                && a[5]==Math.abs(a[8]-a[9]);
    }
    static boolean c4(int[] a) {
        return a[6]==Math.abs(a[10]-a[11])
        && a[7]==Math.abs(a[11]-a[12])
        && a[8]==Math.abs(a[12]-a[13])
        && a[9]==Math.abs(a[13]-a[14]);
    }
    static void show(int[] a) {
        System.out.println(a[0]);
        System.out.println(a[1] + " " + a[2]);
        System.out.println(a[3] + " " + a[4] + " " + a[5]);
        System.out.println(a[6] + " " + a[7] + " " + a[8] + " " + a[9]);
        System.out.println(a[10] + " " + a[11] + " " + a[12] + " " + a[13] + " " + a[14]);
    }

    static void f(int[] a, int k) {
//      z+=1;
        if (k==3 && !c1(a)) return;
        if (k==6 && !c2(a)) return;
        if (k==10 && !c3(a)) return;
        if (k==14) {
            if (c4(a)) show(a);
            return;
        }
        for (int i=k; i<a.length; i++) {
            
            int t = a[k];
            a[k] = a[i];
            a[i] = t;
            
            f(a, k+1);
            
            t = a[k];
            a[k] = a[i];
            a[i] = t;
        }       
    }
    
    
    public static void main(String[] args) {
        int[] x = new int[15];
        for (int i=0; i<15; i++) {
            x[i] = i+1;
        }
        f(x, 0);
    //  System.out.println(z);

    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注