【回溯与邻里交换】纸牌三角

1.回溯算法

旋转有3种可能，镜像有2种

所以最后次数：counts/3/2

#include<iostream>
using namespace std;int num[9];
int counts=0;
bool bools[9];//默认为false 
int dfs(int step){if(step==9){//索引 if((num[0]+num[1]+num[2]+num[3]==num[3]+num[4]+num[5]+num[6])&&(num[0]+num[1]+num[2]+num[3]==num[6]+num[7]+num[8]+num[0]))counts++;return 0;}for(int i=0;i<9;i++){if(!bools[i]){bools[i]=true;num[step]=i;dfs(step+1);bools[i]=false;}}
}
int main(){dfs(0);cout<<counts/6;
}

2.邻里交换

#include<iostream>
#include<algorithm>
using namespace std;int a[]={1,2,3,4,5,6,7,8,9};
int counts=0;
int f(int a[],int step){if(step==sizeof(a)-1){//step为索引 if(a[0]+a[1]+a[2]+a[3]==a[3]+a[4]+a[5]+a[6]&&a[0]+a[1]+a[2]+a[3]==a[6]+a[7]+a[8]+a[0])counts++;return 0;}for(int i=step;i<sizeof(a);i++){int x=a[i];//交换 a[i]=a[step];a[step]=x;f(a,step+1);int y=a[i];//还原 a[i]=a[step];a[step]=y;}
}
int main(){f(a,0);cout<<counts/6;
}