下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。

在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。

題意分析

也就是 給了一個n數(shù)字

然后就會形成 第一行長度為n的三角形

然后用+ -號 把三角形填充

問是否可以用 + -號相等的數(shù)量 進(jìn)行填充三角形

可以有多少中方案？？？

思路過程分析

首先我們利用簡單的樣例分析
如果n=3
然后我們用一行為
+++分析 如果第一行是+++，根據(jù)+和-個數(shù)相等，剩下的符合只能是—

所以如下
+++
- -
-

如果是

+-+
--
+

++-
-+
-

由上總結(jié)出規(guī)律就是，如果第一行確定了，那么剩下的行都是根據(jù)上一行而確定的

也就是

+++  第一行都是+
第二行 就上 它的左上角和右上角
++ 得-
+- 得+
-+ 得+
-- 得+

根據(jù)這個規(guī)律就能構(gòu)圖了

所以我們那就先把第一行的所有情況都遍歷一邊，
然后把每次情況都構(gòu)圖一次，
記錄下+ -號的個數(shù)
看 + -號是不是各一半

算法分析

我們已經(jīng)知道 過程了

那么如何 寫出算法？

首先由于 要把第一行的所有情況都遍歷一邊

那么我們就是要用 dfs全排列方法遍歷

所以我們用dfs（t）t表示第一行中的位置
構(gòu)建第一行，

但是我們發(fā)現(xiàn)，比如n = 100，t = 20時候，其實(shí)是可以把前20個所對應(yīng)下面的行構(gòu)建出來，并且如果這種情況下，如果-號或者+號已經(jīng)大于一半，那么就不可能是這種情況了，就直接剪紙了

比如 n = 3
++未知
-未知
未知

也就是如果知道前兩個是++
那么第二行的第一個也就知道了

這樣的算法就可以是優(yōu)化后的算法了

本題的思路 也就差不多了
直接上代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-772588.html

//5-4 符號三角形問題
//0+  1-
#include <iostream>
using namespace std;
int n;//n行，第一行有n個元素 
int sum=0;//記錄滿足題意的數(shù)
int half;//n*(n+1)/4 
int cnt;//'-'的個數(shù)
int p[100][100]; //符號三角形矩陣 
void Output(){
	cout<<"------------\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i+1;j++){
			cout<<p[i][j]<<" ";
		}
		cout<<endl;
	}
} 
void BackTrack(int t){ //第t行 
//	cout<<"cnt="<<cnt<<" half="<<half<<endl;
	//正負(fù)號如果出現(xiàn) 一方>half
	if(cnt>half || (t*(t-1)/2-cnt)>half) return;
	if(t>n){
		Output(); 
		sum++;	
	}
	else{
		for(int i=0;i<=1;i++){
			p[1][t] = i;
			cnt += i;//'-'的個數(shù)
			for(int j=2;j<=t;j++){
				p[j][t-j+1] = p[j-1][t-j+1] ^ p[j-1][t-j+2];//^相同取0，不同取1 
				cnt+=p[j][t-j+1];
			}
			BackTrack(t+1);
			for(int j=2;j<=t;j++){
				cnt-=p[j][t-j+1];
			} 
			cnt -= i;
		}
	}
} 
int main(){
	cin>>n;
	half=n*(n+1)/2;//共有n*(n+1)/2個符號 
	
	if(half%2==1){  //奇數(shù)個符號的話，不存在'+'的個數(shù)等于'-'的個數(shù) 
		cout<<"無解\n";
	}
	else{
		half=half/2;
		BackTrack(1);
		cout<<"sum="<<sum<<endl;
	}

	return 0;
} 
/*
7
*/

到了這里，關(guān)于符號三角形-計算機(jī)算法設(shè)計與分析【1600+字解析 dfs全排列 列舉情況】【題意分析】【算法分析】【思路是怎么來的】【過程是什么】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！