Fibonacci Number Generation with Golden Ratio Code

The formula and explanation are all available in here in wikipedia. It won’t produce correct result for any number greater than 70.

Code Fibonacci Generation with Golden ratio:
/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Fibonacci number generation using golden ratio.
 * Technique:
 */

#include<bits/stdc++.h>
using namespace std;


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    long double phi  = 1.61803398874989484820458683436563811772030917980576286213544862270526046281890;
    long double phiN = 0.61803398874989484820458683436563811772030917980576286213544862270526046281890;


    // Change value of n to desired value.
    // Should give correct Fibonacci value for 1 to 70.
    int n = 70;

    long double F = ( pow(phi, n) - pow( phiN, n ) ) / sqrt(5);

    cout.setf(ios::fixed);
    cout << setprecision(0) << round(F) << "\n";



    return 0;
}
Advertisements

Simple Polynomial data structure and Calculator for single variable

Explanation:

The first code takes an integer for the value of the variable and the next one takes a double for the value of variable and produces value of the function.

I have commented the second code to make it easy. Pun intended on lines 144 to 147.

Calculates an equation with given value of the variable. If the equation is,

f(x) = -50x^{-3} +3x -40x^2 +10x^{-5} -7x^{10}

then for,

x = -3, \ f(x) = -413710.189300 \\  x = -2, \ f(x) = -7328.062500 \\  x = -1, \ f(x) = -10.000000 \\  x = 0, \ \ \ f(x) = \ \ \ Undefined \\  x = 1, \ \ \ f(x) = -84.000000 \\  x = 2, \ \ \ f(x) = -7327.937500 \\  x = 3, \ \ \ f(x) = -413695.810700 \\

(Pease Test this code before using, I haven’t done much testing). Check against this site. To use this from console comment freopen lines. Otherwise make two txt files named input and output in the same directory as the cpp file and follow the given equation input format.

Input:
-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10
0
y
-3
y
-2
y
-1
y
0
y
1
y
2
y
3
n
Output:
-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10 
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413710.189300
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7328.062500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -10.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
Sorry Try something different
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -84.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7327.937500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413695.810700
Calculate value of Equation for given value (y/n)?
Exiting...

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator for single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();

    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;

    temp->next = NULL;
    current->next = temp;
    current = temp;

    return current;
}


void printEquation(node* dummy){
    node* tmp = dummy->next;
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");
}


void calculateEquation(node* dummy, int var){

    double sum = 0;
    bool calculable;


    node* tmp = dummy->next;
    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;


        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        sum = sum + variableValue * constantValue;
        tmp = tmp->next;


        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;



    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    printEquation(dummy);


    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable.\n");

            int variableValue;
            scanf("%d", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}

 

Working with float numbers:

If the equation is,

f(x) = - 4x^{2} - 4x - 9

Input:
+4x^+2 -4x^+1 -9x^+0
0
y
5
y
2.5
y
1.25
y
1.875
n
Output:
+4x^+2 -4x^+1 -9x^+0 
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 71.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 6.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -7.750000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -2.437500
Calculate value of Equation for given value (y/n)?
Exiting...

Code for float:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator with single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();


    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;


    temp->next = NULL;
    current->next = temp;
    current = temp;


    return current;
}


void printEquation(node* dummy){

    // dummy is just an empty node to keep track of front of equation.
    // It is not part of equation. Equation starts after dummy node.
    node* tmp = dummy->next;

    // Print the equation term by term.
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");

}


