藍橋杯 湊算式

第七屆藍橋杯java語言題目之湊算式

第一部分：題目

湊算式

       B      DEF

A + --- + ------- = 10

       C      GHI

（如果顯示有問題，可以參見下圖）

這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。

比如：

6+8/3+952/714 就是一種解法，

5+3/1+972/486 是另一種解法。

這個算式一共有多少種解法？

注意：你送出應該是個整數，不要填寫任何多餘的内容或說明性文字。

這個題不多說了，可以直接暴力生成9的全排列然後去驗證等式是否成立，隻是驗證的時候如果防止精度問題可以通分把除法變成乘法。

直接給出全排列算法，DFS算法 ，大家随意選擇。。。。。

package LX;

public class 湊算式_全排列{
	static int count = 0;
	public static void main(String[]args){
		int[] a = {0,1,2,3,4,5,6,7,8,9};
		f(1,a);
		System.out.println(count);
		
	}
	
	public static void f(int k,int[] a){
		if(k==a.length-1&&check(a)){
			count++;
			return ;
		}
		
		for(int i=k;i<a.length;i++){
			int t = a[i];
			a[i] = a[k];//互換位置
			a[k] = t;
			
			f(k+1,a); //遞歸
			
			t = a[i];
			a[i] = a[k];//回溯
			a[k] = t;
		}
	}
	public static boolean check(int[]a){
		boolean flag = false;
		int DEF = a[4]*100+a[5]*10+a[6];
		int GHI = a[7]*100+a[8]*10+a[9];
		int result = a[1]*GHI*a[3] + a[2]*GHI + a[3]*DEF - 10*a[3]*GHI;
		if(result==0){
			flag = true;
		}
		return flag;
	}
}
           

package LX;
public class 湊算式_DFS{
	
	//标記使用位置元素
	static int[] visited = new int[10];
	//記錄搜尋路徑；
	static int[] path = new int[10];
	static int count = 0;
	public static void main(String[]args){
		DFS(1);
		System.out.println(count);
	}
	
	public static void DFS(int k){
		if(k==path.length&&check(path)){
			count++;
			return ;
		}
		
		for(int i=1;i<visited.length;i++){
			if(visited[i]==0){
				visited[i] = 1;
				path[k] = i;
				
				DFS(k+1);
				
				visited[i] = 0;
			}
		}
	}
	public static boolean check(int[]a){
		boolean flag = false;
		int DEF = a[4]*100+a[5]*10+a[6];
		int GHI = a[7]*100+a[8]*10+a[9];
		int result = a[1]*GHI*a[3] + a[2]*GHI + a[3]*DEF - 10*a[3]*GHI;
		if(result==0){
			flag = true;
		}
		return flag;
	}
}