Somme de la matrice multidimensionnelle

Question

J'ai besoin de calculer la somme d'un tableau multidimensionnel. ne nécessite pas d'espace supplémentaire, pas de récursivité.

class MultiDimensionArray { 
    // This is a provided function, Assume it works 
    public static Long getValue(int... indexOfDimension) { 
     //... 
     return value; 
    } 
    // lengthOfDeminsion: each dimension's length, assume it is valid: lengthOfDeminsion[i]>0. 
    public static Long sum(MultiDimensionArray mArray, int[] lengthOfDeminsion) { 
     ... 
     return sum; 
    } 

Comment implémenter la méthode sum()? il semble que je doive implémenter une "boucle imbriquée de niveau n". Je peux le faire via la récursivité, mais sans récursion, je ne sais vraiment pas comment y parvenir.

Answer 1

Je ne comprends pas ce que signifie l'espace supplémentaire. Mais mon idée est d'allouer un n-uplet (n = nombre dimensions) et quelques variables auxiliaires.

int n = lengthOfDimension.Length; 
int[] tuple = new int[n]; // all zeroes 
int at = n-2; 
Long sum = 0; 
do 
{ 
    for (tuple[n-1] = 0; tuple[n-1] < lengthOfDimension[n-1]; tuple[n-1]++) 
    { 
     sum += getValue(tuple); 
    } 
    while (at >= 0 && ++tuple[at] == lengthOfDimension[at]) 
    { 
     tuple[at--] = 0; 
    } 
    if (at >= 0) at = n-2; 
} 
while (at >= 0); 

Le cheval de travail est la boucle qui parcourt ici la dimension la plus faible de l'hypercube, en utilisant tuple pour sélectionner la ligne droite. Par la suite, les valeurs dans tuple seront incrémentées jusqu'à ce que la longueur de la cote respective soit atteinte, où la valeur est remise à zéro et la valeur supérieure suivante (at-1) est incrémentée. La tâche est terminée lorsque le tuple [0] a été encapsulé.