文章目录

一、问题描述二、解题思路三、相关算法1.交换法2.抽取法3.使用c++中提供的函数进行全排列

---

一、问题描述

相关的三角形堆如下所示： 0 2 1 4 3 6 9 5 7 8 条件为下层的孩子的值大于上层的父亲的值，求出所有满足条件的三角形堆的数量。

二、解题思路

解题思路：解空间为10个不重复的数字，每一种不同的顺序代表一种不同的堆放方式，用全排列可以获得所有的堆放方式。在进行全排列中需要判断每个排列方式是否满足条件。

三、相关算法

1.交换法

代码如下（示例）：

#include <bits/stdc++.h> using namespace std; int number=0; int child[2][6]={{1,3,4,6,7,8},{2,4,5,7,8,9}};//记录前6个元素的左、右孩子的下标。第一行表示为前6个元素的左孩子，第二行表示为前6个元素的右孩子。 bool check(int a[],int n){ for(int i=0;i<6;i++){ //只有前6个元素才有左右孩子 if(a[child[0][i]]<a[i]||a[child[1][i]]<a[i]){ //当第i+1个元素大于其左孩子或者大于其右孩子时不满足条件。 return false; } } return true; } void f(int p,int a[],int n){ if(p==n){ if(check(a,n)){ //当全排列完成后选择满足条件的全排列 number++; cout<<" "<<a[0]<<endl; cout<<" "<<a[1]<<" "<<a[2]<<endl; cout<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<endl; cout<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9]<<endl; } return; } for(int i=p;i<n;i++){ swap(a[i],a[p]); f(p+1,a,n); swap(a[i],a[p]); } } int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9}; int p=0; int n=10; f(p,a,n); cout<<number<<endl; return 0; }

2.抽取法

代码如下（示例）：

#include <bits/stdc++.h> using namespace std; int cnt = 0; //记录全排列含有多少种方式 int vis[15] = {0}; //记录每个元素是否被访问过 int child[2][6]={{1,3,4,6,7,8},{2,4,5,7,8,9}};//记录前6个元素的左、右孩子的下标。第一行表示为前6个元素的左孩子，第二行表示为前6个元素的右孩子。 bool check(int b[],int n){ for(int i=0;i<6;i++){ //只有前6个元素才有左右孩子 if(b[child[0][i]]<b[i]||b[child[1][i]]<b[i]){ //当第i+1个元素大于其左孩子或者大于其右孩子时不满足条件。 return false; } } return true; } void f(int a[],int n,int b[],int p){ if(p==n){ if(check(b,n)){ //当全排列完成后选择满足条件的全排列 cnt++; cout<<" "<<b[0]<<endl; cout<<" "<<b[1]<<" "<<b[2]<<endl; cout<<" "<<b[3]<<" "<<b[4]<<" "<<b[5]<<endl; cout<<b[6]<<" "<<b[7]<<" "<<b[8]<<" "<<b[9]<<endl; } return; } for(int i=0;i<n;i++){ if(!vis[i]){ //若未被访问过，则将元素追加到新的数组 vis[i] = 1; //将vis[i]置为1，表示其被访问过 b[p] = a[i]; f(a,n,b,p+1); vis[i] = 0; //返回到初始状态，保证后面的抽取是正确的 } } } int main(){ int a[15] = {0,1,2,3,4,5,6,7,8,9}; int b[15]={0}; int n=10; f(a,n,b,0); cout<<cnt<<endl; //求解出满足条件的搭积木的种类数量 return 0; }

3.使用c++中提供的函数进行全排列

代码如下（示例）：

#include <bits/stdc++.h> using namespace std; int child[2][6]={{1,3,4,6,7,8},{2,4,5,7,8,9}};//记录前6个元素的左、右孩子的下标。第一行表示为前6个元素的左孩子，第二行表示为前6个元素的右孩子。 bool check(int a[],int n){ for(int i=0;i<6;i++){ //只有前6个元素才有左右孩子 if(a[child[0][i]]<a[i]||a[child[1][i]]<a[i]){ //当第i+1个元素大于其左孩子或者大于其右孩子时不满足条件。 return false; } } return true; } int main(){ int a[15]={0,1,2,3,4,5,6,7,8,9}; int number=0; do{ if(check(a,10)){ //当全排列完成后选择满足条件的全排列 number++; cout<<" "<<a[0]<<endl; cout<<" "<<a[1]<<" "<<a[2]<<endl; cout<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<endl; cout<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9]<<endl; } }while(next_permutation(a,a+10)); //对数组a进行全排列 cout<<number<<endl; return 0; }