实验四 回溯算法和分支限界法 符号三角形问题

 基本题一:符号三角形问题

一、实验目的与要求

1、掌握符号三角形问题的算法;

2、初步掌握回溯算法;

二、实验题

下面都是“-”。下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2个异号下面都是“-”。

+   +   -   +   -   +   +

+   -   -   -   -   +

-   +   +   +   -

   -   +   +   -

   -   +   -

   -   -

   +

 

 

在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。

三、实验提示

void Triangle::Backtrack(int t)

{

  if ((count>half)||(t*(t-1)/2-count>half)) return;

  if (t>n) sum++;

    else

      for (inti=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;

     }

  }

 

四,源代码

import java.io.*;

import java.util.*;

 

 

public class Triangles1

{

       public static int n,

              half,

              count;

       public static int[][] p;

       public static long sum;

 

       public static long computs(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++){

                     if(p[j-1][t-j+1]==p[j-1][t-j+2])p[j][t-j+1]=1;

                     else p[j][t-j+1]=0;

                     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 static void main(String[] args)

       {

              System.out.println("请输入第一行符号值:");

              Scanner read =new Scanner(System.in);

              int n=read.nextInt();

              System.out.println("个数:"+computs(n));

       }

}输入:7

结果:

 

实验四 回溯算法和分支限界法 符号三角形问题



本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/824853

上一篇:JAVA构造方法与方法是啥意思


下一篇:Swift3.0语言教程查找字符集和子字符串