void calculateEquation(node* dummy, double var){

    double sum = 0;
    bool calculable;


    // dummy->next because dummy node is not a part of the equation.
    node* tmp = dummy->next;

    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;

        // make constant negative if the sign is negative.
        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        // calculate the value of the variable with given exponent.
        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        // multiply the calculated value of variable with the constant.
        sum = sum + variableValue * constantValue;

        // calculate the next term of the equation.
        tmp = tmp->next;


        // If not calculable. Ex: divide by zero. then print this.
        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    // print the result.
    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;


    // Dummy node to make insertion code simpler.
    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    // Take input of equation term by term.
    // If
    //     taking input from console stop input using null terminator ( ctrl + z ).
    // Else
    //     when taking input from file enter a 0 in a line by itself to stop input.
    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    // print the
    printEquation(dummy);


    // Enter different values for the variable to get the value of function.
    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable:\n");

            double variableValue;
            scanf("%lf", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}

Grade School High Precision Floating Point Number Adder Implementation in C++

Warning: This program has not been thoroughly tested. So it may produce incorrect results.

How the Code Works:

Note this problem calculates the integer and fractional portion separately in array as opposed to techniques learned in numerical analysis. To test if outputs are correct check against other high precision calculator such as this calculator.

Similar to this problem or same techniques used in uva problem 424 integer inquiry solution, uva problem 10035 primary arithmetic solution, uva problem 713 adding reversed numbers solution. The technique from this problem can also be applied to the mentioned problems.


Solution Steps:
Example Input:
25.401
534.2914
710.84
9.7808
980.7223

Note here are two separate arrays with one for decimal part and other for fraction. The dot is not stored anywhere, it is just shown to make it easy to understand. First the numbers are aligned with padding functions to create this,

025 . 4010
534 . 2914
710 . 8400
009 . 7808
980 . 7223

Although not used in this problem below, this pic that shows how I calculated sum column-row (column major) wise which is not cache friendly.

uva 424 integer inquiry order of operation
uva 424 integer inquiry order of operation

As shown in the pic above the technique is almost same but this time row and columns are interchanged and kept in a separate array which looks like this,

New Decimal Array:
05709 
23108 
54090 
New Fraction Array:
42877
09482
11002
04083

Next the operation is carried out as shown below,

row wise addition of high precision floating point numbers
row wise addition of high precision floating point numbers

Sample Test Input:

3.6692156156
65652.6459156456415616561
33.54615616
1.1
9854949494968498.49684984444444444444444443213615312613216512331918565

Output:

Output: 9854949495034189.45813726568600610054444443213615312613216512331918565

Code:

/********************************************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Naive High Precision Floating Point Number Adder
 *
 * Warning:   This Code is mostly useless and hard to read. It is not represented in
 *            usual sign, exponent sign, exponent magnitude, mantissa magnitude format.
 *            The Program should produce correct output till given FRACTION_LIMIT after
 *            decimal point for unsigned numbers (Negative numbers not supported).
 *
 *            Also it may not necessary produce correct result as it is not throughly
 *            tested. Use it with caution.
 *
 *            Please follow input format. I have not handled any exception for incorrect
 *            input formats.
 *
 *******************************************************************************************/



#include<stdio.h>
#include<string.h>



// Increase the TEST_NUMBERS to calculate more float numbers.
#define TEST_NUMBERS  5

#define DECIMAL_SIZE  100
#define FRACTION_SIZE 100




// Function Prototypes
void sumDecimal(char **, int, int);
void sumFractions(char **, int);


// Array for holding decimal and fractional portion
static char decimal[TEST_NUMBERS][DECIMAL_SIZE];
static char fraction[TEST_NUMBERS][FRACTION_SIZE];


// Pointers reversed decimal and fractional result array.
char *resDec, *resFrac;
int resDecLen, resFracLen;



// Align decimal portion of the numbers and zeros.
void fixPaddingDecimal(int carry){

    // Holds calculated length of all strings.
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest decimal.
    int maxlength = memo[0] = strlen(decimal[0]);


    // Get the max length for padding or aligning.
    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(decimal[i]);
        if( len > maxlength )
            maxlength = len;
    }



    // Shift elements by appropriate positions or, create padding.
    // Look at my other linked pages from the post to understand this part.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            int padding = maxlength - len;

            for(int j = len - 1; j >= 0; --j)
                decimal[i][padding + j] = decimal[i][j];

            for(int j = 0; j < padding; ++j)
                decimal[i][j] = '0';
        }
    }



    // Create a new 2D array that will hold values in the new changed order.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Copy decimal portion to the mew changed order array.
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = decimal[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */


    // After fixing alignment add the decimal portion.
    sumDecimal( cacheFrindlyFloatOrganization, maxlength, carry);

}



