dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: Interesting Problem

  1. #1
    Join Date
    Dec 2015
    Posts
    4

    Interesting Problem

    Given an array of n numbers,develop a deterministic algorith that will say if it is possible or not to insert between each two numbers one of the operators "+", "-", "*"(multiplication), "/"(division),such as the result of the expression would be equal to 0.
    Example:
    1)7 3 2 2 -> 7-3-2*2 => Success
    2)7 3 5 11 -> no possible combination => FAIL

    Do you know an algorith for this problem or have an idea how to solve it?

  2. #2
    Join Date
    Mar 2001
    Posts
    2,527

    Re: Interesting Problem

    The algorithm for a basic math problem? Must be school.
    ahoodin
    To keep the plot moving, that's why.

  3. #3
    Join Date
    Dec 2015
    Posts
    4

    Re: Interesting Problem

    The brute solution will be very expensive since time complexity if i check all the possibilities will be 4^n,and that too much i think. I am interested in finding something more efficient.

  4. #4
    Join Date
    Jun 2015
    Posts
    208

    Re: Interesting Problem

    Quote Originally Posted by Vlad_Dohotaru View Post
    Do you know an algorith for this problem or have an idea how to solve it?
    You can always check every possible combination.

    In the example there are 4 numbers in between which there are 3 places to put any of 4 operators. So the total number of combinations to will be 3^4 = 81. It can easily be done with 3 fixed nested loops or recursively to a depth of 3.

  5. #5
    Join Date
    Dec 2015
    Posts
    4

    Re: Interesting Problem

    What if the input will be 100 numbers? Isn't there a more efficient solution? checking every possible combinationt obviously does not work for a greater amount of numbers as input.

  6. #6
    Join Date
    Jun 2015
    Posts
    208

    Re: Interesting Problem

    Quote Originally Posted by Vlad_Dohotaru View Post
    What if the input will be 100 numbers? Isn't there a more efficient solution? checking every possible combinationt obviously does not work for a greater amount of numbers as input.
    There may not exist a more efficient solution. Some problems simply have no solution (in polynominal time). That's why public-key cryptography works. Also see NP-completeness.

    I suspect your problem may be one of those very hard intractable problems (with the disclaimer that I've been wrong before ). To know for sure the approach is to show that ones problem is equivalent to one of the known standard hard problems. If that's the case any hope of finding an efficient solution is gone and only small inputs can be solved within a reasonable time.

    By the way, your problem is underspecified. You haven't defined what kind of division / is. If it's the integer division you find in most programming languages your second example could evaluate to 0 like this,

    7 / 3 / 5 / 11 = 0
    Last edited by tiliavirga; December 12th, 2015 at 01:52 AM.

  7. #7
    Join Date
    Dec 2015
    Posts
    4

    Re: Interesting Problem

    Thank you, tiliavirga for your answer. It is mathematical division,like 7 / 3 = 2.(3)

  8. #8
    Join Date
    Jun 2015
    Posts
    208

    Re: Interesting Problem

    Quote Originally Posted by Vlad_Dohotaru View Post
    It is mathematical division,like 7 / 3 = 2.(3)
    There is no such thing as "mathematical" division in some divine God-given sense. In every specific case algebraic operations must be defined. With your definition of division you have effectively graduated your problem from the natural numbers to the real numbers. Then, since a digital computer is finite, you also need to be more specific about what you mean by 0 (or rather 0.0).

    Anyway, just like nature has put a cap on the speed of light it has put a cap on computing (quite fascinating I think). Some problems simply are intractable. It's important to be aware of this to avoid wasting time on futile solution attempts. Unfortunately to actually prove intractability isn't the easiest of things. The most common approach is to show that a problem is equivalent to another problem that's already been proved intractable. But this is PhD stuff so one usually has to rely on intuition.
    Last edited by tiliavirga; December 14th, 2015 at 03:13 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)