Inverser un tableau sans utiliser l'itération

Question

Une question m'a été posée aujourd'hui et je ne crois pas que ce soit possible, mais je peux me tromper ou j'y pense trop. Comment inverser un tableau sans utiliser l'itération en C ?

Je pense que c'est impossible parce que le tableau peut avoir n'importe quelle taille et qu'aucun programme C ne peut être exprimé avec ce genre de support en tête sans utiliser une forme d'itération.

Answer 1

La réponse à votre question est la suivante, oui, il est possible d'inverser un tableau sans itération . La formulation de la question elle-même peut être ambiguë, cependant, l'esprit de la question est évident : un algorithme récursif peut être utilisé ; et il n'y a aucune ambiguïté quant à la signification de l'expression récursif dans ce sens.

Si, dans le cadre d'un entretien avec une entreprise de premier plan, cette question vous était posée, le pseudo-code suivant suffirait à démontrer que vous êtes une personne compétente. vraiment compris ce que signifie la récursion :

function reverse(array)

    if (length(array) < 2) then
        return array

    left_half = reverse(array[0 .. (n/2)-1])
    right_half = reverse(array[(n/2) .. (n-1)])

    return right_half + left_half

end

Par exemple, si nous avons un tableau de 16 éléments contenant les 16 premières lettres de l'alphabet latin, [A] [P], l'algorithme inverse ci-dessus pourrait être visualisé comme suit :

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Recurse
2.        ABCDEFGH                IJKLMNOP           Recurse
3.    ABCD        EFGH        IJKL        MNOP       Recurse
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Recurse

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Reverse
7.    DCBA        HGFE        LKJI        PONM       Reverse
8.        HGFEDCBA                PONMLKJI           Reverse
9.                PONMLKJIHGFEDCBA                   Reverse

                  Reversed Output

Tout problème résolu à l'aide d'un algorithme récursif suit la méthode Diviser pour mieux régner paradigme, à savoir que :

1. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant plus petit que le problème original, mais pouvant être résolu de manière similaire ( Diviser ).

2. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant indépendant et pouvant être résolu soit de manière récursive, soit de manière simple si la taille est suffisamment petite ( Conquérir ).

