3

Given 6 integers and 1 target value, write a function to get the target value using 6 integers with any on these operations +,*,-,/

This is what I did

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);

    }
}

I know this is wrong because I'm just using 1 operation at a time, what can I do to do multiple operations at once. For example, if it were a complex array like {45, 4, 84, 63, 91, 20, 400} and my target value was 455 which is (91*20)/4, then how can my program do that? How can it try all possible operations?

4

1 回答 1

1

It looks to me like you're trying to write a solver for the Countdown numbers game.

It's not a trivial task, and you do generally end up with a 'brute-force' search running through many combinations. I've written solvers for it before, but I'd struggle to write one in 20 minutes.

Here's some pseudocode that I hope illustrates the process. I am assuming all of your numbers are positive:

// 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);
                    }
                }
            }
        }
    }
}

By b op a is valid, I mean that the calculation is not a subtraction resulting in zero or a division with a nonzero remainder. As the numbers are sorted in ascending order and b comes after a in the list, b will be greater than or equal to a. By making this restriction, we avoid duplicating effort thanks to the commutativity of + and * and ending up with negative numbers with -.

We can also check for and filter out 'useless' operations such as multiplying or dividing by 1, subtractions such as 8 - 4 (which 'wastes' the 8) or divisions such as 25 / 5 (which 'wastes' the 25).

Once you've found a target, you may want to keep going to see if you can hit the target using fewer steps. It's possible that the first time a target is found there are redundant steps; by searching for the shortest you guarantee to remove these.

于 2013-03-30T20:07:44.400 回答