第七届蓝桥杯大赛个人赛省赛（软件类）3 凑算式 【全排列解法】

这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。

比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？

注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

  

看了下网上的方法，大多是用暴力枚举或者dfs回溯的，看到这个题我的第一想法就是全排列，一说全排列那自然而然就是next_permutation 函数了，在每次的排列情况下判断是否符合条件 ，问题解决。（这里也可以用乘法代替除法的思想来处理一下 ，避免麻烦）

答案是：29

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[10]={1,2,3,4,5,6,7,8,9};
	///////////A B C D E F G H I
	int count = 0;
	while(next_permutation(a,a+9)){
		//A*C*G*H*I + B*G*H*I + D*E*F*C ==10*C*G*H*I
		if(a[0]+a[1]*1.00/a[2]+(a[3]*100+a[4]*10+a[5])*1.00/(a[6]*100+a[7]*10+a[8])*1.00==10){
			cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "  <<a[3]<<" "  <<a[4]<<" "  <<a[5]<<" "  <<a[6]<<" "  <<a[7]<<" "<<a[8]<<" "  ;  
			count ++ ;
			cout<<endl;
		}
		
	}
	cout<<count;
	return 0;
} 

java 的dfs写法：

package demo;

public class Main凑算式 {
	static int a[] =new int [9];
	static boolean B []=new boolean [9];
	static int count = 0;
	static void cou(int cur){
		if(cur == 9){
			if(check()){
				count++;
			}
		}else{
			for(int i = 0;i<9;i++){
				if(B[i] == false){
					B[i] = true;
					a[cur] = i+1;
					cou(cur+1);
					B[i] = false;
				}
			}
		}
	}
	
	
	
	private static boolean check() {
		if(a[0]+a[1]*1.00/a[2]+(a[3]*100+a[4]*10+a[5])*1.00/(a[6]*100+a[7]*10+a[8])*1.00==10){
			return true;
		}
		return false;
	}



	public static void main(String[] args) {
			for(int i=0;i<9;i++){
				B[i] = false;
			}
			cou(0);
			System.out.println(count);
	}

}