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
>
> many thanks, charles!
It would seem like there are a finite number of ways to divide the input
string into 3 substrings. Each of the three divisions of the string would
evaluate to an arithmetic 'term'.
You can use the rules of arithmetic to prune some of the divisions
possible.
For example, if the first division is moving to the right, the first term
starts out small. When the first term becomes larger than the input
value, there is no way for an addition to decrease the sum to the first
input value, so your algorithm would fail with "".
And if the second division is moving to the right, the second term starts
out small and the third term starts out large. If the second term ever
becomes larger than the first input value, or if the second term is larger
than the first input value minus the first term, you can prune here any
further second divisions and go back to the next first division.
Similarly, if the third term ever becomes too small to make the
multiplication as large as the first input value, then further second
divisions will always fail and you can go back to look at the next first
division.
There might exist some game strategy more optimal than the others, and it
would seem to be in the choosing of when and where to make the divisions.
Arithmetic rules would help you choose a better strategy and, as the
multiplication has a larger effect on the outcome than the addition, it
might be wiser to give it the most consideration.
Tim
--
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.
|
