符号三角形问题 解向量:用n元组刈1n表示符号三角形的第一行。 可行性约束函数:当前符号三角形所包含的“+”个数与“ 个数均不超过n*n+1)4 无解的判断:n*n+1)/2为奇数 private stati oid backtrack /int 复杂度分析 if((co if(t>f 计算可行性约束需要O(n)时间,在最坏情况下有 eeO(2)个结点需要计算可行性约束,故解符号三角 p形问题的回溯算法所需的计算时间为O(n2) for(int j=2 j <=t; j ++) plIt-j+1]=pl-1][t-j+1]p[-1[t-j+2 count+=poI[t-j+1 backtrack(t+1) for(int j=2; j<=t; j ++)count-=pDIt-j+11 count-=i14 符号三角形问题 •解向量：用n元组x[1:n]表示符号三角形的第一行。 •可行性约束函数：当前符号三角形所包含的“+”个数与“-” 个数均不超过n*(n+1)/4 •无解的判断：n*(n+1)/2为奇数 private 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; } } + + - + - + + + - - - - + - + + + - - + + - - + - - - + 复杂度分析 计算可行性约束需要O(n)时间，在最坏情况下有 O(2n )个结点需要计算可行性约束，故解符号三角 形问题的回溯算法所需的计算时间为 O(n2n )