Liste Circolari

di il
12 risposte

Liste Circolari

Salve a tutti.. Ho un esercizio che mi sta facendo incasinare molto... vi riporto il testo

Si realizzi un programma per la risoluzione del problema seguente.
Un premio deve essere assegnato ad un’unica persona scelta tra N persone.
Le N persone dovranno eliminarsi a vicenda per individuare il vincitore. L’ultimo
rimasto è quindi il vincitore.
Supponiamo che le N persone abbiano deciso di competere per il premio
sistemandosi in circolo ed eliminando la persona che occupa il posto M,
stringendosi al crescere del numero degli eliminati.
Il problema consiste nel determinare chi è il vincitore o, più in generale, nel
determinare l’ordine con cui le persone vengono eliminate.
Ad esempio, siano dati N=9 e M=5, le N persone siano numerate 1 2 3 4 5 6 7 8
9.
Il programma leggerà i valori di N e M e stamperà la sequenza risultante
5 1 7 4 3 6 9 2 8.

Posso usare soltanto array e niente funzioni tipo calloc... dunque sto cercando di far si che il programma ogni volta che elimina un giocatore attribuisce un valore nullo e al successivo turno fa posizionare dove il giocatore è stato eliminato il suo prossimo valore non nullo...

Vi ringrazio molto per il Vostro aiuto.

12 Risposte

  • Re: Liste Circolari

    E' una cosa troppo complessa?
  • Re: Liste Circolari

    Dipende da cosa hai fatto fino ad adesso. Se devi asare solo array statici devi prevedere lo shift a sx dei elementi una volta rimosso uno e l'aggiornamento dei elementi restanti.
  • Re: Liste Circolari

    Si volevo fare questa operazione che hai descritto tu ma non so come far slittare i valori nella cella adiacente e far rigirare gli elementi precedenti alla posizione che elimina il giocatore facendoli diventare ultimi...
    in breve so che devo fare così
    ho 9 elementi 1,2,3,4,5,6,7,8,9
    viene eliminato il numero 5 e dunque al successivo giro l'array sarà formato da
    6,7,8,9,1,2,3,4 eliminando in questo turno il valore 1 ma non riesco a fare l'operazione di scambio tra le celle
  • Re: Liste Circolari

    J è la posizione dove l'elemento va eleiminato. N sono gli elementi rimasti
    
    for(i = j; i < N; i++)
     a[i] = a[i+1];
    
    prima il vettore era
    1,2,3,4,5,6,7,8,9
    con j = 4 e N = 9
    dopo
    1,2,3,4,6,7,8,9
  • Re: Liste Circolari

    Non mi funziona in modo esatto poichè la sequenza del secondo turno deve far eliminare il giocatore 1 poi il 7 e così via... questo è qll che ho scritto ma non funziona ancora... scusa se ti stresso
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int ppl[9]={1,2,3,4,5,6,7,8,9}; //9 persone
    int M; //posizione che elimina il giocatore
    int contN = 9; //conta le persone in gioco
    int i; //contatore
    
    main()
    {
        do
        {
            printf("\nInserire un valore per M; min 0 max 8: ");
            scanf("%d",&M);
        }
        while(M < 0 || M > 8); //controlla se l'input è compreso tra 1 e 9 se lo è prosegue
    
     for (i=M; i<contN; i++)
        {
            printf("\nIl giocatore %d, e' stato eliminato!", ppl[M]);
            ppl[i] = ppl[i+1];
        }
    }
  • Re: Liste Circolari

    Allora quella che ti ho scritto è la parte di riassestamento dopo l'eliminazione del giocatore. Per eliminare devi fare così:
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int ppl[9]={1,2,3,4,5,6,7,8,9}; //9 persone
    int M; //posizione che elimina il giocatore
    int contN = 9; //conta le persone in gioco
    int i; //contatore
    
    int main()
    {
    	int tempPos = 0;
        do
        {
            printf("\nInserire un valore per M; min 0 max 8: ");
            scanf("%d",&M);
        }
        while(M < 0 || M > 8); //controlla se l'input è compreso tra 1 e 9 se lo è prosegue
    
    	while(contN > 1)
    	{
    		tempPos--;
    		//elimina il giocatore di turno
    		tempPos = (tempPos + M) % contN;
    		printf("\nIl giocatore %d, e' stato eliminato!", ppl[tempPos]);
    		//slita di uno a partire da quello eliminato
    		for (i=tempPos; i<contN; i++)
    		{
               ppl[i] = ppl[i+1];
    		}
    		contN--;
    	}
    	printf("\nHa vinto il giocatore %d",ppl[0]);
    }
    
  • Re: Liste Circolari

    Grandissimo!! Funziona tutto grazie mille non riuscivo ad uscirne fuori..
  • Re: Liste Circolari

    while(M < 0 || M > 8); 
    Perchè? Così se si inserisce 0 dà errore e non si può inserire 9.

  • Re: Liste Circolari

    Se si inserisce 0 va bene perche 0 non è minore di 0 ma uguale. Se inserisci 9 da errore com'è giusto che sia.
  • Re: Liste Circolari

    Ma a me dà errore! Credi che non sia capace di vedere che dà errore?
  • Re: Liste Circolari

    Cos'è che da errore? se ti riferisci all'indice che va a -1 se si inserisce 0 basta solo modificare l'algoritmo.
    
    while(contN > 1)
    	{
    		if(M)
    			tempPos--;
    		//elimina il giocatore di turno
    		tempPos = (tempPos + M) % contN;
    		printf("\nIl giocatore %d, e' stato eliminato!", ppl[tempPos]);
    		//slita di uno a partire da quello eliminato
    		for (i=tempPos; i<contN; i++)
    		{
    			ppl[i] = ppl[i+1];
    		}
    		contN--;
    	}
    
  • Re: Liste Circolari

    Così va! Grazie
Devi accedere o registrarti per scrivere nel forum
12 risposte