Algoritmo somma vettori sparsi

[xber-gigi]

algoritmo di somma di due vettori sparsi, memorizzati nel formato a coordinate. Nei test usare vettori di ordine 100, 200, 500, in cui solo il 5% degli elementi è non nullo. Generare a caso sia il valore di un elemento non nullo (un intero in 0,1,..,10) sia il suo indice. Usare la function rand() in <stdlib.h> per generare numeri casuali; per esempio, se numero_casuale è un int, la chiamata numero_casuale=rand()%11; genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..,10).

Ragazzi per favore potreste spiegarmi cosa richiede questo esercizio??? E' molto importante!!!

Ho realizzato il programma con due array creati casualmente ma mi hanno detto che non va bene in quanto devono essere vettori sparsi.
Per favore potreste aiutarmi???

[cionci]

Sparso significa che ci sono molti elemnti pari a 0... In questo caso ti da la percentuale degli elementi che devono essere diversi da zero...

In pratica fai un test sulla percentuale del 5% ed in tal caso generi un numero > 0...

[xber-gigi]

Io ho fatto nel seguente modo che ora incollo.
Mi è stato detto che non ho fatto un corretto uso del formato a coordinate e che quindi devo riprogettare completamente tutta la parte.
Per favore aiutatemi!!! Fatemi capire dove ho sbagliato!!!

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

void main ()

{
int vett1[1000], vett2[1000];
int n,i,nonulli,numero_casuale,posizione,prod_scalare;
printf ("Indicare la grandezza dei vettori: ");
scanf ("%d",&n);

/* CALCOLO DEL 5% DELLA GRANDEZZA DEL VETTORE*/

nonulli = (n * 5) /100;

/* INSERISCE IL VALORE 0 AD OGNI IDICE DEL VETTORE*/

for (i=0;i<n;i++)
{
vett1[i] = 0;
}
for (i=0;i<n;i++)
{
vett2[i] = 0;
}

/* ATTRIBUISCE IN POSIZIONI CASUALI NUMERI CASUALI*/

for (i=1;i<=nonulli;i++)
{
numero_casuale=1+rand()%10;
posizione=rand()%(n-1);

/* SE LA POSIZIONE USCITA è GIà OCCUPATA DA UN INTERO, UTILIZZA LA PROSSIMA DIVERSA DA ZERO */

while (vett1[posizione]!=0)
{
posizione=(posizione+1) %n;
}

vett1[posizione]=numero_casuale;
}

for (i=1;i<=nonulli;i++)
{
numero_casuale=1+rand()%10;
posizione=rand()%(n-1);

while (vett2[posizione]!=0)
{
posizione=(posizione+1) %n ;
}

vett2[posizione]=numero_casuale;
}

/* STAMPA DEI VETTORI*/

printf ("STAMPA VETTORE NUMERO UNO\n");
for (i=0;i<n;i++)
{
printf ("%d ", vett1[i]);
}
printf ("\n\n");

printf ("STAMPA VETTORE NUMERO DUE\n");
for (i=0;i<n;i++)
{
printf ("%d ", vett2[i]);
}

[cionci]

Mi sembra che sia fatto come richiedeva il testo...ci sono però alcune cose che potevi compattare molto di più...ad esempio:

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

void main ()

{
	int vett1[1000], vett2[1000];
	int n,i,nonulli,numero_casuale,posizione,prod_scalare;
		printf ("Indicare la grandezza dei vettori: ");
	scanf ("%d",&n);
	
	/* CALCOLO DEL 5% DELLA GRANDEZZA DEL VETTORE*/

	nonulli = (n * 5) /100;
	
	/* INSERISCE IL VALORE 0 AD OGNI IDICE DEL VETTORE*/
	
	for (i=0;i<n;i++)
		vett2[i] = vett1[i] = 0;
	
	/* ATTRIBUISCE IN POSIZIONI CASUALI NUMERI CASUALI*/
	
	for (i=1;i<=nonulli;i++)
	{
		numero_casuale=1+rand()%10;
		posizione=rand()%(n-1);
		
		/* SE LA POSIZIONE USCITA è GIà OCCUPATA DA UN INTERO, UTILIZZA LA PROSSIMA DIVERSA DA ZERO */
		
		while (vett1[posizione]!=0)
		{ 
			posizione=(posizione+1) %n;
		}

		vett1[posizione]=numero_casuale;

		numero_casuale=1+rand()%10;
		posizione=rand()%(n-1);

		while (vett2[posizione]!=0)
		{ 
			posizione=(posizione+1) %n ;
		}

		vett2[posizione]=numero_casuale;
	}
	
	/* STAMPA DEI VETTORI*/
	
	printf ("STAMPA VETTORE NUMERO UNO\n");
	for (i=0;i<n;i++)
	{
		printf ("%d ", vett1[i]);
	}
	printf ("\n\n");
	
	printf ("STAMPA VETTORE NUMERO DUE\n");
	for (i=0;i<n;i++)
	{
		printf ("%d ", vett2[i]);
	}
}

[cionci]

Ora che ci penso...che intende per "formato a coordinate" ?

[xber-gigi]

Per le matrici o i vettori formati per la maggiorparte da zero è preferibile usare il criterio di memorizzazione a coordinate.
Questo è formato da tre array 1D.
Il primo contiene tutti gli elementi non nulli della matrice (o vettore).
Il secondo contiene l'indice della colonna.
Il terzo contiene l'indice della riga.

[cionci]

Ah...ok... Questa cosa non l'hai fatta per niente nel tuo programma...

[xber-gigi]

Si ma cmq non so proprio come proseguire ora!!!
Come dichiaro l'array se non so quanto è lungo?!?!?
Devo immettere io la grandezza del vettore!
Brother of true metal! Help me!!!

[cionci]

Nemmeno prima sapevi quanto era lungo...eppure la dimensione l'hai data

Fai lo stesso discorso di prima oppure procedi con l'allocazione dinamica che non so se hai già fatto...

[cionci]

Ah...ricordati che non hai una matrice...quindi non ti serve un vettore in meno...

[xber-gigi]

Ti rigrazio per le rispote!

Sapete per caso la formula per la somma di due vettori?!?!??

[xber-gigi]

Sono proprio in difficoltà!!!
Aiuto!!!

Ora che genero l'array con le coordinate attraverso una rand come faccio a vedere se la stessa coordinata non mi è uscita prima??? Ovvero che non mi escano due numeri uguali nello stesso array?!?!?!

Per favore help!!! Sto entrando in pallone con la testa!!!

[cionci]

Ci sono diversi modi...

1) Estrai un nuovo nume3ro fino a quando non esiste all'interno delle coordinate (soluzione non buone secondo me)

