Torna indietro   Hardware Upgrade Forum > Software > Programmazione

Nuova Dacia Spring, del modello precedente resta solo il nome: più grande, più efficiente e ora prodotta in Europa
Nuova Dacia Spring, del modello precedente resta solo il nome: più grande, più efficiente e ora prodotta in Europa
La seconda generazione della citycar elettrica di Dacia passa alla piattaforma RGEV small di Renault Group, cresce di 15 cm in lunghezza e 18 cm in larghezza, adotta un motore da 80 CV e una batteria LFP da 27,5 kWh per 250 km WLTP. Prezzi da 17.900 euro, produzione a Novo Mesto in Slovenia.
BOOX Picco: l'ebook reader minuscolo è una genialata, e si può attaccare allo smartphone
BOOX Picco: l'ebook reader minuscolo è una genialata, e si può attaccare allo smartphone
BOOX ha portato sul mercato Picco, un e-reader da 3,97 pollici che pesa 58 grammi e si aggancia al retro dello smartphone con un anello magnetico. Lo abbiamo usato con Pixel 11 Pro XL e iPhone 18 Pro per capire se un formato così ridotto regga la prova della lettura quotidiana
AMD EPYC Venice: dentro Zen 6, i SoC a 256 core e la sfida al costo della memoria
AMD EPYC Venice: dentro Zen 6, i SoC a 256 core e la sfida al costo della memoria
A Las Vegas AMD ha svelato i dettagli architetturali delle CPU EPYC di sesta generazione, note con il nome in codice Venice. Nuovi core Zen 6 e Zen 6c costruiti a 2 nanometri, fino a 256 core per socket, 16 canali di memoria, interfaccia PCI Express 6.0 e un'intera famiglia di proposte che va da Venice SP7 a Verano. Senza dimenticare la memoria, oggi la voce di costo più pesante in un server: AMD risponde con CXL 3.1 e con la tecnologia software MEXT, che porta la memoria flash dentro la gerarchia della DRAM.
Tutti gli articoli Tutte le news

Vai al Forum
Rispondi
 
Strumenti
Old 29-01-2007, 11:02   #1
lucas87
Bannato
 
Iscritto dal: Oct 2006
Messaggi: 170
C. Conta coppie >0

L'esercizio è il seguente:

Scrivere una funzione (iterativa) che calcoli il numero di coppie (i,j) tali che
A[i]+B[j]>0 per due vettori A e B.

Sembra una stronzata e infatti lo è!!!
Di seguito è postata la soluzione.
Ma ora c'è da fare una piccola variazione. Ipotizzare che i 2 vettori A e B siano ordinati e sfruttare il fatto che siano ordinati per creare un algoritmo piu efficiente.

Come si puo fare?

Soluzione senza ipotizzare che i vettori siano ordinati:

Codice HTML:
#include<stdio.h>
#include<stdlib.h>



void leggi_array(int *, int );
int cnt_coppie(int *, int *, int, int);



int main(void){
int dim1,dim2;
    printf("Immetti la dimensione del primo Array:");
    scanf("%d",&dim1);
    int v1[dim1];
    printf("Immetti la dimensione del secondo Array:");
    scanf("%d",&dim2);
    int v2[dim2];
    printf("caricamento primo vettore\n");
    leggi_array(v1,dim1);
    printf("caricamento secondo vettore\n");
    leggi_array(v2,dim2);
    printf("numero di coppie la cui somma e' maggiore di 0 e' = %d\n",cnt_coppie(v1,v2,dim1,dim2));
   system("PAUSE");
}

