Ordinamento e Array

[shiony710]

Salve a tutti,
tra un paio di giorni ho l'esame di programmazione, devo però portare dei programmi, uno di questi mi sta dando diversi problemi nell'implementazione. Vi scrivo qui sotto il testo richiesto:

In questo esercizio ti viene chiesto di implementare l'algoritmo di Selection Sort visto in classe.

Una volta implementato l'algoritmo, risolvi i seguenti esercizi:
3. Dato un vettore di interi v e un intero x, scrivi una funzione in C che stampa a video la piu piccola
sequenza di elementi di v la cui somma supera x. Ad esempio, supponiamo che v = {3; 12;-1; 10}.
A tal ne basta prendere la sequenza formata dall'unico elemento 12 per avere 12 > 10. Qual'e la
complessita computazionale dell'algoritmo proposto?

Probabilmente, anzi quasi sicuramente ci sarà un modo migliore per implementarlo, quindi anche in questo vorrei essere aiutato, comunque la parte che mi manca è quella che mi confronta i singoli elementi dell'array con la x, quando ho provato a implementarlo il problema è che mi stampava tutti e tre i risultati, cioè sia la somma di due che somma dei tre elementi insieme al singolo.
Vi scrivo, quindi, il codice qui sotto:

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

const int dim = 3;		//Dimensione

int main()
{
    int* v = (int*)calloc(dim,sizeof(int));	//Crea un array dinamico di 4 celle tute inizializzate a 0
    int k,somma,i,j,totale;
    printf("Inserisci elementi:\n"); 
    for (i = 0 ; i < dim ; i++ )
    {			//Inserisco i valori nelle celle scandite da 0 a 3
        printf("\tInserisci valore: ");
        scanf("%d", &v[i]);
	}
    
    int x;
    printf("inserisci un intero x \n");		//Setto il valore di x
    scanf("%d", &x);
    
    k = somma = totale = 0;
    while(k < dim)
    {							//Se il mio scan di indice raggiunge la fine dell'array
		for(j = 0; j < dim; j++)
        {			//Sotto ciclo per scandire le altre posizioni
			if(j != k)
            {						//Leggo tutte le posizioni tranne in quella dove sono
				somma = v[k]+v[j];
				if(somma > x)
                {				//Se la somma è superiore a x, ho finito esco dal programma e faccio una stampa.
					printf("Nella posizione v[%d]=%d e v[%d]=%d la loro somma e' %d supera il valore x=%d\n",k,v[k],j,v[j],somma,x);
                    return 0;
				}
                
		    }
		}
		k++;
		for(j = 0; j < dim; j++)
        {
		    if(j != k)
		    {
                totale = v[k]+v[j]+v[j++];
                if(somma < x && totale > x)
	            {
				    printf("La somma di tutti gli elementi nel vettore e' %d supera il valore x=%d\n",totale,x);
                    return 0;   
				}
		    }
		}
	}
	printf("La somma di tutti gli elementi dell'array e' minore di x= %d\n",x);	//Se sono arrivati qui senza essere stato bloccato sopra vuol dire che non ci sono elementi per cui la loro somma sia superiore ad x.
	free(v);	//Libero la memoria allocata per V, per renderla di nuovo disponibile al OS
    return 0;
}

Chiedo un vostro aiuto, ringrazio anticipatamente.

[wingman87]

