Trouver le nombre minimal dans un tableau avec la récursivité?

int i = 0;
int min = x[i];
while ( i < n ){
    if ( x[i] < min ){
        min = x[i];
    }
    i++;
}
return min;

J'ai écrit la forme itérative pour trouver le nombre minimum d'un tableau. Mais je voudrais écrire une fonction qui avec la récursivité. S'il vous plaît aider!

La liste est triée? Si elle l'est, la récursivité pourrait faire plus de sens, sinon, la récursivité semble maladroit ici.
Si la liste est triée, le premier élément serait le minimum et ni itération, ni la récursivité aurait du sens.
Bien, même si elle a été trié, le dernier élément pourrait également être le minimum selon la façon dont elle a été trié...
Ne nous laissons pas faire d'hypothèses et de considérer la liste triée.

OriginalL'auteur user133466 | 2009-11-14

  1. 14

    Parce que cela sonne comme des devoirs, voici un indice: La valeur minimum dans un tableau est le premier élément, ou le nombre minimal dans le reste de la matrice, celle qui est la plus petite.

    Veuillez noter: Si oui ou non ce fait est devoirs ne sont pas pertinentes. C'est le genre d'exercice que vous obtenez beaucoup plus de valeur à partir de si vous découvrez la solution, que vous pourrez par la copie de la solution de quelqu'un d'autre.

    OriginalL'auteur Greg Hewgill

  2. 2

    Le nombre minimal d'un élément de tableau est un élément dans le tableau.

    Le nombre minimum d'un tableau avec la taille > 1 est le minimum du premier élément et le minimum du reste de la matrice.

    (Le nombre minimum d'un tableau vide n'est pas défini.)

    OriginalL'auteur sepp2k

  3. 2

    Ce n'est pas une solution optimale, car vous pouvez enregistrer le résultat de l'appel récursif dans une variable int, mais je n'étais pas dans mon exercice.

    De toute façon, cette fonction permet de rechercher la valeur la plus basse dans un tableau int en utilisant la récursivité.
    Comme le premier, il vérifie le nombre d'éléments dans le tableau en vérifiant si la taille est égale à 1, puis retourne la première valeur comme résultat. Si le tableau est plus grand que 1 (et techniquement aussi lorsque le bas), il compare la dernière valeur du tableau avec l'appel récursif avec le reste de la matrice.

    La récursivité s'arrête à l'0-index, puis compare cette valeur à l'indice 1. Il compare ensuite la valeur la plus faible de l'indice 0 et 1 par la valeur de l'indice 3 et ainsi de suite jusqu'à ce qu'il atteigne la dernière valeur.

    int minimum(int array[], int size) {
    if (size == 1) {
        return array[0];
    }
    else {
        return (array[size] < minimum(array, size - 1))
            ? array[size]
            : minimum(array, size - 1);
    }
}

int array[5] = {5, 99, 205, 1, 15};
int smallest = minimum(array, 4); //4 = index of the last element

    Règles dans mon exercice:

    • De ne pas modifier le tableau
    • Ne pas utiliser de variable
    • Utiliser la récursivité
    Vous montrez aussi écrire quelque chose pour expliquer un peu ce que vous avez fait. Juste pour être compréhensible par un novice
    Je n'avais aucune idée de comment résoudre mon exercice, même après avoir regardé cette page. J'avais toujours la page qui s'ouvre après j'ai trouvé la solution moi-même et a décidé de le poster ici. De toute façon, j'ai édité mon post et ajouté une explication.
    le mien était juste une suggestion (avec une erreur 😀 show -> devrait. Putain smartphone auto-correcteur) pour une réponse complète. Pour l'avenir, c'est apprécier si vous commenter votre code, parce que vous pouvez en dire plus à ce sujet. Bien sûr, c'était un simple exercice de sorte qu'il n'était pas vraiment important, mais c'est une question de novice, donc je chose est gentil de donner une réponse pour un novice. +1 pour l'effort 🙂

    OriginalL'auteur botder

  4. 1

    Sons comme des devoirs, mais votre meilleur pari est quelque chose comme ceci:

    int main(void) {
    int size = 2;
    int test[] = {0,1};
    int min = test[0];
    findMin(&min, test, size);
    printf("%d", min);
}

void findMin(int* min, int* test, int* length);

void findMin(int* min, int* test, int* length) {
    if (length >= 0) {
         if (*test < *min) {
            *min = test;
         }
         findMin(min, test++, (*length)--);
    }
}
    Techniquement récursive mais manque de gestalt.

    OriginalL'auteur Myles

  5. 1

    Voici une fonction qui retourne un pointeur vers la valeur minimale:

    #include <stddef.h>

