Pregunta Impresión de la diferencia de los números adyacentes sin utilizar matriz


Recientemente encontré un rompecabezas en C para escribir un programa para leer un conjunto de números enteros x0, X1, X2, ……. hasta que un -1 se ingresa como entrada ..

Después de leer el -1, el programa debe imprimir la diferencia entre cada número adyacente. Es decir, x1-X0, X2-X1, X3-X2, ...

p.ej: Entrada:
1 2 4 7 11 -1

Salida
1 2 3 4

La salida es el resultado de (2-1), (4-2), (7-4), (11-7)

El problema es que el programa no debería estar utilizando una matriz. Incluso las matrices asignadas dinámicamente no funcionan.

Lo intenté mucho y este es mi lo que he venido con

#include<stdio.h>

int a, b;
int fn()
{
    int r=b-a;
    a=b;
    scanf("%d", &b);
    if(b!=-1)
    {
        printf("%d ", fn());
    }
    return r;
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d ", fn() );
    return 0;
}

El programa anterior usa una función recursiva pero en este método, ya que es como una pila, el valor que se calculó en último lugar se imprime primero en lugar de que el valor que se calculó primero se imprima primero.

Es decir, la salida para la misma entrada que arriba es: 4 3 2 1 en lugar de 1 2 3 4

¿Hay alguna manera de guardar los valores tomados de esta pila de llamadas (corríjame si no estoy usando los términos correctos) y empújelos nuevamente a la pila para que al recuperar el primer valor calculado ahora sea el primero en aparecer?

P.ej: Obtuve los valores 4, 3, 2 y 1 con fn() porque era así en la pila antes 4 fue reventado:

4
3
2
1

Supongamos que saco todos los elementos de la pila y los empujo a otra pila en el orden en que fueron extraídos. Entonces la nueva pila sería

1
2
3
4

(es decir, 4 Se abrió y empujó primero (y por lo tanto terminó en la parte inferior), luego 3 se hizo estallar y empujó y así sucesivamente.)

Si se pudiera hacer esto, podríamos simplemente extraer elementos de la nueva pila y mostrarlos en el orden en el que aparecen.

Nota: la pila a la que me refiero es la pila de llamadas y no una pila creada explícitamente (que probablemente necesitaría una matriz).

O tal vez hay una forma más simple?

EDITAR: Necesito que las fases de entrada y salida estén separadas y no intercaladas. No se debe mostrar ninguna salida antes de que se indique el final de la entrada con la -1.

EDITAR: El programa no puede usar archivos para almacenar la entrada que se leerá más tarde.


5
2017-08-08 01:38


origen


Respuestas:


¿Hay alguna manera de guardar los valores tomados de esta pila de llamadas ... y empujarlos nuevamente a la pila para que al recuperar el primer valor calculado ahora sea el primero en aparecer?

Recuenta cada vez que se lee un número (excepto -1).

Crear una lista enlazada compuesta de variables en la recursión anterior.

No se utilizan matrices a excepción de printf() formato.

Un poco más de trabajo necesario para evitar un espacio después de la última impresión. int.

#include<stdio.h>
#include<stdlib.h>

typedef struct list {
  const struct list *prev;
  int i;
} list;

void print_list(const list *previous) {
  if (previous && previous->prev) {
    print_list(previous->prev);
    printf("%d ", previous->i - previous->prev->i);
  }
}

void JSfoo(const list *previous) {
  list node = { previous, 0 };
  int cnt = scanf("%d", &node.i);
  if (cnt == 1 && node.i != -1) {
    JSfoo(&node);
  } else {
    print_list(previous);
    puts("");
  }
}

int main(void) {
  JSfoo(NULL);
  return 0;
}

Salida (no intercalada)

1 2 4 7 11 -1
1 2 3 4 

Una alternativa mantendría una cola para negar la necesidad de imprimir recursivamente. Mismo resultado.

El siguiente utiliza una cola circular. Solo aviso 1 next puntero necesario. El identificador de cola solo debe apuntar al final de la cola. No hay necesidad de punteros a la cabeza y cola. La inserción es O(1).

#include<stdio.h>
#include<stdlib.h>

typedef struct que {
  struct que *next;
  int i;
} que;

// Pass in the tail of the queue and return the updated tail
// `tail` points to the head.  (Circular queue)
que *que_append(que *tail, que *node) {
  if (tail) {
    node->next = tail->next;
    tail->next = node;
  } else {
    node->next = node;
  }
  return node;
}

void JSfoo(que *tail) {
  que node;
  int cnt = scanf("%d", &node.i);
  if (cnt == 1 && node.i != -1) {
    tail = que_append(tail, &node);
    JSfoo(tail);
  } else if (tail) {
    que *head = tail->next;
    while (head != tail) {
      printf("%d ", head->next->i - head->i);
      head = head->next;
    }
    puts("");
  }
}

4
2017-08-08 18:05



¿Espera que el programa deje de tomar más caracteres de entrada del usuario inmediatamente después de ingresar "-1" y siga con la impresión de la diferencia?

Si no es así, es decir, si permite que el usuario ingrese más caracteres después de "-1", su programa lo ignorará hasta que se ingrese una nueva línea, y en ese punto, su programa puede imprimir la secuencia de diferencias. A continuación, puede utilizar el siguiente fragmento de código:

unsigned int x, y;
while( scanf("%d",&x)==1 && x != -1 && scanf("%d",&y)==1 && y != -1 )
    printf("%d ",y-x);
printf("\n");

EDITAR: gracias a @ JoëlHecht por señalar el error en el código anterior, leí mal la especificación de salida deseada, el siguiente código debería solucionarlo:

int x, y = -1;
while( scanf("%d",&x)==1 && x != -1 ) {
    if( y != -1 ) printf("%d ",x-y);
    y = x;
}
printf("\n");

2
2017-08-08 04:48



Este es un problema clásico que requiere una función recursiva. Una función recursiva (1) toma un valor y proporciona una prueba para un condición de salida romper la recursion; (2) preforma alguna operación sobre datos; entonces (3) vuelve a llamarse (hace una llamada recursiva) haciendo que el proceso se repita.

En su caso, el valor que necesita la función recursiva es (1) el previamente leído entero y luego leerá un current valor de stdin (validando y manejando cualquier error) y probar si current es  -1 Para el condición de salida. La función debe entonces (2) imprimir la diferencia entre current y previous. Entonces necesita (3) pasar el current valor como un argumento a la función recursiva, llamándose de nuevo hasta que se cumpla la condición de salida.

Poniendo esas piezas juntas, puedes hacer algo similar a lo siguiente difference() función:

#include <stdio.h>
#include <stdlib.h>  /* for EXIT_FAILURE */

/* recursive function taking previous read value as input */
void difference (int prev)
{
    int current;                /* variable to hold current value */

    if (scanf ("%d", &current) != 1) {  /* read / validate input */
        fprintf (stderr, "error: invalid input.\n");
        exit (EXIT_FAILURE);
    }

    if (current == -1)               /* recusion exit condition */
        return;

    printf (" %d", current - prev);         /* print difference */

    difference (current);     /* recursive call passing current */
}

int main (void) {

    int n;                          /* variable for first value */

    if (scanf ("%d", &n) != 1) {    /* read / validate input */
        fprintf (stderr, "error: invalid input.\n");
        exit (EXIT_FAILURE);
    }

    if (n == -1)                    /* verify not -1 */
        return 0;

    difference (n);     /* recursive call passing first value */

    putchar ('\n');     /* tidy up */

    return 0;
}

Ejemplo de uso / salida

$ ./bin/diffints
1 2 4 7 11 -1
 1 2 3 4

Usando una función de ayuda para iniciar la recursión

Si quisieras poner en orden las cosas main() un poco más, podrías crear un función de ayuda Eso leería el primer valor y comenzaría la recursión. Eso te dejaría nada más que una sola llamada a la función de ayuda en main(). Esto no cambia el funcionamiento del programa en absoluto. En lugar de llamar y validar la devolución de scanf y haciendo la primera llamada a difference en main(), esas tareas simplemente se mueven a una nueva función llamada diffcheck() que luego llama difference() para iniciar la recursion. Depende de ti.

#include <stdio.h>
#include <stdlib.h>  /* for EXIT_FAILURE */

/* recursive function taking previous read value as input */
void difference (int prev)
{
    int current;                /* variable to hold current value */

    if (scanf ("%d", &current) != 1) {  /* read / validate input */
        fprintf (stderr, "error: invalid input.\n");
        exit (EXIT_FAILURE);
    }

    if (current == -1)               /* recusion exit condition */
        return;

    printf (" %d", current - prev);         /* print difference */

    difference (current);     /* recursive call passing current */
}

/* helper function to read 1st value and call difference */
void diffcheck (void)
{
    int n;                          /* variable for first value */

    if (scanf ("%d", &n) != 1) {    /* read / validate input */
        fprintf (stderr, "error: invalid input.\n");
        exit (EXIT_FAILURE);
    }

    if (n == -1)                    /* verify not -1 */
        return;

    difference (n);     /* recursive call passing first value */

    putchar ('\n');     /* tidy up */
}

int main (void) {

    diffcheck();
    return 0;
}

Nota: cómo main() se reduce a una sola llamada a diffcheck() que es mucho más limpio que repetir la lectura / validación y la primera verificación en todos los lugares donde desee llamar al difference Funciona a lo largo de tu código.

Mirar las cosas, pensar a través de la operación de la función recursiva para difference(), y avísame si tienes más preguntas.


1
2017-08-08 06:59



El programa sera

#include <stdio.h>

int main()
{
   unsigned int x, y;

   if(!(scanf("%d",&x)==1 && x != -1))
      return 0;

   while(scanf("%d",&y)==1 && y != -1 )
   {
        printf("%d ",y-x);
        x = y;
   }
   printf("\n");
} 

0
2017-08-08 05:24



Esto es lo que se me ocurrió:

#include <stdio.h>

int a, b;
void fn()
{
    int r=b-a;
    a=b;

    scanf("%d", &b);
    printf("%d ", r);

    if(b!=-1)
        fn();
}

int main()
{
    scanf("%d%d", &a, &b);
    fn();
    printf("\n");
    return 0;
}

-1
2017-08-08 01:52