// Add all the decimal numbers.
void sumDecimal(char **cacheFrindlyFloatOrganization, int maxlength, int carry){

    // Holds the output decimal part in reversed order.
    char *resultDecimal = new char[maxlength + 1];

    int z = 0;


    // Again look at the pages linked from this post.
    // I have explained this in uva 424, 10035, 713 etc.
    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultDecimal[z++] = sum % 10 + '0';
        carry = sum / 10;
    }

    // Stored in reversed order
    if(carry)
        resultDecimal[z++] = carry + '0';
    resultDecimal[z] = '\0';


    // Store the address and length of resultDecimal
    resDec = resultDecimal;
    resDecLen = z;


}



// As explained above this ALMOST does the same thing as function decimal code.
void fixPaddingFraction(){

    // Holds calculated length of all strings
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest fraction
    int maxlength = memo[0] = strlen(fraction[0]);

    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(fraction[i]);
        if( len > maxlength )
            maxlength = len;
    }


    // Add zeros to empty positions.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            for(int j = len ; j < maxlength; ++j)
                fraction[i][j] = '0';
            fraction[i][maxlength] = '\0';
        }
    }


    // Explained above.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Interchanging row and columns
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = fraction[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */

    // Sum the fractional array part.
    sumFractions(cacheFrindlyFloatOrganization, maxlength);
}




// Does ALMOST the same thing for decimal function code.
void sumFractions(char **cacheFrindlyFloatOrganization, int maxlength){

    char *resultFraction = new char[maxlength + 1];

    int z = 0, carry = 0;

    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultFraction[z++] = sum % 10 + '0';
        carry = sum / 10;
    }


    // Stored in reversed order
    resultFraction[z] = '\0';


    // Hold the address and length resultFraction array.
    resFrac = resultFraction;
    resFracLen = z;


    // Call the padding function for by sending the carry from fraction part.
    fixPaddingDecimal(carry);
}



// The output decimal and fraction array are in reversed order.
// They need to be reversed before outputting.
void reverseString(char *tmpString, int tmpStringLen){

    for(int i = 0, j = tmpStringLen - 1; i < j; ++i, --j ){
        int temp = tmpString[i];
        tmpString[i] = tmpString[j];
        tmpString[j] = temp;
    }
}



int main(){


    // Comment freopen lines below to input and output from console.
    // In order to use freopen create a file named input_file.txt
    // in same directory as your cpp file. The output of the program
    // will be in output_file.txt file.

    /*
    freopen("input_file.txt", "r", stdin);
    freopen("output_file.txt", "w", stdout);
    */



    for(int i = 0; i < TEST_NUMBERS; ++i){
        //printf("Enter float:\n");
        scanf("%[0-9].%[0-9]", &decimal[i], &fraction[i]);
        getchar();
    }


    // This is where it all starts.
    fixPaddingFraction();



    reverseString(resDec, resDecLen);
    reverseString(resFrac, resFracLen);


    // Debug
    printf("Output: %s.%s\n", resDec, resFrac );



    return 0;
}

UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Warning this is a terrible dynamic programming and memoization solution. If you want a fast and efficient solution then, this isn’t what you are looking for.

Problem Statement:

Given an input integer that represent a rational number sequence term shown by cantor, output the rational number for that term.


Solution Types:

I have given two solution, one of which uses a 2D array to store the rational number sequence as shown by cantor and using a traversal pattern memoize the series in another array. Although the first one can be improved to only traverse 1/4 th of the array but that’s still a lot.

