nyoj-----幸运三角形
幸运三角形
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
话说有这么一个图形，只有两种符号组成（‘+’或者‘-’），图形的最上层有n个符号，往下个数依次减一，形成倒置的金字塔形状，除第一层外（第一层为所有可能情况），每层形状都由上层决定，相邻的符号相同，则下层的符号为‘+’，反之，为‘-’;如下图所示（n = 3 时的两种情况)：
如果图中的两种符号个数相同，那这个三角形就是幸运三角形，如上图中的图（2）.
输入有多组测试数据（少于20组）。
每行含一个整数n（0<n<20)。输出输出相应的幸运三角形个数。样例输入
3
4样例输出
4
6代码：
1 #include<stdio.h>
2 int str[20]={0};
3 bool map[20][20];
4 void dfs(int x,int pos)
5 {
6 int i;
7 if(x==pos)
8 {
9 int ans=0;
10 do{
11 if(map[pos][pos]) ans++;
12 for(i=1;i<pos;i++) //下一城
13 {
14 if(map[pos][i]==map[pos][i+1]) map[pos-1][i]=1; //tong wei 1
15 else map[pos-1][i]=0;
16 if(map[pos][i]) ans++;
17 if(4*ans>x*(x+1)) return ;
18 }
19 }while(--pos);
20 if(4*ans==x*(x+1)) str[x]++;
21 return ;
22 }
23 map[x][pos+1]=0; //采用横向搜索
24 dfs(x,pos+1);
25 map[x][pos+1]=1;
26 dfs(x,pos+1);
27 }
28 int main()
29 {
30 int n,i;
31 for(i=1;i<19;i++)
32 {
33 if(i%4==3||i%4==0)dfs(i,0);
34 }
35 str[19]=32757;
36 while(scanf("%d",&n)!=EOF)
37 {
38 printf("%d\n",str[n]);
39 }
40 return 0;
41 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-01-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录