int cnt_coppie(int *t1,int *t2, int dim1, int dim2){
     int i,j,cnt;
     cnt=0;
     for (i=0;i<dim1;++i){
         for (j=0;j<dim2;++j){
             if ((t1[i]+t2[j])>0) ++cnt;
         }
     }
     return cnt;
}
     
     
void leggi_array(int *t, int d){
    int i;
    for(i=0;i<d;i++){
	printf("Immetti t[%d]= ",i);
	scanf("%d",&t[i]);
    }
}
lucas87 è offline   Rispondi citando il messaggio o parte di esso
Old 29-01-2007, 11:30   #2
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 16216
Modifica leggermente l'algoritmo di ricerca binaria in modo che trovi, in un vettore, non l'indice dell'elemento con un valore fissato ma quello del più piccolo elemento che non scende al di sotto di quel valore.
A questo punto, per ogni A[k] applica la ricerca modificata a B sul valore -A[k]: trova j, e aggiungi len(B)-j al totale delle coppie.

EDIT: questo ipotizza che sia ordinato solo B... si può fare di meglio...

... ah, sì: chiamare l'algoritmo solo sulla porzione di B tra l'ultimo indice trovato, e la fine.
ARIEDIT: questo andrebbe bene se A fosse letto a partire dall'elemento più grande.
Se invece parti dal più piccolo, fai la tua ricerca una volta sola quando hai A[1]; poi, quando conti A[2], noti che tutti gli elementi di B che hai trovato al primo passaggio, vanno ancora bene, e devi al più aggiungere qualcuno di quelli di prima... e mi sa che così arrivi a tempo O(N + K) anziché O(N log K), dove N è la lunghezza di A e K quella di B...
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO DarthMaul = Asus FX505 Ryzen 7 3700U 8GB GeForce GTX 1650 Win10 + Ubuntu

Ultima modifica di Ziosilvio : 29-01-2007 alle 14:11.
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 29-01-2007, 11:51   #3
lucas87
Bannato
 
Iscritto dal: Oct 2006
Messaggi: 170
Provato e funzionante. Grazie della risposta Ziosilvio.

Qualcuno sa come sfruttare il fatto che entrambi i vettori siano ordinati?

Grazie in anticipo.
lucas87 è offline   Rispondi citando il messaggio o parte di esso
Old 29-01-2007, 11:57   #4
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 517
Un'idea, una volta che hai ordinato gli array, é:

per ogni a[i], cerca l'indice j per cui a[i]+b[j]>0
coppie += Dimensione_array_b - j

Su un array ordinato puoi ottimizzare anche la ricerca, ad esempio eseguendo una ricerca selettiva, ovvero non scorrendo l'array b elemento per elemento alla ricerca del primo elemento che soddisfa la condizione voluta.
Un esempio di ricerca selettiva:

Codice:
jInf=0
jSup=Dimensione_array_b;

while (jSup!=jInf)
{
    j = jSup-jInf/2;
    If (b[j] soddisfa la condizione) jSup=j
    else jInf = j
}
la j finale che ottieni dovrebbe essere il primo indice j che verifica la condizione da te voluta
__________________
Il sole è giallo
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 29-01-2007, 14:09   #5
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 16216
Quote:
Originariamente inviato da lucas87
Qualcuno sa come sfruttare il fatto che entrambi i vettori siano ordinati?
Ho editato il mio post precedente. Vedi un po' se funziona...
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO DarthMaul = Asus FX505 Ryzen 7 3700U 8GB GeForce GTX 1650 Win10 + Ubuntu
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 29-01-2007, 18:15   #6
lucas87
Bannato
 
Iscritto dal: Oct 2006
Messaggi: 170
Mhh..per ziosilvio, lo fatto come dici tu pero in esecuzione non da problemi, a volte va, ma penso per puro caso. Se ti capita di fare il codice, fammi sapere se ti va e magari postalo se hai tempo.

ciao
lucas87 è offline   Rispondi citando il messaggio o parte di esso
Old 30-01-2007, 11:43   #7
lucas87
Bannato
 
Iscritto dal: Oct 2006
Messaggi: 170
Utilizzando l'idea di yorkeiser lo fatto funzionare, non pero usando la ricerca effettuata in quell'altro modo, in quanto mi creava problemi alcune volte.

Posto la probabile soluzione finale:

