How to resolve the algorithm Padovan sequence step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Padovan sequence step by step in the C programming language

Table of Contents

Problem Statement

The Padovan sequence is similar to the Fibonacci sequence in several ways. Some are given in the table below, and the referenced video shows some of the geometric similarities. Show output here, on this page.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Padovan sequence step by step in the C programming language

The provided C code demonstrates the generation of the Padovan sequence and its connection to the L-system. Here's a detailed explanation of the code:

  1. Header Files:

    • The code includes several standard C library headers:
      • <stdio.h> for input/output operations
      • <stdlib.h> for memory allocation and other utility functions
      • <math.h> for mathematical functions
      • <string.h> for string manipulation

  2. Padovan Sequence Generation:

    • The pRec function implements a recursive approach to calculate the nth value of the Padovan sequence.
      • It utilizes memoization to store previously calculated values and avoid redundant calculations.
    • The pFloor function provides an alternative method to calculate the nth value of the Padovan sequence using a floor function.

  3. L-System Generation:

    • The nextLSystem function generates the next value in the L-system sequence based on the previous value.
      • It iterates through the input string, replacing characters according to the L-system rules (A -> B, B -> C, C -> AB).

  4. Main Function:

    • The main function is the entry point of the program.
    • It prints the first 20 terms of the Padovan sequence using the recursive approach.
    • It compares the results from the recursive and floor functions to verify their consistency up to P_63.
    • It generates and prints the first 10 strings of the L-system sequence.
    • It compares the lengths of L-system strings to the corresponding Padovan sequence values (up to P_31) to demonstrate their relationship.

  5. Constants and Variables:

    • BUFSZ is a constant that defines the size of buffers used throughout the program.

  6. Usage:

    • The program provides a way to explore the relationship between the Padovan sequence and the L-system.
    • It demonstrates the recursive and floor-based methods for generating Padovan sequence values.
    • It highlights the L-system's string generation process and its connection to the Padovan sequence.

Source code in the c programming language

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

/* Generate (and memoize) the Padovan sequence using
 * the recurrence relationship */
int pRec(int n) {
    static int *memo = NULL;
    static size_t curSize = 0;
    
    /* grow memoization array when necessary and fill with zeroes */
    if (curSize <= (size_t) n) {
        size_t lastSize = curSize;
        while (curSize <= (size_t) n) curSize += 1024 * sizeof(int);
        memo = realloc(memo, curSize * sizeof(int));
        memset(memo + lastSize, 0, (curSize - lastSize) * sizeof(int));
    }
    
    /* if we don't have the value for N yet, calculate it */
    if (memo[n] == 0) {
        if (n<=2) memo[n] = 1;
        else memo[n] = pRec(n-2) + pRec(n-3);
    }
    
    return memo[n];
}

/* Calculate the Nth value of the Padovan sequence
 * using the floor function */
int pFloor(int n) {
    long double p = 1.324717957244746025960908854;
    long double s = 1.0453567932525329623;
    return powl(p, n-1)/s + 0.5;
}

/* Given the previous value for the L-system, generate the
 * next value */
void nextLSystem(const char *prev, char *buf) {
    while (*prev) {
        switch (*prev++) {
            case 'A': *buf++ = 'B'; break;
            case 'B': *buf++ = 'C'; break;
            case 'C': *buf++ = 'A'; *buf++ = 'B'; break;
        }
    }
    *buf = '\0';
}

int main() {
    // 8192 is enough up to P_33.
    #define BUFSZ 8192
    char buf1[BUFSZ], buf2[BUFSZ];
    int i;
    
    /* Print P_0..P_19 */
    printf("P_0 .. P_19: ");
    for (i=0; i<20; i++) printf("%d ", pRec(i));
    printf("\n");
    
    /* Check that functions match up to P_63 */
    printf("The floor- and recurrence-based functions ");
    for (i=0; i<64; i++) {
        if (pRec(i) != pFloor(i)) {
            printf("do not match at %d: %d != %d.\n",
                i, pRec(i), pFloor(i));
            break;
        }
    }
    if (i == 64) {
        printf("match from P_0 to P_63.\n");
    }
    
    /* Show first 10 L-system strings */
    printf("\nThe first 10 L-system strings are:\n"); 
    for (strcpy(buf1, "A"), i=0; i<10; i++) {
        printf("%s\n", buf1);
        strcpy(buf2, buf1);
        nextLSystem(buf2, buf1);
    }
    
    /* Check lengths of strings against pFloor up to P_31 */
    printf("\nThe floor- and L-system-based functions ");
    for (strcpy(buf1, "A"), i=0; i<32; i++) {
        if ((int)strlen(buf1) != pFloor(i)) {
            printf("do not match at %d: %d != %d\n",
                i, (int)strlen(buf1), pFloor(i));
            break;
        }
        strcpy(buf2, buf1);
        nextLSystem(buf2, buf1);
    }
    if (i == 32) {
        printf("match from P_0 to P_31.\n");
    }
    
    return 0;
}

You may also check:How to resolve the algorithm Farey sequence step by step in the Maxima programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Boolean values step by step in the Self programming language
You may also check:How to resolve the algorithm Exponentiation operator step by step in the J programming language
You may also check:How to resolve the algorithm Lychrel numbers step by step in the D programming language