OliForum Matematico

Faccio di più, scrivo un programmino C per il problema: --------- #include <stdio> int a[1000]; typedef struct { int i; int p; } s; s b[1000]; int c[1000]; int out[1000]; int main(void){ int n=0; int j=0; int x,y,i,m; while(scanf("%d",&a[n])!=-1)n++; b[0].i=a[0]; b[0].p=0; c[0]=-1; for...

Se poi non si vogliono usare gli alberi di ricerca è sufficiente ordinare l'array di input all'inizio e memorizzarlo in un array c. Ad ogni passo per verificare se abbiamo già inserito in b un elemento maggiore di a eseguiamo una ricerca binaria in c, tenendo conto del fatto che dobbiamo cercare ele...

Forse l'ho trovato, ditemi voi se sia corretto. Mantengo un'array b di lunghezza n, dove n è la lunghezza dell'array a contenente l'input. Inizialmente l'array b è inizializzato per esempio a -1, tranne che b[1]=a[1]. j=1 Per i =2 to n { flag =0 for z=1 to j se a <b[j] allora { b[j]=a flag=1 termin...

Io userei la programmazione dinamica in combinazione con alberi di ricerca. Ogni elemento dell'array punterà all'elemento che lo precede nella sequenza ascendente più lunga. Per trovare quest'ultima basta trovare l'elemento di valore più grande nell'array minore o eguale ad esso che lo precede (per...

Forse l'ho trovato, ditemi voi se sia corretto. Mantengo un'array b di lunghezza n, dove n è la lunghezza dell'array a contenente l'input. Inizialmente l'array b è inizializzato per esempio a -1, tranne che b[1]=a[1]. j=1 Per i =2 to n { flag =0 for z=1 to j se a <b[j] allora { b[j]=a flag=1 termina...

Inoltre aggiungo che per "meno di O(n^2)" in Informatica si suole usare la notazione o(n^2), con la "o" minuscola in luogo della Big-oh.

Io userei la programmazione dinamica in combinazione con alberi di ricerca. Ogni elemento dell'array punterà all'elemento che lo precede nella sequenza ascendente più lunga. Per trovare quest'ultima basta trovare l'elemento di valore più grande nell'array minore o eguale ad esso che lo precede (per ...

Beh,il limite superiore (finito) non credo qualcuno l'abbia trovato :shock:,altrimenti costui avrebbe anche dimostrato la congettura :D .Per quanto riguarda il limite inferiore,invece,io dico log_2(n)+1 .L'algoritmo di Collatz infatti termina il più rapidamente possibile quando n è una potenza di d...

Qui è la definizione del problema 3n+1 di Collatz: http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=5064

Scrivere un algoritmo che calcoli s(n) che non sia quello banale e che sia asintoticamente più veloce possibile.
Questo problema è presente nelle gare online dell'ACM.

Avete presente il problema del 3n+1? La funzione T(n) è definita come T(n)= (3n+1)/2 se n=1 mod 2 T(n)=n/2 se n=0 mod 2. (Alternativamente per n dispari invece che con (3n+1)/2 a volte si definisce T(n)=3n+1). Se col simbolo Tk(n) intendiamo la funzione T(n) iterata k volte, la sequenza (n,T(n), T2(...

Io invece stavo pensando (e per il momento continua a sembrarmi una buona scelta) ad una tesina sull'Intelligenza Artificiale. Il problema è: ci sono aspetti matematici dell'argomento che possano essere trattati utilizzando le conoscenze di un liceo scientifico? Grazie anticipate a chiunque voglia ...

Libro eccelso, un vero capolavoro. Può sembrare che non parli di niente se non si ha una visione unitaria delle scienze formali ed umane, che è il messaggio che vuole trasmettere l'autore: l'I.A. è la scienza in cui convergono materie che superficialmente potrebbero sembrare non avere collegamenti, ...

Hai mostrato un algoritmo che soddisfa quella proprietà ma non è affatto una dimostrazione che ogni algoritmo per quel problema deve avere quella proprietà.
Ad ogni modo si scrive "qual è", non "qual'è" (è un errore grave).

Saluti

Infatti, parlavo di "insiemistica non euclidea", ovvero, in analogia con le geometrie non euclidee, privata di alcuni assiomi E' proprio quello che mi interessava. Mi puoi consigliare del materiale in rete o dei libri da consigliarmi? E nello specifico hai referenze al sistema di Quine ch...

Mmmh...se guardiamo alle partizioni di S : constando S di un solo elemento, \mathfrak{P}_S avrà due elementi. Allora l'insieme S-elemento dovra avere anch'esso due sottoinsiemi. Ma l'insieme S-elemento dovrà contenere egli stesso un altro insieme elemento S'\equiv S . Quindi avremo infiniti insiemi...