Fibonacci for letters

Question

I was programming a code for a case provided by my university. It was about making a Fibonacci function, but for letters. For example, if f(0) -> a, f(1) -> b, then f(2) -> ba, and so on. I was halfway until finish when I found a problem that I cannot solve.

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

void fib(char bank[][700], char result[700], int n) {
    char temp[700];
    for (int i = 2; i <= n; i++) {
        if (i > 2) {
            strcpy(bank[i - 1], result);
        }
        for (int k = 0; bank[i - 1][k] != 0; k++) {
            result[k] = bank[i - 1][k];
        }
        strcat(result, bank[i - 2]);
    }
}

int main() {
    int cases = 0;
    scanf("%d", &cases);
    getchar();
    
    for (int i = 1; i <= cases; i++) {
        int n = 0; char first[5] = {};
        char wordBank[][700] = {{},{}};
        char result[700] = "#";
        scanf("%d %c %c", &n, &first[0], &first[1]);
        getchar();
        wordBank[0][0] = first[0];
        wordBank[1][0] = first[1];
        
        if (n == 0) {
            printf("Case #%d: %c\n", i, first[0]);
        } else if (n == 1) {
            printf("Case #%d: %c\n", i, first[1]);
        } else if (n > 1) {
            fib(wordBank, result, n);
            printf("Case #%d: %s\n", i, result);
        }
    }
    
    return 0;
}

So the example input is:

3
2 a b
3 a b
4 a b

3 on line 1 is the number of test cases,
2 on line 2 is the result of f(n),
a and b on line 2 in f(0) and f(1),

The output would be:

Case #1: ba
Case #2: bab
Case #3: babba

The problem occur when I try to input n more than 3. I try to use usleep function to kind of slow down the process because I think that's the source of the problem. usleep only help me until a few more n range.

The f(0) and f(1) are guaranteed 1 letter, so it can't be 'ab' for f(0) or f(1) or any other more than 1 letter combination for both f(0) and f(1).

Answer 1

char wordBank[][700] = {{},{}}; defines wordBank as an array of only two arrays of 700 characters each (all 1400 characters are '\0').

Try defining a larger array

char wordBank[100][700] = {0};

See https://ideone.com/W9guSZ

Answer 2

For starters this header:

#include <unistd.h>

is redundant because neither declaration from the header is used in the program.

The function main without parameters shall be declared like:

int main( void )

Using the function getchar as for example in this line:

scanf("%d", &cases); getchar();

is also redundant. You should remove calls of getchar.

It is unclear why you are using the magic number 700 in the program.

Within the function the array temp:

char temp[700];

is not used.

You declared the array wordBank:

char wordBank[][700] = {{},{}};

only with two elements. But within the function there can be an access to memory outside the array due to the loops:

for(int i = 2; i <= n; i++){
    if(i > 2){
        strcpy(bank[i - 1], result);
    }
    for(int k = 0; bank[i - 1][k] != 0; k++){
        result[k] = bank[i - 1][k];
    }
    strcat(result, bank[i - 2]);
}

when n is greater than 2 that results in undefined behavior.

According to the assignment the function should build a new string.

It should be declared like:

char * fib( size_t n, char c1, char c2 );

using arbitraty two initial characters. The caller of the function should pass the characters to the function.

I would define the function the following way as shown in the demonstration program below:

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

char * fib( size_t n, char c1, char c2 )
{
    size_t first = 0;
    size_t second = 1;

    size_t length = 1;

    for (size_t i = 0; i < n; i++)
    {
        length += first;
        second += first;
        first = second - first;
    }

    char *result = calloc( length + 1, 1 );

    if (result != NULL)
    {
        size_t previous_size = 0;
        size_t next_size = 0;

        char *p = result;

        size_t i = 0;

        do
        {
            switch (i)
            {
            case 0:
                *p = c1;
                break;

            case 1:
                *p = c2;
                break;

            case 2:
                *p++ = c2;
                *p++ = c1;
                next_size = 1;
                previous_size = 1;
                break;

            case 3:
                *p++ = c2;
                break;

            default:
                memcpy( p, result, previous_size );
                p += previous_size;
                break;
            }

            next_size += previous_size;
            previous_size = next_size - previous_size;
        } while ( i++ < n);
    }

    return result;
}

int main( void )
{
    const size_t N = 10;

    for (size_t i = 0; i < N; i++)
    {
        char *s = fib( i, 'a', 'b');
        if ( s != NULL ) puts( s );
        free( s );
    }
}

The program output is:

a
b
ba
bab
babba
babbabab
babbababbabba
babbababbabbababbabab
babbababbabbababbababbabbababbabba
babbababbabbababbababbabbababbabbababbababbabbababbabab