试探与回溯-差三角问题

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


   3
 1 4
5 6 2


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


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


    ?
   4 ?
  ? ? ?
 ? ? ? ?
? ? ? ? ?
*/

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


   3
 1 4
5 6 2


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


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


    ?
   4 ?
  ? ? ?
 ? ? ? ?
? ? ? ? ?
*/
public class ChaSanJiao {
	//分为4层的检测
	static boolean check1(int[] a) {
		return a[0] == Math.abs(a[1] - a[2]);
	}


	static boolean check2(int[] a) {
		return a[1] == Math.abs(a[3] - a[4]) && a[2] == Math.abs(a[4] - a[5]);
	}


	static boolean check3(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 check4(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) {
		// System.out.print(k+" ");
		if (k == 3 && !check1(a))
			return;
		if (k == 6 && !check2(a))
			return;
		if (k == 10 && !check3(a))
			return;


		if (k == 14) {
			// show(a);
			if (check4(a))
				show(a);
			return;
		}


		for (int i = k; i < a.length; i++) {
			{
				int t = a[k];
				a[k] = a[i];
				a[i] = t;
			} // a[k] <--> a[i]


			f(a, k + 1);


			{
				int t = a[k];
				a[k] = a[i];
				a[i] = t;
			} // a[k] <--> a[i]
		}
	}


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

    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

试探与回溯-差三角问题,布布扣,bubuko.com

试探与回溯-差三角问题

原文：http://blog.csdn.net/u011925500/article/details/20296161