The next solution discards the 2D array and using the traversal pattern with some optimization memoizes the series.

The time difference as of UVA submission running time is,

0.245 ms (1st technique)
0.072 ms (2nd technique)

Removing the recursion by replacing with iterative version ( A bit harder to do ) will make it even faster. I think this one can be further improved but have no idea how.

Figuring out the algorithm:


Note everything here is assuming indexing starts from 1 instead of 0. But in my code I start with index 0 instead of 1.

 

Sequence Traversal within Matrix:
cantor sequence matrix
cantor sequence matrix

Unraveling the Sequence:
cantor sequence chain
cantor sequence chain

Traversal Pattern and Sub structure/pattern:
cantor structure and substructure pattern
cantor structure and substructure pattern

Substructure and Movement within Matrix:
cantor movement within matrix
cantor movement within matrix

Points To Notice:

1. Moves right when row number is 0 and column number is even.
2. Moves down-left when row number is 0 and column number is odd.
3. Moves down when column number is 0 and column number is odd.
4. Moves up-right when column number is 0 and column number is even.
5. Diagonal traversal gets bigger by 1 unit for each down or right movements.


Traversing the Matrix:

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c - 1 times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r - 1 times)} & \forall : col = 0; row \in Even \\    \end{cases}

OR, In my code,

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c + diagonal times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r + diagonal times)} & \forall : col = 0; row \in Even \\    \end{cases}

Note: Increment the index and diagonal also.


Filling the Matrix (1st code only):

CantorTable_{i,j} =     \begin{cases}      numerator = row, & \forall : Column, rows \\     denominator = column, & \forall : Column, rows \\    \end{cases}


Base case:

Note when row or the column is equal to 0 then there is a turn. If row or column becomes less than 0 then it should stop.

Also the amount values to memoize is N which is the maximum cantor sequence value for this problem. So if N values are memoized then the process should stop.

if (r < 0 || c < 0 || index > M)
    return;

Storing the fractions in 2D Struct Array:

Instead of storing the values in string it is better to store the fraction in a struct. There are 3 things in the fraction the numerator, a division sign , the denominator. There is no need to store the division sign since all elements within matrix are fraction.

struct CantorSequence{
    int numerator;
    int denominator;
};

About Space:

The first solution requires a total of O( M + \frac{N(N+1)}{2} ) space including storing the cantor sequence in another array and pre calculating the 2D cantor table and traversing.

The second solution requires a total of O( M ) space including storing the cantor sequence in another array.

Here, M is 10000000 and N is 4500. N can be adjusted but 4500 is a safe value.


Please point out if the post contains mistakes.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

3
14
7
10000000 

 


Output:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629

Code Recursive DP 2D struct Traversal and Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            2D struct array,
 *            2D half diagonal fill,
 *            Recursive Dynamic Programming
 ***********************************************************************/


#include<stdio.h>
#include<string.h>

// N * N should be almost twice greater than or equal to M.
// Or, N should be such that N*(N+1)/2 is greater than M.
#define N 4500


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
} CT[N][N];


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];


/**
 * Fill in the cantor table.
 */
void CantorFill(){

    for(int row = 0; row < N; ++row){

        int cutoff = N - row;

        for(int col = 0; col < cutoff; ++col){
            CT[row][col].numerator   = row + 1;
            CT[row][col].denominator = col + 1;
        }

    }

}


void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    OrderedCantor[index].numerator = CT[r][c].numerator;
    OrderedCantor[index].denominator = CT[r][c].denominator;



    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {


    // Initialize Cantor table
    CantorFill();


    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}


Code Recursive DP Sequence Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            Recursive Dynamic Programming
 ***********************************************************************/


#include<stdio.h>
#include<string.h>


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
};


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];




