java recursive problem

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

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 on other sites
Quote:
 Original post by ryonckc20041)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 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 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 -1int 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 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 on other sites
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

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632996
• Total Posts
3009776
• Who's Online (See full list)

There are no registered users currently online

×

Important Information

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!