int *recursiveMin(int *x, int n) {
  if (x == NULL || n == 0)
      return NULL;
  if (n == 1)
      return x;
  int *t = recursiveMin(x + 1, n - 1);
  return *x < *t ? x : t;
}

    OriginalL'auteur DigitalRoss

  6. 1

    règle générale de la récursivité est pour éviter les "petits pas" - "premier élément par rapport au reste du tableau" est une très mauvaise idée. essayez de traiter le tableau en deux, comme ceci:

    min( array ) {
   if size of array == 1 return array[0]
   else if size of array == 2 return array[0] < array[1] ? array[0] : array[1]
   else {
      firstmin = min( firsthalf) //stored to avoid double calls
      secondmin = min( secondhalf)
      firstmin < second_min ? firstmin : secondmin
   }
 }

    pour la poursuite de l'optimisation:

    - éviter la matrice de copies - envisager l'utilisation de quicksort-comme signature (tableau, de, pour)

    - éviter les appels récursifs pour les tailles < 2

    De 10 réponses, c'est la seule 1 qui commence à la récursivité intelligemment. +1

    OriginalL'auteur Frantisek Kossuth

  7. 0

    Pourquoi voulez-vous faire avec la récursivité? Une règle générale avec la récursivité est de ne pas utiliser la récursivité si vous pouvez le faire à l'intérieur d'un linéaire simple boucle.

    Sans doute parce que la cession a dit de le faire avec la récursivité.
    Meh. J'aime la récursivité. Fondamentalement, je suis d'appliquer l'inverse de la règle (à condition que le compilateur a récursion sur la queue de l'optimisation).
    À l'aide de la queue de la récursivité, il semble comme s'il n'y a pas de différence entre la droite de la boucle et la récursivité, en supposant une demi-décent compilateur. Il dépend seulement de ce qui est plus clair au niveau du code.
    exactement. Et pour cette raison, j'ai souvent (pas toujours) préfèrent la récursivité. Pour beaucoup de choses, la récursivité correspond à l'expression naturelle d'un concept mathématique, littéralement, tandis que itération nécessite de refactoring. Je reconnais que beaucoup de gens ont un problème avec la récursivité j'ai donc essayer de l'éviter dans un “non naturelle de l'habitat”. Mais l'OP problème est en fait extrêmement bien adaptés à la récursivité (c'est juste une simple réduction à l'aide de min que l'opération).

    OriginalL'auteur Makach

  8. 0

    Essayer:

      int recursive_min(list<int> arr) {
    return recursive_min(arr);
  }

    Bien que cela ne fonctionne pas dans des langages impératifs.

    Une réponse plus sérieuse serait, en pseudo-code:

    func recursive_min( list l ) {
 head = l[1]
 tail = l[2<->end]
 if l.length==1 return head else return min(head,recursive_min(tail))
}

    Bien que cela ne fonctionne pas, si l est vide.

    OriginalL'auteur Jack V.

  9. 0
    int findMin(int a[], int len) {
// normal version
// if (len==1) return a[0];
// return (a[len-1] < findMin(a,len-1))? a[len-1] : findMin(a,len-1);
// memoization version, sort of?

    int rightside;
    if (len==1) return a[0];

    rightside = findMin(a,len-1);

    return (a[len-1] < rightside)? a[len-1] : rightside;
}

    OriginalL'auteur Timothy Law

  10. 0
    #include <iostream>
#include <cstdlib>
using namespace std;

int min(int [], int);
void mostrar(int [], int);

int main() {
    int f[] = {4, 9, 0, -1, 5, 8, -3, 6, -4, 0};
    int t = sizeof(f)/sizeof(int);
    cout << "\nEl valor m\xa1nimo para los valores:\n";
    mostrar(f, t);
    cout << "\nes: " << min(f, t);
    system("pause>nul");
}

int min(int x[], int p) {
    if (p == 1)
        return x[0];
    int aux = min(x+1, p-1);
    return x[0] < aux ? x[0] : aux;
}

void mostrar(int v[], int k) {
    if (k > 1)
        mostrar(v, k-1);
    cout << v[k-1] << " ";
}

    OriginalL'auteur H. Murcia

  11. 0
    const int = 20;

int getmin (int v[], int n);

main ()
{
    int v[N];
    int i,n,min;

    printf("\n\tType number of elements:\t");
    scanf("%d",&n);

    for (i=0;i<n;i++)
    {
        printf("\nv[%d]:\t",i);
        scanf("%d",&v[i]);             
    }

    min = getmin (v,n);

    printf("\n\n\tMinimume value is %d.",min); 
}

int getmin (int v[],int n)
{
    if (n>0)
    {
        if ( v[n-2] > v[n-1] )
        {
            v[n-2]=v[n-1];               
        }
        getmin (v,n-1);
    }

    return v[n-2];       
}
    j'ai vu un exercice fine dans l'examen de c, et j'ai essayé de le résoudre de cette façon. Je sais que je suis à 1 an de retard pour cette discussion, mais peut-être que je pourrais utiles ci-après pour les visiteurs.

    OriginalL'auteur Diti Ymeri