算法题--搭积木

搭积木

小明最近喜欢搭数字积木，
一共有10块积木，每个积木上有一个数字，0~9。

搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。

下面是两种合格的搭法：

   0
  1 2
 3 4 5
6 7 8 9

   0
  3 1
 7 5 2
9 8 6 4    

请你计算这样的搭法一共有多少种？

请填表示总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

解题思路：这道题为塔型结构问题，常规操作先把10个元素存入数组，从题目可以得出条件：上面的元素一定比它底下两个元素小。我采用回溯算法解决，利用回溯算法，对数组进行排列，穷举出所有可能出现的情况，然后再根据条件进行筛选。

代码示例：

public class Main {
// 定义变量，用来记录符合的情况数
static int n;
// 回溯算法，列出所有可能的情况
static void recall(int[] a, int k) {
if (k == a.length - 1) {
select(a);
return;
}
for (int i = k; i < a.length; i++) {
{
int t = a[i];
a[i] = a[k];
a[k] = t;
}
recall(a, k + 1);
{// 回溯
int t = a[i];
a[i] = a[k];
a[k] = t;
}
}
}
// 筛选
static void select(int[] a) {
if (a[1] < a[0])
return;
if (a[2] < a[0])
return;
if (a[3] < a[1])
return;
if (a[4] < a[1])
return;
if (a[4] < a[2])
return;
if (a[5] < a[2])
return;
if (a[6] < a[3])
return;
if (a[7] < a[3])
return;
if (a[7] < a[4])
return;
if (a[8] < a[4])
return;
if (a[8] < a[5])
return;
if (a[9] < a[5])
return;
n++;
}
public static void main(String[] args) {
int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
recall(a, 0);
System.out.println(n);
}
}

输出结果：768

最后

以上就是柔弱项链为你收集整理的算法题--搭积木的全部内容，希望文章能够帮你解决算法题--搭积木所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。