张书涵_符号三角形问题

《张书涵_符号三角形问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于符号三角形数与n的关系的研究与实现云南师范大学计算机应用技术张书涵1问题描述在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。例如图1：由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。++-+-+++----+-+++--++--+---+图1符号三角形本文就是计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同，并且探讨两种符号数相同的不同符号三角形的个数与n的

2、关系。2问题分析用n元组x[1:n]表示符号三角形的第一行。X[i]=1表示第一行第i个符号为“+”，X[i]=0表示第一行第i个符号为“-”。可行性约束函数为，当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4。容易看出，第1行n个符号的数值不同，将直接导致符号三角形的数值F(n)不同。显然，符号三角形的个数F(n)是随着n的变化而变化。那么，得知F(n)与n必然存在一种关系。其次，一个符号三角形有n(n+1)/2个符号，显然这个公式的分子n，n+1中必有一个为偶数。记G(n)为一个符号三角形

3、所包含的符号数，假定n为偶数。则上述的公式可改写成：。而且n/2必须再次为偶数，不然就不满足条件：符号三角形的符号数G(n)所含的“+”和“—”的个数相同。所以，n必然是4的倍数，即n=4k，其中k=1，2，3，······。根据上面的论述，易知当公式的分子n，n+1中有且只有一个为4的倍数，此探讨才有意义，并且研究的条件再次收缩。3问题解决用穷举法列出n和符号数以及符号三角形数F（n）的映射表，如表1所示。n符号总数符号三角形个数F（n）11023036441065150621072812836409450105

4、5011661711278410表1n和符号数以及符号三角形数F（n）的映射表根据穷举的结果我们也可以看出，当n=4i或n=4i-1（i=1,2,3,4…）时存在符号三角形，当n=4i-2或4i-3时不存在符号三角数。4运行结果5总结通过上述的分析，基本上理解了回溯算法。当n=4i或n=4i-1（i=1,2,3,4…）时存在符号三角形，当n=4i-2或4i-3时不存在符号三角数。但是运用现有的技术很难得到F(n)关于n的精确表达式。所以，这个问题还有待进一步研究。附录：程序代码：#include"iostream"

5、usingnamespacestd;typedefunsignedcharuchar;charcc[2]={'+','-'};//便于输出intn,//第一行符号总数half,//全部符号总数一半counter;//1计数，即“-”号计数uchar**p;//符号存储空间longsum;//符合条件的三角形计数//t，第一行第t个符号voidBacktrace(intt){inti,j;if(t>n){//符号填充完毕sum++;//打印符号cout<<"第"<

6、+i){for(j=1;j=2时，可以运算出下面行的某些符号{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//通过异或运算下行符号counter+=p[j][

7、t-j+1];}if((counter<=half)&&(t*(t+1)/2-counter<=half)){//若符号统计未超过半数，并且另一种符号也未超过半数Backtrace(t+1);//在第一行增加下一个符号}//回溯，判断另一种符号情况for(j=2;j<=t;++j){counter-=p[j][t-j+1];}counter-=i;}}}intmain(){cout<<"请输入第一行符号个数n：";cin>>n;counter=0;sum=0;half=n*(n+1)/2;inti=0;if(hal

8、f%2==0){//总数须为偶数，若为奇数则无解half/=2;p=newuchar*[n+1];for(i=0;i<=n;++i){p[i]=newuchar[n+1];memset(p[i],0,sizeof(uchar)*(n+1));}Backtrace(1);for(i=0;i<=n;++i){delete[]p[i];}delete[]p;}co