OliForum Matematico

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...

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...

Dai, perchè non postate la soluzione?
Si può fare in tempo lineare in maniera semplice, la coppia di numeri esiste sempre.

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.

Scegliamo 8 vettori in $ Z_{3}^{4} $. Provare che tra questi ce ne sono 4 linearmente dipendenti.

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ì ...

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.

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...

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...

Quante volte in media occorre lanciare un dado prima di ottenere due 6 consecutivi?

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...

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 mant...

Nessun'altra idea per farlo in tempo lineare e spazio costante?

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...

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 ??