• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help me solve this with Divide and Conquer  RSS feed

 
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello guys, can you please give me an idea on how to solve this.. i believe i need Divide and Conquer method, maybe im wong..

I have to solve this:
x2+s(x)+200·x=N

N is given by the user, also A and B, which is the range of X.
but the range can be up to 1,000,000,000

Any ideas please?
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
can you explain what that means? I assume your "x2" means x * x, but I have no idea what s(x) would mean.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ohh im sorry.
yes, that means x*x.. and s(x) means the sum of the numbers in a number... thats easy, i already wrote that..
for example s(115) would be 1+1+5..
 
Ranch Hand
Posts: 10128
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Still your question is not clear enough. What is that A and B you are referring to in your first post? Do you mean that x can be anywhere between A and B which could be 0 and 1,000,000,000?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
well..divide and conquer generally means "pick some of the possibilities. Determine if the solution is in that set, or not. discard the the set you don't need. repeat."

A common example is guessing a number between 1 and 100. I will tell you higher or lower. How would you solve that?

What you need to do is figure out how YOU would solve it using your brain, pencil and paper. Once you can do that, and ONLY once you can do that, do you start writing code.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joe Harry wrote:Still your question is not clear enough. What is that A and B you are referring to in your first post? Do you mean that x can be anywhere between A and B which could be 0 and 1,000,000,000?


Yes, thats correct .. X will be numbers from A to B..


fred rosenberger wrote:well..divide and conquer generally means "pick some of the possibilities. Determine if the solution is in that set, or not. discard the the set you don't need. repeat."

A common example is guessing a number between 1 and 100. I will tell you higher or lower. How would you solve that?

What you need to do is figure out how YOU would solve it using your brain, pencil and paper. Once you can do that, and ONLY once you can do that, do you start writing code.


Thats what im asking help for... i know how divide and.conquer works, i just need some help how to properly implement it..
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
so again...How would YOU solve it with pencil, paper, and your brain?

Programming is not about writing code. it is about thinking through problems. Literally writing stuff down on paper. "first I would do this. Then I would do this".

then, you take those steps, and revise, them. explain in more detail how you do that step. Eventually, you get to the point where you could give those directions to a 10 year old child, and reasonably expect them to be able to perform the actions.

Only when you have that done should you consider writing a single line of code.

so, give us those steps you've written down.
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:so again...How would YOU solve it with pencil, paper, and your brain?

Programming is not about writing code. it is about thinking through problems. Literally writing stuff down on paper. "first I would do this. Then I would do this".

then, you take those steps, and revise, them. explain in more detail how you do that step. Eventually, you get to the point where you could give those directions to a 10 year old child, and reasonably expect them to be able to perform the actions.

Only when you have that done should you consider writing a single line of code.

so, give us those steps you've written down.


Dude, I honestly understand completely what you are saying, the thing is that I'm not asking for a code or a complete solution.. I'm asking help for the idea on how to solve it, writing it is easy, I know that...
The thing is that I have no idea...

Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??
 
Ranch Hand
Posts: 221
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have to go with Fred and Joe on this. I admit that I'm not the brightest crayon in the box, but based on the information you have provided, I still don't know what you are trying to solve for.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:I'm asking help for the idea on how to solve it
and that is exactly what I am doing.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??

Maybe I mis-spoke. Don't diving your range into two halves.

instead, choose a number somewhere in the range. for example, say N is 1456, A = 0, B = 10.

What would you do?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:
Kaspersky Ukshini wrote:Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??

Maybe I mis-spoke. Don't diving your range into two halves.

instead, choose a number somewhere in the range. for example, say N is 1456, A = 0, B = 10.

What would you do?



Got it!
I choose ONE number, if that number doesn't give me the exact result N, then I check if the result for that choosen number is BIGGER or SMALLER than the result I need (N)... if it's bigger, I set a new B, which would be my choosen nubmer in this case...and repeat it... is that correct?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:Got it!
I choose ONE number, if that number doesn't give me the exact result N, then I check if the result for that choosen number is BIGGER or SMALLER than the result I need (N)... if it's bigger, I set a new B, which would be my choosen nubmer in this case...and repeat it... is that correct?


CORRECT!!! GOOD JOB!!!

Doesn't it feel so much better to figure it out yourself than to be told the answer?

Now...the next question becomes...how do you choose your one number?
also...if you choose a number and you KNOW it is too big, do you really need to set B to that number, or is there a slightly better choice?

Also note: This sort of method ONLY works if your results are ordered. I haven't completely convinced myself that given any number x, that x+1 is always larger, but I'm about 99% sure.
 
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And, of course, if there is at least one point for which the equation holds.

So, my first advice is: set s(x) equal to 0 for the moment, and test if the
equation, with given A, B and N, has a solution.

for x between 0 and 1.000.000.000, you would have that s(x) <= 81,
so the initial solution should be close.

Question: what to do with s(x) if x is not an integer? For instance: x = 2 / 3?

Greetz,
Piet
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All the time, I was thinking that all the formula is EQUAL to X, so that was freaking me out lol.... I noticed it was =N (which Is a fixed value once the user inputs it lol)

anyways, I need some help with this part:



does my N, in this case hold

-2,147,483,648 to 2,147,483,647

Just to make sure...
 
Piet Souris
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, you would have x^2 + s(x)+ 200x = x or

x^2 + s(x) + 199x = 0

which is nearly the given formula, with N = 0.

And whether your inputted N willl be between these values?
Depends on what you type in. Try typing 'javaranch' for instance ;)

Greetz,
Piet
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Doneeeeeeeeee!!!

I did it, thank you guyss !!!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!