张书涵_符号三角形问题(2)

表1 n和符号数以及符号三角形数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" 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; j<i; ++j) {

cout << " "; }

for(j=1; j<=n-i+1; ++j) {

cout << cc[ p[i][j] ] << " "; }

cout << "\n"; } } else

{ for(i=0; i<2; ++i) {

p[1][t] = i; //第一行第t个符号 counter += i; //“-”号统计

for(j=2; j<=t; ++j) //当第一行符号>=2时，可以运算出下面行的某些符号 {

p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2];//通过异或运算下行符号 counter += p[j][t-j+1]; }

if( (counter <= half) && ( t*(t+1)/2 - counter <= half) )

{//若符号统计未超过半数，并且另一种符号也未超过半数 Backtrace(t+1); //在第一行增加下一个符号