Rekurencyjne wypełnianie przekątnych tablicy

0

Witajcie. Myślałem, że w miarę rozumiem używanie rekurencji, ale tylko mi się wydawało.

Chciałbym przećwiczyć sobie wypełnianie rekurencyjnie tablic dwuwymiarowych w różne wzory np. węże, skośne linie, różne inne patterny.

Tutaj wezmę przykład wypełniania "po przekątnej". Wypełniona tablica dwuwymiarowa tablica[5][5] (kwadrat) powinna wyglądać tak:
title

O ile wypełnienie tego w sposób iteracyjny nie powinno stanowić dla mnie wielkiego wyzwania, to w sposób rekurencyjny nie wiem nawet jak zacząć.

Póki co mam tylko szkielet kodu (przepraszam za język polski.

#include <iostream>

const int rozmiar = 5;
int tablica[rozmiar][rozmiar] = {};

void wypelnienie(int n)
{
    // warunek do przerwania rekursji
    if (n > rozmiar)
        return;

    for (int i = 0; i < rozmiar; i++) {
        for (int j = 0; j < rozmiar; j++) {
            tablica[i][j] = n;
        }
    }
    wypelnienie(n + 1);
}

int main()
{
    wypelnienie(1);
}

Oczywiście nie wszystko ma tu sens, warunki w pętlach pewnie nie pasują. Nie wiem jak dalej ugryźć to zadanie jeśli chodzi o rozwiązanie rekurencyjne.

2

A czemu to musi być rekurencja? Iteracja nie wystarczy?

0

Nie wystarczy. Takie jest odgórne polecenie z uczelni. To są dodatkowe (dla chętnych) zadania niepodlegające ocenie, jednak i tak chciałbym się nauczyć jak to rozwiązać jeśli się da.

0

Podam Ci gotowca, ale w Pascalu, a Ty go przeportuj na C++ i spróbuj zrozumieć jak działa i dlaczego działa. ;)

type
  TMyArray = array [0 .. 4, 0 .. 4] of Integer;

  procedure FillArray(out AArray: TMyArray; AX, AY, AValue, AStep: Integer);
  begin
    if (AX = 5) or (AY = 5) then Exit;

    AArray[AX, AY] := AValue;

    if AValue in [0, 5] then
      AStep *= -1;

    FillArray(AArray, AX + 1, AY, AValue + AStep, AStep);
    FillArray(AArray, AX, AY + 1, AValue + AStep, AStep);
  end;

Przykładowe wywołanie:

var
  MyArray: TMyArray;
begin
  FillArray(MyArray, 0, 0, 1, 1);

oraz wyjście:

  1  2  3  4  5
  2  3  4  5  4
  3  4  5  4  3
  4  5  4  3  2
  5  4  3  2  1

https://ideone.com/ytva1k

PS: to jest algorytm naiwny – krótki w implementacji, ale redundantny w działaniu. Przyda się lepsza wersja.

0

Rozwiązanie w OCamlu:

let wypelnij n = 
    let arr = Array.make_matrix n n 0 in
    let rec loop1 i = 
        if i = -1 then arr else
            let rec loop2 j =
            if j = -1 then arr 
            else let _ = (arr.(i).(j) <- (if i+j < n then (i+j+1) else (2*n-i-j-1))) in loop2(j - 1)
        in let _ = loop2 (n-1) in loop1 (i - 1)
    in loop1 (n-1);;



let arr = wypelnij 6;;
Array.iter (fun x -> let _ = ((Array.iter (fun x -> Printf.printf "% 4d " x) x), print_newline()) in ()) arr;;

Try it online!

@furious programming to za to jest dość efektywne rozwiązanie :)

0
Fioletowy Król napisał(a):

Nie wystarczy. Takie jest odgórne polecenie z uczelni.

Czy w końcu nastał czas kiedy jedyny biznesowy case rekurencji to zadanie w szkole?

0

@furious programming: Pomógłbyś zinterpretować tę linię?

if AValue in [0, 5] then
      // instrukcja;
0

To to samo co poniższy zlepek porównań:

if (AValue = 0) or (AValue = 5) then

Pamiętaj, że ten mój przykład trzeba udoskonalić, bo choć działa prawidłowo, to dla macierzy o rozmiarze 5x5 wykonuje 251 przypisań, co jest potworną nadmiarowością. To tylko pierwszy pomysł z brzegu, który zadziałał. ;)

0

Przeanalizuj to Bracie:

#include <iostream>

using namespace std;

int fillTable(int *table, int rows, int columns)
{
    if (rows == 0)
    {
        for (int cnt = 0; cnt < columns; cnt++)
        {
            *(table + cnt) = cnt + 1;
        }
        return rows;
    }
    else
    {
        int offset = fillTable(table, rows - 1, columns);
        if (offset > 0)
        {
            for (int cnt = 0; cnt < columns; cnt++)
            {
                //*(table + cnt + columns * offset) = (cnt + 1 + offset) <= columns ? cnt + 1 + offset : (cnt + offset + 1) % columns;
                int value = (cnt + 1 + offset) <= columns ? cnt + 1 + offset : columns - (cnt + 1 + offset - columns);
                *(table + cnt + columns * offset) = value;
            }
        }
        offset++;
        return offset;
    }
}

int main()
{
    int rows = 5, columns = 5;
    int table[rows][columns] = {};
    
    fillTable(&table[0][0], rows, columns);

    for (int cnt1 = 0; cnt1 < rows; cnt1++)
    {
        for (int cnt2 = 0; cnt2 < columns; cnt2++)
        {
            cout << table[cnt1][cnt2] << " ";
        }
        cout << endl;
    }
    return 0;
}

https://onlinegdb.com/HkOZkS_pX

1

Wpadłem na pomysł jak wykluczyć wielokrotne przypisania do tej samej komórki – wystarczy dodać jeden warunek. W dalszym ciągu kod będzie krótki i nie będzie zawierał żadnych pętli. Niestety tablice w C++ dały mi w kość, więc poniższe trzeba traktować bardziej jako pseudokod.

const int size = 5;
int array[size][size] = {};

void fill(int x, int y, int value, int step)
{
  if (x == size || y == size) return;
  
  array[x][y] = value;
  
  if (value == 0 || value == size)
    step *= -1;
  
  fill(x + 1, y, value + step, step);
  
  if (y == 0)
    fill(x, y + 1, value + step, step);
}

Funkcja fill nie jest wrażliwa na rozmiar tablicy – macierz może być większa lub mniejsza niż 5x5. Wywołanie musi wyglądać w ten sposób (inne wartości parametrów nie są dozwolone):

fill(0, 0, 1, 1);

Działający na tej samej zasadzie programik w Pascalu tutaj – https://ideone.com/2SciVP

0
tab = []

SIZE = 5

#create empty array
SIZE.times do
  temp = []
  SIZE.times do
    temp.push nil
  end
  tab.push temp
end


def fillInsideRec(tab,i,j)
  if(j >= SIZE)
    return
  else
    tab[i][j] = j+1+i
    if(tab[i][j]>SIZE)
      diff = tab[i][j] - SIZE
      tab [i][j] = SIZE - diff
    end
    fillInsideRec(tab,i,j+1)
  end
end

def fillArrRec(tab,i)
  if(i >= SIZE)
    return
  else
    fillInsideRec(tab,i,0)
    fillArrRec(tab,i+1)
  end
end

fillArrRec(tab,0)

tab

1 użytkowników online, w tym zalogowanych: 0, gości: 1