java 蓝桥杯凑算式（两种方法暴力和dfs）

布满荆棘的人生 2022-04-13 09:44 170阅读 0赞

![20160524002023711][]

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

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

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

解题：

这个题还是没什么好说的，但是有一个小小的容易出错的点，就是int 和double类型的定义，代码中已经注解

最终结果是29

方法一：

import java.util.*;
     
    public class Main
    {
    	public static void main(String args[])
    	{
    		double a,b,c,count=0;//需要将a,b,c三数定义成double 类型
    		
    		for(int A=1;A<=9;A++)
    		{
    			
    			a=A;
    			for(int B=1;B<=9;B++)
    			{
    				for(int C=1;C<=9;C++)
    				{
    					b=B*1.00/C;    //这是关键的容易出错的一步，因为如果b是int类型，会出现5/4=1而不是1.25会导致后面出错
    					for(int D=1;D<=9;D++)
    					{
    						for(int E=1;E<=9;E++)
    						{
    							for(int F=1;F<=9;F++)
    							{
    								for(int G=1;G<=9;G++)
    								{
    									for(int H=1;H<=9;H++)
    									{
    										for(int I=1;I<=9;I++)
    										{
    											c=(D*100+E*10+F)*1.00/(G*100+H*10+I);
    											int []kk=new int[10];  //用来检验是否9个数有重复
    											kk[A]++;kk[B]++;kk[C]++;kk[D]++;kk[E]++;
    											kk[F]++;kk[G]++;kk[H]++;kk[I]++;
    											int i;
    											for(i=1;i<=9;i++)
    											{
    												if(kk[i]!=1)break;//如果有一个数重复则无效
    												if(i==9&&a+b+c==10)count++;//只有当所有数都为1，且满足和为是10才计数
    											}
    											
    											
    											
    										}
    									}
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    		System.out.println(count);
    	}
    }

方法二：

import java.util.*;
     public class Main
     {
    	    static int[] g;
        static boolean[] usered;
        static int sum =0;
        public static void main(String[] args) {
            usered=new boolean[10];
            g=new int[10];
            Backtrack(1);
            System.out.println(sum);
        }
        static void Backtrack(int index){
             if(index==10){
                   sum+=isCheck(g)?1:0;
                   return;
             }
            for (int i = 1; i <=9 ; i++) {
                 if(!usered[i]){
                     usered[i]=true;
                     g[index]=i;
                     Backtrack(index+1);
                     usered[i]=false;
                 }
            }
        }
    
        private static boolean isCheck(int[] g) {
            double m1= g[1];
            double m2= g[2]*1.0/g[3]*1.0;
            double  m3= (g[4]*100+g[5]*10+g[6])*1.0/(g[7]*100+g[8]*10+g[9])*1.0;
            return m1+m2+m3==10.00?true:false;
        }
     }

[20160524002023711]: /images/20220413/42737091847b445f86a002267ed2c333.png