fac5_4.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 162 页，例
//符号三角形问题的回溯解法
//
   class Triangles 
   { 
    
     static int n;                // 第一行的符号个数
     static int half;             // n*(n+1)/4
     static int count ;           // 当前“+”个数 
     static int [][] p;           // 符号三角形矩阵
     static long sum;             // 已找到的符号三角形数
     
    
     public static long compute(int nn)  
      {
        n=nn;
        count=0;
        sum=0;
        half=n*(n+1)/2;
        if(half%2==1)return 0;
        half=half/2;
        
        p=new int[n+1][n+1];
        for(int i=0;i<=n;i++)
          for(int j=0;j<=n;j++)p[i][j]=0;
        backtrack(1);
        return sum;
      }
     public static void backtrack(int t)
    {
     if((count>half)||(t*(t-1)/2-count>half))return ;
     if(t>n)sum++;
     else
      for(int i=0;i<2;i++)
       {
        p[1][t]=i;
        count+=i;
        for(int j=2;j<=t;j++)
         {
          p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
          count+=p[j][t-j+1];
         }
       backtrack(t+1);
       for(int j=2;j<=t;j++)
         count-=p[j][t-j+1]; 
       count-=i;
       }
    }
   }
      
  
      public class Fac5_4{
      public static void main(String args[])
  {
     Triangles  abc=new Triangles ();
     int n1=3;      
     System.out.println("最大符号三角形数 " + abc.compute(n1));
  }
}