i got this recursion
b(0,0)=1Code:int b(int n,int count) { int i; count =a(n,count); for(i=0;i<n;i++) count =b(i,count); return count;
b(1,0)=3
b(1,1)=4
b(2,0)=8
the formula for function "a" is a(n,c)=2^n + c
what is the formal way to find a formula for b
so i could predict whats the output of each input like b(12,15)??
i dont have any intuition
i am looking for the formal way
Last edited by transgalactic2; 10-09-2008 at 02:52 PM.
Most any book with "discrete mathematics" in the title will contain information on solving recurrence relations (which is what this is). I don't feel like typing two chapters into this little box, so go read.
Something like:
b(n, count) = foldr (b, a(n,count), [0..n])
[0..n] is the list of elements from 0 to n. In math terms this is a sequence.
foldr is accumulate function:
Prototype would look something like:
in foldr(int (*func)(int,int), int initial, List list)
It applies func to each element of the list, taking the previous result as the first argument except for the first tiome, when initial is used.
It can be defined recursively as:
if the list is empty, the result is the initial value z
if not, apply f to the first element and the result of folding the rest
That's a math formula for you. You can try to simplify it by moving the recursion out of foldr and into b, so that b recurses twice. Then apply other simplification methods on recursive functions.
The general process is:
1) Convert loops into common higher order recursive functions, like foldr.
2) Convert the compleat function to not use higher order functions.
3) Apply techniques for simplifying recursive functions.
But I'm a computer programmer, and this is a programming forum. A mathematician will probably give you better advice.
EDIT: forgot about a().
Last edited by King Mir; 10-09-2008 at 07:00 PM.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Did you mean to say
... otherwise it assigns count a lot redundantly. I can't replicate your results nohow.Code:count += b(i,count);
Here it is simplified to first order:
But that's as far as I know how to take this. As tabstop sais, consult a discrete math textbook.Code:b(c, n) = foldr (b, a(n,c), [0..n]) b(c, n) = b( a(n,c),f([0..n]) ) f(emptyList) = emptyList f(list) = b( list[0], f( tail(list) ) ) Tail is function that returns the rest of the list, excluding list[0].
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
It's not redundant, because count appears again in the right side of the equation.Originally Posted by nonoob
Effectively it's the same as:
Where op is the function b, except with argument reversed.Code:int i=0 for(;i<n;++i) count op= i;
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
this is a part of the solution but
i cant completely understand how to get there
and how to come to a formula from that expression
b(n,count) = b(n,0)+count
b(n):=b(n,0)
b(n) = 2^n + b(0) + b(1) + b(2) + ... + b(n-1)
and using this outputs
b(0,0)=1
b(1,0)=3
b(1,1)=4
b(2,0)=8
in the end we need to come to the formula
b(n,c)=c+(n+2)*2^(n-1)
You'll need to figure out what b(0) is, to start the recurrence off. You'll also want to write b(n) in terms of b(n-1). Given your first three lines are true (I haven't tried to verify them against your code):
b(n-1) = 2^(n-1) + b(0) + ... + b(n-2)
b(n) = 2^n + b(0) + ... + b(n-2) + b(n-1)
you can write b(n) = b(n-1) + b(n-1) + 2^(n-1), with the first b(n-1) being the literal b(n-1) at the end of the expression, the second b(n-1) being everything else in the expression (since it matches the first line above it, except for the constant), and the last bit being the difference between the constants.
And then your discrete math textbook should have the proof that a recurrence of the form b(n) = 2b(n-1) + 2^(n-1) has the form of c2^n + dn2^n for some c and d.
i got the idea that i need to build a formula for
a(n) using a(n-1) terms
the time in the test only allows me to find this 4 cases
b(0,0)=1
b(1,0)=3
b(1,1)=4
b(2,0)=8
i cant see any pattern by looking only at these 4
if i will study the discrete math course
could i find your formula using these 4 cases?
Yes. (I believe you would need three to solve the 3x3 system for the missing coefficients.)
I swear this looks familiar. I believe this question was asked last week.
i got these points for this function "b" :
b(0,0)=1
b(1,0)=3
b(1,1)=4
b(2,0)=8
b(0)=1
b(1)=2+1=3
b(2)=4+1+3=8
b(n)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)+b(n-1)
b(n-1)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)
b(n)=b(n-1)+b(n-1) =2*b(n-1)
which by the way is wrong because b(1) doesn't equal to 2* b(0)
b(n)=2*b(n-1)
how to transform it to the formula
b(n,c)=c+(n-2)*2^(n-1)
???
That's because you can't get from
tob(n)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)+b(n-1)
(Or at least they're not consistent.) What you should have, matching what you posted way up top, is "b(n-1) = 2^(n-1) + b(0) + b(1) + ... + b(n-2)". Which is also why b(n) = 2*b(n-1) is wrong, and not what I posted above.b(n-1)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)
