华为OJ——24点游戏算法

题目描述

问题描述： 　　给出4个1-10的数字，通过加减乘除，得到数字为24就算胜利 输入： 4个1-10的数字。[数字允许重复，测试用例保证无异常数字] 输出： true or false 输入描述: 输入4个int整数 输出描述: 返回能否得到24点，能输出true，不能输出false 示例1 输入 7 2 1 10 输出 true

实现代码

思路： 　　①递归思想：每次和一个数的运算结果，都被当做num参数进行下一次运算放入的check函数中，所以实际上，num就是运算结果中； 　　②每次和一个数的运算都有４种可能，由temp[i]的置0置1，控制了每次递归的数不重复 　　③若只要num==24,则说明if（check()==true）,然后最终返回到第一层，return true

package cn.c_shuang.demo64;

import java.util.Scanner;
/**
 * 24点游戏算法
 * @author Cshuang
 *
 */
public class Main {
          
   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double num = 0.0;
        while(in.hasNextInt()){
            int[] initNums = new int[4];
            int[] temp = new int[4];
            for (int i = 0; i < initNums.length; i++) {
                initNums[i] = in.nextInt();
            }
            System.out.println(check(initNums,temp, num));
        }
        in.close();
    }

    public static boolean check(int[] initNums,int[] temp,double num){
        for (int i = 0; i < initNums.length; i++) {
            if (temp[i]==0) {
         
  //之所以加上temp的限制，是避免元素本身和自己做运算
                temp[i] = 1;
                if (check(initNums, temp,num + initNums[i])
                        || check(initNums,temp ,num - initNums[i])
                        || check(initNums,temp ,num * initNums[i])
                        || check(initNums, temp,num / initNums[i])) {
                    return true;
                }
                temp[i] = 0;
            }
        }
         if(num==24)
             return true;
         else
             return false;
    }

}