Secondo me il problema è mal posto: perché l'esercizio inizia dicendo che ti viene richiesto di implementare l'algoritmo di selection sort?
Probabilmente vuole che il vettore lo tratti come un insieme e non come una sequenza al fine di trovare la più piccola sequenza di numeri (diversi) la cui somma supera x.
Così avrebbe molta più attinenza con il sorting...
Se così non fosse, riguardo il tuo codice, ti consiglio di dividerlo in sotto funzioni (tra l'altro ti viene richiesto di scrivere una funzione). Inoltre la dimensione dell'array deve essere variabile quindi il modo in cui hai scritto l'algoritmo non va proprio bene...

[GTKM]

Edito: già risposto wingman

[mattia01]

Ordini il vettore dal più piccolo al più grande poi di volta in volta sommi gli elemento dell'array fino a che la somma supera l'intero di riferimento

[mattia01]

Nell'esempio il vettore ordinato sarebbe v= {12,10,3,-1} e x=10, quindi dato che 12 è già maggiore di x il ciclo di somma si chiude e il risultato è 12

[Zeppe79]

se vuoi risolvere l'esercizio utilizzando il sorting, come dice mattia, ordini il vettore dall'intero più grande al più piccolo, e all'interno di un ciclo fai il confronto. es: v=[9,4,-5,7,3,11] e x=14.
ordini v, così da avere [11,9,7,4,3,-5]
inizi il ciclo:
11 > 14 ? no
(11+9) > 14 ? sì -> fine ciclo, trovato il risultato

[shiony710]

Credo di averlo terminato, a me il programma funziona correttamente ditemi se c'è qualcosa da correggere

#include <stdio.h>
 
int main()
{
   int v[100], n, i, j, position, swap, somma=0;
   
 
   printf("Inserisci il numero degli elementi\n");
   scanf("%d", &n);
 
   printf("Inserisci %d elementi\n", n);
 
   for ( i = 0 ; i < n ; i++ )
      scanf("%d", &v[i]);
 
   for ( i = 0 ; i < ( n - 1 ) ; i++ )
   {
      position = i;
 
      for ( j = i + 1 ; j < n ; j++ )
      {
         if ( v[position] < v[j] )
            position = j;
      }
      if ( position != i )
      {
         swap = v[i];
         v[i] = v[position];
         v[position] = swap;
      }
   }
 
   printf("Lista in ordine decrescente:\n");
 
   for ( i = 0 ; i < n ; i++ )
      printf("%d\n", v[i]);
    int x;
    printf("inserisci un intero x \n");		//Setto il valore di x
    scanf("%d", &x);
    for( i = 0; i < n; i++)
	{
	     if ( v[i] > x)
         {
  			 printf("Il primo elemento dell'array=%d e' maggiore di x=%d", v[i], x);
			 return 0;
		 }
		 else
		 {
			for(i = 0; i < n; i++)
			{
				somma += v[i];
				if (somma > x)
			    {
					printf("la somma degli elementi e' %d maggiore di x %d", somma, x);
					return 0;
			    }
			}
		 }
	 
       printf("La somma di tutti gli elementi dell'array e' minore di x= %d\n",x);	
    }
	return 0;
   
}

[mattia01]

Ad occhio sembra che funzioni ma non mi pare che ritorni un secondo vettore che contiene solo la minore sequenza di elementi che servono per superare il numero x

[shiony710]

ma perché comunque il testo non è molto chiaro, non capisco se come sequenza intendi il minor numero di elementi da utilizzare o anche la grandezza degli elementi, se fosse come nel secondo caso come dovrei cambiarlo?

[mattia01]

La traccia dice di stampare a video la più piccola sequenza degli elementi dell'array v, tale che la somma di questi superi il valore di x

[shiony710]

Si, ma ripeto non si capisce se con "sequenza" intendo il numero di elementi da utilizzare o anche la grandezza degli elementi

[GTKM]

Scusatemi eh, che c'è di poco chiaro? Una sequenza è una serie di oggetti disposti in un certo ordine.

Dunque, il compito del programma è quello di stampare a video la più piccola "lista" di numeri la cui somma supera 'x'.

Comunque, non per rompere le uova nel paniere, ma l'esercizio chiede che sia scritta una funzione che risolva questo problema. Tra l'altro, il C è stato proprio pensato e realizzato per scomporre il programma in funzioni.
Mettere tutto nel main è il modo peggiore di usare questo linguaggio

[mattia01]

Sono pienamente d'accordo!

[Zeppe79]

dorvesti spezzare il codice in funzioni, anche solo per aumentare la leggibilità: almeno 1 funzione che fa il sorting (array in ingresso,e array in uscita), 1 funzione che fa la ricerca (array in ingresso, x in ingresso, risultato in uscita). Nel main tieni l'interazione con l'utente.

Secondo me nella funzione di ricerca fai un ciclo di troppo:

for( i = 0; i < n; i++)
{
    if ( v[i] > x)
    {
        printf("Il primo elemento dell'array=%d e' maggiore di x=%d", v[i], x);
	return 0;
     }
    .....

secondo me il controllo che fai su v[i] lo puoi integrare nel secondo ciclo, iniziando da somma = 0;

somma = 0;
for(i = 0; i < n; i++)
{
	somma += v[i];

	if (somma > x)
        {
		printf("la somma degli elementi e' %d maggiore di x %d", somma, x);
		return 0;
	}
}

In più dovresti salvare l'array di elementi la cui somma > x, o quanto meno l'indice i dell'array ordinato dove raggiungi il risultato.

[shiony710]

Ok perfetto, vi ringrazio per l'aiuto, siete stati gentilissimi , vorrei però usufruire una seconda volta del vostro aiuto per chiedermi chiarimenti riguardante la complessità, sia in questo programma che in generale.
Perché studiandola sia da internet che dal libro, ho avuto scarsi risultati nel comprenderla, quindi se in qualche modo potete darmi una mano ne sarei entusiasta