La ricerca ha trovato 109 risultati

da rand
14 mag 2010, 11:34
Forum: Informatica
Argomento: Somma di interi
Risposte: 8
Visite : 11456

E' ovvio, così usi lo stack per tenere i riporti, e quindi usi spazio aggiuntivo lineare. Si può fare senza ricorsione e in spazio costante.
da rand
08 feb 2010, 22:14
Forum: Informatica
Argomento: Somma di interi
Risposte: 8
Visite : 11456

Non ho capito cosa intendi per tralasciando la parte intera, ma
stando al tuo pseudocodice 999 + 001 farebbe 900.
da rand
08 feb 2010, 19:37
Forum: Informatica
Argomento: Somma di interi
Risposte: 8
Visite : 11456

Chiaramente ottimi in senso asintotico. In altre parole la soluzione ottima deve usare spazio (=numero di celle di memoria) aggiuntivo costante e indipendente dalla dimensione dell'input, e tempo proporzionale alla dimensione dell'input.
da rand
08 feb 2010, 17:49
Forum: Informatica
Argomento: Somma di interi
Risposte: 8
Visite : 11456

Notate che non è una banale trasposizione della somma di interi, perchè l'algoritmo da scuola materna richiede alla meglio spazio aggiuntivo lineare, data la particolare rappresentazione dell'input. Infatti, facendo la somma con riporto nel modo banale, dobbiamo elaborare le cifre nell'ordine dalla ...
da rand
06 feb 2010, 18:33
Forum: Informatica
Argomento: Somma di interi
Risposte: 8
Visite : 11456

Somma di interi

Le cifre decimali di due interi x e y (arbitrariamente grandi) sono rappresentate tramite due liste di interi tra 0 e 9 singolarmente linkate. Vale a dire ogni nodo di ciascuna lista contiene una cifra e un puntatore alla cifra successiva (ma non alla precedente). Problema: dare un algoritmo che met...
da rand
27 gen 2010, 18:03
Forum: Informatica
Argomento: Scambio di sequenze simili
Risposte: 8
Visite : 10738

HINT: una specie di ricerca binaria e controllo di parità
da rand
26 gen 2010, 18:25
Forum: Informatica
Argomento: Scambio di sequenze simili
Risposte: 8
Visite : 10738

E' vero, alla fine A e B non fanno altro che colorare un particolare ipergrafo, infatti il lemma è equivalente alla soluzione.

Ma se volete esiste anche un modo elementare e diretto per farlo, che usa al più l'aritmetica modulo 2 ...
da rand
25 gen 2010, 23:56
Forum: Informatica
Argomento: Scambio di sequenze simili
Risposte: 8
Visite : 10738

... precisazione: la comunicazione è a senso unico da A verso B: ossia il tutto si riduce ad A che invia un unico messaggio a B di lunghezza logaritmica. Non è prevista nessuna interazione da B, che può ricevere da A ma non rispondere.
da rand
25 gen 2010, 23:37
Forum: Informatica
Argomento: Scambio di sequenze simili
Risposte: 8
Visite : 10738

Yes...
da rand
25 gen 2010, 20:47
Forum: Informatica
Argomento: Scambio di sequenze simili
Risposte: 8
Visite : 10738

Scambio di sequenze simili

Ci sono due persone A e B, che possiedono rispettivamente due sequenze binarie x e y. Nessuno dei due conosce la sequenza posseduta dall'altro, ma si sa che x e y hanno la stessa lunghezza e differiscono in un solo bit (che è ovviamente ignoto sia ad A che a B). Dimostrare che mediante una strategia...
da rand
05 gen 2010, 13:24
Forum: Matematica non elementare
Argomento: Complessità geometrica
Risposte: 2
Visite : 2499

Ok ma questo esclude soltanto il caso in cui le regioni sono triangoli a loro volta. Cosa si può dire più in generale?
da rand
04 gen 2010, 19:44
Forum: Matematica non elementare
Argomento: Complessità geometrica
Risposte: 2
Visite : 2499

Complessità geometrica

E' possibile costruire un triangolo che non può essere dissezionato in 3 regioni congruenti ?

ps: Non so se sia un problema noto o meno, ne quanto sia difficile la risposta perchè la ignoro io stesso. Avete qualche idea?
da rand
09 dic 2009, 13:02
Forum: Combinatoria
Argomento: Partizionare potenze del due
Risposte: 3
Visite : 2221

Beh, in effetti forse sono io che confondo Algebra e Combinatoria :-).
Al di là di questo la soluzione dovrebbe essere quella. Se volete leggerla ecco la partizione che risolve il problema:
In A tutti gli interi che hanno un numero pari di 1 nella rappresentazione binaria e in B tutti gli altri
da rand
07 dic 2009, 12:12
Forum: Combinatoria
Argomento: Partizionare potenze del due
Risposte: 3
Visite : 2221

Partizionare potenze del due

Dimostrare che:
Per ogni k si possono partizionare gli interi da 1 a $ 2^k $ in due insiemi A e B tali che, per ogni $ 1 \leq i \leq k-1 $, le sommatorie delle potenze i-esime degli interi in A e in B sono uguali. Enjoy!

P.S.: l'ho postato qui perchè la soluzione mi sembra essenzialmente combinatoria
da rand
23 set 2009, 02:34
Forum: Combinatoria
Argomento: abbinamento traminte segmenti senza intersezioni
Risposte: 2
Visite : 2080

abbinamento traminte segmenti senza intersezioni

Ci sono N punti bianchi ed N punti neri nel piano tali che nessuna retta passa per più di 2 punti, bianchi o neri che siano. Dimostrare che comunque siano disposti i punti si possono sempre tacciare N segmenti con un estremo bianco e l'altro nero tali che nessuna coppia di segmenti si intersechi. (N...