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

[Trap D]

Fin de partie
Même en Haskell, ça ne fonctionnera pas.
Un des calculs me donne un résultat de 587 chiffres après un calcul de 21,5 secondes ! (et ce n'est qu'un résultat intermédiaire).
Je vais changer de méthode pour résoudre le problème !

[tbc92]

Si le calcule passe par les calculs de fact(x), fact(y) et fact(x+y), effectivement, ces résultats intermédiaires vont donner des nombres très grands.

Mais ça revient en fait à cette boucle :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
si y>x alors      // On inverse les 2 termes pour avoir une boucle aussi courte que possible.
   y0=y
   y=x
   x=y0
fin
 
resu = 1
pour i = 1 a y
  resu=resu*(x+y)/i
fin
renvoyer resu

Ici, aucun résultat intermédiaire avec des nombres nettement plus grands que le résultat final.

[Flodelarab]

Peut-on avoir un ordre de grandeur de x et y ?

Python donne instantanément f(100;100) = 90548514656103281165404177077484163874504589675413336841320

Si tu es bien en-dessus de ces valeurs, tu rentres dans le domaine de la cryptographie, où il est normal que l'ordinateur soit dépassé. Il faut marcher sur des œufs.

As-tu lu cet article pour avoir une approximation (clic ici) de f(x,y) ?

[Trap D]

C'est f(333193, 156) qui a pris ce temps sur Haskell, j'ai vérifié f(100,100) est aussi instantané sur Haskell.
Ce calcul de f(333193, 156) est un calcul intermédiaire, j'en ai une centaine comme ça à faire, si je continues avec le même raisonnement, c'est pour ça que je dis que je dois changer absolument de concept de résolution du problème.
Pour la petite histoire, je tente de résoudre un problème "moyen" sur Codingame, alors je me dis qu'il y a forcément une solution 10000 fois plus rapide (la programmation dynamique par exemple).
Ce que c'est que d'avoir la tête dans le sac.