void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    // change from table traversed DP
    OrderedCantor[index].numerator = r + 1;
    OrderedCantor[index].denominator = c + 1;


    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    else if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {

    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}

C++ Code for finding Parametric Equation and Vector form for Line L through two points p1 and p2

Description:

Given two points P_1 (x_1, y_1, z_1) and P_2 (x_2, y_2, z_2) we are to find the parametric equation and vector form of line through these points.

The parallel vector to the line is,

\overrightarrow{P_1 P_2} = < x_2 - x_1, y_2 - y_1, z_2 - z_1 >

So the parallel vector of P_1 (2, 4, -1) and P_2 (5, 0, 7) is,

\overrightarrow{P_1 P_2} = < 5 - 2, 0 - 4, 7 - (-1) > = < 3, -4, 8 >

Note that \vec{v} is the parallel vector. We know,

\vec{r} = \vec{r_0} + t \vec{v}

where,
\vec{r} = < x, y, z >
\vec{r_0} = < x_0, y_0, z_0 >
\vec{v} = < a, b, c >

So the vector equation form is,

\vec{r} = \vec{r_0} + t \vec{v}
< x, y, z > = < x_0, y_0, z_0 > + t < a, b, c >

Also the parametric form is,

x = x_0 + at
y = y_0 + bt
z = z_0 + ct

Now we can use either vector from origin to P_1 or origin to P_2 . Here the vector from origin to  origin to P_1 which is (0, 0, 0) to (2, 4, -1) is,

\vec{r_0} = < 2 - 0, 4 - 0, -1 - 0 > = < 2, 4, -1 >

So the vector equation of line through P_1 and P_2 is,

< x, y, z > = < 2, 4, -1 > + t < 3, -4, 8 >

calculating further,
< x, y, z > = < 2, 4, -1 > + < 3t, -4t, 8t >
< x, y, z > = < 2 + 3t, 4 - 4t, -1 + 8t >

Finally,

L: x = 2 + 3t, y = 4 - 4t, z = -1 + 8t

Similarly the equation of the line can found out using origin to P_2 .


Input:

input for parametric equation
input for parametric equation

 

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Find parametric equations for the line through p1 and p2.
 *          Also for the segment joining these points.
 */

#include<stdio.h>

struct myVector{
    int x, y, z;
} v1, v2;

void input2dPoints(){
    printf("Enter p1:");
    scanf("%d %d", &v1.x, &v1.y);
    printf("Enter p2:");
    scanf("%d %d", &v2.x, &v2.y);
}

void input3dPoints(){
    printf("Enter p1:");
    scanf("%d %d %d", &v1.x, &v1.y, &v1.z);
    printf("Enter p2:");
    scanf("%d %d %d", &v2.x, &v2.y, &v2.z);
}

struct myVector calculateParallelVector(int choice){
    if(choice == 1)
        return {v2.x - v1.x, v2.y - v1.y};
    else{
        return {v2.x - v1.x, v2.y - v1.y, v2.z - v1.z};
    }
};

void printParametricAndVectorForm(int point, struct myVector mv, struct myVector parallelVector){
        printf("Taking point p%d(%d, %d) on the line L we get parametric equation:\n", point, mv.x, mv.y);
        printf("L: x = %d + %dt, y = %d + %dt\n",  mv.x, parallelVector.x, mv.y, parallelVector.y);
        printf("\n");
        printf("Vector form:\n");
        printf("<x, y> = <%d, %d> + t <%d, %d>\n",  mv.x, mv.y, parallelVector.x, parallelVector.y);
        printf("\n\n");
}

