张书涵_符号三角形问题.doc

关于符号三角形数与n的关系的研究与实现 云南师范大学 计算机应用技术 张书涵 1 问题描述 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。 例如图1：由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 图1 符号三角形 本文就是计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同，并且探讨两种符号数相同的不同符号三角形的个数与n的关系。 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)为一个符号三角形所包含的符号数，假定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） 1 1 0 2 3 0 3 6 4 4 10 6 5 15 0 6 21 0 7 28 12 8 36 40 9 45 0 10 55 0 11 66 171 12 78 410 表1 n和符号数以及符号三角形数F（n）的映射表 根据穷举的结果我们也可以看出，当n=4i或n=4i-1（i=1,2,3,4…）时存在符号三角形，当n=4i-2或4i-3时不存在符号三角数。 4 运行结果 5 总结 通过上述的分析，基本上理解了算法…）时存在符号三角形，当n=4i-2或4i-3时不存在符号三角数。但是运用现有的技术很难得到F(n)关于n的精确表达式。所以，这个问题还有待进一步研究。 附录： 程序代码： #includeiostream using namespace std; typedef unsigned char uchar; char cc[2]={+,-}; //便于输出 int n, //第一行符号总数 half, //全部符号总数一半 counter; //1计数，即“-”号计数 uchar **p; //符号存储空间 long sum; //符合条件的三角形计数 //t，第一行第t个符号 void Backtrace(int 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[ p[i][j] ] ; } cout \n; } } else { for(i=0; i2; ++i) { p[1][t] = i; //第一行第t个符号 counter += i; //“-”号统计 for(j=2; j=t; ++j) //当第一行符号=2时，可以运算出下面行的某些符号