Gli esercizi

Testi e soluzioni di alcuni esercizi

Inserimento nella sequenza ordinata

/*
**  inserimento.c
**
**  Leggere in input una sequenza di n numeri interi e memorizzarla
**  in un array A. Si supponga che la sequenza letta in input sia
**  gia' ordinata in ordine crescente. Generare in modo casuale una
**  seconda sequenza di m numeri interi ed inserire gli elementi
**  generati nella posizione corretta nell'array A in modo che A
**  continui ad essere ordinato, eventualmente spostando in avanti
**  gli elementi gia' presenti per fare posto ai nuovi elementi da
**  inserire. Stampare in output l'array A.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Aprile 2001
*/

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

#define MAX 100

/*
 *  Legge in input un vettore di interi. Restituisce il numero di
 *  elementi letti.
 */

int leggi_array(int V[]) {
  int i, n;

  printf("Numero di elementi: ");
  scanf("%d", &n);
  for (i=0; i<n; i++)
    scanf("%d", &V[i]);
  return(n);
}

/*
 *  Genera in modo casuale un vettore di interi. Restituisce il numero
 *  di elementi prodotti.
 */

int genera_array(int V[]) {
  int i, n;

  printf("Numero di elementi: ");
  scanf("%d", &n);
  srand((unsigned)time(NULL));
  for (i=0; i<n; i++)
    V[i] = rand() % 100;
  return(n);
}

/*
 *  Stampa un array di n elementi.
 */

void stampa_array(int V[], int n) {
  int i;

  for (i=0; i<n; i++)
    printf("%d ", V[i]);
  printf("\n");
  return;
}

/*
 *  Inserisce gli elementi di B in A rispettando l'ordinamento
 *  crescente.
 */

void inserisci(int A[], int n, int B[], int m) {
  int i, j;

  for (j=0; j<m; j++) {
    i = n+j-1;
    while (i>=0 && A[i]>B[j]) {
      A[i+1] = A[i];
      i--;
    }
    A[i+1] = B[j];
  }
  return;
}

/*
 *  Funzione principale.
 */

int main(void) {
  int i, n, m, x, A[MAX], B[MAX];
  n = leggi_array(A);
  m = genera_array(B);
  printf("La sequenza generata in modo casuale e':\n");
  stampa_array(B, m);
  inserisci(A, n, B, m);
  stampa_array(A, n+m);
  return(0);
}