[C] Funzione più efficiente che sfrutti l'ordinamento del vettore

[.:DarkSkull:.]

Salve a tutti! Mi trovo a riscrivere di nuovo su questo forum, perché l'altro giorno ho fatto un esame di C dove un esercizio chiedeva di scrivere una funzione che dato un vettore, la sua dimensione e un numero k in input, ritornasse il numero delle coppie degli elementi la cui somma fosse stata maggiore di k.
Ecco il codice che ho scritto così che possiate capire meglio:

#include <stdio.h>

int func(int T[], int D, int k);

int main()
{
 int num;
 int V[7] = {1,4,3,2,5,6};
 printf("Inserisci un numero:\n");
 scanf("%d",&num);
 printf("%d\n", func(V, 7, num));
 return 0;
}

int func(int T[], int D, int k)
{
 int i,j,count,somma;
 count = 0;
 somma = 0;
 for(i = 0; i < D; i++) {
  for(j = i + 1; j < D; j++) {
   somma = T[i] + T[j];
   if(somma > k) {
    printf("\n%d+%d\n", T[i], T[j]);
    count++;
   }
  }
 }
 return count;
}

Fin qua tutto ok... L'esercizio poi chiedeva di fare una funzione più efficiente poichè sfruttasse il fatto che l'array avesse gli elementi ordinati in modo crescente. Mi sapreste dare qualche consiglio?

[cifa]

Ehi ho fatto lo stesso esame anche io, Galesi eh ? Io ho preso la lode quindi penso che la mia soluzione sia quella che cercava lui, switcho a linux e ti dico

[.:DarkSkull:.]

Grande! Mi potresti dire anche se per il terzo problema la soluzione potrebbe essere questa?

#include <stdio.h>

void merge(int *A, int na , int *B, int nb , int *C);

int main()
{
 int V[5] = {1,8,12,16,18};
 int T[5] = {3,6,9,12,15};
 int U[10];
 
 merge(V,5,T,5,U);

 return 0;
}

void merge( int A[], int na, int B[], int nb, int C[])
{
 int i,j,k;
 i=j=k=0;
//Termina quando termina il primo array
 while (i<na && j<nb) {
  if (A[i]<B[j])
   C[k++]=A[i++];
  else
   C[k++]=B[j++];
 }
//Copiatura del rimantente array 
 while (i<na)
 {
  C[k++]=A[i++];
 }
 while (j<nb)
 {
  C[k++]=B[j++];
 }

 printf("\n");
 for(i = 0; i < 10; i++)
 {
  printf(" %d ", C[i]);
 }
 printf("\n");
}

Per tutti gli utenti... Questo problema consisteva nell'implementare una funzione che facesse la fusione ordinata su due array ordinati.

[cifa]

Ecco il codice:

int couples(int T[], int D, int k){
	int i=0;
	int j=D-1;
	int count=0;
	while(i!=j){
		if(T[i]+T[j]>k){
			count+=j-i; 
			j--;
		}else{
			i++;
		}
	}
	return count;
}

L'idea si dovrebbe capire dal codice, se non la capisci dimmi pure che provo a spiegartela (dico provo perchè sto distrutto XD)

[cifa]

Sì bene o male anche io ho fatto così il terzo esercizio, il mio codice aveva piccole differenze ad esempio io l'array me lo creo e lo restituisco dentro il metodo con

int *R=malloc(sizeof(int)*(na+nb))

, ma anche come fai te dovrebbe andargli bene.

[.:DarkSkull:.]

Grazie ancora! Ma ho notato che (non so chi dei due abbia sbagliato), in output il mio programma con k=3 e il vettore V[7] = {1,2,3,4,5,6}; manda:

1+3
1+4
1+5
1+6
2+3
2+4
2+5
2+6
3+4
3+5
3+6
4+5
4+6
5+6
14

Il tuo invece manda questo:

1+0
2+0
3+0
4+0
4+6
4+5
6

Così a occhio penso che sia il mio quello giusto!!! Tu che ne pensi? Con questo non voglio criticarti, anzi grazie mille per la disponibilità!

[cifa]

Originariamente inviato da .arkSkull:.
Grazie ancora! Ma ho notato che (non so chi dei due abbia sbagliato), in output il mio programma con k=3 e il vettore V[7] = {1,2,3,4,5,6}; manda:

1+3
1+4
1+5
1+6
2+3
2+4
2+5
2+6
3+4
3+5
3+6
4+5
4+6
5+6
14

Il tuo invece manda questo:

1+0
2+0
3+0
4+0
4+6
4+5
6

Così a occhio penso che sia il mio quello giusto!!! Tu che ne pensi? Con questo non voglio criticarti, anzi grazie mille per la disponibilità!

Hai modificato qualcosa nel codice si vede Ho ri-eseguito il mio codice ore e l'output è 14

Occhio che comunque la dimensione di quell'array è 6 e non 7.


Non ha senso con il mio algoritmo stampare le coppie, o quantomeno, non ce la fai con un print piazzato lì.

Ti spiego l'idea:
Consideriamo il tuo array

1 2 3 4 5 6

poniamo i=0 e j=5
T[i]+T[j] = 7, di conseguenza essendo T[i] sicuramente più piccolo di tutti gli elementi T[i+1]...T[j-1] possiamo affermare senza confronti che le coppie in questo caso sono tutte quelle formate da T[j] e tutti gli elementi T[i]...T[j-1], dunque j-i!

Fatto ciò possiamo spostare la j per fare lo stesso ragionamento. Nel caso arrivi una coppia tale che T[j]+T[i]<k significa dobbiamo incrementare un valore, ma dato che T[j] è il maggiore fra i non confrontati, l'unica cosa da fare è incrementare il valore di T[i] e questo, grazie all'ordinamento crescente del vettore, è ottenibile con i++

[.:DarkSkull:.]

Hai ragione allora grazie mille!!

[alka]

Originariamente inviato da .arkSkull:.
Mi potresti dire anche se per il terzo problema la soluzione potrebbe essere questa?

Il terzo problema lo conoscete voi, ma è totalmente ignoto al resto degli utenti di questo forum.

Se c'è un problema da affrontare per cui farsi dare eventualmente una mano e che può essere d'aiuto a tutti, ben venga, ma se usate il forum per scambiarvi messaggi per la risoluzione dei compiti a casa assegnatovi che solo voi conoscete, allora non ci siamo (usate i messaggi privati, oppure una sana casella di posta elettronica).

[cifa]

Originariamente inviato da .arkSkull:.
Hai ragione allora grazie mille!!

Ti ho editato sopra con la spiegazione dell'idea, magari ti è più chiaro.
Scusa la probabile confusione, ma sono veramente distrutto