Discussion :

[Trap D]

Bonjour
J'ai une fonction récursive toute simple
f(x,y) = f(x-1,y) + f(x, y-1)
f(x, 0) = f(0, y) = 1
Je pense que cette fonction doit être connue et porter un nom mais je l'ignore.
J'aurais voulu connaître son nom, et aussi une méthode rapide de calcul, par exemple une méthode pour la dérécursiver car je n'en ai pas trouvé .
Tout ce que j'ai trouvé est

ce qui ne me mène pas très loin par rapport à la première définition !
J'obtiens en C

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAX 10000
unsigned long long int val[MAX][MAX];
unsigned long long int f(int x, int y)
{
    if (val[x][y] == 0)
    {
        unsigned long long int tt = 0;
        for (int i = 0; i <= x; i++)
        {
            if (y == 0)
                tt = 1;
            else
                tt += f(i, y - 1)) ;
        }
        val[x][y] = tt;
    }
    return val[x][y];
}

La mémoïsation c'est bien gentil mais quand on a de très grandes valeurs on arrive vite aux limites des systèmes.
Merci pour vos conseils et indications !

[Flodelarab]

Bonjour

Déjà, ça part mal. Je ne suis pas d'accord avec ta formule (écrite en latex). Il manque forcément un "+1" quelque part.

Ensuite, la formule fait évidemment pensé au triangle de pascal. Et c'est sans surprise que j'arrive à la formule suivante :



Il te reste à discuter si x>y ou x<y pour savoir lequel touche le sol le premier.

Bonne chance

[Trap D]

Merci de ta réponse.
La formule (Libre Office formule) est sans doute fausse pour le +1 mais le code C est correct, et effectivement le triangle de Pascal s'invite dans la danse.
Pour x et y, avec la mémoïsation j'appelle toujours avec x plus petit que y, mais ça ne suffit pas pour accélérer les calculs.
Je continue ...
PS je ne connaissais pas la balise spécifique C !
A quand la balise Prolog

[Flodelarab]

Pour la mémoïsation, c'est d'accord. Mais reste un peu plus au niveau théorique. Je ne suis pas convaincu que tu ne puisses pas tout résoudre théoriquement avant de faire le code. Pour n=4, les paramètres vont de (x-4;y) à (x;y-4) en passant par (x-2;y-2), par exemple. Donc il arrivera des cas où le second paramètre sera plus petit que le premier.C'est ça qu'il faut régler pour finir le calcul.

[tbc92]

Sauf erreur, f(x,y)=fact(x+y)/( fact(x)*fact(y) ) où fact() est la fonction factorielle.
Ca devrait permettre une implémentation permettant de calculer f(x,y) en direct, sans passer par les calculs de tous les éléments précédents.
Par contre, il faut certainement simplifier les calculs avant de faire la division :
Par exemple, pour calculer f(1000,4), si on calcule fact(1004) ... puis qu'on divise par fact(1000) et par fact(4), on va passer par des nombres très grands (dépassement de capacité ...) pour arriver à un calcul simple en fait.

[Trap D]

Merci de vos contributions et désolé pour la réponse tardive.
J'ai réussi à vérifier gràce au triangle de Pascal que

Je n'ai plus qu'à abandonner le C pour faire mes calculs en Haskell, j'aurais moins de problèmes ...
Merci.
PS C'est exactement ce que tu as écrit tbc92 mais je voulais trouver tout seul