给定6个整数和1个目标值，用*、-、/这些操作中的任意一个，编写一个函数来使用6个整数获得目标值

Question

给定6个整数和1个目标值，用+，*，-，/这些操作中的任意一个写一个函数来获取目标值

这就是我所做的

public class Solution {
    public static void main(String[] args) {
int target =5;
int a[]={1,3,2,10,15,8};
int i,j;
for(j=0;j<6;j++)
for(i=0;i<6;i++)
    if(a[i]/a[j]==target)       System.out.println(a[i]+"/"+a[j]+"="+target);
for(j=0;j<6;j++)
for(i=0;i<6;i++)
    if(a[i]+a[j]==target)       System.out.println(a[i]+"+"+a[j]+"="+target);   

for(j=0;j<6;j++)
for(i=0;i<6;i++)
    if(a[i]*a[j]==target)       System.out.println(a[i]+"*"+a[j]+"="+target);
for(j=0;j<6;j++)
for(i=0;i<6;i++)
    if(a[i]-a[j]==target)       System.out.println(a[i]+"-"+a[j]+"="+target);
    }
}

我知道这是错误的，因为我一次只使用一个操作，我能做些什么来一次执行多个操作呢?例如，如果它是一个复杂的数组，如{45,4,84,63,91,20,400}，我的目标值是455，即(91*20)/4，那么我的程序如何做到这一点?它如何尝试所有可能的操作?

Answer 1

在我看来你是在为倒计时数字游戏写一个解算器。

这不是一项微不足道的任务，你通常会在许多组合中进行"蛮力"搜索。我以前写过求解程序，但我很难在20分钟内写出一个。

下面是一些伪代码，我希望它们能说明这个过程。我假设你所有的数字都是正数:

// Assume numbers is sorted in ascending order
// progress_so_far lists the steps we have taken to get the solution.
void search(numbers, progress_so_far, target) {    
    for each a in numbers {
        for each b in numbers after a {
            for each op in + - * / {
                if (b op a is valid) {
                    result = b op a;
                    if (result == target) {
                       // Success !
                       // Print out how we got there.
                    }
                    else if (numbers.size() > 2) {
                        new_numbers = copy of numbers with a and b removed and result added, sorted in ascending order;
                        new_progress = copy of progress_so_far with 'b op a' added;
                        search(new_numbers, new_progress, target);
                    }
                }
            }
        }
    }
}

通过b op a is valid，我的意思是计算不是导致零的减法，也不是余数为非零的除法。由于数字按升序排列，b在a之后，因此b将大于或等于a。通过这个限制，我们避免了由于+和*的可交换性而导致的重复工作，并且-的结果是负数。

我们还可以检查并过滤掉"无用"的操作，如乘或除1，减法，如8 - 4(浪费8)或除法，如25/5(浪费25)。

一旦你找到了一个目标，你可能想继续前进，看看你是否可以用更少的步骤达到目标。第一次找到目标时可能会有冗余的步骤;