An example program for control statements and conditional statements

An example program for control statements and conditional statements

/*
* An example program for control statements and conditional statements
* problem: write a program to solve the following problem:
*    statement: Let there be an integer array A with n elements. Lets say that
*    we choose m numbers from the n numbers (a number can be chosen twice) and add them
*    to obtain the value x. So algorithmically determine the number of combinations
*    possible to bring about the sum x. Note: the values can be repeated.
**** By K Sreram
*/


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int evaluateSum(int* array, int size)
{
    int i, s = 0;
    for (i = 0; i<size; ++i)
        s += array[i];
    return s;
}

void display(int *array, int size)
{
    int i;
    for (i = 0; i < size; ++i)
        printf("\n%d", array[i]);
    printf("\n\n");
}
int evaluate(int *instant, int depth,
    const int *mainArray, const int size_mainArray,
    const int maxDepth, const int result)
{
    int i;
    static unsigned long long int count = 0;

    if (depth == 0)   count = 0; // this ensures that this function can be used for a second time

    if (depth == (maxDepth - 1)) // base case
        for (i = 0; i<size_mainArray; ++i)
        {
            instant[depth] = mainArray[i];
            if (evaluateSum(instant, depth+1) == result) // condition is checked and the combination is displayed
            {
                display(instant, depth+1);
                ++count;
            }
        }
    else if (depth < (maxDepth - 1))
    {
        ++depth;
        for (i = 0; i<size_mainArray; ++i)
        {
            instant[depth - 1] = mainArray[i]; // this creates the array that's being checked
            // the condition is checked in the base case
            evaluate(instant, depth, mainArray, size_mainArray, maxDepth, result);
        }
    }
    return count;
}
void getElements(int* array , int size)
{
    int i, r;
    for(i = 0; i<size; ++i)
    {
        scanf("%d", &r);
        array[i] = r;
    }
}

/// this program runs at O(2^(N+1)) time complexity and O(N) space complexity. The solution is inefficient for larger values
int main()
{
    int result;
    int *mainArray;
    int size_mainArray;
    int *instantArray;
    int size_instant;
    printf("enter the size of the main array:");
    scanf("%d", &size_mainArray);
    printf("\nenter the size of the summation:");
    scanf("%d", &size_instant);
    mainArray = malloc(sizeof(int)*size_mainArray);
    instantArray = malloc(sizeof(int)*size_instant);
    printf("\nenter the elements: ");
    getElements(mainArray, size_mainArray);
    printf("enter result:");
    scanf("%d", &result);
    int count = evaluate(instantArray, 0, mainArray, size_mainArray, size_instant,result);
    printf("\n number of combinations possible: %d", count);
    getch();
    return 0;
}



copyright (c) 2015 K Sreram.
 
About my blog