//@Override
void printParametricAndVectorForm(int point, struct myVector mv, struct myVector parallelVector, int dimension){
        printf("Taking point p%d(%d, %d, %d) on the line L we get parametric equation:\n", point, mv.x, mv.y, mv.z);
        printf("L: x = %d + %dt, y = %d + %dt, z = %d + %dt\n",  mv.x, parallelVector.x, mv.y, parallelVector.y, mv.z, parallelVector.z);
        printf("\n");
        printf("Vector form:\n");
        printf("<x, y, z> = <%d, %d, %d> + t <%d, %d, %d>\n",  mv.x, mv.y, mv.z, parallelVector.x, parallelVector.y, parallelVector.z);
        printf("\n\n");
}

int main(){
    int choice;
    struct myVector parallelVector;

    printf("1. Two Dimensional.\n");
    printf("2. Three Dimensional.\n");
    printf("\nChoice: ");
    scanf("%d", &choice);
    printf("\n");

    switch(choice){
    case 1:
        input2dPoints();

        printf("\n");
        parallelVector = calculateParallelVector(choice);
        printf("Parallel vector -> p1p2 to the line L is: <%d, %d>\n", parallelVector.x, parallelVector.y);
        printf("\n\n");

        printParametricAndVectorForm(1, v1, parallelVector);
        printParametricAndVectorForm(2, v2, parallelVector);

        break;

    case 2:
        input3dPoints();

        printf("\n");
        parallelVector = calculateParallelVector(choice);
        printf("Parallel vector -> p1p2 to the line L is: <%d, %d, %d>\n", parallelVector.x, parallelVector.y, parallelVector.z);
        printf("\n\n");

        printParametricAndVectorForm(1, v1, parallelVector, 3);
        printParametricAndVectorForm(2, v2, parallelVector, 3);

        break;

    default:
        printf("Wrong input.\n");
    }

    return 0;
}

Simple Program to Calculate Distance in 3 Dimensional Plane

In 2-space if two points are p1(x1, y1) and p2(x2, y2) then the distance between them is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2}

Similarly in 3-space distance between two points p1(x1, y1, z1) and p2(x2, y2, z2) is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}

 

Example:

Distance between point (1, 1, 2) and point (3, -2, 4) is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}
d = \sqrt[]{(3 - 1)^2 + (-2 - 1)^2 + (4 - 2)^2}
d = \sqrt[]{4 + 9 + 4}
d = 4.12


Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<cmath>
#include<algorithm>

struct point{
    float x, y, z;
};

// descending comparison x
bool point_sorter_x_desc(point const &p0, point const &p1){
    return p0.x > p1.x;
}

// ascending comparison x
bool point_sorter_x_asc(point const &p0, point const &p1){
    return p0.x < p1.x;
}

// descending comparison y
bool point_sorter_y(point const &p0, point const &p1){
    return p0.y > p1.y;
}

// descending comparison y
bool point_sorter_z(point const &p0, point const &p1){
    return p0.z > p1.z;
}

// descending comparison priority x then y then z
bool point_sorter_greatest(point const &p0, point const &p1){
    if(p0.x > p1.x)
        return p0.x > p1.x;
    if(p0.y > p1.y)
        return p0.y > p1.y;
    return p0.z > p1.z;
}

