首页 > 代码库 > NYOJ-491 幸运三角形

NYOJ-491 幸运三角形

幸运三角形

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述

        话说有这么一个图形,只有两种符号组成(‘+’或者‘-’),图形的最上层有n个符号,往下个数依次减一,形成倒置的金字塔形状,除第一层外(第一层为所有可能情况),每层形状都由上层决定,相邻的符号相同,则下层的符号为‘+’,反之,为‘-’;如下图所示(n = 3 时的两种情况):

                                           

如果图中的两种符号个数相同,那这个三角形就是幸运三角形,如上图中的图(2).

输入
有多组测试数据(少于20组)。
每行含一个整数n(0<n<20)。
输出
输出相应的幸运三角形个数。
样例输入
3
4
样例输出
4
6

   


01.#include<iostream>
02.using namespace std;
03.int n,sum=0,a[25][25];
04.void fun(int k,int p,int q)
05.{
06.int x,y,t,i,j;
07.if(k==n)
08.{
09.if(p==q)
10.sum++;
11.return;
12.}
13.for(t=0;t<2;t++)
14.{
15.x=p,y=q,a[0][k]=t;
16.t?x++:y++;
17.for(i=1,j=k-1;j>-1;i++,j--)
18.{
19.a[i][j]=a[i-1][j]^a[i-1][j+1];
20.a[i][j]?x++:y++;
21.}
22.fun(k+1,x,y);
23.}  
24.}
25.int main()
26.{
27.while(cin>>n)
28.{
29.sum=0;
30.if(n*(n+1)/2%2==0)
31.fun(0,0,0);
32.cout<<sum<<endl;
33.}
34.return 0;
35.}



回溯法

01.#include<iostream>
02.#include<cstring>
03.using namespace std;
04.unsigned char uchar;
05.char cc[2]={‘+‘,‘-‘};
06.int n,half,count;
07.char **p;
08.long sum;
09.void Backtrace(int t)
10.{
11.int i,j;
12.if(t>n)
13.sum++;
14.else
15.for(i=0;i<2;i++)
16.{
17.p[1][t]=i;
18.count+=i;
19.for(j=2;j<=t;j++)
20.{
21.p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
22.count+=p[j][t-j+1];
23.}
24.if((count<=half)&&(t*(t+1)/2-count<=half))
25.Backtrace(t+1);
26.for(j=2;j<=t;j++)
27.count-=p[j][t-j+1];
28.count-=i;
29.}
30.}
31.int main()
32.{
33.while(cin>>n)
34.{
35.count=0;
36.sum=0;
37.half=n*(n+1)/2;
38.if(half%2==0)
39.{
40.half/=2;
41.p=new char *[n+1];
42.for(int i=0;i<=n;i++)
43.{
44.p[i]=new char[n+1];
45.memset(p[i],0,sizeof(char)*(n+1));
46.}
47.Backtrace(1);
48.}
49.cout<<sum<<endl;
50.}
51.return 0;
52.}