Icebeing wrote:
> Hi all,
>
> Some time ago, I got hit with this problem on a game-programming
> test, and it's bugged me ever since:
>
> The program has 2 inputs:
>
> 1 32-bit integer, called result
> 1 input string of digits
>
> The algorithm calls to construct an arithmetic expression string from
> the input string so that it evaluates to the result value, by
> inserting '+' and '*'
>
> example:
>
> input 1 = 44550
> input 2 = "8888225"
>
> algorithm spits out: "8888+22*5"
>
> the algorithm spits out "" if no arithmetic expression can "fit" input
> 2 with input 1
>
> best approach i could come up with is a brute-force method...any math-
> heads know a better approach to this?
> my number theory is rusty lol
Brute force isn't necessarily that bad; at least, it isn't for reasonable
lengths of the input string of digits and assuming you are using a
computer
to execute the algorithm (this is comp.lang.c.moderated so I think that's
a safe assumption, although the question is pretty much completely
off-topic for the group.)
If R is the desired result, D is the string of digits and l(D) is the
number of digits in that string, then even when l(D) is 21, there's
only 3 billion or so combinations to consider. A few seconds work.
The number of combinations to consider is at most 3**(l(D)-1) since
between each digit there are only 3 possibilities: nothing, a + or *.
For some R and D you can reduce the number to consider by discarding
any combination where there are at least l(R) nothings in sequence,
since they will produce a number greater than R. (Unles, of course,
there are zeros in D which appear at the front of that subsequence.)
In the example you gave, any combination involving a 6 digit number
(and hence one + or *) cannot produce the desired 5 digit result.
In that example, even 5 consecutive digits (4 consecutive nothings
between digits) will produce a number that is too large.
How much that reduces the problem space, if at all, is dependent on
the size of R and D. What seems mildly interesting to consider
is whether and at what point large values of l(D) make the problem
computationally difficult by the brute force approach.
That said, I imagine other posters by now have probably proposed
much more elegant solutions.
--
comp.lang.c.moderated - moderation address: clcm@[EMAIL PROTECTED]
-- you must
have an appropriate newsgroups line in your header for your mail to be
seen,
or the newsgroup name in square brackets in the subject line. Sorry.
|