int main(){

    int N;
    printf("Enter number of points:\n");
    scanf("%d", &N);

    /*
     * Comment this section to hard code points
     * Uncomment to take user input
     */

    //struct point *p = new point[N];

    //for(int i = 0; i < N; ++i)
      //  scanf("%f %f %f", &p[i].x, &p[i].y, &p[i].z);

    /*
     * Comment this section to input points
     * Uncomment the struct memory allocation and scan above
     */
    struct point p[6] = {
        {1,1,2},
        {3,-2,4},
        {10,10,12},
        {6,2,7},
        {5,6,9},
        {8,1,1}
    };

    // Sort based on the point in x axis
    std::sort(p, p + N, &point_sorter_x_asc);

    // show the sorted points
    printf("\nSorted Points:\n\n");
    for(int i = 0; i < N; ++i)
        printf("P%d: (%.2f , %.2f, %.2f)\n", i, p[i].x, p[i].y, p[i].z);
    printf("\n\n");

    // Finding distance in 3-Dimensional Plane
    float total_distance = 0;
    for(int i = 1; i < N; ++i){
        float distance = sqrt( pow( p[i].x - p[i - 1].x, 2 ) + pow( p[i].y - p[i - 1].y, 2 ) + pow( p[i].z - p[i - 1].z, 2 ) );
        printf("\nDistance between points (%.2f,%.2f,%.2f) and (%.2f,%.2f,%.2f) is: %.2f\n", p[i - 1].x, p[i - 1].y, p[i - 1].z, p[i].x, p[i].y, p[i].z, distance);
        total_distance += distance;
    }

    printf("\n\n");
    printf("Total Distance: %.2f\n", total_distance);

	return 0;
}

Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Ternary Heap Sort
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for(i=0; i<SIZE; ++i){
        A[i] = rand() % SIZE;
        printf("%d ", A[i]);
    }
    printf("\n");

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i)
        printf("%d ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

In this problem a few key points are,
  1. The amount doesn’t exceed $300.00
  2. Exit / terminate program for the input of 0.00
  3. Amount can be / is a floating point number
  4. There are different values that can be used make up the decimal and the fractional portion
  5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, $1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

For example,
  • $4.70      =      470 cents
  • $2.00      =      200 cents
  • $6.75      =      675 cents
  • $300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Compile with C++ to be safe from compile errors although some codes do work with C compiler.


Input:

0.20
2.00
4.90
6.70
8.45
0.00

 


Output:

  0.20                4
  2.00              293
  4.90             5698
  6.70            19187
  8.45            49007

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars
 */

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main(){
    unsigned i, j;
    float n;

    c[0] = 1;
    for(i = 0; i < 11; ++i){
        for(j = coins[i]; j < N; ++j)
            c[j] += c[j - coins[i]];
    }

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

Code (Loop Split):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars ( Loop Split )
 */

#include<stdio.h>

#define N 30002

static long long c[N];

int main(){
    unsigned i, j;
    float n;

    c[0] = 1;

    /*
     * Loop Split
     */

    for(j = 5; j < N; ++j)
        c[j] += c[j - 5];

    for(j = 10; j < N; ++j)
        c[j] += c[j - 10];

    for(j = 20; j < N; ++j)
        c[j] += c[j - 20];

    for(j = 50; j < N; ++j)
        c[j] += c[j - 50];

    for(j = 100; j < N; ++j)
        c[j] += c[j - 100];

    for(j = 200; j < N; ++j)
        c[j] += c[j - 200];

    for(j = 500; j < N; ++j)
        c[j] += c[j - 500];

    for(j = 1000; j < N; ++j)
        c[j] += c[j - 1000];

    for(j = 2000; j < N; ++j)
        c[j] += c[j - 2000];

    for(j = 5000; j < N; ++j)
        c[j] += c[j - 5000];

    for(j = 10000; j < N; ++j)
        c[j] += c[j - 10000];

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

Inputting directed, undirected, weighted and unweighted graph in C, C++ Adjacency Matrix

The codes below uses 2D array adjacency matrix. For both sparse and dense graph the space requirement is always O(v2) in adjacency matrix. The codes below can be used take input and store graphs for graph algorithm related problems.

Related to this have a look at,

DIRECTED, UNDIRECTED, WEIGHTED, UNWEIGHTED GRAPH REPRESENTATION IN ADJACENCY LIST, MATRIX REFERENCE SHEET


Input for Directed Weighted Graph:

directed weighted input
directed weighted input

Code Directed Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        Graph[u][v] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Directed Unweighted Graph:

directed unweighted input
directed unweighted input

Code Directed Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // For directed graph edges (u,v) != (v,u)
        Graph[u][v] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Undirected Weighted Graph:

undirected weighted input
undirected weighted input

Code Undirected Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        // For undirected edge (u,v) = (v,u)
        Graph[u][v] = Graph[v][u] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

 

Input for Undirected Unweighted Graph:

undirected unweighted input
undirected unweighted input

Code Undirected Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // Here value of 1 represents there is an edge (u,v)
        Graph[u][v] = Graph[v][u] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

0-1 Knapsack Iterative and Recursive with Code

0-1 Knapsack:

This problem can be solved be dynamic programming. Given some weight of items and their benefits / values / amount, we are to maximize the amount / benefit for given weight limit.

Background:

Suppose we are thief trying to steal. We got a knapsack with a weight carry limit. We go to a house there are a few items. The items have weights and also resale value. Now with our limited weight in the knapsack and many valuable items to take, we need to maximize our gain. We can do so by trying all items and filling the weight limit.

We will be given a few things as input. Such as number of items, each of their weights, each of their monetary value / cost ( if it represents cost ) and a weight limit. We are to find that by trying all items and the weight limit what is the maximum possible benefit.

If it is unclear the Wikipedia article on 0-1 knapsack may be helpful. I will show the table fill and items taken in the knapsack in another post.


Recurrence Relation:

The recurrence relation for this problem follows,

cost[ i, w ] = cost[ i – 1, w ] if, Wi > w
cost[ i, w ] = max( cost[ i – 1, w ], cost[ i – 1, w – W] ) if, Wi <= w


Question:
items | weight | benefit
========================
1     | 6      | 10
2     | 1      | 5
3     | 2      | 7
4     | 5      | 12
5     | 4      | 8
6     | 3      | 6

For weight of 10 what is the maximum possible benefit by trying all item?


Answer:

For this problem max benefit is 26.

The answer is always found in cost[ item_count, total_weight ]
Our item_count was 6 and total_weight was 10.
Here the answer is in cost[ 6, 10 ] which is 26.

Table Fill:
knapsack table fill output
knapsack table fill output

Code:


Iterative:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack iterative
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

void dynamicKnapsack(){
    int i = 0;

    /*
     * Set each column in first(zeroth) row to zero
     */
    for(; i <= total_weight; ++i)
        CostTable[0][i] = 0;

    /*
     * Set each row in first(zeroth) column to zero
     */
    for(int i = 0; i <= item_count; ++i){
        CostTable[i][0] = 0;

        /*
         * calculate till required weight
         */
        for(int w = 1; w <= total_weight; ++w){
            /*
             * Get value from row above
             * or,
             * the value from a left column (w - Weight[i]) in the row above with added benefit
             */
            if(Weight[i] <= w)
                CostTable[i][w] = max(Benefit[i] + CostTable[i-1][w - Weight[i]], CostTable[i-1][w]);
            else
                CostTable[i][w] = CostTable[i-1][w];
        }
    }
}

void printCostTable(){
    for(int i = 0; i <= item_count; ++i){
        printf("%d:  ", i);
        for(int w = 0; w <= total_weight; ++w)
            printf("%d ", CostTable[i][w]);
        printf("\n");
    }
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    dynamicKnapsack();

    printf("Max Benefit: %d\n\n", CostTable[item_count][total_weight]);

    printCostTable();

    return 0;
}

Recursive:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack recursive
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
    if(i == 0 || w == 0)
        return 0;

    if(Weight[i] > w)
        return RecursiveKnapsack(i - 1, w);
    else
        return max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

    return 0;
}

Recursive Memoized:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack recursive memoization
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
    if(CostTable[i][w] != -1)
        return CostTable[i][w];

    if(Weight[i] > w)
        CostTable[i][w] = RecursiveKnapsack(i - 1, w);
    else
        CostTable[i][w] = max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    /*
     * Set all values of 2D matrix CostTable to Minus 1
     */
    for(int i = 0; i <= item_count; ++i)
        for(int w = 0; w <= total_weight; ++w)
            CostTable[i][w] = -1;

    printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

    return 0;
}