La ricerca ha trovato 109 risultati

da rand
18 lug 2007, 15:31
Forum: Informatica
Argomento: Divisori in sottoinsieme di [2n]
Risposte: 9
Visite : 9702

Ok, questa è la soluzione che usa la forza bruta. Corretta, ma fa del lavoro inutile e per questo non è lineare in tempo. Infatti se gli interi sono n+1 ci si può limitare a tentare solo dei particolari valori di k (con riferimento al messaggio di Ipparco), quali? (Hint: la coppia di numeri esiste s...
da rand
14 lug 2007, 11:16
Forum: Informatica
Argomento: Divisori in sottoinsieme di [2n]
Risposte: 9
Visite : 9702

Se, in un caso speciale, i numeri fossero dati nell'intervallo [n+1,2n], il programma diventa equivalente a trovare, dati degli interi ~ a_1,a_2,\ldots,a_n , i 2 che sono uguali (sapendo che ce ne sono). Ma questo forse è un po' più chiaro che è difficile farlo in tempo lineare! Perchè ??? Puoi far...
da rand
05 lug 2007, 18:28
Forum: Informatica
Argomento: Divisori in sottoinsieme di [2n]
Risposte: 9
Visite : 9702

Dai, perchè non postate la soluzione?
Si può fare in tempo lineare in maniera semplice, la coppia di numeri esiste sempre.
da rand
29 giu 2007, 16:31
Forum: Informatica
Argomento: Divisori in sottoinsieme di [2n]
Risposte: 9
Visite : 9702

Divisori in sottoinsieme di [2n]

Dato un insieme di n+1 interi compresi tra 1 e 2n dare un algoritmo il più efficiente possibile che individua (se presente...) una coppia di suoi elementi che siano uno un divisore dell'altro.
da rand
20 giu 2007, 18:47
Forum: Matematica non elementare
Argomento: Tra 8 ce ne sono 4 linearmente dipendenti.
Risposte: 3
Visite : 2550

Tra 8 ce ne sono 4 linearmente dipendenti.

Scegliamo 8 vettori in $ Z_{3}^{4} $. Provare che tra questi ce ne sono 4 linearmente dipendenti.
da rand
16 giu 2007, 15:41
Forum: Informatica
Argomento: Ancora puzzle smemorati
Risposte: 3
Visite : 5553

Io avevo in mente questa soluzione. Si può vedere un qualunque shift ciclico come prodotto di 3 inversioni, dove un' inversione è una permutazione del tipo (a a+1 ... b-1 b) --> (b b-1 ... a+1 a). Poichè è facile effettuare un' inversione in loco e in tempo lineare anche lo shift ciclico viene così ...
da rand
13 giu 2007, 18:07
Forum: Informatica
Argomento: K numeri più grandi in A
Risposte: 5
Visite : 7324

Penso che lo si possa fare in 3 passi: trovi il k-esimo più grande in tempo lineare con algoritmi classici, poi trovi i k più grandi in tempo lineare, semplicemente confrontandoli con il k-esimo, infine ordini questi elementi in O(k log k). In totale si richiede O(n + k log k) tempo.
da rand
10 giu 2007, 15:37
Forum: Informatica
Argomento: Ancora puzzle smemorati
Risposte: 3
Visite : 5553

Ancora puzzle smemorati

Un'altro problemino che diventa non banale se vogliamo essere efficienti in spazio: dato un array A[1]A[2]...A[n] e un intero K sovrascrivere l'array A con il suo shift ciclico A[k]....A[n]A[1]...A[k-1] in tempo O(n) usando come memoria solo l'array A + una quantità costante e indipendente da n di r...
da rand
08 giu 2007, 18:24
Forum: Matematica non elementare
Argomento: Disuguaglianza integrale
Risposte: 2
Visite : 1961

Si potrebbe fare così, poniamo \mu = (\int_{0}^{1} x f(x))/\int_{0}^{1} f(x) . Per ogni x > 0 si ha che (x^2 - \mu^2)(x-\mu) \geq 0 , dunque \int_{0}^{1} (x^2 - \mu^2)(x-\mu)f(x) è anche lui non negativo. Ma sviluppando i conti in maniera semplice viene fuori che quest'ultimo integrale è proprio \in...
da rand
07 giu 2007, 18:41
Forum: Matematica non elementare
Argomento: Numero medio di lanci per due 6
Risposte: 7
Visite : 3742

Numero medio di lanci per due 6

Quante volte in media occorre lanciare un dado prima di ottenere due 6 consecutivi?
da rand
02 giu 2007, 18:34
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 24647

Quest'algoritmo si generalizza facilmente a trovare tutti gli elementi la cui frequenza è superiore a una certa soglia 1/k, dove k è un parametro intero, naturalmente sempre in tempo lineare e spazio costante, ed essendo semplice da implementare credo sia una soluzione molto efficiente anche nella p...
da rand
01 giu 2007, 13:04
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 24647

Va bene, ecco la soluzione. L'algoritmo fa due scansioni sul vettore A in questione. L' idea, come nell'hint, è di determinare nella prima scansione un solo elemento "candidato" ad essere il maggioritario e nella seconda verificare se questo è davvero maggioritario. La prima scansione mantiene una c...
da rand
30 mag 2007, 22:04
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 24647

Nessun'altra idea per farlo in tempo lineare e spazio costante?
da rand
30 mag 2007, 21:53
Forum: Combinatoria
Argomento: Quando Gardner incontra Silvan
Risposte: 9
Visite : 6586

Quando Gardner incontra Silvan

Un noto prestigiatore vi pone davanti un classico mazzo di 52 carte di 4 semi e vi chiede di sceglierne 5 a caso. Lui non può vedere le carte quando voi le scegliete e a quel momento ha zero informazioni sulla loro identità. Quindi vi chiede di passare le carte al suo assistente, il quale, dopo un p...
da rand
25 mag 2007, 16:04
Forum: Informatica
Argomento: Elemento più frequente
Risposte: 30
Visite : 24647

La soluzione sarebbe corretta se avesse spazio costante, invece ce l'ha logaritmico, perchè bisogna tenere traccia dei risultati forniti dalle chiamate ricorsive. Inoltre non è lineare in tempo. Andiamo, perchè volete complicarvi così tanto la vita ?? :wink: