Jump to content
  • Advertisement
Sign in to follow this  
someboddy

Difficult computer science problem

This topic is 4367 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
The term you are looking for is "constant space".

This problem is provably unsolvable in constant space. Assume for a moment that we have inserted all integers between 1 and (N-1) into the program. The last integer we insert can result in any number of integers between N/2 and (N-1) being lower than the average (we can insert, to this effect, any number between 0 and N²). Therefore, the program must store enough information to determine which of the N/2 possibilities is valid, which cannot be done for any N if we restrict ourselves to constant space.

Share this post


Link to post
Share on other sites
I'm assuming you can hold variables. Can't you have a variable that's initialised to zero. Then if the inputted number is greater than the average then increase the variable. If it's -1 then quit. Or have I missed an obvious problem?

Share this post


Link to post
Share on other sites
This sounds suspiciously like homework. All I'll say is that it can be solved within the constraints listed using a technique that teachers/professors love to set homework problems about.

EDIT: This does depend on the interpretation of the list of constraints.

Σnigma

Share this post


Link to post
Share on other sites
The obvious problem is that you need to know all the numbers to get the average.

It can be done if you iterated the sequence twice, once to find the average and again to count how many are higher. Without storing them, you'd have the input the whole sequence twice.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
The obvious problem is that you need to know all the numbers to get the average.

It can be done if you iterated the sequence twice, once to find the average and again to count how many are higher. Without storing them, you'd have the input the whole sequence twice.


Ah, I misread it. I thought it was a given average as opposed to the average of the numbers inputted.

Share this post


Link to post
Share on other sites
Well..I'm curious. Maybe the OP can let us know when teh homework gets turned in so someone can tell me what this is all about :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
This sounds suspiciously like homework. All I'll say is that it can be solved within the constraints listed using a technique that teachers/professors love to set homework problems about.

EDIT: This does depend on the interpretation of the list of constraints.

Σnigma


what is "interpretation of the list of constraints"?

Share this post


Link to post
Share on other sites
Quote:
Original post by Semion_N
what is "interpretation of the list of constraints"?


It is the interpretation of the ect (sic) in the OP's question. Does his question mean to rule out any memory storage (constant space solving, which is provably impossible)? Does his question mean to rule out only the standard imperative storage approaches (hinting at an easily expressed recursive solution)?

I've interpreted it as the first option, since a recursive solution technically uses a stack (unless it uses tail recursion, but then the problem becomes provably unsolvable again). If it's homework, then the recursive solution would be a good answer, though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!