Difficult computer science problem
-
the problem says that you mustn't use arrays or other allocation of memory.
SnaidiS(Semion)
then, no chance to resolve it ;P
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
-
Does anyone know an algorithm that recieves an unknown amount of numbers(it stops when it recieves -1) and calculates how many of them are above the average without using an array, list, vector, stack, file ect.? Is it even possible?
SnaidiS(Semion)
So what kind of storage are you allowed to use?
--Mike-- Visual C++ MVP :cool: LINKS~! Ericahist | PimpFish | CP SearchBar v3.0 | C++ Forum FAQ
-
So what kind of storage are you allowed to use?
--Mike-- Visual C++ MVP :cool: LINKS~! Ericahist | PimpFish | CP SearchBar v3.0 | C++ Forum FAQ
-
then, no chance to resolve it ;P
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
-
You say that there is no chanse to resolve it so can you prove it mathematiclly?
SnaidiS(Semion)
i'm tired with your thread... go find someone else to bore
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
-
Does anyone know an algorithm that recieves an unknown amount of numbers(it stops when it recieves -1) and calculates how many of them are above the average without using an array, list, vector, stack, file ect.? Is it even possible?
SnaidiS(Semion)
-
Can't you keep a running total and the number of inputs in two variables. Then you can calculate the average and of course half the number of variables is above the average. Or am I missing something?
led mike
missing something calculating the average "on the run" is easy to do with a float and an integer. but to tell how many of the inputs were upper than the average... no chance if you don't store the datas...
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
-
Does anyone know an algorithm that recieves an unknown amount of numbers(it stops when it recieves -1) and calculates how many of them are above the average without using an array, list, vector, stack, file ect.? Is it even possible?
SnaidiS(Semion)
it's not possible; as soon as you receive a new number the average will be modified, and since you cannot keep an history of the values already read, there is no way of determining what numbers that you already read that are above or below the average. (unproven, and unverified ) The problem with the average is that you can have a new value that will completly "unbalance" the computed average, for example you have a series of values in the [1, 10] range, the average will be between those 2 values, but if at some point you have a very large value, it will mess the result, and statistically the result will not be valid, unless you can filter out those bad values. ( but I expect someone to come with a brilliant mathematical answer that will awe us )
Maximilien Lincourt Your Head A Splode - Strong Bad
-
Can't you keep a running total and the number of inputs in two variables. Then you can calculate the average and of course half the number of variables is above the average. Or am I missing something?
led mike
led mike wrote:
...of course half the number of variables is above the average. Or am I missing something?
That outliers can skew things quite a bit. Given the set {1, 2, 5, 7, 10, 18}, the average is 7.1. Four numbers in the set are below this, and two numbers are above.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
-
Does anyone know an algorithm that recieves an unknown amount of numbers(it stops when it recieves -1) and calculates how many of them are above the average without using an array, list, vector, stack, file ect.? Is it even possible?
SnaidiS(Semion)
I'm guessing recursion is your friend here, assuming a magic computer that'll never stack overflow Pseudo-C-ish-code
above_average = 0;
void main()
{
doit(0,0)
print( above_average " of your numbers were above average )
}int doit( int sum, int count )
{
print( "enter number, -1 to end" );
int input
get input from keyboardint average;
if input == -1
{
average = sum/count
}
else
{
average = doit(sum+input, count+1)
if( input > average )
{
above_average++
}
}
return average
}Now remember, your lecturer is probably reading these forums.... (Technically, this is using a stack, just not the kind of stack most people would think of!)
-- Help me! I'm turning into a grapefruit! Buzzwords!
-
I'm guessing recursion is your friend here, assuming a magic computer that'll never stack overflow Pseudo-C-ish-code
above_average = 0;
void main()
{
doit(0,0)
print( above_average " of your numbers were above average )
}int doit( int sum, int count )
{
print( "enter number, -1 to end" );
int input
get input from keyboardint average;
if input == -1
{
average = sum/count
}
else
{
average = doit(sum+input, count+1)
if( input > average )
{
above_average++
}
}
return average
}Now remember, your lecturer is probably reading these forums.... (Technically, this is using a stack, just not the kind of stack most people would think of!)
-- Help me! I'm turning into a grapefruit! Buzzwords!
benjymous wrote:
(Technically, this is using a stack, just not the kind of stack most people would think of!)
Declaring variables and calling functions would violate the "no stack" requirement! Nice solution, BTW.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
-
I'm guessing recursion is your friend here, assuming a magic computer that'll never stack overflow Pseudo-C-ish-code
above_average = 0;
void main()
{
doit(0,0)
print( above_average " of your numbers were above average )
}int doit( int sum, int count )
{
print( "enter number, -1 to end" );
int input
get input from keyboardint average;
if input == -1
{
average = sum/count
}
else
{
average = doit(sum+input, count+1)
if( input > average )
{
above_average++
}
}
return average
}Now remember, your lecturer is probably reading these forums.... (Technically, this is using a stack, just not the kind of stack most people would think of!)
-- Help me! I'm turning into a grapefruit! Buzzwords!
nice
-
missing something calculating the average "on the run" is easy to do with a float and an integer. but to tell how many of the inputs were upper than the average... no chance if you don't store the datas...
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
-
You say that there is no chanse to resolve it so can you prove it mathematiclly?
SnaidiS(Semion)
Do you have any idea about it?:)
WhiteSky