c - por - matriz inversa y transpuesta

Invertir una matriz sin usar la iteración

Question

Hoy se me hizo una pregunta y no creo que sea posible, pero podría equivocarme o pensarlo demasiado. ¿Cómo se puede invertir una matriz sin usar la iteración en C?

Mi pensamiento es que es imposible debido al hecho de que la matriz puede ser de cualquier tamaño y que ningún programa C se puede expresar con ese tipo de soporte en mente sin usar alguna forma de iteración.

Answer 1

Aquí hay una solución ordenada que usa recursividad en una función de JavaScript. No requiere ningún parámetro que no sea la matriz en sí.

/* 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;
    }
}

Llámalo de la siguiente manera;

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

Tenga en cuenta que si no utiliza la función anidada copyChop para hacer el corte de la matriz, terminará con una matriz como primer elemento en su resultado final. No estoy seguro de por qué esto debería ser tan

Answer 2

Como han dicho las personas en los comentarios, depende de la definición de iteración.

Caso 1. Iteración como un estilo de programación, diferente de la recursión

Si uno toma recursion (simplemente) como una alternativa a la iteración, entonces la solución recursiva presentada por Kalai es la respuesta correcta.

Caso 2. Iteración como tiempo lineal límite inferior

Si uno toma la iteración como "examinar cada elemento", entonces la pregunta es si la inversión de la matriz requiere tiempo lineal o si puede hacerse en tiempo sublineal.

Para mostrar que no hay un algoritmo sublineal para la inversión de la matriz, considere una matriz con n elementos. Supongamos que existe un algoritmo A para inversión que no necesita leer cada elemento. Luego existe un elemento a[i] para algo i en 0..n-1 que el algoritmo nunca lee, pero que aún puede revertir correctamente la matriz. ( EDITAR : debemos excluir el elemento medio de una matriz de longitud impar; ver los comentarios debajo de este rango, ver los comentarios a continuación), pero esto no afecta si el algoritmo es lineal o sublineal en el caso asintótico.

Como el algoritmo nunca lee el elemento a[i] , podemos cambiar su valor. Digamos que hacemos esto Entonces, el algoritmo, que nunca ha leído este valor, producirá la misma respuesta para la inversión que antes de que cambiemos su valor. Pero esta respuesta no será correcta para el nuevo valor de a[i] . Por lo tanto, no existe un algoritmo de inversión correcto que no lea al menos cada elemento de matriz de entrada (guardar uno). Por lo tanto, la inversión de matriz tiene un límite inferior de O (n) y, por lo tanto, requiere iteración (de acuerdo con la definición de trabajo para este escenario).

(Tenga en cuenta que esta prueba es solo para la inversión de matriz y no se extiende a algoritmos que realmente tienen implementaciones sublineales, como la búsqueda binaria y la búsqueda de elementos).

Caso 3. Iteración como una construcción de bucle

Si la iteración se toma como "bucle hasta que se cumpla una condición", esto se traduce en código máquina con saltos condicionales, que se sabe que requieren una optimización seria del compilador (aprovechando la predicción de bifurcación, etc.) En este caso, alguien pregunta si hay una La forma de hacer algo "sin iteración" puede tener en mente el desenrollamiento del bucle (al código de línea recta). En este caso, en principio puede escribir código C en línea recta (sin bucle). Pero esta técnica no es general; solo funciona si conoce el tamaño de la matriz de antemano. (Perdón por agregar este caso más o menos frívolo a la respuesta, pero lo hice para completarlo y porque he escuchado el término "iteración" utilizado de esta manera, y el desenrollado del bucle es una optimización importante del compilador).

Answer 3

Implemente una función recursiva para invertir una matriz ordenada. Es decir, dado el conjunto [1, 2, 3, 4, 5] su procedimiento debería devolver [5, 4, 3, 2, 1].

Answer 4

La respuesta a su pregunta es que, sí, es posible invertir una matriz sin iteración . La redacción de la pregunta misma puede ser ambigua, sin embargo, el espíritu de la pregunta es obvio: se puede usar un algoritmo recursivo; y no hay ambigüedad en absoluto en cuanto al significado de recursivo en este sentido.

Si, en una situación de entrevista con una empresa de alto vuelo, se le hizo esta pregunta, entonces el siguiente pseudocódigo sería suficiente para demostrar que realmente entendió lo que se entiende por recursión:

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

Por ejemplo, si tenemos una matriz de 16 elementos que contienen las primeras 16 letras del alfabeto latino, [A] .. [P], el algoritmo inverso anterior podría visualizarse de la siguiente manera:

                   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

Cualquier problema que se resuelva con un algoritmo recursivo sigue el paradigma Dividir y Conquistar , a saber que:

1. El problema se divide en [dos o más] subproblemas en los que cada subproblema es más pequeño que, pero puede resolverse de manera similar al problema original ( Dividir ).

2. El problema se divide en [dos o más] subproblemas en los que cada subproblema es independiente y puede resolverse recursivamente o de manera directa si es lo suficientemente pequeño ( Conquista ).

3. El problema se divide en [dos o más] subproblemas donde los resultados de esos sub-problemas se combinan para dar la solución al problema original ( Combinar ).

El pseudo-código anterior para invertir una matriz cumple estrictamente los criterios anteriores. Por lo tanto, se puede considerar un algoritmo recursivo y podemos afirmar sin ninguna duda que se puede revertir una matriz sin usar la iteración.

INFORMACIÓN ADICIONAL DE ANTECEDENTES
La diferencia entre iteración, implementaciones recursivas y algoritmos recursivos

Es un malentendido común que una implementación recursiva significa que un algoritmo es recursivo. Ellos no son equivalentes. Aquí hay una explicación definitiva de por qué, incluida una explicación detallada de la solución anterior.

¿Qué son la iteración y la recursión?

En 1990, tres de los eruditos más respetados del análisis de algoritmos modernos en el campo de la informática, Thomas H. Cormen , Charles E. Leiserson y Ronald L. Rivest , lanzaron su muy aclamada Introducción a los algoritmos . En este libro, que representa la reunión de más de 200 textos respetados por derecho propio, y que durante más de 20 años se ha utilizado como el primer y único texto para la enseñanza de algoritmos en la mayoría de las universidades de primer nivel en todo el mundo, Mssrs . Cormen, Leiserson y Rivest fueron explícitos sobre lo que constituye iteración y lo que constituye recurrencia .

En su análisis y comparación de dos algoritmos clasificadores clásicos, Insertion Sort y Merge Sort , explican las propiedades fundamentales de los algoritmos iterativos y recursivos (a veces denominados algoritmos incrementales para desambiguar cuando se usa la noción matemática clásica de iteration en el mismo contexto).

En primer lugar, Insertion Sort se clasifica como un algoritmo iterativo, con su comportamiento resumido de la siguiente manera:

Después de haber ordenado el subcampo A [1 .. j -1], insertamos el elemento A [ j ] en su lugar adecuado, produciendo el arreglo ordenado A [1 .. j ].

Fuente: Introducción a los algoritmos - Cormen, Leisersen, Rivest, 1990 MIT Press

Esta declaración clasifica un algoritmo iterativo como uno que se basa en el resultado o el estado de una ejecución previa ("iteración") del algoritmo, y que dichos resultados o información de estado se usan para resolver el problema de la iteración actual.

Merge Sort, por otro lado, se clasifica como un algoritmo recursivo. Un algoritmo recursivo se ajusta a un paradigma de procesamiento llamado Divide and Conquer, que es un conjunto de tres criterios fundamentales que diferencian el funcionamiento de los algoritmos recursivos de los algoritmos no recursivos. Un algoritmo puede considerarse recursivo si, durante el procesamiento de un problema determinado:

1. El problema se divide en [dos o más] subproblemas en los que cada subproblema es más pequeño que, pero puede resolverse de manera similar al problema original ( Dividir ).

2. El problema se divide en [dos o más] subproblemas en los que cada subproblema se puede resolver recursivamente o de manera directa si es lo suficientemente pequeño ( Conquer ).

3. El problema se divide en [dos o más] subproblemas donde los resultados de esos sub-problemas se combinan para dar la solución al problema original ( Combinar ).

Referencia: Introducción a los algoritmos - Cormen, Leisersen, Rivest, 1990 MIT Press

Tanto los algoritmos iterativos como los algoritmos recursivos continúan su trabajo hasta que se alcanza una condición de terminación . La condición de terminación en Insertion Sort es que el j ''ésimo elemento se ha colocado correctamente en la matriz A [1 .. j ]. La condición de terminación en un algoritmo Dividir y Conquistar es cuando el Criterio 2 del paradigma "toca fondo", es decir, el tamaño de un sub-problema alcanza un tamaño lo suficientemente pequeño como para poder ser resuelto sin una subdivisión adicional.

Es importante tener en cuenta que el paradigma Dividir y Conquistar requiere que los sub-problemas se puedan resolver de manera similar al problema original para permitir la recursión. Como el problema original es un problema independiente, sin dependencias externas, se deduce que los sub-problemas también deben poder resolverse como si fueran problemas independientes sin dependencias externas, particularmente en otros sub-problemas . Esto significa que los sub-problemas en los algoritmos de Divide y Conquista deben ser naturalmente independientes .

Por el contrario, es igualmente importante tener en cuenta que la entrada a algoritmos iterativos se basa en iteraciones previas del algoritmo, por lo que debe considerarse y procesarse en orden. Esto crea dependencias entre iteraciones que evitan que el algoritmo divida el problema en subproblemas que pueden resolverse recursivamente. En Insertion Sort, por ejemplo, no puede dividir los elementos A [1 .. j ] en dos subconjuntos de modo que la posición ordenada en la matriz de A [ j ] se decida antes que todos los elementos A [1 .. j -1 ] se han colocado, ya que la posición real real de A [ j ] puede moverse mientras cualquiera de A [1 .. j -1] se está colocando.

Algoritmos Recursivos vs. Implementaciones Recursivas

El malentendido general del término recursión proviene del hecho de que existe una suposición común y errónea de que una implementación recursiva para alguna tarea significa automáticamente que el problema ha sido resuelto con un algoritmo recursivo. Los algoritmos recursivos no son lo mismo que las implementaciones recursivas y nunca lo han sido.

Una implementación recursiva implica una función, o grupo de funciones, que eventualmente se llaman a sí mismas para resolver una sub-porción de la tarea global exactamente de la misma manera que la tarea general se está resolviendo. Ocurre que los algoritmos recursivos (es decir, aquellos que satisfacen el paradigma Dividir y Conquistar), se prestan bien a las implementaciones recursivas. Sin embargo, los algoritmos recursivos se pueden implementar usando solo construcciones iterativas como for(...) y while(...) ya que todos los algoritmos, incluidos los algoritmos recursivos, terminan realizando alguna tarea repetidamente para obtener un resultado.

Otros colaboradores de esta publicación han demostrado perfectamente que los algoritmos iterativos se pueden implementar usando una función recursiva. De hecho, las implementaciones recursivas son posibles para todo lo que implica iterar hasta que se cumpla alguna condición de terminación. Las implementaciones recursivas donde no hay pasos de división o combinación en el algoritmo subyacente son equivalentes a las implementaciones iterativas con una condición de terminación estándar.

Tomando Insertion Sort como ejemplo, ya sabemos (y se ha demostrado) que Insertion Sort es un algoritmo iterativo. Sin embargo, esto no impide una implementación recursiva de Insertion Sort. De hecho, una implementación recursiva se puede crear muy fácilmente de la siguiente manera:

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

Como se puede ver, la implementación es recursiva. Sin embargo, Insertion Sort es un algoritmo iterativo y esto lo sabemos. Entonces, ¿cómo sabemos que incluso utilizando la implementación recursiva anterior nuestro algoritmo de ordenación de inserción no se ha vuelto recursivo? Vamos a aplicar los tres criterios del paradigma Dividir y Conquistar a nuestro algoritmo y verificarlo.

1. El problema se divide en [dos o más] subproblemas en los que cada subproblema es más pequeño que, pero puede resolverse de manera similar al problema original.

   SÍ : excluyendo una matriz de longitud uno, el método para insertar un elemento A [ j ] en su lugar apropiado en la matriz es idéntico al método utilizado para insertar todos los elementos anteriores A [1 .. j -1] en la matriz.

2. El problema se divide en [dos o más] subproblemas en los que cada subproblema es independiente y puede resolverse recursivamente o de manera directa si es lo suficientemente pequeño.

   NO : la colocación correcta del elemento A [ j ] depende por completo de la matriz que contiene los elementos A [1 .. j -1] y de los elementos que se ordenan. Por lo tanto, el elemento A [ j ] (llamado itemToSort ) no se coloca en la matriz antes de que se procese el resto de la matriz.

3. El problema se divide en [dos o más] sub-problemas donde los resultados de esos sub-problemas se combinan para dar la solución al problema original.

   NO : Siendo un algoritmo iterativo, solo un elemento A [ j ] se puede colocar correctamente en cualquier iteración dada. El espacio A [1 .. j ] no se divide en subproblemas donde A [1], A [2] ... A [ j ] se colocan de forma independiente y luego todos estos elementos correctamente colocados se combinan para dar el orden formación.

Claramente, nuestra implementación recursiva no ha hecho que el algoritmo de ordenación de inserción sea recursivo en la naturaleza. De hecho, la recursión en la implementación en este caso actúa como control de flujo , permitiendo que la iteración continúe hasta que se cumpla la condición de terminación. Por lo tanto, el uso de una implementación recursiva no cambió nuestro algoritmo en un algoritmo recursivo.

Invertir una matriz sin usar un algoritmo iterativo

Entonces, ahora que entendemos qué hace que un algoritmo sea iterativo, y lo que lo hace recursivo, ¿cómo es que podemos invertir una matriz "sin usar iteración"?

Hay dos formas de invertir una matriz. Ambos métodos requieren que conozca la longitud de la matriz por adelantado. El algoritmo de iteración se ve favorecido por su eficacia y su pseudocódigo se ve de la siguiente manera:

function reverse(array)

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

end

Este es un algoritmo puramente iterativo. Examinemos por qué podemos llegar a esta conclusión comparándola con el paradigma Dividir y Conquistar que determina la recursividad de un algoritmo.

1. El problema se divide en [dos o más] subproblemas en los que cada subproblema es más pequeño que, pero puede resolverse de manera similar al problema original.

   SÍ : la inversión de la matriz se divide en su granularidad más fina, los elementos y el procesamiento para cada elemento es idéntico a todos los demás elementos procesados.

2. El problema se divide en [dos o más] subproblemas en los que cada subproblema es independiente y puede resolverse recursivamente o de manera directa si es lo suficientemente pequeño.

   SÍ : la reversión del elemento i en la matriz es posible sin requerir que el elemento (i + 1) (por ejemplo) se haya invertido o no. Además, la inversión del elemento i en la matriz no requiere los resultados de otras inversiones de elementos para poder completar.

3. El problema se divide en [dos o más] sub-problemas donde los resultados de esos sub-problemas se combinan para dar la solución al problema original.

   NO : al ser un algoritmo iterativo, solo se realiza una etapa de cálculo en cada paso del algoritmo. No divide los problemas en subproblemas y no se fusionan los resultados de dos o más subproblemas para obtener un resultado.

Los analsys anteriores de nuestro primer algoritmo confirmaron que no se ajusta al paradigma Divide and Conquer, y por lo tanto no se puede considerar como un algoritmo recursivo. Sin embargo, como se cumplieron los criterios (1) y los criterios (2), es evidente que podría ser posible un algoritmo recursivo.

La clave está en el hecho de que los sub-problemas en nuestra solución iterativa son de la menor granularidad posible (es decir, elementos). Al dividir el problema en sub-problemas sucesivamente más pequeños y más pequeños (en lugar de ir por la granularidad más fina desde el principio), y luego fusionar los resultados de los sub-problemas, el algoritmo puede hacerse recursivo.

Por ejemplo, si tenemos una matriz de 16 elementos que contienen las primeras 16 letras del alfabeto latino (A..P), un algoritmo recursivo tendría el siguiente aspecto visual:

                   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

Desde el nivel superior, los 16 elementos se dividen progresivamente en tamaños de subproblemas más pequeños de exactamente el mismo tamaño (niveles 1 a 4) hasta que alcanzamos la granularidad más fina del subproblema; matrices de longitud de unidad en orden directo (paso 5, elementos individuales). En este punto, nuestros 16 elementos de matriz todavía parecen estar en orden. Sin embargo, al mismo tiempo también se invierten, ya que una matriz de elemento único también es una matriz invertida por derecho propio. Los resultados de las matrices de un solo elemento se combinan para obtener ocho matrices invertidas de longitud dos (paso 6), luego se fusionan nuevamente para obtener cuatro matrices invertidas de longitud cuatro (paso 7), y así sucesivamente hasta que nuestra matriz original haya sido reconstruida en reversa (pasos 6 a 9).

El pseudocódigo para el algoritmo recursivo para invertir una matriz se ve de la siguiente manera:

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

Como puede ver, el algoritmo divide el problema en sub-problemas hasta que alcanza la granularidad más fina del sub-problema que da un resultado instantáneo. A continuación, invierte los resultados mientras se combinan para dar una matriz de resultados invertidos. Aunque creemos que este algoritmo es recursivo, apliquemos los tres criterios para los algoritmos de Dividir y Conquistar para confirmar.

1. El problema se divide en [dos o más] subproblemas en los que cada subproblema es más pequeño que, pero puede resolverse de manera similar al problema original.

   SÍ : puede revertir la matriz en el nivel uno usando exactamente el mismo algoritmo que en los niveles 2, 3, 4 o cinco.

2. El problema se divide en [dos o más] subproblemas en los que cada subproblema es independiente y puede resolverse recursivamente o de manera directa si es lo suficientemente pequeño.

   SÍ : cada sub-problema que no sea de longitud unitaria se resuelve al dividir el problema en dos sub-arrays independientes y reversar recursivamente esas sub-matrices. Las matrices de longitud de unidad, las matrices más pequeñas posibles, se invierten por sí mismas, lo que proporciona una condición de terminación y un primer conjunto garantizado de resultados combinados.

3. El problema se divide en [dos o más] sub-problemas donde los resultados de esos sub-problemas se combinan para dar la solución al problema original.

   SÍ : todos los problemas en los niveles 6, 7, 8 y 9 están compuestos únicamente por resultados del nivel inmediatamente anterior; es decir, de sus sub-problemas. La inversión de la matriz en cada nivel da como resultado un resultado invertido en general.

Como se puede ver, nuestro algoritmo recursivo pasó los tres criterios para el paradigma Dividir y Conquistar y, por lo tanto, puede considerarse un algoritmo verdaderamente recursivo. Por lo tanto, es posible invertir una matriz sin usar un algoritmo iterativo.

Es interesante observar que nuestro algoritmo iterativo original para la inversión de matriz se puede implementar usando una función recursiva. El pseudo código para tal implementación es el siguiente:

function reverse(array)

    if length(array) < 2
        return
    end

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

end

Esto es similar a las soluciones propuestas por otros carteles. Esta es una implementación recursiva ya que la función definida finalmente se llama a sí misma para realizar repetidamente la misma tarea sobre todos los elementos en la matriz. Sin embargo, esto no hace que el algoritmo sea recursivo, ya que no hay una división de los problemas en subproblemas, y no hay una fusión de los resultados de los subproblemas para dar el resultado final. En este caso, la recursión se está utilizando simplemente como una construcción de control de flujo, y algorítmicamente se puede probar que el resultado general está realizando la misma secuencia de pasos, exactamente en el mismo orden, que el algoritmo iterativo original que se propuso para el solución.

Esa es la diferencia entre un algoritmo iterativo , un algoritmo recursivo y una implementación recursiva .

Answer 5

Use la función recursiva.

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);
}

Simplemente llame al método anterior como inverso (array, 0, lengthofarray-1)

Answer 6

   #include<stdio.h>


   void rev(int *a,int i,int n)
  {

if(i<n/2)
{
    int temp = a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=temp;
    rev(a,++i,n);
 }
}
int main()
    {
    int array[] = {3,2,4,5,6,7,8};
   int len = (sizeof(array)/sizeof(int));
   rev(array,0,len);    
   for(int i=0;i<len;i++)
   {
    printf("/n array[%d]->%d",i,array[i]);
  }
}