6
votes

Calculer l'élément de matrice progressivement, en utilisant des voisins

J'ai ce problème de Java, que je soupçonne que cela concerne un algorithme de niveau supérieur, mais mes recherches n'ont pas été en mesure de trouver quelque chose de pratique.

Vous construisez un tableau comme suit: P> xxx pré>

essentiellement, a _{i, j sub> = A _{i-1, j-1 sub> + a _{i-1, j sub>. Il est censé renvoyer l'élément à l'index (L, C): pour (4, 1), il devrait renvoyer 4, (5, 2) renvoie 10, etc. Ma solution est simple, mais ce n'est pas suffisant: P>}}}

static long get(int l, int c){
    long[][] matrix = new long[l+1][l+1];
    matrix[0][0]=1;
    matrix[1][0]=1; 
    matrix[1][1]=1;
    for(int i=2;i<=l;i++){
        matrix[i][0]=1;
        for(int j=1;j<=i;j++){
            matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j];
        }   
    }
    return matrix[l][c];
}

java algorithm matrix

0 commentaires

3 Réponses :

12
votes

Vous décrivez Triangle de Pascal , pour laquelle une formule fermée existe:

(x+y)^2 = 1* x^2 + 2xy + 1*y^2
(x+y)^3 = 1*x^3 + 3*xy^2 + 3yx^2 + 1*y^3

0 commentaires

4
votes

Vous n'avez pas besoin d'utiliser une boucle, c'est simplement Triangle de Pascal , La formule:

(n, k) = n! / ( k! * (n-k)!)

0 commentaires

0
votes

Essayez ceci:

static long get(int l, int c) throws Exception {
    if (l != c)
         throw new Exception("l != c");
    long[][] matrix = new long[l+1][l+1];
    matrix[0][0]=1;
    for (int i = 1; i <= l; ++i) {
         for (int j = 0; j <= i; ++j) {
              if (j - 1 >= 0) {
                    matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1];
              } else {
                    matrix[i][j] = matrix[i - 1][j];
              }
         }
    }
    return matrix[l][c];
}

0 commentaires