Hints: see http://www.research.att.com/~njas/sequences/A000041, which
relates the solution of your problem to the Partition Problem. Then
see http://en.wikipedia.org/wiki/Partition_function_%28number_theory%29,
which gives a recursion for calculating the Partition Function. Put
the two together and you've got it.
If you need more help, please be sure to state whether or not this is
for homework in some class you are taking.
Dave
On Nov 27, 6:08 pm, Rupesh Bhochhibhoya <[EMAIL PROTECTED]> wrote:
> I have come up with the solution but still this is not the for the
> general case. I would like to make my problem clear once again.
>
> The problem is to find total number of solutions for the following
> expression.
>
> if k=1, the expression is like this: 1*x1=1, so number of solution is
> 1, i.e. x1=1.
>
> if k=2, the expression is like this: 1*x1 + 2*x2=2, so number of
> solution is 2: (x1=2,x2=0) and (x1=0,x2=1)
>
> so the general expression is like this: 1*x1 + 2*x2 + 3*x3
> +4*x4+........+k*xk = k, where xn adn k are non-negative integers. we
> need to find how many possible solution are there for this expression.
> I can code for the specific value of k but i couldn't figure out for
> general case: please help if you can find me for general case. here is
> my logic.
>
> if you are given k=3
>
> then
>
> for(x1=0;x1<=k;x1++)
> {
> sum=x1;
> s1=sum;
> for(x2=0;x2<=k;x2++)
> {
> sum=sum+2*x2;
> s2=sum;
> for(x3=0;x3<=k;x3++)
> {
> sum=sum+3*x3;
> if(sum==k)
> count=count+1;
> sum=s2;}
> sum=s1;
> }
> }
>
> print(count);
>
> here you can see that loop increases as k increases i.e. number of
> loops=k and we check for the condition at most inner loop. that means
> check every possible combination. can any one help me for general
> case?
>
> thanks
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
