La ricerca ha trovato 109 risultati

da rand
25 mag 2007, 14:36
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 26309

L'hint ve l'ho già postato in realtà. Basta pensare ai vincoli del problema. Tempo lineare e spazio costante vuol dire che al massimo è consentito fare una o più scansioni durante le quali ci si può portar dietro un elemento e magari anche un contatore. Questo è sufficiente per poter scandire l'arra...
da rand
24 mag 2007, 10:40
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 26309

Quello che dice =Betta= non ha spazio costante e non è nemmeno lineare. Detto rozzamente "spazio costante" significa usare un numero di celle di memoria finito e indipendente dalla lunghezza dell'array. Questo restringe parecchio il numero di cose ragionevoli da fare.
da rand
22 mag 2007, 12:44
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 26309

L'idea di Ipparco è molto buona. Ma non è ancora la soluzione "vera". Si può risolvere in tempo lineare (questo è già un hint) con un approccio differente ma per nulla sofisticato. Dai, che non è difficile.
da rand
19 mag 2007, 19:50
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 26309

Elemento più frequente

Questo non è certo originale ma è sempre carino per chi non lo conosce già: Determinare se in un array di interi c'è un valore che si ripete più della metà delle volte usando spazio costante e senza alterare l'array. La soluzione banale prende tempo quadratico ma esiste qualcosa di molto migliore ch...
da rand
11 mag 2007, 17:18
Forum: Combinatoria
Argomento: Una terna ancora!
Risposte: 7
Visite : 4934

Non vi annoierò con un'altra domanda impossibile... ma con una soluzione algebrica di questo problema così maltrattato :( . Ammettiamo per assurdo che ogni coppia di triple sia disgiunta o abbia due elementi nell'intersezione. Numeriamo gli n elementi e le n+1 triple e costruiamo una matrice X di di...
da rand
09 mag 2007, 10:07
Forum: Combinatoria
Argomento: La scacchiera malata
Risposte: 13
Visite : 6686

Una mente malata potrebbe chiedersi: che succede al gioco se si fa diventare la scacchiera cilindrica? Vorrebbe dire far diventare adiacenti le caselle che stanno su due bordi opposti.
da rand
03 mag 2007, 14:31
Forum: Informatica
Argomento: Calcolare il logaritmo con addizione, sottrazione, mol e div
Risposte: 8
Visite : 8156

La cosa interessante del calcolo $ \lfloor log_{2}(x) \rfloor $ è che si può fare usando un numero costante di operazioni logico-aritmetiche (addizione, moltiplicazione, shift, and, not), trovarle è un'impresa!
da rand
01 mag 2007, 18:11
Forum: Informatica
Argomento: Raggiungibilità in albero
Risposte: 5
Visite : 5999

@Ippparco: In effetti si, avevo in mente la soluzione che hai descritto informalmente. Ogni persona prende come etichetta una coppia di interi in [N] che sono semplicemente il tempo di inizio e il tempo di fine visita del nodo corrispondente in una visita in profondità dell'albero. L'etichetta ha 2 ...
da rand
29 apr 2007, 17:57
Forum: Informatica
Argomento: Raggiungibilità in albero
Risposte: 5
Visite : 5999

Raggiungibilità in albero

Un'azienda vi pone il seguente insensato problema. Il personale è costituito da N persone organizzate gerarchicamente secondo un albero di dipendenze. Ogni persona dell'azienda corrisponde ad un nodo dell'albero e tutti i suoi dipendenti stanno nel sottoalbero radicato nel nodo corrispondente. Sulle...
da rand
27 apr 2007, 09:43
Forum: Combinatoria
Argomento: telematica unimi 1
Risposte: 4
Visite : 3490

Sarei curioso di sapere se la soluzione è basata sul fatto che la mosse sono "invertibili" o si può fare qualcosa di più intelligente. Invertibili nel senso che da due distribuzioni distinte non si può arrivare nella stessa effettuando una mossa che mette l'ultimo seme nella stessa scatola.
da rand
13 apr 2007, 15:25
Forum: Informatica
Argomento: Una particolare sequenza di bit
Risposte: 5
Visite : 8091

Si, in realtà è più difficile di quanto pensassi! Avevo letto su un libro di algoritmi quella che credevo una soluzione elegante, ma mi sono reso conto che c'è un' incompletezza, e che la soluzione vera è in realta più complessa. Comunque chi vuol sapere come costruire una sequenza infinita square-f...
da rand
12 apr 2007, 18:08
Forum: Informatica
Argomento: Una particolare sequenza di bit
Risposte: 5
Visite : 8091

Il problema l'ho formulato in una maniera che un pò confonde, perchè il fatto è che esiste almeno una sequenza infinita di bit libera da quadrati, cosa però non evidente. Il problema vero è trovare una procedura che la genera un bit alla volta, dopodichè ne deriva una soluzione del problema di sopra...
da rand
12 apr 2007, 15:38
Forum: Combinatoria
Argomento: Triangolo o quadrato in grafo denso (prob. ben noto)
Risposte: 0
Visite : 2297

Triangolo o quadrato in grafo denso (prob. ben noto)

Dimostrare che se un grafo di n nodi ha più di n\sqrt{n} archi allora contiene sempre almeno un triangolo o almeno un quadrato ("o" inclusivo). Un triangolo in un grafo è un insieme di 3 nodi connessi tra loro, cioè un ciclo di 3 nodi, un quadrato analogamente è un ciclo semplice di 4 nodi. Ciao.
da rand
04 apr 2007, 15:26
Forum: Combinatoria
Argomento: Partizioni dispari o distinte? E' uguale!
Risposte: 4
Visite : 3587

E' molto carino: Infatti i due tipi di partizione sono in corrispondenza biunivoca. Data una partizione a interi distinti posso associargli la partizione a interi dispari che si ottiene prendendo uno degli elementi e dividendolo in due elementi uguali e ripetendo questo fino a che non rimango con un...
da rand
01 apr 2007, 17:54
Forum: Informatica
Argomento: Una particolare sequenza di bit
Risposte: 5
Visite : 8091

Una particolare sequenza di bit

Una sequenza di bit si dice quadrata quando è data dalla concatenazione di due sequenze uguali, ad es.: 00,11, 0101, 000000,... sono tutte quadrate. Generare sequenze quadrate non è difficile. Provate invece a dare un algoritmo che dato N genera una sequenza di N bit che non contiene sottosequenze q...