Tags:
create new tag
view all tags

Soluzione dell' HomeWork3aa0203

Vedi anche: HomeWork3aa0203, DomandeHomework3aa0203, RisultatiHomework3aa0203


/*
    HomeWork3: bucket-sort
    Usiamo le seguenti strutture dati:
    - vettore contenente i valori da ordinare
    - matrice per eseguire le passate
    - vettore di 10 elementi che tiene il conto di quanti sono inseriti in ciascuna riga della matrice
*/

#include <stdio.h>
#include <limits.h>
 
/* numero di valori in input */
#define SIZE 50
/* i valori vengono considerati come numeri in base 10 */
#define RANGE 10
 
/*
   esegue una passata per la potenza data
   - trasferisce da vettore a matrice
   - rimette nel vettore
   - azzera il vettore che conta quanti numeri sono inseriti in ciascuna riga della matrice
   - torna il valore
      '1' se tutti i valori sono minori della potenza corrente
      '0' se ce n'e' uno maggiore o uguale
*/
int passata(int valori[SIZE], int matrice[RANGE][SIZE], int potenza)
{
   int inseriti[RANGE] = { 0 };   /* numero di elementi inseriti in ciascuna riga della matrice */
   int tuttiminori = 1;      /* indicatore che tutti i valori sono minori della potenza */
   int cifra = 0;         /* cifra corrente */
   int i, j, k;

   /* azzero il numero di numeri inseriti in ciascuna riga*/
   for (i=0 ; i < RANGE ; i---++)
      inseriti[i] = 0;

   /* facciamo una passata */
   for (i=0 ; i<SIZE ; i---++) {
      /* calcolo la cifra corrente del valore corrente*/
      cifra = (valori[i] / potenza) % 10;
      /* inserisco il valore nella riga giusta ed incremento il conteggio degli elementi presenti */
      matrice[cifra][inseriti[cifra]---++] = valori[i];
      /* se il valore corrente Ŕ maggiore della prossima potenza devo ripetere la passata */
      /* faccio il confronto dopo un cast a double per essere sicuro di gestire numeri vicino a INT_MAX */
      if (valori[i] >= (double)potenza*10)
         tuttiminori = 0;
   }

   /* ricopiamo i valori indietro nel vettore di appoggio nell'ordine giusto */
   k = 0;
   for (i=0 ; i < RANGE ; i---++)
      for (j=0 ; j < inseriti[i] ; j---++)
         valori[k---++] = matrice[i][j];

   /* faccio sapere se serve un'altra passata */
   return tuttiminori;
}

/* programma principale */
int main(int argc, char * argv[]) {
    /* dichiarazioni */
    int matrice[RANGE][SIZE] = { 0 };   /* matrice */
    int valori[SIZE] = { 0 };      /* vettore di appoggio dei valori */
    int i;
    int potenza = 1;         /* potenza di dieci corrente */
    int passate = 1;         /* conteggio delle passate */
    int tuttiminori = 0;      /* indicatore=1 se tutti i valori sono minori della prossima potenza */

    /* dati personali */
    printf("Andrea\nSterbini\n02\n02\n1961\nsterbini@dsi.uniroma1NOSPAM.it\n");

    /* lettura degli input */
    for (i=0 ; i<SIZE ; i---++)
        scanf("%d",&valori[i]);

    /* ciclo per le varie potenze di 10 crescenti */
    while (tuttiminori==0) {
       tuttiminori = passata(valori, matrice, potenza);
       potenza *= 10;
       passate---++;
    }

    /* output dei valori (che sono tornati nel vettore di appoggio) */
    for (i=0 ; i<SIZE ; i---++)
        printf("%d\n",valori[i]);

    /* stampa del numero di passate */
    printf("%d\n",passate);

    return 0;
}

-- AndreaSterbini - 13 Nov 2002

Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r5 - 2003-09-30 - AndreaSterbini






 
ATTENZIONE: per spostamento su altro server twiki potrÓ essere inattivo per brevi periodi nel pomeriggio di lunedý 8/8.
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback