• Advertisement
Sign in to follow this  

java recursive problem

This topic is 4926 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

how do I generate a recursive tree and search for the minimum value? User have to enter an integer(n) within the range of 1-5000 he can substract if the integer statisfy the following: 1)If the number is even, he can substract n/2 from n 2)If n is divisible by 3 or 4,he can substract (n%10)X((n/10)%10) 3)If n is divisible by 5, he can substract 13 He can repeat 1,2,3 any amount of times. Find the smallest number he can get [Edited by - ryonckc2004 on October 25, 2004 4:16:22 AM]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Quote:
Original post by ryonckc2004
1)If the number is even, he can substract n/2 from n


You mean just divide by 2?

Quote:

2)If n is divisible by 3 or 4,he can substract n%10+(n/10)%10


Is being divisible by 4 any different than being even? I don't see how you can reconcile this with the first rule. Also, (n/10)%10 is always going to be 0 if n is an integer. So you may as well make this rule simply by n%10.

Quote:

3)If n is divisible by 5, he can substract 13


No comment here. Note that f(z) is the same regardless of how you arrived at z (hint: use dynamic programming).

Share this post


Link to post
Share on other sites
take for example if n = 112 the smallest = 3.
apply (1) 2 times u get 28
apply (2) 1 time u get 12
apply (1) 2 times u get 3

if n = 48 then smallest = 1
apply (2) 1 time u get 16
apply (1) 4 times u get 1

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Quote:

2)If n is divisible by 3 or 4,he can substract n%10+(n/10)%10


Is being divisible by 4 any different than being even? I don't see how you can reconcile this with the first rule. Also, (n/10)%10 is always going to be 0 if n is an integer. So you may as well make this rule simply by n%10.


If it is divisible by 4, then (I think), you might apply any of the two rules. If it is divisible by 20 or 30 (divisible by 2, 3 and 5 or 2, 4 and 5), then you might apply any rule you want.

Also, (n/10)%10 has no reason to be 0. Take 120 for example. 120/10 = 12, 12%10 = 2... (n*10)%10 is always 0 (with a multiplication).

n%10 + (n/10)%10 is the sum of the two last digits of the number written in base 10. So if n=142, the value is 4+2=6

Quote:

Note that f(z) is the same regardless of how you arrived at z (hint: use dynamic programming).


Yes, that's a good idea... But the 3 rules seem to make the number small very quickly. So I'm pretty sure that computing f(z) for any z from 0 to n is very time consumming.
The basic recursive idea would be

f(z) = min(f(apply_rule_1(z)), f(apply_rule_2(z)), f(apply_rule_3(z), z). (apply a rule only if possible of course).

The bad thing with that is that is may recompute several times the same f(z). So you could just store the result, and compute f(z) only if it has not already been computed.

Something like

int computed[n+1]; //init all values to -1
int f(int z)
{
if(computed[z] >= 0)
return computed[z];
int min = z;
int after_rule;
if(can_apply_rule_1(z) &&
(after_rule = f(apply_rule_1(z)))<min)
min = after_rule;
if(can_apply_rule_2(z) &&
(after_rule = f(apply_rule_2(z)))<min)
min = after_rule;
if(can_apply_rule_3(z) &&
(after_rule = f(apply_rule_3(z)))<min)
min = after_rule;
return computed[z] = min;
}

Share this post


Link to post
Share on other sites
:) interesting, a click on profile suggests your posts Mr Ryonckc2004 are made multiples of 7 days apart, and in general are toy-java problems.

would it be fair to guess that Java class is on a Tuesday

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by VincentLascaux
Quote:
Original post by Anonymous Poster
Quote:

2)If n is divisible by 3 or 4,he can substract n%10+(n/10)%10


Is being divisible by 4 any different than being even? I don't see how you can reconcile this with the first rule. Also, (n/10)%10 is always going to be 0 if n is an integer. So you may as well make this rule simply by n%10.


If it is divisible by 4, then (I think), you might apply any of the two rules. If it is divisible by 20 or 30 (divisible by 2, 3 and 5 or 2, 4 and 5), then you might apply any rule you want.

Also, (n/10)%10 has no reason to be 0. Take 120 for example. 120/10 = 12, 12%10 = 2... (n*10)%10 is always 0 (with a multiplication).

n%10 + (n/10)%10 is the sum of the two last digits of the number written in base 10. So if n=142, the value is 4+2=6

Quote:

Note that f(z) is the same regardless of how you arrived at z (hint: use dynamic programming).


Yes, that's a good idea... But the 3 rules seem to make the number small very quickly. So I'm pretty sure that computing f(z) for any z from 0 to n is very time consumming.
The basic recursive idea would be

f(z) = min(f(apply_rule_1(z)), f(apply_rule_2(z)), f(apply_rule_3(z), z). (apply a rule only if possible of course).

The bad thing with that is that is may recompute several times the same f(z). So you could just store the result, and compute f(z) only if it has not already been computed.

Something like

int computed[n+1]; //init all values to -1
int f(int z)
{
if(computed[z] >= 0)
return computed[z];
int min = z;
int after_rule;
if(can_apply_rule_1(z) &&
(after_rule = f(apply_rule_1(z)))


it does not solve the problem. the method will return a result which cannot go smaller but what I seek its a min result that is possible. to do that, you have to exhaust all possible cases. that is apply all the rules more than 1 time each and generate a recursive data tree and search for the minimum

Share this post


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

  • Advertisement