历届试题搭积木（dfs 优化）

柔情只为你懂 2022-09-27 14:24 167阅读 0赞

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

下面是两种合格的搭法：   
0   
1 2   
3 4 5   
6 7 8 9

0   
3 1   
7 5 2   
9 8 6 4   
请你计算这样的搭法一共有多少种？

请填表示总数目的数字。

思路：

用c++的STL写这种提交答案的题再好不过了，快准狠啊

#include<iostream>  
    #include<algorithm>
    #include<cstdio>  
    using namespace std;
    int main()
    {
    	int a[10]={0,1,2,3,4,5,6,7,8,9},cnt=0;
    	do
    	{
    	  if ((a[0]<a[1]&&a[0]<a[2]) &&
    		 (a[1]<a[3]&&a[1]<a[4]) &&
    		  (a[2]<a[4]&&a[2]<a[5]) && 
    		  (a[3]<a[6]&&a[3]<a[7])&&
    		  (a[4]<a[7]&&a[4]<a[8])&&
    		  (a[5]<a[8]&&a[5]<a[9]) )
    		  {
    		  	cnt++;
    		   }
    	}while (next_permutation(a,a+10));
    	cout<<cnt;
    	return 0;
    }

用深搜的方法：

#include<iostream>  
    #include<cstdio>  
    using namespace std;
    int a[10],v[10]={0},cnt=0;
    void dfs(int x)
    {
    	int i;
    	if (x >10)
    	 return ;
    	if (x == 10)
    	{
    		if ((a[0]<a[1]&&a[0]<a[2]) &&
    		 (a[1]<a[3]&&a[1]<a[4]) &&
    		  (a[2]<a[4]&&a[2]<a[5]) && 
    		  (a[3]<a[6]&&a[3]<a[7])&&
    		  (a[4]<a[7]&&a[4]<a[8])&&
    		  (a[5]<a[8]&&a[5]<a[9]) )
    		  {
    		  	cnt++;
    		   }
    		return ;
    	}
    	for (i=0; i<10; i++)
    	{
    		if (!v[i])
    		{
    			a[x] = i;
    			v[i] = 1;
    			dfs(x+1);
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	dfs(0);
    	cout<<cnt;
    	return 0;
    }

上面两种方法运行时间都差不多，在通过给深搜优化，缩短时间

#include<iostream>  
    #include<cstdio>  
    using namespace std;
    int a[10],v[10]={0},cnt=0;
    void dfs(int x)
    {
    	int i;
    	if (x>10)
    	 return ;
    	else if (x == 3)
    	{
    		if (a[0]>a[1]|| a[0]>a[2])
    		return ;
    	} 
    	else if (x == 6)
    	{
    		if (a[1]>a[3] || a[1]>a[4] || a[2]>a[4] || a[2]>a[5])
    		 return ;
    	}
    	else if (x == 10)
    	{
    		if (a[3]>a[6] || a[3]>a[7] || a[4]>a[7] || a[4]>a[8] || a[5]>a[8] || a[5]>a[9])
    		 return ;
    		cnt++;
    	 }
    	for (i=0; i<10; i++)
    	{
    		if (!v[i])
    		{
    			a[x] = i;
    			v[i] = 1;
    			dfs(x+1);
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	dfs(0);
    	cout<<cnt;
    	return 0;
    }