Tom's Guide | Tom's Hardware | Tom's Games
 |
 |
 |
Im using Dev-C++ and trying to write a program that will return the right combination of 1,3,4,6 (each used once and only once) and operators (+,-,*,/,()) that will evaluate to whatever number you specify, eg 24. Can anyone help?
Hi Jeannie,
You need much more detail about what is to be done.
I have no idea what "the right combination of 1,3,4,6 " is. Right according to what rule?
Just those 4 numbers? Or any which you throw at it?
If you haven't though this through much, better start with a pencil and paper and write pseudo code.
If at first you don't succeed, you're about average.M2
0 
Ok, you can only use the numbers 1,3,4,6. For example, the answer if you want to get 24 is 6/(1-(3/4)). I want to make a program that will try out every combination until it hits one that evaluates to the number that I want. Is that any clearer?
0
Hi Jeannie,
Yes, that's clearer.
We're back to pseudo code.
[declare alowwed nums 1 3 4 6]
[declare result, probably int]
[get result value: from where? user input? file? command line? random?]Until you pseudo code it, you'll be hard pressed to write code that does anything.
If at first you don't succeed, you're about average.M2
0
Something along these lines:
#include <stdio.h>
int main(){
int i=1,o=3,p=4,q=6,t=0;
printf("Value you want returned is\n");
scanf("%d",&t);
?What would come next?
0
We're back to pseudo code.
What method or algorithm can you think of which will try all the possible computations using the four nums and the desired operators?
If at first you don't succeed, you're about average.M2
0
I think Jeannie has been watching Countdown, a quiz programme on British TV.
Contestants are given a number, usually three or for digits and have to devise a mathematical solution to arrive at the given number using any of the ten digits.
I never managed to master it, but the contestants and one a of hosts, Carol Vorderman seemed to be able to do it with ease.
Restricting the available digits to only four makes it even harder. The only way that I can see of doing it is by trial an error.
One possible approach is that is the required number is even then only use even digits in your solution. If there required numbers is odd then only use odd digits bearing in mind that dividing by an odd number will leave a fraction which is probably not what you want.
A better way of arriving at 24 using the supplied digits is 4*6 = 24.
Carol Vorderman brains as well as beauty.
Stuart
0
Hi Stuart,
My instinct tells me that using only the four math operators and parentheses would yield tens of thousands of non-trivial possible formulas.
If at first you don't succeed, you're about average.M2
0
Hi M2
There probably are thousands of possible solutions, especially if the number extends into 3 or 4 digits. In the aforementioned quiz, the contestant that arrived at the solution with the least number of steps was the winner. So 4*6 would beat 6/(1-(3/4))hands down.
One other approach is to first find out if the given number is a prime number. Once you have that sorted it should make it easier to work out the rest.
A search on Google will give you loads of information on prime numbers. Unfortunately, prime numbers are stretching my mathematical abilities to the limit.
Stuart
0
Hi Stuart,
Unfortunately, although I do enjoy countdown, this problem does not come from the program. I need a program that will find the solution using all of the four numbers?
0
Mechanix2Go,
I assume that a for loop or a while loop is necessary but I'm just drawing a blank on how to properly implement them in this case. Its quite complex and my programming skills just aren't up to it.
0
Hey all,
I've been following this thread and find it fascinating. Jeannie, can you give us any clue as to what exactly the purpose of this might be? It's not that it's necessary, but it might help to give a better idea in order to avoid generating trivial possibilities.
I get that you must use all four numbers, but can you use them only once, or more? Second, are +,-,*,and / to be the only operators, or could exponents be introduced? Third, is the number you're looking for ever fractional (decimal)? Fourth, is there _any_ limitations on use of parenthesis?
Depending on the answer to these questions, and mainly the first, I think there is a way to do what you want. If the first question is every number, once and only once, I really think you'd be in business. Rather than looking for a particular combination to match a given number, I think it would be better to calculate all possible sets and find out what numbers they yield.
Let us know what you can when you can. And even if we can't help, good luck because it sounds interesting.
Stephen
"Live long and PROGRAM......or at least do _something_ with all that time...!"
0
Sorry,
I read things a little more and see that you say "once and only once" in your first post. OK, my bad. Second, you're only looking at the four basic operators, which is good (plus parenthesis). Third, if the way I'm thinking of doing it is the only way, I don't believe this thread is named appropriately: it would _not_ be a simple program. Though, not a dreadfully difficult one either. We'll see, but I doubt simplicity will yield a solution to something like this.
Stephen
"Live long and PROGRAM......or at least do _something_ with all that time...!"
0
Hi Stephen,
"I don't believe this thread is named appropriately: it would _not_ be a simple program"
I'm glad you said that; so I didn't need to.
You'll need to build in some 'rules of grammar':
these are not allowed:
++
--
+-
etcnor would you allow 'unmatched' parenthesis.
Once you code the 'syntax checker' the looping through possibilities looks straightforward.
If at first you don't succeed, you're about average.M2
0
why not declare the four variables plus one for the input from user & then ... & I know it seems odd but it's jus an idea.....
switch(input)
{
case a+b+c+d ;
puts(a+b+c+d;
break;
case a-b-c-d:
puts(a-b-c-d)
case a*b*c*d:
}
and so on listing all possible ways to decipher the users inputoutside the box baby it's crowded inside
0
sm,
That'll work. But the chore is figuring out what all the possibilities ARE; nevermind the tedium of typing them in.
Seems preferable to have the code do it for you.
If at first you don't succeed, you're about average.M2
0
I think it would be easier
if jean just posted the entire problem with all parameters and exclusionsthe psuedo code should be possible to figure out
but not if we are guessing at the rules
0
Yep
All we know so far is that this is not as simple a program as originally hoped.
If at first you don't succeed, you're about average.M2
0
Hmm,
It seems I have excited some interest with this problem. It was given as an optional assignment in one of my c-programming tutorials in college. The deadline has since passed but its still annoying me that I can't do it. Im sorry that the thread was named incorrectly but I only realised how difficult it was when I went to implement it! It seems that an elegant, short program is impossible but I'm still trying to come up with something that doesn't require listing all the possibilities. If I could get the code to do it for me....
Jeannie
0
Hi Jeannie,
That desire to figure something out is what separates the programmers [and the real techs] from the rest of the pack.
If at first you don't succeed, you're about average.M2
0
It certainly isn't a simple problem! Possibly the easiest approach to solving it (or at least determining what is involved) is to use prefix notation for arithmetic and construct all the valid arithmetic expressions as (full) binary trees. For each of the 4! permutations of {1,3,4,6} there are 4^3 choices of 3 arithmetic ops from {+,-,*,/} and for each of those 4^3*4! choices, there are 5 possible expressions (5 is the 3rd Catalan number - see the explanation of Catalan number or Catalan's problem at mathworld or somewhere similar).
For example, choosing (1,3,4,6,/,+,+) we get the 5 expressions:
A = (/ (+ 1 3) (+ 4 6))
B = (/ (+ (+ 1 3) 4) 6)
C = (/ 1 (+ 3 (+ 4 6)))
D = (/ (+ 1 (+ 3 4)) 6)
E = (/ 1 (+ (+ 3 4) 6))Draw them out as trees so that "/" is the root node at the top and the four numbers are in order along the bottom and you'll see that A is the balanced tree etc. You'll also notice from the expressions themselves (and their values) that considerations of commutativity etc. mean that there is a lot that could be done to reduce the number of expressions needing to be constructed. You'll also notice that the above expressions are valid Lisp expressions and I'll leave you to ponder the significance and implications of that ;-) Fortunately for this problem, you only need to consider those 5 trees and fill them in with the ordered sets of numbers and operators. The real work in writing more than just a working program would be in filtering the expressions to exclude e.g. a 3 + 1 node when you've already done a 1 + 3 node in the same position in a tree. You'll at least want to filter out the divisions by zero or trap them or something.
0
Interesting problem. You wan't to match an integer by computing "well-formed", generated expressions. So you wan't to write a program that generates wffs?
0  |
 |
 |
This post is quite old and has been locked from receiving new replies. Please create a new posting instead.
| Ads by Google |
