【藍橋杯】算式填符号

匪警請撥110,即使手機欠費也可撥通！

為了保障社會秩序，保護人民群衆生命财産安全，警察叔叔需要與罪犯鬥智鬥勇，因而需要經常性地進行體力訓練和智力訓練！

某批警察叔叔正在進行智力訓練：

1 2 3 4 5 6 7 8 9 = 110

請看上邊的算式，為了使等式成立，需要在數字間填入加号或者減号（可以不填，但不能填入其它符号）。之間沒有填入符号的數字組合成一個數，例如：12+34+56+7-8+9 就是一種合格的填法；123+4+5+67-89 是另一個可能的答案。

請你利用計算機的優勢，幫助警察叔叔快速找到所有答案。

每個答案占一行。形如：

12+34+56+7-8+9

123+4+5+67-89

……

分析：

1.根據題意在每個數字後面都會加上一個符号，要麼是' '，要麼是'+'，要麼是'-',那麼總共需要添加的字元就有8

個，建立一個大小為8的數組用來存儲這些符号。

2.通過遞歸來組合出不同的符号，完成一次遞歸後，就處理字元串，将符号添加進123...9這個數字字元串中。

3.将符号添加進數字字元串中後，進行處理，判斷式子的結果是否是110，是則輸出該等式，再進行下一次遞歸。

/*
 * 0代表"",1代表+，2代表-
 */
public class Main {
	public static int[] sign = new int[9];
	public static String s = "123456789";
	public static void isOk(String s)    //判斷式子是否等于110
	{
		String temp = s;
		String[] num = temp.replace('+', ',').replace('-', ',').split(","); //将式子按照符号分離，得到的就是組合之後的數字
		int sum=Integer.parseInt(num[0]);
		int falg=1;
		for(int i=0;i<s.length();i++)
		{
			if(s.charAt(i)=='+')
			{
				sum+=Integer.parseInt(num[falg]);
				falg++;
			}
			if(s.charAt(i)=='-')
			{
				sum-=Integer.parseInt(num[falg]);
				falg++;
			}
		}
		if(sum==110)
		{
			System.out.println(s);
		}
		
	}
	public static void f(int step)
	{
		if(step == 9)
		{
	
			String s1 = s.charAt(0)+"";
	        StringBuffer str = new StringBuffer();
	        str.append(s1);
	        for(int i=1;i<=8;i++)
	        {
	        	if(sign[i]==0)
	        	{
	        		str.append(s.charAt(i));
	        	}
	        	if(sign[i]==1)
	        	{
	        		str.append("+"+s.charAt(i));
	        	}
	        	if(sign[i]==2)
	        	{
	        		str.append("-"+s.charAt(i));
	        	}
	        }
	        isOk(str+"");
		}else {
			/*sign[step]=0;
			f(step+1);
			sign[step]=1;
			f(step+1);
			sign[step]=2;
			f(step+1);*/
			for(int i=0;i<=2;i++)  //遞歸，分别嘗試填 0,1,2
			{
				sign[step] = i;
				f(step+1);
			}
		}
		
	}
public static void main(String[] args) {
	f(1);
}
}