----- Original Message -----
From: "Dax" <[EMAIL PROTECTED]>
To: "Philippine Linux Users' Group Mailing List" <[EMAIL PROTECTED]>
Sent: Wednesday, November 28, 2001 12:04 PM
Subject: Re: [plug] Interesting small Math problem
>
> Meron bang mas eleganteng solusyon?
> a.k.a pinakakokonting operations at parenthesis? :))))
> I bet me eleganteng soltn si Sacha.
actually, generating all possible combinations of nine nines with plus,
minus, times and divide are so easy (see code below). the maximum
combination is 4 raise to 8 or 65536 combinations without the parenthesis.
injecting parenthesis on a given expression is the most complex and
challenging part here. it is depends on what parenthesis insertion rules you
will going to apply. the basic question here is that, given an expression,
how many parenthesis combination you could derived? with this simple
question, the possible combination is exponential. therefore, i will take
time to finish finding out the smallest positive integer that nine nines
cant express.
fooler.
PS. im using top-down algorithm (my favorite) instead of postfix
algorithm... you can expand that code into a full blown scientific
calculator. creating a full blown scientific calculator is so easy as long
as you know the *order of precedence*.
#include <stdio.h>
#include <string.h>
#define MAXCOMB 65536 /* 4^8 maximum combinations */
char operand[] = "+-*/";
char format[] = "9 9 9 9 9 9 9 9 9";
int errordiv;
char *expression;
int constant(void) {
expression++;
return (9);
}
int term(void) {
int results;
results = constant();
while (memchr("*/", *expression, 2)) {
switch (*expression++) {
case '*' : results = results * constant();
break;
case '/' : if ((results % 9) == 0) {
results = results / constant();
} else {
results = 0;
errordiv = 1;
}
}
}
return (results);
}
int compute(void) {
int results;
results = term();
while (memchr("+-", *expression, 2)) {
switch (*expression++) {
case '+' : results = results + term();
break;
case '-' : results = results - term();
}
}
return (results);
}
int main(void) {
int index, loop, temp;
for (index = 0; index < MAXCOMB; index++) {
temp = index;
for (loop = 8; loop; loop--) {
format[(loop << 1) - 1] = operand[temp & 3];
temp = temp >> 2;
}
expression = format;
errordiv = 0;
temp = compute();
printf("%s = %d\n", format, (errodiv ? -999999999 : temp));
}
return(0);
}
_
Philippine Linux Users Group. Web site and archives at http://plug.linux.org.ph
To leave: send "unsubscribe" in the body to [EMAIL PROTECTED]
To subscribe to the Linux Newbies' List: send "subscribe" in the body to
[EMAIL PROTECTED]
