Cutting A Candy Bar Imagine a candy bar that has k places where it can be cut. Y

Question

Cutting A Candy Bar

Imagine a candy bar that has k places where it can be cut. You would like to know how many how many different cuts are possible to divide the bar into pieces. For example, if k is 3, you could cut the bar at location 1, then location 2, then finally at location 3. We indicate this sequence by '123'. So, if k is 3, we have six ways to divide the bar: 123, 132, 213, 231. Recursively, this can be expressed as:

C(k)=kC(k1)

Let's make this a bit more interesting by adding a restriction. You must always cut the leftmost pieces that can be cut. Now if k is 3, we can cut the bar at locations 123, 132, 213, 312, or 321. A cutting sequence of 231 is not allowed, because after the cut at 2 we would have to make the cut at location 1, since it is the leftmost piece. We still have k possibilities for making the first cut, but now we have to count the number of ways to cut two pieces and multiply. Recursively, this can be expressed as:

D(k)=i=1kD(i1)D(ki)

For example, when k is 3 we would compute

D(3)=i=13D(i1)D(3i)=D(0)D(2)+D(1)D(1)+D(2)D(0)
D(2)=i=12D(i1)D(2i)=D(0)D(1)+D(1)D(0)
D(1)=i=11D(i1)D(1i)=D(0)D(0)

In both cases, when k=0 there is exactly one way to divide the bar.

Specification

Write a java class CandyBar that will read a value k from the keyboard and then display C(k) and D(k).

Hints

In addition to a main method, you should have two recursive methods (one each for C(k) and D(k)).

Summations can easily be transformed into for loops.

Example Dialog:

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf(" ");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k ");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d ",count);
}

===============================================================================

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.