Divisori in sottoinsieme di [2n]

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Divisori in sottoinsieme di [2n]

Messaggio da rand »

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.
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Dai, perchè non postate la soluzione?
Si può fare in tempo lineare in maniera semplice, la coppia di numeri esiste sempre.
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Non capisco... come è possibile farlo in tempo linerare?
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!
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

edriv ha scritto: 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 farlo in tempo lineare usando un array ausiliario di dimensione n che usi per ricordarti degli elementi che hai già visto. E' la soluzione ovvia di questo sottoproblema, prende tempo e spazio lineare (a dirla tutta l'array ausiliario può essere eliminato, ma questa è un'altra storia). La soluzione del problema originale non è molto più difficile, su.
Avatar utente
ipparco
Messaggi: 58
Iscritto il: 24 gen 2007, 10:44
Località: Verona

Messaggio da ipparco »

La vostra discussione mi ha fatto venire in mente questa soluzione: si crea un array $ app $ di $ 2 n $celle, si scorre l'array in input e si valorizza $ [tex] $app = 1[/tex] se $ i $ è un elemento dell'input. Se si trova un elemento presente 2 volte ci si ferma (perchè si è trovata la coppia cercata), altrimenti si esegue il seguente programma:
per ogni $ ind $ che va da 1 a $ n: $
se $ app[ind] = 1 $, si controlla se nell'array $ app $ c'è qualche altro elemento del tipo $ k * ind $ (con $ k $ naturale maggiore di 1) tale che $ app[k * ind] = 1 $. Se questo elemento esiste, si è trovata la coppia cercata (cioè $ (ind, k * ind)) $ e si termina, altrimenti
$ next $ $ ind $
Questo programma compie al più $ n + \sum_{i = 1}^{n} \frac{n}{i} $ passi, cioè $ n + n * \sum_{i = 1}^{n} \frac{1}{i} $, che è all'incirca $ n + n * \log n $.
Il programma è quindi O(nlogn). Forse, ma non ho idea di come si possa fare a dimostrarlo, il programma è anche O(n), perchè se gli elementi dell'insieme sono pochi, la parte "dispendiosa" del programma viene eseguita poco, mentre se gli elementi sono molti, la probabilità di terminare in fretta aumenta. Magari, nel caso particolare di $ n + 1 $ elementi c'è una dimostrazione più semplice.
Mah...
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

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 sempre, per quale motivo?)
Avatar utente
ipparco
Messaggi: 58
Iscritto il: 24 gen 2007, 10:44
Località: Verona

Messaggio da ipparco »

Rand, scusa la domanda in stile "Cultura moderna": c'entra qualcosa il teorema cinese del resto ?
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Non credo. L'esistenza di questa coppia di interi è un'applicazione del principio della piccionaia.
Avatar utente
ipparco
Messaggi: 58
Iscritto il: 24 gen 2007, 10:44
Località: Verona

Messaggio da ipparco »

Rand, bandiera bianca. Ho trovato un po' di esempi con k minimo abbastanza diversi tra loro e quindi non riesco ad immaginare una regola.
Non sono molto forte in teoria dei numeri (eufemismo) :(
Potresti postare la soluzione, dato che sono passati vari giorni dall'ultimo messaggio ?
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Basta considerare l'applicazione che manda $ x = 2^u v $, con $ v $ dispari, in $ v $. In altre parole la funzione che restituisce l'intero diviso per la masima potenza del due che lo divide. Due interi che hanno la stessa immagine sono uno un divisore dell'altro. Poichè il risultato dell'applicazione è un dispari questa funzione mappa l'insieme [2n] in n distinti interi, tutti i dispari minori di 2n. Dunque se scegliamo n+1 interi in [2n] almeno due di essi avranno la stessa immagine (principio della piccionaia) quindi saranno uno un divisore dell'altro. Questa osservazione suggerisce una variante dell'algoritmo forza-bruta postato da Ipparco che consiste nel tentare solo i valori di k che sono potenze di 2. Se lo analizzate vi rendete conto che lavora in tempo lineare.
Rispondi