Recursive algorithm to fill increasing array { 1, 2, 2, 3, 3, 3, ... }

Admin 1
Viewed 198

I have the following task:

Give a recursive algorithm for filling an array like this: one 1, two 2, tree 3, four 4, ... ,n n.

For example, with n = 4 the array is supposed to look like:

{ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 }

My attempt is

Function filling(T, k, n)

if (n = 0) do return 1 
else if (0 <= k) do filling (T, n - k + 1, n);
     else filling(T, k, n - 1);
     fi
fi

with filling(T, k, n)

  • k: block start case of number n,
  • n: number,
  • T: array
recursion arrays algorithm
2 Answers

As you correctly show, the function needs an array T, a starting index k of the area to fill, and a size of the task n, i.e. a maximum number for filling.

The algorithm can be described like this:

if n is zero, return;
otherwise:

perform filling from 1 till n-1,
then append n items of value n

The question arises, how should the last line know where it should start adding.

One simple answer is: the routine may return the index one past the filled area:

size_t filling(int T[], size_t k, size_t n)
{
    if (n != 0)
    {
        k = filling(T, k, n - 1);
        for (size_t i = 0; i < n; i++)
            T[k + i] = n;
    }
    return k + n;
}

Make sure your array is at least n*(n+1)/2 items long, so that you don't overrun it.

user_7336370

You need to take care of two things here:

  • Number of digits to be insert in the array starting from 1, and
  • Count of a digit (which should be equal to digit itself) when inserting it in the array.

Since, the algorithm should be implemented using recursion, we should know the terminating condition of recursion.

Algorithm:

  • Insert digit in array.

  • Check if the count of digit inserted in array is equal to digit or not:

    • If count == digit then reset the count to 0 and increase digit by 1.
    • If count < digit go to step 1.

  • If digit to be inserted in array is greater than n, terminate the recursion.

Implementation in c++:

#include <iostream>
#include <vector>

void filling (std::vector <int>& arr, int k, int n) {
    static int c;

    if (c >= n) {
        c = 0;
        return;
    }

    if (k <= c) {
        k = k + 1;
        arr.push_back(c + 1);
    } else {
        k = 0;
        c = c + 1;
    }

    filling (arr, k, n);
}

int main() {
    std::vector <int> arr;

    int n;

    std::cout << "Enter a number:" << std::endl;
    std::cin >> n;

    filling (arr, 0, n);

    for (const auto& x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

# ./a.out
Enter a number:
5
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 

# ./a.out
Enter a number:
10
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 

# ./a.out
Enter a number:
1
1 

# ./a.out
Enter a number:
4
1 2 2 3 3 3 4 4 4 4
user_85423460
Related