资源预览内容
第1页 / 共3页
第2页 / 共3页
第3页 / 共3页
亲,该文档总共3页全部预览完了,如果喜欢就下载吧!
资源描述
问题描述: 如下图是由14个“+”和14个“-”组成的符号三角形, 2个同号下面都是“+”,2个异号下面都是“-”。 - + + - + + + - + - - + + - - + - + + - - - - + + - + - 在一般情况下,符号三角形的第一行有n个符号, 符号三角形问题要求对于给定的n, 计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 解题思路: 1、不断改变第一行每个符号,搜索符合条件的解,可以使用递归回溯 为了便于运算,设+ 为0,- 为1,这样可以使用异或运算符表示符号三角形的关系 +为+即00=0, -为+即11=0, +-为-即01=1, -+为-即10=1; 2、因为两种符号个数相同,可以对题解树剪枝, 当所有符号总数为奇数时无解,当某种符号超过总数一半时无解 源代码:#includeiostream using namespace std; typedef unsigned char uchar; char cc2=+,-; /便于输出 int n, /第一行符号总数 half, /全部符号总数一半 counter; /1计数,即“-”号计数 uchar *p; /符号存储空间 long sum; /符合条件的三角形计数 void Backtrace(int t) /t,第一行第t个符号 int i, j; if( t n ) /符号填充完毕 sum+; /打印符号 cout 第 sum 个:n; for(i=1; i=n; +i) for(j=1; ji; +j) cout ; for(j=1; j=n-i+1; +j) cout cc pij ; cout n; else for(i=0; i2; +i) p1t = i; /第一行第t个符号 counter += i; /“-”号统计,因为+的值是0 for(j=2; j=2时,可以运算出下面行的某些符号,j可代表行号 pjt-j+1 = pj-1t-j+1pj-1t-j+2;/通过异或运算下行符号,t-j+1确定的很巧 counter += pjt-j+1; if( (counter = half) & ( t*(t+1)/2 - counter = half) ) /若符号统计未超过半数,并且另一种符号也未超过半数,同时隐含两者必须相等才能结束 Backtrace(t+1); /在第一行增加下一个符号 /回溯,判断另一种符号情况 像是出栈一样,恢复所有对counter的操作 for(j=2; j=t; +j) counter -= pjt-j+1; counter -= i; int main() cout n; counter = 0; sum = 0; half = n*(n+1)/2; int i=0; if( half%2 = 0 ) /总数须为偶数,若为奇数则无解 half /= 2; p = new uchar *n+1; for(i=0; i=n; +i) pi = new ucharn+1; memset(pi, 0, sizeof(uchar)*(n+1); Backtrace(1); for(i=0; i=n; +i) /删除二维动态数组的方法 delete pi; delete p; cout n总共 sum 个 endl; return 0;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号