Thursday, April 16, 2009

Recursive Method to Find Total no of ways in which a positive number K can be written as sum of integers smaller than K

consider the a number 5. It can be represented as following sets {1+1+1+1+1},{1+1+1+2},{1+2+2},{1+1+3},{1+4},{2+3},{5+0} hence there are total seven.

recursive solution for finding total no of ways...

T(n) = Sigma (-1)^(m+1)*[ T(n-m*(3*m-1)/2) + T (n-m*(3*m+1)/2)]

where m = 1,2,3.........until (n-m*(3*m+1)/2) > 0;
Example:
T(5) = T(4) +T(3) - T(0)

//------------------------------------------------------------------------------------------------------------//
          int T(int n)
{
if(n < 0)
return 0;
else
{
if(n == 0)
return 1;
else
{
int temp = 1;
int tempr = 0;
int m = 0;
while(temp > 0)
{
m++;
temp = n-m*(3*m+1)/2;
tempr += pow(-1,m+1)*T(n-m*(3*m-1)/2) +
pow(-1,m+1)*T(n-m*(3*m+1)/2);
}
return tempr;
}
}
}

int main()
{
int number;
scanf("%d",number;);
printf("\nTotal ways = %d",T(number));
}

//------------------------------------------------------------------------------------------------------------//

No comments:

Post a Comment

Search Ranjeet's Blog