3. Le problème est divisé en [deux ou plusieurs] sous-problèmes dont les résultats sont combinés pour donner la solution du problème initial (voir l'annexe 1). Combinez ).

Le pseudo-code ci-dessus pour inverser un tableau répond strictement aux critères ci-dessus. Ainsi, il peut être considéré comme un algorithme récursif et nous pouvons affirmer sans aucun doute que l'inversion d'un tableau peut être effectuée sans utiliser l'itération.

---

DE L'INFORMATION DE FOND SUPPLÉMENTAIRE
La différence entre itération, implémentations récursives et algorithmes récursifs.

On croit souvent à tort qu'une mise en œuvre récursive signifie qu'un algorithme est récursif. Ils ne sont pas équivalents. Voici une explication définitive de la raison, y compris une explication détaillée de la solution ci-dessus.

---

Que sont l'itération et la récursion ?

En 1990, trois des spécialistes les plus respectés de l'analyse des algorithmes modernes dans le domaine de l'informatique, Thomas H. Cormen , Charles E. Leiserson et Ronald L. Rivest ont sorti leur très acclamé Introduction aux algorithmes . Dans ce livre, qui représentait la réunion de plus de 200 textes respectés dans leur propre droit, et qui a été utilisé pendant plus de 20 ans comme premier et seul texte pour l'enseignement des algorithmes dans la plupart des universités de premier plan dans le monde, MM. Cormen, Leiserson et Rivest ont été explicites quant à ce qui constitue Iterating et ce qui constitue Récidive .

Dans leur analyse et leur comparaison de deux algorithmes de tri classiques, Tri par insertion et Fusionner le tri ils expliquent les propriétés fondamentales des algorithmes itératifs et récursifs (parfois appelés incrémentiel algorithmes pour désambiguïser quand la notion mathématique classique de itération est utilisé dans le même contexte).

Tout d'abord, le tri par insertion est classé comme un algorithme itératif, son comportement étant résumé comme suit :

Après avoir trié le sous tableau A[1 j -1], nous insérons l'élément unique A[ j ] à sa place, ce qui donne le tableau trié A[1 j ].

Source : Introduction aux algorithmes - Cormen, Leisersen, Rivest, 1990 MIT Press

Cette déclaration classe un algorithme itératif comme un algorithme qui s'appuie sur le résultat ou l'état d'une exécution ("itération") précédente de l'algorithme, et que ces résultats ou informations d'état sont ensuite utilisés pour résoudre le problème de l'itération actuelle.

Le tri par fusion, quant à lui, est classé comme un algorithme récursif. Un algorithme récursif se conforme à un paradigme de traitement appelé Diviser pour mieux régner qui est un ensemble de trois critères fondamentaux qui différencient le fonctionnement des algorithmes récursifs des algorithmes non récursifs. Un algorithme peut être considéré comme récursif si, au cours du traitement d'un problème donné :

1. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant plus petit que le problème original, mais pouvant être résolu de manière similaire ( Diviser ).

2. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème pouvant être résolu soit de manière récursive, soit de manière simple s'il est suffisamment petit ( Conquérir ).

3. Le problème est divisé en [deux ou plusieurs] sous-problèmes dont les résultats sont combinés pour donner la solution du problème initial (voir l'annexe 1). Combinez ).

Référence : Introduction aux algorithmes - Cormen, Leisersen, Rivest, 1990 MIT Press

Les algorithmes itératifs et les algorithmes récursifs poursuivent leur travail jusqu'à ce qu'une condition de terminaison a été atteint. La condition de fin dans le tri par insertion est que l'élément j Le troisième élément a été correctement placé dans le tableau A[1 j ]. La condition de terminaison d'un algorithme de type Diviser et Conquérir est le moment où le critère 2 du paradigme "culmine", c'est-à-dire que la taille d'un sous-problème atteint une taille suffisamment petite pour qu'il puisse être résolu sans autre sous-division.

Il est important de noter que le paradigme "diviser pour régner" exige que les sous-problèmes soient résolubles de manière similaire au problème original pour permettre la récursion. Comme le problème original est un problème autonome, sans dépendances extérieures, il s'ensuit que les sous-problèmes doivent également être solubles comme s'ils étaient des problèmes autonomes sans dépendances extérieures, notamment sur d'autres sous-problèmes . Cela signifie que les sous-problèmes dans les algorithmes de type Diviser et Conquérir devraient être naturellement indépendant .

Inversement, il est tout aussi important de noter que les entrées des algorithmes itératifs sont basées sur les itérations précédentes de l'algorithme, et doivent donc être considérées et traitées dans l'ordre. Cela crée des dépendances entre les itérations qui empêchent l'algorithme de diviser le problème en sous-problèmes pouvant être résolus de manière récursive. Dans le tri par insertion, par exemple, vous ne pouvez pas diviser les éléments A[1 . j ] en deux sous-ensembles tels que la position triée dans le tableau de A[ j ] est décidé avant tous les éléments A[1.. j -1] ont été placés, car la position propre réelle de A[ j ] peut se déplacer tandis que n'importe lequel de A[1.. j -1] sont eux-mêmes placés.

Algorithmes récursifs et implémentations récursives

L'incompréhension générale du terme récursion vient du fait qu'il y a une supposition commune et erronée qu'une récursive mise en œuvre pour une certaine tâche signifie automatiquement que le problème a été résolu avec une récursive algorithme . Récursif algorithmes ne sont pas les mêmes que les récursives mises en œuvre et ne l'ont jamais été.

Une mise en œuvre récursive implique une fonction, ou un groupe de fonctions, qui s'appellent éventuellement elles-mêmes afin de résoudre une sous-partie de la tâche globale, exactement de la même manière que la tâche globale est résolue. Il arrive que les implémentations récursives algorithmes (c'est-à-dire ceux qui satisfont le paradigme Diviser et Conquérir), se prêtent bien aux implémentations récursives. Cependant, les algorithmes récursifs peuvent être implémentés en utilisant uniquement des constructions itératives telles que for(...) et while(...) car tous les algorithmes, y compris les algorithmes récursifs, finissent par exécuter une tâche de manière répétée afin d'obtenir un résultat.

D'autres contributeurs à ce billet ont parfaitement démontré que les algorithmes itératifs peuvent être mis en œuvre à l'aide d'une fonction récursive. En fait, les implémentations récursives sont possibles pour les fonctions suivantes tout qui consiste à itérer jusqu'à ce qu'une condition de fin soit remplie. Les implémentations récursives où il n'y a pas d'étapes de division ou de combinaison dans le processus sous-jacent de l algorithme sont équivalentes aux implémentations itératives avec une condition de terminaison standard.

En prenant le tri par insertion comme exemple, nous savons déjà (et cela a été prouvé) que le tri par insertion est un algorithme itératif. Cependant, cela n'empêche pas un tri récursif. mise en œuvre de Insertion Sort. En fait, une implémentation récursive peut être créée très facilement comme suit :

function insertionSort(array)

    if (length(array) == 1)
        return array
    end

    itemToSort = array[length(array)]
    array = insertionSort(array[1 .. (length(array)-1)])

    find position of itemToSort in array
    insert itemToSort into array

    return array

end

Comme on peut le voir, l'implémentation est récursive. Cependant, le tri par insertion est un algorithme itératif, ce que nous savons. Alors, comment savoir si, même en utilisant l'implémentation récursive ci-dessus, notre algorithme de tri par insertion n'est pas devenu récursif ? Appliquons les trois critères du paradigme Diviser et Conquérir à notre algorithme et vérifions.

1. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant plus petit que le problème initial, mais pouvant être résolu de manière similaire.

   OUI : A l'exclusion d'un tableau de longueur un, la méthode d'insertion d'un élément A[ j ] à sa place dans le tableau est identique à la méthode utilisée pour insérer tous les éléments précédents A[1 . j -1] dans le tableau.

2. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant indépendant et pouvant être résolu soit de manière récursive, soit de manière simple s'il est suffisamment petit.

   NON : Placement correct de l'article A[ j ] est entièrement dépendant sur le tableau contenant A[1.. j -1] et ces éléments étant triés. Par conséquent, l'élément A [ j (appelé itemToSort ) n'est pas placé dans le tableau avant que le reste du tableau ne soit traité.

3. Le problème est divisé en [deux ou plusieurs] sous-problèmes dont les résultats sont combinés pour donner la solution du problème initial.

   NON : S'agissant d'un algorithme itératif, un seul élément A[ j ] peuvent être placés correctement dans toute itération donnée. L'espace A[1.. j ] n'est pas divisé en sous-problèmes où A[1], A[2]...A[ j ] sont tous correctement placés indépendamment et ensuite tous ces éléments correctement placés sont combinés pour donner le tableau trié.

Il est clair que notre implémentation récursive n'a pas rendu l'algorithme de tri par insertion récursif par nature. En fait, la récursion dans l'implémentation dans ce cas agit comme contrôle du débit ce qui permet à l'itération de se poursuivre jusqu'à ce que la condition de fin soit remplie. Par conséquent, l'utilisation d'une implémentation récursive n'a pas transformé notre algorithme en un algorithme récursif.

Inverser un tableau sans utiliser d'algorithme itératif

Maintenant que nous comprenons ce qui rend un algorithme itératif et ce qui le rend récursif, comment se fait-il que nous puissions inverser un tableau "sans utiliser l'itération" ?

Il existe deux façons d'inverser un tableau. Les deux méthodes nécessitent de connaître à l'avance la longueur du tableau. L'algorithme d'itération est privilégié pour son efficacité et son pseudo-code se présente comme suit :

function reverse(array)

    for each index i = 0 to (length(array) / 2 - 1)
        swap array[i] with array[length(array) - i]
    next

end

Il s'agit d'un algorithme purement itératif. Examinons pourquoi nous pouvons arriver à cette conclusion en la comparant au paradigme "Diviser et Conquérir" qui détermine l'efficacité d'un algorithme. récurrence .

1. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant plus petit que le problème initial, mais pouvant être résolu de manière similaire.

   OUI : L'inversion du tableau est décomposée en sa granularité la plus fine, les éléments, et le traitement de chaque élément est identique à tous les autres éléments traités.

2. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant indépendant et pouvant être résolu soit de manière récursive, soit de manière simple s'il est suffisamment petit.

   OUI : Inversion de l'élément i dans le tableau est possible sans exiger que l'élément (i + 1) (par exemple) a été inversé ou non. En outre, l'inversion de l'élément i dans le tableau ne nécessite pas les résultats des inversions d'autres éléments pour pouvoir être complété.

3. Le problème est divisé en [deux ou plusieurs] sous-problèmes dont les résultats sont combinés pour donner la solution du problème initial.

   NON : S'agissant d'un algorithme itératif, une seule étape de calcul est effectuée à chaque pas de l'algorithme. Il ne divise pas les problèmes en sous-problèmes et il n'y a pas de fusion des résultats de deux ou plusieurs sous-problèmes pour obtenir un résultat.

L'analyse ci-dessus de notre premier algorithme a confirmé qu'il ne correspond pas au paradigme Diviser et Conquérir, et ne peut donc pas être considéré comme un algorithme récursif. Cependant, comme les critères (1) et (2) ont été satisfaits, il est évident qu'un algorithme récursif pourrait être possible.

La clé réside dans le fait que les sous-problèmes de notre solution itérative sont de la plus petite granularité possible (c'est-à-dire des éléments). En divisant le problème en sous-problèmes de plus en plus petits (au lieu de choisir la granularité la plus fine dès le départ), puis en fusionnant les résultats des sous-problèmes, l'algorithme peut être rendu récursif.

Par exemple, si nous avons un tableau de 16 éléments contenant les 16 premières lettres de l'alphabet latin (A..P), un algorithme récursif se présenterait visuellement comme suit :

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Divide
2.        ABCDEFGH                IJKLMNOP           Divide
3.    ABCD        EFGH        IJKL        MNOP       Divide
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Divide

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Conquer (Reverse) and Merge
7.    DCBA        HGFE        LKJI        PONM       Conquer (Reverse) and Merge
8.        HGFEDCBA                PONMLKJI           Conquer (Reverse) and Merge
9.                PONMLKJIHGFEDCBA                   Conquer (Reverse) and Merge

                  Reversed Output

À partir du niveau supérieur, les 16 éléments sont progressivement décomposés en sous-problèmes plus petits de taille exactement égale (niveaux 1 à 4) jusqu'à ce que nous atteignions la granularité la plus fine du sous-problème ; des tableaux de longueur unitaire en ordre avant (étape 5, éléments individuels). À ce stade, les 16 éléments de notre tableau semblent toujours être en ordre. Cependant, ils sont en même temps également inversés, car un tableau à un seul élément est également un tableau inversé à part entière. Les résultats des tableaux à un seul élément sont ensuite fusionnés pour obtenir huit tableaux inversés de longueur deux (étape 6), puis fusionnés à nouveau pour obtenir quatre tableaux inversés de longueur quatre (étape 7), et ainsi de suite jusqu'à ce que notre tableau d'origine ait été reconstruit en sens inverse (étapes 6 à 9).

Le pseudo-code de l'algorithme récursif pour inverser un tableau se présente comme suit :

function reverse(array)

    /* check terminating condition. all single elements are also reversed
     * arrays of unit length.
     */
    if (length(array) < 2) then
        return array

    /* divide problem in two equal sub-problems. we process the sub-problems
     * in reverse order so that when combined the array has been reversed.
     */
    return reverse(array[(n/2) .. (n-1)]) + reverse(array[0 .. ((n/2)-1)])

end

Comme vous pouvez le voir, l'algorithme décompose le problème en sous-problèmes jusqu'à ce qu'il atteigne la granularité la plus fine du sous-problème qui donne un résultat instantané. Il inverse ensuite les résultats pendant qu'ils sont fusionnés pour obtenir un tableau de résultats inversés. Bien que nous pensions que cet algorithme est récursif, appliquons les trois critères des algorithmes de type Diviser et Conquérir pour le confirmer.

1. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant plus petit que le problème initial, mais pouvant être résolu de manière similaire.

   OUI : L'inversion du tableau au niveau un peut se faire en utilisant exactement le même algorithme qu'aux niveaux 2, 3, 4 ou cinq.

2. Le problème est divisé en [deux ou plusieurs] sous-problèmes, chaque sous-problème étant indépendant et pouvant être résolu soit de manière récursive, soit de manière simple s'il est suffisamment petit.

   OUI : Chaque sous-problème qui n'est pas de longueur unitaire est résolu en divisant le problème en deux sous-réseaux indépendants et en inversant récursivement ces sous-réseaux. Les tableaux de longueur unitaire, les plus petits tableaux possibles, sont eux-mêmes inversés, ce qui fournit une condition de fin et un premier ensemble garanti de résultats combinés.

3. Le problème est divisé en [deux ou plusieurs] sous-problèmes dont les résultats sont combinés pour donner la solution du problème initial.

   OUI : Tous les problèmes des niveaux 6, 7, 8 et 9 ne sont composés que des résultats du niveau immédiatement supérieur ; c'est-à-dire de leurs sous-problèmes. L'inversion du tableau à chaque niveau donne un résultat global inversé.

Comme on peut le constater, notre algorithme récursif a satisfait aux trois critères du paradigme Diviser et Conquérir et peut donc être considéré comme un véritable algorithme récursif. Par conséquent, il Il est possible d'inverser un tableau sans utiliser d'algorithme itératif.

Il est intéressant de noter que notre algorithme itératif original pour l'inversion de tableau peut être mis en œuvre en utilisant une fonction récursive. Le pseudo-code pour une telle implémentation est le suivant :

function reverse(array)

    if length(array) < 2
        return
    end

    swap array[0] and array[n-1]
    reverse(array[1..(n-1)])

end

Cette solution est similaire aux solutions proposées par d'autres posters. Il s'agit d'une méthode récursive mise en œuvre car la fonction définie finit par s'appeler elle-même pour effectuer de manière répétée la même tâche sur tous les éléments du tableau. Cependant, cela fait pas faire le algorithme récursif, car il n'y a pas de division des problèmes en sous-problèmes, et il n'y a pas de fusion des résultats des sous-problèmes pour donner le résultat final. Dans ce cas, la récursion est simplement utilisée comme une construction de contrôle de flux, et d'un point de vue algorithmique, on peut prouver que le résultat global exécute la même séquence d'étapes, dans exactement le même ordre, que l'algorithme itératif original qui a été proposé pour la solution.

C'est la différence entre un Algorithme itératif , a Algorithme récursif et un Mise en œuvre récursive .

Answer 2

Comme les gens l'ont dit dans les commentaires, cela dépend de la définition de l'itération.

Cas 1. L'itération comme style de programmation, différent de la récursion

Si l'on prend la récursion (simplement) comme une alternative à l'itération, alors la solution récursive présentée par Kalai est la bonne réponse.

Cas 2. L'itération comme borne inférieure en temps linéaire

Si l'on considère que l'itération consiste à "examiner chaque élément", la question est alors de savoir si l'inversion de tableau nécessite un temps linéaire ou peut être effectuée en temps sous-linéaire.

Pour montrer qu'il n'existe pas d'algorithme sublinéaire pour l'inversion de tableau, considérons un tableau avec n éléments. Supposons un algorithme A Il existe une méthode d'inversion qui ne nécessite pas de lire chaque élément. Il existe alors un élément a[i] pour certains i sur 0..n-1 que l'algorithme ne lit jamais, mais il est quand même capable d'inverser correctement le tableau. ( EDIT : Nous devons exclure de cette plage l'élément central d'un tableau de longueur impaire -- voir les commentaires ci-dessous -- mais cela n'a pas d'impact sur le fait que l'algorithme soit linéaire ou sous-linéaire dans le cas asymptotique).

Puisque l'algorithme ne lit jamais l'élément a[i] nous pouvons changer sa valeur. Supposons que nous le fassions. L'algorithme, qui n'a jamais lu cette valeur, produira la même réponse pour l'inversion qu'avant que nous ne changions sa valeur. Mais cette réponse ne sera pas correcte pour la nouvelle valeur de a[i] . Il n'existe donc pas d'algorithme d'inversion correct qui ne lise pas au moins tous les éléments du tableau d'entrée (sauf un). Par conséquent, l'inversion de tableau a une borne inférieure de O(n) et donc nécessite itération (selon la définition de travail pour ce scénario).

(Notez que cette preuve ne concerne que l'inversion de tableau et ne s'étend pas aux algorithmes qui ont vraiment des implémentations sublinéaires, comme la recherche binaire et la recherche d'éléments).

Cas 3. L'itération comme construction en boucle

Si l'itération est considérée comme une "boucle jusqu'à ce qu'une condition soit remplie", cela se traduit par du code machine avec des sauts conditionnels, connus pour nécessiter une sérieuse optimisation du compilateur (en tirant parti de la prédiction de branchement, etc.) Dans ce cas, quelqu'un qui demande s'il existe un moyen de faire quelque chose "sans itération" peut avoir en tête déroulement de la boucle (vers le code en ligne droite). Dans ce cas, vous pouvez en principe écrire du code C en ligne droite (sans boucle). Mais cette technique n'est pas générale ; elle ne fonctionne que si vous connaissez la taille du tableau à l'avance. (Désolé d'ajouter ce cas plus ou moins désinvolte à la réponse, mais je l'ai fait par souci d'exhaustivité et parce que j'ai entendu le terme "itération" utilisé de cette façon, et que le déroulement de boucle est une optimisation importante du compilateur).

Answer 3

Utiliser une fonction récursive.

void reverse(int a[],int start,int end)
{
     int temp;
     temp = a[start];
     a[start] = a[end];
     a[end] = temp;

    if(start==end ||start==end-1)
       return;
    reverse(a, start+1, end-1);
}

Il suffit d'appeler la méthode ci-dessus comme reverse(tableau,0,lengthofarray-1)

Answer 4

Implémentez une fonction récursive pour inverser un tableau trié. Par exemple, étant donné le tableau [ 1, 2, 3, 4, 5] votre procédure doit retourner [5, 4, 3, 2, 1].

Answer 5

Voici une solution astucieuse utilisant la récursion dans une fonction javascript. Elle ne nécessite aucun paramètre autre que le tableau lui-même.

/* Use recursion to reverse an array */
function reverse(a){
    if(a.length==undefined || a.length<2){
        return a;
    }
    b=[];
    b.push(reverse(copyChop(a)));
    b.push(a[0]);
    return b;
    /* Return a copy of an array minus the first element */
    function copyChop(a){ 
        b=a.slice(1); 
        return b;
    }
}

Appelez-le comme suit ;

reverse([1,2,3,4]);

Notez que si vous n'utilisez pas la fonction imbriquée copyChop pour effectuer le découpage en tableaux, vous vous retrouvez avec un tableau comme premier élément dans votre résultat final. Je ne sais pas vraiment pourquoi il en est ainsi