Codice HTML:
#include<stdio.h>
#include<stdlib.h>

#define LIMIT 1024


void leggi_array(int *, int );
int cnt_coppie(int *, int *, int, int);



int main(void){
int dim1,dim2;
    printf("Immetti la dimensione del primo Array:");
    scanf("%d",&dim1);
    int v1[dim1];
    printf("Immetti la dimensione del secondo Array:");
    scanf("%d",&dim2);
    int v2[dim2];
    printf("caricamento primo vettore\n");
    leggi_array(v1,dim1);
    printf("caricamento secondo vettore\n");
    leggi_array(v2,dim2);
    printf("numero di coppie la cui somma e' maggiore di 0 e' = %d\n",cnt_coppie(v1,v2,dim1,dim2));
   system("PAUSE");
}

int cnt_coppie(int *t1,int *t2, int dim1, int dim2){
     int i,j,cnt;
     cnt=0;
     j=0;
     for (i=0;i<dim1;++i){
         for (j=0;j<dim2;++j){
             if ((t1[i]+t2[j])>0){ 
                cnt=cnt+(dim2-j);
                break;
                }
         }
     }
     return cnt;
}                 
     
     
void leggi_array(int *t, int d){
    int i;
    for(i=0;i<d;i++){
	printf("Immetti t[%d]= ",i);
	scanf("%d",&t[i]);
    }
}
lucas87 è offline   Rispondi citando il messaggio o parte di esso
 Rispondi


Nuova Dacia Spring, del modello precedente resta solo il nome: più grande, più efficiente e ora prodotta in Europa Nuova Dacia Spring, del modello precedente resta...
BOOX Picco: l'ebook reader minuscolo è una genialata, e si può attaccare allo smartphone BOOX Picco: l'ebook reader minuscolo è un...
AMD EPYC Venice: dentro Zen 6, i SoC a 256 core e la sfida al costo della memoria AMD EPYC Venice: dentro Zen 6, i SoC a 256 core ...
HONOR Pad X9 Max recensione, schermo ultra large a meno di 400 euro HONOR Pad X9 Max recensione, schermo ultra large...
Lenovo ThinkPad X1 Carbon Gen 14: il business ultraleggero si rinnova dall’interno Lenovo ThinkPad X1 Carbon Gen 14: il business ul...
Amazon anticipa senza preavviso gli scon...
GTA 6 troppo esplicito? Il gioco Rocksta...
Nintendo non ha dubbi: ecco le stime su ...
Samsung, SK hynix e Micron non evitano i...
Huawei sfida Tesla Powerwall con una bat...
Black Friday FRITZ! su Amazon: router Wi...
Niente Chromium: il browser di Cloudflar...
Riscaldamento smart, su Amazon prezzi Bl...
Il cloud per le piccole imprese secondo ...
I 2 portatili con 16GB di RAM e 512GB SS...
Discord su Linux è quasi alla pari con W...
Il Black Friday Amazon è gi&agrav...
Quale robot Dreame comprare al Black Fri...
L'alimentatore trasparente Corsair da 10...
HP OMEN con RTX 5070 e Ryzen 9 ora costa...
Chromium
GPU-Z
OCCT
LibreOffice Portable
Opera One Portable
Opera One 106
CCleaner Portable
CCleaner Standard
Cpu-Z
Driver NVIDIA GeForce 546.65 WHQL
SmartFTP
Trillian
Google Chrome Portable
Google Chrome 120
VirtualBox
Tutti gli articoli Tutte le news Tutti i download

Strumenti

Regole
Non Puoi aprire nuove discussioni
Non Puoi rispondere ai messaggi
Non Puoi allegare file
Non Puoi modificare i tuoi messaggi

Il codice vB è On
Le Faccine sono On
Il codice [IMG] è On
Il codice HTML è Off
Vai al Forum


Tutti gli orari sono GMT +1. Ora sono le: 11:33.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2026, Jelsoft Enterprises Ltd.
Served by www3v