HACKING 120% {Hacking, programmazione, computer & molto altro}

[Esercizio] Somma di due numeri uguale a zero

« Older   Newer »
  Share  
RootkitNeo
view post Posted on 6/9/2013, 22:35     +1   -1




Lo scopo di questo esercizio è molto semplice: contare quenti numeri danno come somma 0.
Il file da utilizzare è linkato qui sotto. Si tratta di un file contenente 1 Milione di numeri. Dovete quindi prenderne due, sommarli e vedere se danno come somma 0. Se la somma è 0, incrementate un contatore. Al termine stamperete il valore di questo contatore.

Download
 
Top
carbos
view post Posted on 6/9/2013, 23:55     +1   -1




E' possibile ordinare quella lista e immetere la lista ordinata in un altro file ed usare quello?
 
Top
RootkitNeo
view post Posted on 7/9/2013, 02:08     +1   -1




E' possibile operare in qualsiasi modo. A voi la scelta di cosa è meglio fare o no. Una volta risolto però non mettere subito il source qui, così gli altri possono scriverlo senza in qualche modo essere influenzati. ;)
 
Top
view post Posted on 9/9/2013, 22:45     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


CODICE
a=open("test.txt","r")
b="ciao"
meno=[]
piu=[]
while 1:
   b=str(a.readline())[:-1]
   if b=='':
       break
   b=int(b)
   if abs(b)==b:
       piu.append(b)
   else:
       meno.append(abs(b))
meno.sort()
piu.sort()

count=0
while len(piu)>0 and len(meno)>0:
   if meno[0] > piu[0]:
       del piu[0]
   elif meno[0]==piu[0]:
       count+=1
       del piu[0]
       del meno[0]
   else:
       del meno[0]
print(count)


Ho avuto un'ora, ho ripassato gli I/O da txt ed ho abbozzato questa brutta.
La posto perché adesso vado a nanna.
Domani sera se ho tempo la rifinisco e ripulisco e velocizzo.

Non l'ho testata su tutta la lista perché su questo computer non riesco nemmeno ad aprire la lista con il notepad, figuriamoci analizzarla e scansionarla! :P

PS: il sistema di confronto tra le due liste è geniale secondo me :)
 
Web  Top
RootkitNeo
view post Posted on 9/9/2013, 23:44     +1   -1




Ti chiederei di allegare anche l'eseguibile, in quanto non avendo Python non posso provarlo (e non mi va di scaricarlo visto che non lo utilizzerei).
 
Top
view post Posted on 10/9/2013, 15:22     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


Sto provando, ho messo una variabile che ogni ciclo del primo while aumenta di uno a si stampa, sono a 60000 in 5 minuti. Quindi considerando che dopo diventerà tutto più grosso e pesante direi, ancora due ore :P
 
Web  Top
RootkitNeo
view post Posted on 10/9/2013, 16:41     +1   -1




In Java ad 1 milione, nel modo rapido, ci vogliono 0.2 secondi. lol
 
Top
view post Posted on 10/9/2013, 17:01     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


Ho quasi finito di caricare, dopo scansiona.

Comunque lo sto riscrivendo con un metodo superrapido! :)
 
Web  Top
view post Posted on 10/9/2013, 17:33     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


LOL ha finito windows e sul mac ho appena finito di scrivere il super rapido, 2 secondi per il risultato! :)

249838

Sia il risultato del lento che del super rapido coincidono: è buffo il mondo della programmazione, tante strade ma solo una è rapida, le altre sono tutte testate contro il muro.

Adesso mi connetto da mac e lo posto.

CODICE
def rootkitneo(notepad):
   lista=[]
   a=open(notepad,"r")
   for x in a.readlines():
       lista.append(abs(int((x[:-1]))))
   return len(lista)-len(set(lista))
       
rootkitneo("1Mints.txt")



Un applauso :)

Edited by Wet Water - 10/9/2013, 18:58
 
Web  Top
RootkitNeo
view post Posted on 10/9/2013, 17:34     +1   -1




Bene! Qusto è il mio codice:

CODICE
int count(int[] a) {
   int N = a.length;
   int cnt = 0;
   Arrays.sort(a);
   for (int i = 0; i < N; i++) {
     if (Arrays.binarySearch(a,-a[i]) > i) {
       cnt++;
      }
    }
    return cnt;
 }
 
Top
view post Posted on 10/9/2013, 17:56     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


Binarysearch è una funzione dell'stdio?
 
Web  Top
RootkitNeo
view post Posted on 10/9/2013, 18:07     +1   -1




No, è in Java l'ho scritto sopra. lol In C++ sarebbe sicuramente più rapido però.

binarySearch in Java è in java.util.Arrays, è un metodo statico.

In C++ invece è presente in <algorithm>, e si chiama binary_search.
Comunque è implementabile tranquillamente anche se non disponibile nell'API del linguaggio (ma quasi tutti credo forniscano un implementazione).
In C è in stdlib.h e si chiama bsearch.
 
Top
view post Posted on 10/9/2013, 18:55     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


Ho cercato la ricerca binaria e se l'ho capita, il mio algoritmo è molto più veloce e furbo :)

1)Carica dal notepad i valori assoluti. 5 --> 5 7--->7 -7 --> 7
2)Mettili in una lista. [5,7,7]
3)Lunghezza lista-lunghezza insieme della lista

Es: lista: [1,2,3,4,4,5,8,8] len=7
Insieme: [1,2,3,4,5,8] len= 5

7-5= 2 coppie!

Così l'unica operazione lunga è il caricamento (un secondo o poco più), il confronto tra lista e insieme della stessa è più che istantaneo.

(E il tuo algoritmo bara perché non carica :P )
 
Web  Top
RootkitNeo
view post Posted on 10/9/2013, 19:19     +1   -1




Ti rispondo meglio da pc.
Che somma ottieni con il mio file comunque?
 
Top
view post Posted on 10/9/2013, 19:41     +1   -1
Avatar

Water can take unforseen forms.

Group:
Founder
Posts:
5,273
Reputation:
+1,147
Location:
Shabang

Status:


Non lo so, perché non ho compilatori java, ma se carichi la lista dovresti ottenere la mia stessa:

249838
 
Web  Top
21 replies since 6/9/2013, 22:35   233 views
  Share