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]

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).

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

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;}

:) 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

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