張書涵_符號三角形問題.doc

關(guān)于符號三角形數(shù)與n的關(guān)系的研究與實現(xiàn)云南師范大學 計算機應(yīng)用技術(shù) 張書涵1 問題描述在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。例如圖1：由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。+ + - + - + + - - - - +- + + + - + + - + - -+ 圖1 符號三角形本文就是計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同，并且探討兩種符號數(shù)相同的不同符號三角形的個數(shù)與n的關(guān)系。2 問題分析用n元組x1:n表示符號三角形的第一行。Xi=1表示第一行第i個符號為“+”， Xi=0表示第一行第i個符號為“-”?？尚行约s束函數(shù)為，當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4 。容易看出，第1行n個符號的數(shù)值不同，將直接導致符號三角形的數(shù)值F(n)不同。顯然，符號三角形的個數(shù)F(n)是隨著n的變化而變化。那么，得知F(n)與n必然存在一種關(guān)系。其次，一個符號三角形有n(n+1)/2個符號，顯然這個公式的分子n，n+1中必有一個為偶數(shù)。記G(n)為一個符號三角形所包含的符號數(shù)，假定n為偶數(shù)。則上述的公式可改寫成：。而且n/2必須再次為偶數(shù)，不然就不滿足條件：符號三角形的符號數(shù)G(n)所含的“+”和“”的個數(shù)相同。所以，n必然是4的倍數(shù)，即n=4k，其中k=1，2，3，。根據(jù)上面的論述，易知當公式的分子n，n+1中有且只有一個為4的倍數(shù)，此探討才有意義，并且研究的條件再次收縮。3 問題解決 用窮舉法列出n和符號數(shù)以及符號三角形數(shù)F（n）的映射表，如表1所示。n符號總數(shù)符號三角形個數(shù)F（n）110230364410651506210728128364094501055011661711278410表1 n和符號數(shù)以及符號三角形數(shù)F（n）的映射表根據(jù)窮舉的結(jié)果我們也可以看出，當n=4i或n=4i-1（i=1,2,3,4）時存在符號三角形，當n=4i-2或4i-3時不存在符號三角數(shù)。4 運行結(jié)果 5 總結(jié)通過上述的分析，基本上理解了回溯算法。當n=4i或n=4i-1（i=1,2,3,4）時存在符號三角形，當n=4i-2或4i-3時不存在符號三角數(shù)。但是運用現(xiàn)有的技術(shù)很難得到F(n)關(guān)于n的精確表達式。所以，這個問題還有待進一步研究。附錄：程序代碼：#includeiostream using namespace std; typedef unsigned char uchar; char cc2=+,-; /便于輸出 int n, /第一行符號總數(shù) half, /全部符號總數(shù)一半 counter; /1計數(shù)，即“-”號計數(shù) uchar *p; /符號存儲空間 long sum; /符合條件的三角形計數(shù) /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 pij ; cout n; else for(i=0; i2; +i) p1t = i; /第一行第t個符號 counter += i; /“-”號統(tǒng)計 for(j=2; j=2時，可以運算出下面行的某些符號 pjt-j+1 = pj-1t-j+1pj-1t-j+2;/通過異或運算下行符號 counter += pjt-j+1; if( (counter = half) & ( t*(t+1)/2 - counter = half) ) /若符號統(tǒng)計未超過半數(shù)，并且另一種符號也未超過半數(shù) Backtrace(t+1); /在第一行增加下一個符號 /回溯，判斷另一種符號情況 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 ) /總數(shù)須為偶數(shù)，若為奇數(shù)則無解 half /= 2; p = new uchar *n+1; for(i=0; i=n; +i) pi = new ucharn+1; memset(pi, 0, sizeo