de manière récursive la somme des entiers dans un tableau

J'ai un programme que je suis en train de faire pour la classe qui retourne la somme de tous les entiers dans un tableau en utilisant la récursivité. Voici mon programme à ce jour:

public class SumOfArray {

private int[] a;
private int n;
private int result;

    public int sumOfArray(int[] a) {

      this.a = a;
      n = a.length;

      if (n == 0)  //base case
      result = 0;
      else
          result = a[n] + sumOfArray(a[n-1]);

      return result;

   } //End SumOfArray method

} //End SumOfArray Class

Mais je suis de trois erreurs qui sont liées, je crois, mais je ne peux pas comprendre pourquoi c'est de trouver un type de null:

SumOfArray.java:25: sumOfArray(int[]) in SumOfArray cannot be applied to (int)
    result = a[n] + sumOfArray(a[n-1]);
                    ^
SumOfArray.java:25: operator + cannot be applied to int,sumOfArray
    result = a[n] + sumOfArray(a[n-1]);
              ^
SumOfArray.java:25: incompatible types
found   : <nulltype>
required: int
    result = a[n] + sumOfArray(a[n-1]);
                  ^
3 errors

En utilisant la récursivité n'est pas seulement plus compliqué, mais beaucoup plus lente dans ce cas. Je suppose que c'est juste un exercice.

InformationsquelleAutor Maggie S. | 2013-11-27

14

La solution est plus simple qu'il n'y paraît, essayez ceci (en supposant un tableau avec les non-longueur zéro):
```
public int sumOfArray(int[] a, int n) {
    if (n == 0)
        return a[n];
    else
        return a[n] + sumOfArray(a, n-1);
}
```
L'appeler comme ceci:
```
int[] a = { 1, 2, 3, 4, 5 };
int sum = sumOfArray(a, a.length-1);
```
- Ce n'est pas le bon, il suffit de fournir des réponses à un élève dans une classe. Ils n'apprennent pas. Vous avez besoin d'expliquer quel est le problème.
InformationsquelleAutor Óscar López
5

Le problème est que a[n-1] est un int, alors que sumOfArray attend un tableau de int.

Astuce: vous pouvez simplifier les choses en les faisant sumOfArray prendre le tableau et le début (ou la fin) de l'indice.

InformationsquelleAutor NPE
3
```
a[n-1] 
```
est l'obtention de l'int à n-1, et non pas la matrice de 0 à n-1.

essayez d'utiliser
```
Arrays.copyOf(a, a.length-1);
```
au lieu
- Je crois que vous pourriez aussi utiliser les Arrays#CopyOfRange trop.
- Sérieusement? Le fait que ce sera (horriblement) de travail ne signifie pas que c'est la bonne approche.
- un.longueur-1); est-ce que l'op devrait a[n-1] à faire.
- Oui, je sais, mais pourquoi créer une copie du tableau et de gaspiller de la mémoire et linéaire du temps de traitement (ce qui fera que cet algorithme en O(n^2) de la mémoire et de temps) quand vous pouvez passer une valeur entière avec le prochain élément du tableau à utiliser, et de garder cet algorithme en O(n) (de la mémoire et de temps)? Comme je l'ai dit dans mon dernier commentaire: le fait qu'il fonctionne (la compile, courir et obtenir le résultat attendu) ne signifie pas c'est la bonne approche.
InformationsquelleAutor Cruncher
1

a est un int tableau. Ainsi a[n-1] est un int. Vous êtes de passage à un int à sumOfArray qui attend un tableau et non une int.

InformationsquelleAutor Steve Kuo

À essayer si vous ne voulez pas passer la longueur de la table :

private static int sumOfArray(int[] array) {

        if (1 == array.length) {
            return array[array.length - 1];
        }

        return array[0] + sumOfArray(Arrays.copyOfRange(array, 1, array.length));
    }

Offcourse vous devez vérifier si le tableau est vide ou pas.

InformationsquelleAutor samach

C'est la seule solution récursive avec une complexité O(N).et avec un paramètre d'entrée d'Un[] seulement.

Vous pouvez gérer nulle et vide(de longueur 0) cas particulier comme Son retour 0 dans cette solution. Vous jetez Exception dans ce cas.

/*
 * Complexity is O(N)
 */
public int recursiveSum2(int A[])
{
    if(A == null || A.length==0)
    {
        return 0;
    }
    else
    {
        return recursiveSum2Internal(A,A.length-1);
    }
}
private int recursiveSum2Internal(int A[],int length)
{
    if(length ==0 )
    {
        return A[length];
    }
    else
    {
        return A[length]+recursiveSum2Internal(A, length-1);
    }
}

InformationsquelleAutor Nick13

Comment de cette solution récursive? Vous faites un petit sous-ensemble qui contient les éléments de la deuxième à la fin. Cette récursivité continue jusqu'à ce que la taille de la matrice est 1.

import java.util.Arrays;

public class Sum {
    public static void main(String[] args){
        int[] arr = {1,2,3,4,5};
        System.out.println(sum(arr)); //15
    }

    public static int sum(int[] array){
        if(array.length == 1){
            return array[0];
        }

        int[] subArr = Arrays.copyOfRange(array, 1, array.length);
        return array[0] + sum(subArr);
    }
}

InformationsquelleAutor TakaSoft

private static int sum(int[] arr) {
    //TODO Auto-generated method stub
    int n = arr.length;

    if(n==1)
    {
        return arr[n-1];
    }

    int ans = arr[0]+sum(Arrays.copyOf(arr, n-1));

    return ans;
}

InformationsquelleAutor Amandeep Singh

Version simplifiée:

//acc -> result accumlator, len - current length of array

public static int sum(int[] arr, int len, int acc) {
    return len == 0 ? acc :  sum(arr, len-1,  arr[len-1]+ acc); 
}   
public static void main(String[] args)  {
    int[] arr= { 5, 1, 6, 2};
    System.out.println(sum(arr, arr.length, 0));
}

InformationsquelleAutor Naresh Krishnamoorthy

Vous devez vous connecter pour publier un commentaire.