2) Estrai un numero...fai la scansione del vettore e verifichi se il numero è già presente fra le coordinate... Se è presente lo incrementi di uno (modulo N)... Riparti a fare la scansione... Così via fino a quando verifichi che il numero non è presente fra le coordinate...Ogni volta devi diminuire la qantità di numeri da cui fai l'estrazione (devi diminuire K di rand() % K + 1)...

[xber-gigi]

Non ci ho capito molto
che struttura interativa dovrei utilizzare???
Help!

[cionci]

Per il secondo:


numero_estratto = 1 + rand() % (N-1);


do {

for(i=0; i< quantità_estratti; ++i)
{
se vet[i] == numero_estratto allora 1 + (numero_estratto % (MAX-1));
}

} while(non ho aumentato il numero estratto);

N = N-1;

E riparti da capo...

[xber-gigi]

Dopo un intera giornata credendo di impazzire sono arrivato a questa conclusione. Credi che vada bene???
Praticamente nel momento in cui trova che il numero pescato casualmente è già nell'array, ripete l'estrazione di un nuovo numero casuale finchè questo non è diverso da quelli già presenti.
Cosa ne dici??? Cè qualche bug secondo te???

/*GENERAZIONE DELLE COORDINATE*/

for (i=0;i<nonulli;i++)
{
do
{
numero_cas = rand()%n;
y=-1;
x=0;

do
{
y=y+1
}
while (coordinate1[y]!=numero || y==nonnulli);

if (coordinate1[y] == numero_cas)
{
x=1;
}
}
while (x==1);
coordinate1[i] = numero_cas;
}

[cionci]

Sbagliato...questo potrebbe portare anche al blocco del programma... Ti ho scritto sopra cosa fare... C'è qualcosa che non ti torna ?

[xber-gigi]

Ok sono riuscito a creare le coordinate.
Ma ora la somma?
Come sommo i due array?

[xber-gigi]

Pensavo che devo lavorare anche sulle coordinate del risultato?!?
Questi maledetti vettori a coordinate mi stanno facendo impazzire!!!
Lo avevo già fatto utilizzando due vettori incizzati normalmente e ci avevo messo 5 minuti a realizzarlo!!!

[cionci]

Allora...per la somma è semplice...

Copia il contenuto del vettore "uno" nel vettore del risultato (fai una copia elemento per elemento dei dati e delle coordinate)...

Comincia a scorrere il vettore "due"... Per ogni elemento delle coordinate del vettore "due": se la coordinata in questione esiste anche nelle coordinate del risultato allora somma il dato corrispondente del vettore "due" al dato corrispondente alla stessa cooridinata nel vettore del risultato...altrimenti aggiungi una nuova coordinata e un nuovo dato al risultato...