algorithm
Catalaans nummeralgoritme

Catalaans nummeralgoritme Basisinformatie

Catalaans getallenalgoritme is Dynamic Programming-algoritme.

In combinatorische wiskunde vormen de Catalaanse getallen een reeks natuurlijke getallen die voorkomen in verschillende telproblemen, vaak met recursief gedefinieerde objecten. De Catalaanse getallen op niet-negatieve gehele getallen n zijn een verzameling getallen die zich voordoen bij het opsommen van bomen van het type: 'Op hoeveel manieren kan een gewone n-gon worden verdeeld in n-2-driehoeken als verschillende oriëntaties afzonderlijk worden geteld?'

Toepassing van Catalan Number Algorithm:

1. Het aantal manieren om munten te stapelen op een onderste rij die bestaat uit n opeenvolgende munten in een vlak, zodat er geen munten aan beide zijden van de onderste munten mogen worden geplaatst en elke extra munt boven twee andere munten moet liggen, is het nde Catalaanse nummer.
2. Het aantal manieren om een reeks van n paar haakjes te groeperen, zodat elke open haakje een overeenkomend gesloten haakje heeft, is het Catalaanse nummer.
3. Het aantal manieren om een n + 2-zijdige convexe polygoon in een vlak in driehoeken te snijden door hoekpunten te verbinden met rechte, niet-snijdende lijnen is het nde Catalaanse getal. Dit is de toepassing waarin Euler geïnteresseerd was.

Met behulp van nul-gebaseerde nummering, wordt het n de Catalaanse nummer direct gegeven in termen van binomiale coëfficiënten door de volgende vergelijking.

Voorbeeld van Catalaans nummer:

Hier waarde van n = 4. (Beste voorbeeld - Van Wikipedia)

Hulpruimte: O(n)
Tijd Complexiteit: O(n^2)

C # Implementatie

public class CatalanNumber
{
    public static int Main(int number)
    {
        int result = 0;
        if (number <= 1) return 1;
        for (int i = 0; i < number; i++)
        {
            result += Main(i)*Main(number - i - 1);
        }
        return result;
    }
}